Metodo Grafico

Formulación de modelos de Programación Lineal

Aunque se ponga en duda, la parte más difícil de PL es reconocer cuándo ésta puede aplicarse y formular el problema matemáticamente. Una vez hecha esa parte, resolver el problema casi siempre es fácil.

Para formular un problema en forma matemática, deben expresarse afirmaciones lógicas en términos matemáticos. Esto se realiza cuando se resuelven “problemas hablados” al estudiar un curso de álgebra. Algo muy parecido sucede aquí al formular las restricciones. Por ejemplo, considérese la siguiente afirmación: A usa 3 horas por unidad y B usa 2 horas por unidad. Si deben usarse todas las 100 horas disponibles, la restricción será:

3A + 2B = 100

Sin embargo, en la mayoría de las situaciones de negocios, no es obligatorio que se usen todos los recursos (en este caso, horas de mano de obra). Más bien la limitación es que se use, cuando mucho, lo que se tiene disponible. Para este caso, la afirmación anterior puede escribirse como una desigualdad:

3A + 2B ≤100

Para que sea aceptable para PL, cada restricción debe ser una suma de variables con exponente 1. Los cuadrados, las raíces cuadradas, etc. no son aceptables, ni tampoco los productos de variables. Además, la forma estándar para una restricción pone a todas las variables del lado izquierdo y sólo una constante positiva o cero del lado derecho. Esto puede requerir algún reacomodo de los términos. Si, por ejemplo, la restricción es que A debe ser por los menos el doble de B, esto puede escribirse como:

A ≥ 2B ó A - 2B ≥ 0

Nótese que pueden moverse términos de un lado a otro de las desigualdades como si fuera un signo de igualdad. Pero al multiplicar una desigualdad por -1, el sentido de esta desigualdad se invierte. Puede ser necesario hacer esto para que los coeficientes del lado derecho sean positivos. Por ejemplo, si se quiere que A sea por lo menos tan grande como B - 2, entonces:

A ≥ B - 2

ó A - B - 2

por último B - A ≥2

Una nota final sobre desigualdades: es sencillo convertir una desigualdad en una ecuación. Todo lo que se tiene que hacer es agregar (o restar) una variable extra. Por ejemplo:

B - A ≤ 2 es lo mismo que B - A + S = 2

en donde S representa la diferencia, o la holgura, entre B - A y 2. S se llama variable de holgura. Por otro lado, se restaría una variable de superávit en el caso siguiente:

A - 2B ≥ 0 es lo mismo que A - 2B -S = 0

Algunos métodos de solución (como el Método Símplex) y la mayoría de los programas de computadora (como el MathProg, que viene en el ORCourseware, que acompaña al libro “Introducción a la Investigación de Operaciones” de los autores Hillier y Lieberman) requieren que todas las desigualdades se conviertan en igualdades.

La metodología de PL requiere que todas las variables sean positivas o cero, es decir, no negativas. Para la mayoría de los problemas esto es real, no se querría una solución que diga: prodúzcanse menos dos cajas o contrátense menos cuatro personas.

Mientras que no existe un límite en el número de restricciones que puede tener un problema de PL, sólo puede haber un objetivo. La forma matemática del objetivo se llama función objetivo. Debe llevar consigo el maximizar o minimizar alguna medida numérica. Podría ser maximizar el rendimiento, la ganancia, la contribución marginal o los contactos con los clientes. Podría ser minimizar el costo, el número de empleados o el material de desperdicio. Con frecuencia el objetivo es evidente al observar el problema.

Como el valor de la función objetivo no se conoce hasta que se resuelve el problema, se usa la letra Z para representarlo. La función objetivo tendrá, entonces, la forma:

Maximizar Z = 4A + 6B

ó

Minimizar Z = 2x1 + 5x2

Se analiza una aplicación para ilustrar el formato de los problemas de Programación Lineal.

Planeación de la fuerza de trabajo.

El gerente de personal de “La Tortuga Veloz, S.A. de C.V.”, está analizando la necesidad de mano de obra semi calificada durante los próximos seis meses. Se lleva 1 mes adiestrar a una persona nueva. Durante este período de entrenamiento un trabajador regular, junto con uno en adiestramiento (aprendiz), producen el equivalente a lo que producen 1.2 trabajadores regulares. Se paga $500.00 mensuales a quien está en entrenamiento, mientras que los trabajadores regulares ganan $800.00 mensuales. La rotación de personal entre los trabajadores regulares es bastante alta, del 10% mensual. El gerente de personal debe decidir cuántas personas necesita contratar cada mes para adiestramiento. En seguida se da el número de meses-hombre necesarios. También se desea tener una fuerza de trabajo regular de 110 al principio de julio. En cuanto al 1º de enero, hay 58 empleados regulares.

Mes Meses-hombre requeridos Mes Meses-hombre requeridos

Enero 60 Abril 80

Febrero 50 Mayo 70

Marzo 60 Junio 100

Este problema tiene un aspecto dinámico, ya que la fuerza de trabajo en cualquier mes depende de la fuerza de trabajo regular y en adiestramiento del mes anterior. Para cualquier mes, el número total de meses-hombre disponibles se puede expresar como sigue:

Meses-hombre disponibles: Ri + 0.2Ai

en donde: Ri = número de trabajadores regulares al principio del mes

Ai = número de aprendices contratados en el mes.

Entonces los requerimientos de cada mes pueden expresarse por las restricciones:

enero R1 + 0.2A1 ≥ 60

febrero R2 + 0.2A2 ≥ 50

marzo R3 + 0.2A3 ≥ 60

abril R4 + 0.2A4 ≥ 80

mayo R5 + 0.2A5 ≥ 70

junio R6 + 0.2A6 ≥ 100

julio (principio) R7 ≥ 110

Debido a la rotación, el 10% de los trabajadores regulares se van cada mes. Así, el número de trabajadores regulares disponibles, por ejemplo, al principio de febrero sería:

R2 = 0.9R1 + A1

En la misma forma, pueden escribirse las ecuaciones para el número de trabajadores disponibles al principio de cada mes:

Enero R1 = 58 (dado)

Febrero R2 = 0.9R1 + A1

Marzo R3 = 0.9R2 + A2

Abril R4 = 0.9R3 + A3

Mayo R5 = 0.9R4 + A4

Junio R6 = 0.9R5 + A5

Julio R7 = 0.9R6 + A6

El objetivo global del gerente de personal es minimizar el costo. La función objetivo es:

Minimizar: Z = 800(R1 + R2 + R3 + R4 + R5 + R6) + 500(A1 + A2 + A3 + A4 + A5 + A6)

Ahora se tiene el problema en el formato general de PL con 13 variables y 14 restricciones.

Los tomadores de decisiones en las empresas establecen criterios que debe cumplir una solución y, después, buscan esa solución. En PL, los criterios se expresan como restricciones. Se exploran las soluciones posibles y se usa la función objetivo para elegir la mejor de entre aquellas que cumplen con los criterios. La PL se denomina técnica de optimización, pero optimiza sólo dentro de los límites de las restricciones. En realidad es un método de satisfacción de criterios.

Forma estándar de los modelos de Programación Lineal.

Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea xj (una variable de decisión) el nivel de la actividad j, para j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea cj el incremento que resulta en Z por cada incremento unitario en xj (para j = 1, 2, ..., n). Ahora sea bi la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase aij como la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m y j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x1, x2, ..., xn para:

Maximizar Z = c1x1 + c2x2 + ... + cnxn,

sujeto a las restricciones:

a11x1 + a12x2 + ... + a1nxn £ b1

a21x1 + a22x2 + ... + a2nxn £ b2

am1x1 + am2x2 + ... + amnxn £ bm y

x1 ³ 0, x2 ³0, ..., xn ³ 0

Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL.

En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c1x1 + c2x2 + ... + cnxn, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función del tipo ai1x1 + ai2x2 + ... + ainxn, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones xj ³ 0 se llaman restricciones de no negatividad. Las variables xj son las variables de decisión. Las constantes de entrada, aij, bi, cj, reciben el nombre de parámetros del modelo.

Otras formas de modelos de Programación Lineal.

Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de algunos

...