Investigacion Operativa

3.4.5 Programación lineal : Método Simplex

Los problemas reales de programación lineal generalmente tienen variables de decisión y muchas restricciones. Tales problemas no pueden ser resueltos gráficamente. Se usan algoritmos tales como el simples. El método simplex es un procedimiento iterativo que progresivamente permite obtener una solución óptima para los problemas de programación lineal. Existen numerosos programas tanto para computadoras centrales como para personales. Aunque el método simples es especialmente útil en problemas de gran escala (resueltos con una computadora), en seguida se practicará en el caso del mismo problema que fue resuelto gráficamente en el ejemplo sobre la empresa química “Chemical”.

Procedimiento general del simplex

1. Establézcase la tabla inicial de simples. Formular la función objetivo y las restricciones e introducir las variables de decisión, variable en la solución, valor en solución (LD), C (contribución de la variable), Z (costo de introducir la variable), C – Z (contribución neta de la variable).

2. Selecciónese la columna pivote. Ésta es la columna con el número positivo más grande en el renglón inferior (C - Z). Esta se convierte en la nueva variable de la solución.

3. Selecciónese el renglón pivote. Éste es el renglón con la razón más pequeña del valor LD dividido por el valor de la columna pivote. Úsense sólo números positivos. Esto identifica la variable que deja la solución.

4. Enciérrese en un círculo el elemento pivote. Ésta es la intersección del renglón y la columna pivotes.

5. Conviértase al elemento pivote en un 1. Hágase esto dividiendo cada valor del renglón pivote entre el valor pivote. Métase este renglón en una tabla nueva.

6. Genérense los demás renglones de la nueva tabla con ceros en la columna pivote. Esto se hace multiplicando el nuevo renglón (del paso 5) por el negativo del elemento en la columna pivote. El resultado será sumado al antiguo renglón. Introdúzcase este renglón revisado en la nueva tabla, y continúese este procedimiento en cada renglón de la sección central de la tabla.

7. Prueba de optimización. Calcúlense los valores de Z y C – Z. Los valores de Z de cada columna son (elementos de la columna) ( C ). Si todos los valores de C – Z son ≤ 0, la solución es óptima. Léanse los valores de las variables en la solución de la columna de LD y el valor de la función objetivo del renglón de Z en la columna de LD. Si la solución no es óptima, regrese al paso 2.

Variables de holgura- El método simples empieza con el planteamiento de una función objetivo y ecuaciones de restricción. Las rutinas computarizadas de programación lineal (PL) automáticamente arreglarán esos datos iniciales, pero tratándose de soluciones manuales, debe construirse en cada paso la tabla de simples. Esto requiere que las restricciones sean establecidas como igualdades. En los problemas de maximización se logra esto añadiendo variables de holgura (s) a cada restricción. La holgura representa una cantidad no utilizada, o la diferencia entre lo que es usado y el límite de lo que puede usarse.

Por ejemplo añadiendo variables de holgura a las desigualdades del ejemplo de la industria “Chemical”; se tienen las nuevas ecuaciones que se muestran en la siguiente tabla. Nótese que S1 está relacionada con la restricción de la máquina A y S2 lo está con la máquina B.

Restricción Desigualdad Ecuación con holgura

Máquina A h 4x + 6y ≤ 12 4x + 6y + S1 = 12

Máquina B h 8x + 4y ≤ 16 8x + 4y + S2 = 16

La restricción de la máquina A ahora indica cuatro horas por el número de unidades de X producidas más seis horas por el número de unidades de Y producidas, más las horas de holgura = 12. Así, pues, si una unidad de X y una Y son producidas, se tienen dos horas de tiempo de holgura S en la máquina A, dado que 4(1) + 6(1) + 2 = 12. Si ni X ni Y son producidas, “se produce” una holgura total, y S1 = 12.

El método simplex siempre comienza con una solución factible dentro de la cual sólo se produce holgura. Esto corresponde al origen en la solución gráfica, dónde X y Y son iguales a cero. Se empieza con una solución inexacta, pero factible, que corresponde a una esquina de la región factible. Se empieza con una solución inexacta, pero factible, que corresponde al origen, donde sólo se produce holgura, es decir, cero utilidad. Por tanto, las variables de holgura (por ejemplo S1 y S2 están en la solución, y las otras variables de decisión (X y Y) no están en la solución (así, tienen valores de cero).

Preséntense la función objetivo y las restricciones del siguiente ejemplo en una tabla inicial de simplex

Una empresa química “Chemical” produce limpiadores para automóviles X y pulidores Y y gana $10 en cada lote de X, y $30 en Y. Ambos productos requieren procesarse en las mismas máquinas, A y B, pero X requiere cuatro horas en A y ocho en B, mientras que Y requiere seis horas en A y cuatro en B. Durante la semana entrante las máquinas A y B tienen 12 y 16 horas de capacidad disponible, respectivamente. Suponiendo que existe demanda de ambos productos, cuántos lotes de cada uno deben producirse para alcanzar la unidad óptima Z?.

La función objetivo es:

Max Z = $10X + $30Y

Las restricciones son:

h maquina A : 4X + 6Y = 12

h máquina B : 8X + 4Y =16

X,Y ≥ 0

Formato simplex

C 10 30 0 0 Valores de solución

Variables de la solución Variables de decisión

X Y S1 S2 (LD)

0 S1 4 6 1 0 12

0 S2 8 4 0 1 16

Z 0 0 0 0 0

C-Z 10 30 0 0 0

Elementos de la tabla simplex.

La parte central de la tabla simplex consta de los coeficientes de las restricciones de:

4X + 6Y + 1S1 + 0S2 = 12

8X + 4Y + 0S1 + 1S2 =16

Nótese que se ha asignado un uno (1) a la variable de holgura asociada con su propia restricción, y un cero (0) a la otra variable de holgura

La columna de variables en la solución indica cuáles variables están en la solución (en este caso, sólo las de hoguera) y la columna de valores solución indica las cantidades de solución. Los números vienen del lado derecho LD de las restricciones (en este caso, 12 horas de holgura para la máquina A y 16 horas para la B)

La C en la esquina superior izquierda encabeza a la vez un renglón y una columna. Especifican la cantidad de contribución a la función objetivo de cada unidad de las variables a que se refiere. Esto es, cada unidad de X (limpiador) contribuye

...