Álgebra (71) · Unidad 6 — Algoritmo simplex
Minimizar con el dual: problemas de costo mínimo
Un mínimo con restricciones «≥» (cubrir al menos tanto de cada cosa al menor costo) no es estándar, pero su dual sí: es un máximo con «≤». Se resuelve el dual por simplex y la solución del mínimo se lee en la tabla final, en los indicadores de las holguras con el signo cambiado; el costo mínimo es el máximo del dual.
La explicación
El problema de costo mínimo
Muchos problemas de Económicas tienen esta forma: hay que cubrir al menos ciertas cantidades (horas de trabajo, nutrientes, unidades pedidas) combinando cosas que tienen un costo, y se quiere gastar lo menos posible.
sujeta a M·w ≥ c , w ≥ 0
No es estándar: las restricciones son «≥» con términos positivos, así que el origen no las cumple (no comprar nada no cubre nada), y el truco de 6.6 (maximizar −u) no sirve, porque la región no es la de un problema estándar.
La salida: resolver el dual
El dual de ese mínimo es un máximo con «≤»: el mismo esquema de 6.7, leído al revés.
sujeta a Mᵗ·x ≤ b , x ≥ 0
Es estándar si los costos bi son ≥ 0, que en un problema de costos siempre pasa. Los cj (lo que hay que cubrir) pueden tener cualquier signo: pasan a ser los coeficientes de z.
2. Armá el dual: una variable xj por cada restricción «≥»; los términos independientes (lo que hay que cubrir) van a z; la columna de cada wi da una restricción «≤ bi», con su costo a la derecha.
3. Resolvé el dual por simplex.
4. En la tabla final, wi = −(indicador de la holgura si), y el costo mínimo es el máximo del dual: mín u = máx z.
5. Contestá en las variables del problema original, las w, que son las que el enunciado pregunta.
Ojo con quién es quién. Las x del dual son auxiliares (se pueden leer como el valor de cada unidad que hay que cubrir), pero la pregunta es por las w. Lo que se lee en la columna b de la tabla final son las x; las w están en la fila de indicadores, debajo de las holguras.
Un ejemplo corto
Minimizar u = 6w1 + 4w2 sujeta a w1 + w2 ≥ 6 ; 3w1 + w2 ≥ 12. El dual es maximizar z = 6x1 + 12x2 sujeta a x1 + 3x2 ≤ 6 (columna de w1, costo 6) ; x1 + x2 ≤ 4 (columna de w2, costo 4). Su tabla final tiene indicadores −3 y −3 en las holguras y la esquina z − 30: la solución del mínimo es w = (3, 3), con u = 30.
Plantear bien las restricciones «≥»
Las frases típicas: «por lo menos», «al menos», «como mínimo» son «≥». «Dedicar al ciclismo por lo menos lo mismo que al trote y la natación juntos» es c ≥ t + n, o sea −t + c − n ≥ 0. Si una restricción queda con término negativo (por ejemplo −w1 + w2 ≥ −3) no hay problema: ese −3 es el coeficiente de una x en el dual.
Y si alguna restricción del mínimo viene como «≤», se multiplica por −1 para que quede «≥» antes de armar el dual.
El control que conviene hacer siempre
Reemplazá la w en el problema original: tiene que cumplir todas las restricciones «≥» (alguna con margen, alguna justa) y el costo b·w tiene que dar lo mismo que la esquina de la tabla final del dual. Si hay dos variables, además se puede dibujar la región del mínimo (que es no acotada «hacia arriba») y evaluar u en sus vértices.
Minimizar u = 6w₁ + 4w₂ sujeta a w₁ + w₂ ≥ 6 ; 3w₁ + w₂ ≥ 12 ; w₁ ≥ 0, w₂ ≥ 0, resolviendo el problema dual por el método simplex. Controlar con el método gráfico.
¿Por qué el dual? Las restricciones son «≥» con términos 6 y 12: el origen no las cumple y el problema no es estándar.
El dual. Dos restricciones → dos variables x1, x2. La columna de w1 es (1, 3) y cuesta 6; la de w2 es (1, 1) y cuesta 4.
x1 + 3x2 ≤ 6
x1 + x2 ≤ 4
x1, x2 ≥ 0
El simplex del dual. Entra x2 (12). Cocientes 6/3 = 2 y 4/1 = 4: fila 1.
( ⅔ 0 │ −⅓ 1 │ 2 )
( 2 0 │ −4 0 │ z − 24 )
Entra x1 (2). Cocientes 2 / ⅓ = 6 y 2 / ⅔ = 3: fila 2.
( 1 0 │ −½ 3/2 │ 3 )
( 0 0 │ −3 −3 │ z − 30 )
Final: máx z = 30.
La solución del mínimo: los indicadores de s1 y s2 son −3 y −3. Entonces w1 = 3, w2 = 3, y mín u = 30.
Control en el original: 3 + 3 = 6 ≥ 6 ✔, 9 + 3 = 12 ≥ 12 ✔, u = 18 + 12 = 30 ✔.
Control gráfico: la región del mínimo es no acotada hacia arriba y a la derecha, con puntos esquina (0, 12), (3, 3) y (6, 0). u vale 48, 30 y 36: el menor es 30, en (3, 3) ✔. (Como los costos son positivos, u crece hacia el lado abierto: el mínimo existe.)
Dónde se pierde el punto: contestar w = (3, 1), que es la columna b de la tabla final: ésas son x1 y x2 del dual. El control lo caza: 3 + 1 = 4, no llega a 6.
Una cadena de heladerías necesita por día al menos 10 kg de cobertura de chocolate y al menos 12 kg de dulce de leche. Tres proveedores venden cajas: la del proveedor A trae 1 kg de chocolate y 1 de dulce de leche y cuesta 2 decenas de miles de pesos; la de B trae 2 y 1 y cuesta 4; la de C trae 1 y 2 y cuesta 3. ¿Cuántas cajas de cada uno conviene comprar para cubrir lo que hace falta al menor costo?
El mínimo: w1, w2, w3 = cajas de A, B y C.
chocolate: w1 + 2w2 + w3 ≥ 10
dulce: w1 + w2 + 2w3 ≥ 12
w ≥ 0
El dual: dos restricciones → x1, x2; tres variables → tres restricciones, una por proveedor (su columna y su costo).
A: x1 + x2 ≤ 2
B: 2x1 + x2 ≤ 4
C: x1 + 2x2 ≤ 3
El simplex del dual. Entra x2 (12). Cocientes 2, 4 y 3/2: fila 3; z = 18 y a x1 le queda indicador 4. Entra x1: su columna es (½, 3/2, ½) con b = (½, 5/2, 3/2), cocientes 1, 5/3 y 3: fila 1. Tabla final:
( 0 0 │ −3 1 1 │ 1 )
( 0 1 │ −1 0 1 │ 1 )
( 0 0 │ −8 0 −2 │ z − 22 )
La solución: indicadores de s1, s2, s3: −8, 0, −2. Entonces w = (8, 0, 2) y mín u = 22.
Respuesta: conviene comprar 8 cajas de A, ninguna de B y 2 de C, a un costo de 22 decenas de miles de pesos (220 mil).
Control en el original: chocolate 8 + 0 + 2 = 10 ≥ 10 ✔, dulce 8 + 0 + 4 = 12 ≥ 12 ✔, u = 16 + 0 + 6 = 22 ✔. Otras compras que cubren lo mismo cuestan más: 12 cajas de A cuestan 24, y sólo C (10 cajas para el chocolate) cuesta 30.
Una lectura del dual: x = (1, 1) dice que, en el margen, cada kg de chocolate y cada kg de dulce que se pida de más encarece la compra en 1 decena de miles. Y la holgura de B es básica (vale 1): la caja de B «vale» 2 + 1 = 3 por lo que trae y cuesta 4, por eso no se compra.
Dónde se cae la mayoría
- Intentar el simplex directamente sobre el mínimo con «≥»: la tabla inicial no representaría un punto de la región (el origen no cubre nada).
- Contestar con la columna b de la tabla final del dual: ésas son las x del dual. Las variables del mínimo son los indicadores de las holguras, con el signo cambiado.
- Armar el dual por filas: cada restricción del dual sale de la columna de una variable w del mínimo, con su costo a la derecha.
- Poner los costos en la función del dual: los costos van a la derecha de las restricciones, y lo que hay que cubrir va a la función z.
- Traducir «al menos el doble de A que de B» como 2w_A ≥ w_B: es w_A ≥ 2w_B, o sea w_A − 2w_B ≥ 0.
Hasta acá la explicación. La práctica es la otra mitad: 7 ejercicios de este tema, en cuatro niveles, que no te dicen sólo si está bien al final sino que te corrigen en cada paso y te explican por qué. Además trae una animación que muestra la idea en movimiento.
Practicar Minimizar con el dual: problemas de costo mínimo →Dónde entra este tema en el parcial
- Segundo parcial — Las encuestas más baratas, por el dual25 puntos · resuelto paso a paso
Los otros temas de la unidad 6
Algoritmo simplex