Álgebra (71) · Unidad 6 — Algoritmo simplex
El problema dual
El dual de maximizar c·x con A·x ≤ b y x ≥ 0 es minimizar b·w con Aᵗ·w ≥ c y w ≥ 0: una variable por restricción, una restricción por variable. Los dos tienen el mismo valor óptimo, y la solución del dual se lee en la tabla final del máximo: son los indicadores de las holguras, con el signo cambiado.
La explicación
Dos problemas que se miran al espejo
A cada problema estándar de maximización le corresponde otro, de minimización, que se arma con los mismos números: el problema dual.
Dual: mín u = b·w , Aᵗ·w ≥ c , w ≥ 0
2. Su función a minimizar es u = b1w1 + … + bmwm: los coeficientes son los términos independientes del primal.
3. Tiene una restricción por cada variable xj del primal: sus coeficientes son la columna j de A, con «≥» y a la derecha cj.
4. Y w ≥ 0.
Por ejemplo, para maximizar z = 2x1 + 3x2 sujeta a x1 + 2x2 ≤ 12 ; x1 + x2 ≤ 8 ; 3x1 + x2 ≤ 18:
w1 + w2 + 3w3 ≥ 2 (columna de x1)
2w1 + w2 + w3 ≥ 3 (columna de x2)
w1, w2, w3 ≥ 0
Lo más fácil es no pensarlo por filas: la fila j del dual es la columna j del primal. Es transponer la matriz.
El teorema de dualidad
Si uno de los dos problemas tiene solución óptima, el otro también, y los dos valores óptimos coinciden: máx z = mín u. Además, para cualquier x factible del primal y cualquier w factible del dual vale c·x ≤ b·w: los valores del máximo siempre quedan por debajo de los del mínimo, y se tocan en el óptimo.
La solución del dual se lee en la tabla final del máximo
No hace falta resolver el dual aparte. En la tabla final del primal:
En el ejemplo, la tabla final (la de 6.2) tiene indicadores −1, −1 y 0 en las columnas de s1, s2 y s3, y la esquina dice z − 20. Entonces w = (1, 1, 0) y mín u = 20. Se controla en el dual: 1 + 1 + 0 = 2 ≥ 2 ✔, 2 + 1 + 0 = 3 ≥ 3 ✔, y u = 12 + 8 + 0 = 20 ✔.
Por qué funciona, en una línea: los indicadores finales de las x son cj − (Aᵗ·w)j, y que sean todos ≤ 0 (tabla final) es exactamente que w cumpla las restricciones del dual.
La lectura económica
Si el primal es un problema de producción (x = cantidades, b = recursos disponibles, c = ganancias), el dual es el problema de alguien que quiere comprar todos los recursos: wi es el precio que ofrece por cada unidad del recurso i. Cada restricción del dual dice que por los recursos que lleva un producto tiene que pagar al menos lo que el fabricante ganaría haciéndolo; y el comprador quiere gastar lo menos posible (mín b·w). El óptimo dice cuánto vale, en el margen, cada unidad de recurso.
Dos consecuencias que se usan mucho: un recurso que sobra (su holgura es básica y positiva) tiene wi = 0, porque una unidad más no agregaría ganancia; y lo que pagaría el comprador en total es exactamente la ganancia máxima.
El control que conviene hacer siempre
Con la w que leíste: que sea ≥ 0, que cumpla todas las restricciones del dual (reemplazá en cada una), y que b·w dé el mismo número que la esquina de la tabla final. Si b·w no coincide con máx z, hay un error de lectura (casi siempre, un signo).
Plantear el problema dual de maximizar z = 2x₁ + 3x₂ sujeta a x₁ + 2x₂ ≤ 12 ; x₁ + x₂ ≤ 8 ; 3x₁ + x₂ ≤ 18 ; x ≥ 0, y leer su solución en la tabla final del máximo: ( 0 1 │ 1 −1 0 │ 4 ) ; ( 1 0 │ −1 2 0 │ 4 ) ; ( 0 0 │ 2 −5 1 │ 2 ) ; indicadores ( 0 0 │ −1 −1 0 │ z − 20 ).
El dual. Tres restricciones en el primal → tres variables w1, w2, w3. Dos variables en el primal → dos restricciones en el dual.
mín u = 12w1 + 8w2 + 18w3
w1 + w2 + 3w3 ≥ 2
2w1 + w2 + w3 ≥ 3
w ≥ 0
La solución del primal (de la tabla): x2 = 4, x1 = 4, s3 = 2; máx z = 20.
La solución del dual: los indicadores de s1, s2, s3 son −1, −1, 0. Con el signo cambiado:
Control en el dual:
2 + 1 + 0 = 3 ≥ 3 ✔
u = 12 + 8 + 0 = 20 = máx z ✔
Lectura: si las restricciones fueran recursos, una unidad más del primero o del segundo agregaría 1 a la ganancia máxima, y una más del tercero no agregaría nada: de ése ya sobran 2 (s3 = 2). Por eso w3 = 0.
Dónde se pierde el punto: leer w en la columna b. Daría (4, 4, 2), con u = 48 + 32 + 36 = 116 ≠ 20: el control de b·w lo delata enseguida.
La fábrica de pastas del tema 6.2 maximiza z = 4x₁ + 5x₂ + 3x₃ sujeta a x₁ + x₂ + x₃ ≤ 100 (kg de harina) ; 2x₁ + x₂ + 3x₃ ≤ 240 (minutos de amasado) ; x₁ + 2x₂ + x₃ ≤ 160 (minutos de envasado), y su tabla final tiene indicadores ( 0 0 −1 │ −3 0 −1 │ z − 460 ). Otra fábrica le quiere comprar toda la harina y todas las horas de amasado y envasado. Plantear el dual, dar su solución e interpretarla.
Las variables del dual: w1 = precio por kg de harina, w2 = por minuto de amasado, w3 = por minuto de envasado (en miles de pesos).
El dual: el comprador quiere pagar lo menos posible por todo, pero cada caja tiene que «valer» al menos lo que la fábrica ganaría haciéndola:
ravioles: w1 + 2w2 + w3 ≥ 4
ñoquis: w1 + w2 + 2w3 ≥ 5
sorrentinos: w1 + 3w2 + w3 ≥ 3
w ≥ 0
La solución: los indicadores de s1, s2, s3 son −3, 0, −1:
Control: 3 + 0 + 1 = 4 ≥ 4 ✔; 3 + 0 + 2 = 5 ≥ 5 ✔; 3 + 0 + 1 = 4 ≥ 3 ✔; u = 300 + 0 + 160 = 460 = máx z ✔.
La lectura: el kilo de harina vale 3 mil pesos, el minuto de envasado mil pesos, y el de amasado nada: en la solución óptima sobran 100 minutos de amasado (s2 = 100), así que tener uno más no cambia la ganancia. Vendiendo todo a esos precios, la fábrica cobra 460 mil pesos, lo mismo que ganaría produciendo.
Una cosa más que se ve en el control: la restricción de los sorrentinos se cumple con margen (4 > 3). Los recursos que lleva una caja de sorrentinos valen más que lo que se gana con ella: por eso en el óptimo x3 = 0.
Dónde se pierde el punto: escribir las restricciones del dual con las filas del primal (por ejemplo w1 + w2 + w3 ≥ 4 usando la fila de la harina) en vez de las columnas.
Dónde se cae la mayoría
- Leer la solución del dual en la columna b de la tabla final: está en la fila de indicadores, debajo de las holguras.
- Olvidarse del cambio de signo: los indicadores de las holguras son ≤ 0 y w es ≥ 0.
- Armar las restricciones del dual por filas de A en vez de por columnas: la restricción j del dual usa los coeficientes de x_j en todas las restricciones.
- Dejar «≤» en el dual o dejarlo como máximo: el dual de un máximo con «≤» es un mínimo con «≥».
- Poner en la función del dual los coeficientes de z: los coeficientes de u son los términos independientes del primal, y los de z van a la derecha de las restricciones.
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 El problema dual →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