Descubriendo el espejo de la optimización Lineal, el fascinante mundo de la dualidad

¿Alguna vez has sentido que un problema tiene dos caras? En el mundo de las matemáticas y la optimización, esto no es sólo una sensación: es la teoría de la dualidad. La dualidad es uno de los resultados más sorprendentes de la optimización lineal: cada problema tiene un espejo matemático que produce el mismo valor óptimo, pero desde una perspectiva completamente distinta.

Origen

La teoría de la dualidad nació de conversaciones entre dos mentes brillantes: George Dantzig y John von Neumann. Juntos descubrieron que cada problema de optimización lineal, que llamamos Primal tiene un “gemelo” matemático llamado Dual.

Teoría de juegos y optimización lineal: piedra, papel o tijera

Para entender la dualidad, nada mejor que un juego que todos conocemos. El juego Piedra, Papel o Tijera es un juego de suma cero, lo que significa que lo que un jugador gana, el otro lo pierde. La base de un juego es la matriz de pagos que representa los resultados para el Jugador I (por filas):

Si queremos encontrar la estrategia óptima usando optimización lineal, consideremos a ambos jugadores:

• Jugador I (Primal): Busca maximizar su ganancia mínima (estrategia maximin) definiendo la probabilidad de elegir cada opción:

\[\begin{aligned} \max\;\; & \min\{x_2-x_3, -x_1+x_3,x_1-x_2\} \\ \textrm{s. a:}\;\; & x_1 + x_2 + x_3 = 1 \\ & x_1, x_2, x_3 \geqslant 0 \end{aligned}\]

Introducimos una variable $z$ que representa la ganancia mínima garantizada y la forzamos a ser menor o igual que cada posible resultado. Con este paso, conseguimos un modelo totalmente lineal:

\[\begin{aligned} \max\;\; & z \\ \textrm{s. a:}\;\; & -x_2 + x_3 + z \leqslant 0 \\ & x_1 - x_3 + z \leqslant 0 \\ & -x_1 + x_2 + z \leqslant 0 \\ & x_1 + x_2 + x_3 = 1 \\ & x_1, x_2, x_3 \geqslant 0\\ & z \in \mathbb{R} \end{aligned}\]

Esta estrategia puede ser modelada con optimización lineal:

• Jugador II (Dual): Busca minimizar la pérdida máxima que el otro le puede infligir (estrategia minimax).

Esta estrategia también se puede modelar con optimización lineal:

\[\begin{aligned} \min\;\; & \max\{-u_2+u_3, u_1-u_3,-u_1+u_2\} \\ \textrm{s. a:}\;\; & u_1 + u_2 + u_3 = 1 \\ & u_1, u_2, u_3 \geqslant 0 \end{aligned}\]

que en su forma lineal viene dado por:

\[\begin{aligned} \min\;\; & w \\ \textrm{s. a:}\;\; & u_2 - u_3 + w \geqslant 0 \\ & -u_1 + u_3 + w \geqslant 0 \\ & u_1 - u_2 + w \geqslant 0 \\ & u_1 + u_2 + u_3 = 1 \\ & u_1, u_2, u_3 \geqslant 0\\ & w \in \mathbb{R} \end{aligned}\]

Lo asombroso es que, al resolver ambos modelos, llegamos a la misma conclusión: la estrategia óptima para ambos es jugar cada opción con una probabilidad de 1/3, es decir $x_1=x_2=x_3=1/3$ y $u_1,u_2,u_3=1/3$. El valor esperado del juego para ambos es 0, es decir, $z=w=0$. ¡La dualidad nos muestra que el equilibrio del juego es el mismo para ambos bandos!

Este resultado es un caso particular del teorema minimax, uno de los pilares de la teoría de juegos.

Ejemplo 2: El Dilema de los Recursos (Empresa vs. Competidor)

Imagina una empresa que fabrica cuatro productos $(p_1,p_2,p_3,p_4)$ usando tres recursos (materias primas) limitados ($r_1,r_2,r_3$) para maximizar su beneficio. Su modelización viene dada por:

\[\begin{aligned} \max\;\; & z = 4x_1 + 3x_2 + 6x_3 + 2x_4 \\ \textrm{s. a:}\;\; & 2x_1 + 3x_2 + 1.5x_3 + 4x_4 \leqslant 300 \\ & 2x_1 + 4x_2 + 3x_3 + x_4 \leqslant 500 \\ & 5x_1 + x_2 + 2x_3 + 2x_4 \leqslant 250 \\ & x_1, x_2, x_3, x_4 \geqslant 0 \end{aligned}\]

y es lo que denominaremos problema primal.

Ahora, imagina a un competidor que no quiere fabricar nada, sino comprarle los recursos a la primera empresa al menor costo posible. Este competidor debe decidir cuánto pagar por cada unidad de recurso ($u_1,u_2,u_3$), con la condición de que el precio ofrecido sea lo suficientemente atractivo como para que a la empresa le compense vender en lugar de producir:

\[\begin{aligned} \min\;\; & w = 300u_1 + 500u_2 + 250u_3 \\ \textrm{s. a:}\;\; & 2u_1 + 2u_2 + 5u_3 \geqslant 4 \\ & 3u_1 + 4u_2 + u_3 \geqslant 3 \\ & 1.5u_1 + 3u_2 + 2u_3 \geqslant 6 \\ & 4u_1 + u_2 + 2u_3 \geqslant 2 \\ & u_1, u_2, u_3 \geqslant 0 \end{aligned}\]

y a este problema lo denominaremos Dual.

Resolviendo ambos modelos de forma independiente se obtiene que $z^* = 750$ y $w^* = 750$, siendo el beneficio la empresa igual al coste mínimo con el que el competidor adquiriría los recursos.

Aquí vemos las dos perspectivas sobre el mismo problema:

• El Ingeniero (Primal): Se enfoca en las cantidades de producto a fabricar.

• El Economista (Dual): Se enfoca en los precios o el valor de los recursos (llamados “precios sombra”).

Tabla de equivalencias

La pareja de problemas duales en su forma canónica viene dada por:

\[\begin{aligned} \min\;\;& LP_c = \mathbf{c}^\intercal \mathbf{x} \\ \textrm{s. a:} \;\;& \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \\ \end{aligned} \qquad \begin{aligned} \max\;\;& DLP_c = \mathbf{b}^\intercal \mathbf{u} \\ \textrm{s. a:} \;\;& \mathbf{A}^\intercal \mathbf{u} \leqslant \mathbf{c} \\ & \mathbf{u} \geqslant \mathbf{0} \end{aligned}\]

de los cuales se puede obtener la siguiente tabla, la “piedra rosetta” de la optimización. Te permite traducir cualquier problema de optimización a su espejo dual de forma mecánica:

Recuerda que el número de variables y restricciones de cada problema son los números de restricciones y variables del otro, es decir, cada restricción del primal corresponde a una variable dual y cada variable primal corresponde a una restricción del dual. Esto induce que en el dual, se tenga que transponer la matriz de coeficientes técnicos.

Resultados fundamentales

A continuación se recopilan varios resultados teóricos que tienen gran importancia en la teoría de la dualidad:

Doble dualidad

El problema dual de un problema dual es el problema primal.

Teorema débil de dualidad

Dadas $\bar{\mathbf{x}}$ y $\bar{\mathbf{u}}$ soluciones factibles de los problemas primal $LP_c$ y dual $DLP_c$, respectivamente, se verifica siempre la siguiente afirmación:

\[\mathbf{c}^\intercal \bar{\mathbf{x}} \geqslant \mathbf{b}^\intercal \bar{\mathbf{u}}\]

que tiene diferentes consecuencias que desembocan en el siguiente resultado:

Teorema fundamental de la dualidad

Dados dos problemas duales $LP$ y $DLP$, sólo ocurre una de las siguientes situaciones:

• Ambos problemas son infactibles.
• Un problema tiene solución óptima no acotada y el otro es infactible.
• Ambos problemas tienen solución óptima.

El siguiente resultado es clave para relacionar directamente las soluciones de un problema con el otro:

Teorema de holguras complementarias

Dados dos problemas $LP_c$ y $DLP_c$ en sus formas canónicas, entonces dos soluciones factibles $\bar{\mathbf{x}}$ y $\bar{\mathbf{u}}$ son óptimas si y sólo si:

\[\begin{cases}\bar{\mathbf{u}}^\intercal(\mathbf{A}\bar{\mathbf{x}}-\mathbf{b})=0 \\ (\mathbf{c}^\intercal - \bar{\mathbf{u}}^\intercal\mathbf{A})\bar{\mathbf{x}} = 0 \end{cases}\]

De forma explícita, se tiene que dadas dos soluciones factibles $\bar{\mathbf{x}}$ y $\bar{\mathbf{u}}$, entonces se cumplen:

\[\begin{aligned} u_i\,(a_i^\intercal x - b_i) & = 0 && \forall i \\ x_j\,(c_j - a_j^\intercal u) & = 0 && \forall j \end{aligned}\]

Y esto equivale a decir:

• Si $x_j > 0$, entonces la restricción dual correspondiente se cumple con igualdad.

• Si $c_j - a_j^\intercal u > 0$, entonces $x_j = 0$.

• Si $u_i > 0$, entonces la restricción primal correspondiente se cumple con igualdad.
• Si $a_i^\intercal x - b_i > 0$, entonces $u_i = 0$.

Identificación de la solución dual

Podríamos creer que al resolver un problema de optimización lineal mediante el Símplex sólo obtenemos la solución del problema original (Primal). Sin embargo, la tabla final nos revela la solución del problema Dual sin necesidad de hacer ni un sólo cálculo extra.

En una tabla del Símplex la información se distribuye de la siguiente manera:

• Variables Duales ($u_i$): Se encuentran en la fila del objetivo ($z_j − c_j$) bajo las columnas que correspondían a las variables de holgura iniciales del Primal. Estos valores representan cuánto mejoraríamos el beneficio si tuviéramos una unidad extra de cada recurso.

• Variables de Holgura Duales: Se encuentran en la misma fila del objetivo, pero bajo las columnas de las variables de decisión originales ($x_j$).

• Valor Óptimo: El valor de la función objetivo es exactamente el mismo para ambos problemas ($z^* = w^*$).

La Economía en el problema Dual (Precios Sombra)

La dualidad no es solo un espejo matemático, es una herramienta de decisión empresarial. Para un economista, las variables duales se conocen como Precios Sombra.

¿Qué es un Precio Sombra?

Es el valor marginal de un recurso. Nos indica cuánto aumentaría nuestra función objetivo (por ejemplo, el beneficio total) si incrementáramos en una unidad la disponibilidad de ese recurso limitado, manteniendo todo lo demás constante.

Interpretación Económica Clave:

Si el Precio Sombra es $>0$: El recurso es “escaso”. Lo estamos usando todo (su variable de holgura en el primal es 0). Vale la pena pagar por conseguir más de este recurso, siempre que el coste sea menor al precio sombra.

Si el Precio Sombra es $=0$: El recurso “sobra”. No hemos agotado la cantidad disponible, por lo que tener una unidad adicional no nos aporta ningún beneficio extra. Su valor marginal es nulo.

Conclusión

Desde un punto de vista geométrico, la dualidad tiene una interpretación fascinante: mientras el problema primal busca el mejor punto dentro de un poliedro factible, el problema dual describe el hiperplano que lo sostiene en el óptimo.

Dos perspectivas distintas sobre el mismo fenómeno: una decide qué hacer, la otra revela cuánto vale cada recurso.

Y, sorprendentemente, ambas llegan exactamente al mismo resultado.