Programación lineal, método Simplex:

Programación lineal, método Simplex:

Típico ejemplo de maximizar la producción o beneficios de una empresa: la inyectora de plástico Zonda, que produce mesas y sillas, en 3 talleres -carpintería, tapizado y empaque- con las siguientes restricciones: X₁ <= 3 (... con X₁; X₂ >=0 )

X₂ <= 6 F.O.: Maximizar Z_j= 8X₁+ 3X₂

6X₁+ 4X₂ <= 36 (donde $8 y $3 son los beneficios en ambos productos)

(Precaución: si los coeficientes técnicos -del cuadro resumen- no fueran uno razone por regla de tres como pasa esos coeficientes hacia los del sistema de restricciones)

1) Transformar a ecuaciones, agregando las variables de holgura (capacidad ociosa en cada sección)

1X₁ + 0X₂ + 1X₃ + 0X₄ + 0X₅ = 3

0X₁ + 1X₂+ 0X₃ + 1X₄+ 0X₅=6

6X₁ + 4X₂ + 0X₃ + 0X₄+ 1X₅= 36

2) Tabla 0: la primer línea es común para todas las tablas, con estas 8 columnas: C; X; B; A₁...₅

(en realidad puede omitirse en las siguientes tablas o pasos del cálculo si se ponen a continuación)

3) Agregar los coeficientes de la funcion objetivo (f.o., o funcional) arriba de cada A_j de la línea 1.

(como ayuda para calcular el punto 9)

4) En la columna X (X₀ en esta tabla...) van las variable básicas, según el sistema de ecuaciones. La primer solución (en el origen) solo incluye las variables de holgura (nada producido, sólo excedentes)

Se suponen variables contínuas; fraccionables.

5) En la columna C (C₀ aquí) van los coefic. de las variables básicas en la f.o. Es es valor (o costo en su caso) que tiene en el funcional )

6) En la columna B van los recursos iniciales. B es el valor de cada variable X en este paso (tabla) del cálculo Simples.En las próximas tablas irán los recursos utilizados para esa etapa (o solución de la frontera acodada).

7) En A_{1 ... 5} van, por ahora, los coeficientes del sistema de ecuaciones; i filas, j columnas. Cada Aij indica cuánto disminuye el valor de la variables Xi por cada unidad de Xj que decida fabricar (o que sobre si j es un insumo. O sea, cuánto disminuye el valor de Xi por cada unidad con que j entre valiendo a la base.

8) Conviene trazar rayas: tras la columna B; tras la colum. A_5; y otra inferior.

9) Agregar una última fila: calculando cada A como: (åC₀A_i) – Z_j

10) Variable que entra: el mayor negativo en la fila inferior (señalar con una flecha vertical). Se toma el mayor negativo (mayor en valor absoluto) por que mejora el funcional).

11) Agregar una última columna, q (teta): calcular como B / cada coefic. en la columna de la variable que entra.

12) Variable que sale: el menor positivo en q (señalar con una flecha horizontal), ya que indica el valor con que la variable entra a la base y las variables no pueden ser nulas o negativas.

13) Pivote: intersección entre ambas flechas. Circular el pivote o subrayar.

Tabla 0:

8 3 0 0 0

C₀ X₀ B A₁ A₂ A₃A₄ A₅ q

0 X₃3 1 0 1 0 0 3 ¬

0 X₄6 0 1 0 1 0 -

0 X₅36 6 4 0 0 1 6

-8 -3 0 0 0

14) Para la Tabla 1 repetir la fila 1 (cambiando aquí el subíndice de las 3 primeras columnas)

15) Repetir los coeficientes del funcional arriba de los A de la fila 1.

16) En la columna X cambiar la var. que sale por la variable que entra.

17) Anotar en la colum. C el valor que tiene cada variable en el funcional.

18) Calcular la nueva línea del pivote como = linea pivote anterior / pivote

19) En la columna del pivote van ceros (salvo el 1 del pivote)

20) Para calcular cada elemento restante observar los extremos del cuadrado con diagonal en el pivote . Al número en la tabla anterior restarle la otra diagonal dividida por el pivote.

21) Calcula la fila inferior según (9)

22) Calcular la columna q según (11)

23) Marcar con flechas la var. que entra (según 10) y la var. que sale (según 12); circular su intersección como nuevo pivote.

Tabla 1:

8 3 0 0 0

C₁ X₁ B₁ A₁ A₂ A₃A₄ A₅ q

8 X₁3 1 0 1 0 0 -

0 X₄6 0 1 0 1 0 6

0 X₅18 0 4 -6 0 1 4,5 ¬

0 -3 8 0 0

24) Se llega al óptimo cuando una tabla tiene todo positivo en la última fila.

25) Los coeficientes B indican las producciones; puede quedar algún recurso ocioso. El valor máximo Z se anota al final bajo B ( Z = 8(3) + 3(4,5) = $37,50 ) y sobra 1,5 del recurso 2.

Tabla 2:

8 3 0 0 0

C₂ X₂ B₂ A₁ A₂ A₃A₄ A₅ q

8 X₁3 1 0 1 0 0

0 X₄1,5 0 0 1,5 1 -1/4

3 X₂4,5 0 1 -1,5 0 1/4

37,50 0 0 3,5 0 0,75

Contribución marginal (precios sombra o máximo a pagar por otra unidad ): 3,5 y 0,75 para estos dos insumos.

Costo de oportunidad: si hubiera quedado alguna cifra abajo en las columnas de los producto A₁ ó A₂ (indicando que no se produce ese bien) sería el costo o perdida si se decidiera producir lo que no conviene.

Casos para Minimizar el costo de producción:

Como el origen de coordenadas no puede ser el paso inicial suponemos costos muy altos para los insumos al solo efecto del paso/tabla inicial. Además de las variables reales y las slag (aquí con signo -) se agregarán las nuevas variables, artificiales (+) en el funcional y como columnas en las tablas para considerar esos altos costos. En la columna C de la tabla 0 inicial se anotan esos altos costos, continuando el proceso hasta obtener el precio de cada insumo que minimiza lo requerido para la produccion de bienes dada cuando todos los valores de la última fila sean positivos.

Sin embargo, es más fácil calcular el primal, o sea, el dual del mínimo.

DUAL:

Todo caso normal de maximización implica uno de minimización y viceversa.

Como los cálculos para minimizar son mayores que para maximizar, debido a esos agregados comentados, es posible calcular el dual de un mínimo convirtiéndolo en un caso de máximo, al considerar los recursos disponibles como los coeficientes de las variables de un nuevo funcional y tomando los coeficientes de las filas del sistema de restricciones del mínimo como columnas para el sistema del máximo.

Es decir, el dual tiene una variable por cada restricción del primal (y el dual tiene tantas restricciones como variables hay en el primal).

Solo se trata de que el funcional pase a ser terminos independientes y poner las filas como columnas (las desigualdades tendran sentido inverso). Esto vale igualmente cuando en el primal hay mezcladas desigualdades contrarias: si alguna es negativa se le agregara una variable artificial tal como se dijo)

Ej.: Min Z = 5X1 + 9X2 sujeto a -3X1 - 2X2 >= -6

5X1 + X2 >= 10

X1 + 10X2 >= 9 (...y X1; X2 >=0)

Su dual es:

Max. B = -6Y1 + 10Y2 + 9Y3

-3Y1 + 5Y2 + Y3 <= 5

Sujeto a : -2Y1 + Y2 <= 9

(...con Y1; Y2 >=0)

(2variables y 3 restricciones pasan a ser 3 variables y 2 restricciones...)

Véanse cualquiera de estos textos (aunque no los mezcle; son equivalentes pero cambian los pasos):

310 ejercicios con resolución en Investigación Operaciones, de R. Bronson. Ed. McGraw-Hill

Ricardo F. Solana –Producción- Ed. Interamericana, 1994; Dieguez y Porto: Problemas de Microeconomía, Amorrortu; Taha – Investigación de Operaciones; etc.

S. Eiras Roel