Dualidad: formulación del dual, relaciones e interpretación económica

1. La pregunta

Una empresa tiene 240 horas de máquina. Nunca las ha comprado en un mercado: son suyas, vienen con la nave. ¿Cuánto vale una hora?

No hay factura que lo diga. Y sin embargo la respuesta es decisiva: determina si conviene alquilar una máquina más, si compensa un turno extra, y a qué precio mínimo tiene sentido aceptar un encargo. La dualidad es el mecanismo que asigna precio a los recursos que no lo tienen, y es probablemente el resultado más útil de todo el bloque 4.

2. Intuición

Piensa en dos personas mirando la misma fábrica.

El productor se pregunta: con estos recursos, ¿qué plan de producción maximiza mi beneficio? Ese es el problema primal, el del tema 16.

Un inversor que quiere comprar la fábrica entera se pregunta lo contrario: ¿qué precio mínimo debo ofrecer por cada recurso para que al dueño le compense vender en vez de producir? Ese es el problema dual.

El inversor quiere pagar lo menos posible: minimiza el desembolso total. Pero tiene una restricción: por cada producto, lo que ofrece por los recursos que ese producto consume debe ser al menos el margen que el productor obtendría fabricándolo. Si ofreciera menos, al dueño le compensaría producir en vez de vender.

Y aquí está el resultado extraordinario: el precio mínimo que hace desistir al productor es exactamente el beneficio máximo que este podía obtener. Los dos problemas tienen el mismo valor óptimo. No es una coincidencia: es el teorema de dualidad fuerte.

Esos precios que resuelven el problema del inversor se llaman precios sombra. Ya aparecieron en la tabla final del símplex, en la fila $z$ bajo las columnas de holgura, y son los mismos multiplicadores de Lagrange del tema 14 con otro nombre.

3. Formalización

Construcción del dual

Dado el primal

$$\max z={\mathbf{c}}^{\top }\mathbf{x}\text{s.a.}\mathbf{Ax}\le \mathbf{b},\mathbf{x}\ge 0$$

su dual es

$$\min w={\mathbf{b}}^{\top }\mathbf{y}\text{s.a.}{\mathbf{A}}^{\top }\mathbf{y}\ge \mathbf{c},\mathbf{y}\ge 0$$

donde $\mathbf{y}$ es el vector de variables duales o precios sombra, con una componente por cada restricción del primal.

Todo se invierte de forma sistemática:

Primal (máximo)	Dual (mínimo)
$m$ restricciones	$m$ variables
$n$ variables	$n$ restricciones
coeficientes objetivo $\mathbf{c}$	términos independientes $\mathbf{c}$
términos independientes $\mathbf{b}$	coeficientes objetivo $\mathbf{b}$
matriz $\mathbf{A}$	matriz ${\mathbf{A}}^{\top }$
restricción $\le$	variable $\ge 0$
restricción $=$	variable libre de signo
variable $\ge 0$	restricción $\ge$
variable libre	restricción $=$

El dual del dual es el primal. Los dos problemas son la misma información vista desde dos lados; ninguno es «el original».

Interpretación de cada pieza

Con el primal en clave de producción:

• $y_i$ = precio sombra del recurso $i$: lo que aporta al beneficio una unidad adicional de ese recurso. Sus unidades son euros por unidad de recurso.
• La restricción dual $j$-ésima, ${\sum }_i{a}_{ij}{y}_i\ge c_j$, dice: el valor imputado de los recursos que consume una unidad del producto $j$ debe ser al menos su margen. Si fuera menor, convendría fabricar más de ese producto.
• El objetivo dual ${\sum }_i{b}_i{y}_i$ es el valor total imputado a los recursos de la empresa.

Teoremas de dualidad

Dualidad débil. Para cualquier $\mathbf{x}$ factible del primal y cualquier $\mathbf{y}$ factible del dual:

$${\mathbf{c}}^{\top }\mathbf{x}\le {\mathbf{b}}^{\top }\mathbf{y}$$

Cualquier solución dual factible es una cota superior del beneficio alcanzable. La demostración cabe en una línea:

$${\mathbf{c}}^{\top }\mathbf{x}\le ({\mathbf{A}}^{\top }\mathbf{y}{)}^{\top }\mathbf{x}={\mathbf{y}}^{\top }\mathbf{Ax}\le {\mathbf{y}}^{\top }\mathbf{b}$$

usando primero $\mathbf{c}\le {\mathbf{A}}^{\top }\mathbf{y}$ con $\mathbf{x}\ge 0$, y después $\mathbf{Ax}\le \mathbf{b}$ con $\mathbf{y}\ge 0$.

Dualidad fuerte. Si el primal tiene solución óptima finita, el dual también, y

$$z^{\ast }=w^{\ast }$$

Consecuencias que hay que reconocer:

• Primal no acotado $⟹$ dual infactible.
• Primal infactible $⟹$ dual infactible o no acotado.
• Si uno tiene óptimo finito, el otro también.

Holgura complementaria. En el óptimo, para cada par restricción-variable:

$$y_i^{\ast }\left(b_i-\sum _j{a}_{ij}{x}_j^{\ast }\right)=0\text{para cada }i$$ $$x_j^{\ast }\left(\sum _i{a}_{ij}{y}_i^{\ast }-c_j\right)=0\text{para cada }j$$

En palabras, y esto es lo que se usa a diario:

• Si un recurso sobra, su precio sombra es cero. Nadie paga por lo que no escasea.
• Si un recurso tiene precio sombra positivo, está agotado.
• Si un producto se fabrica ($x_j>0$), su restricción dual se cumple con igualdad: su margen iguala exactamente el valor de los recursos que consume.
• Si la restricción dual es estricta, ese producto no se fabrica. No paga lo que cuesta.

Es la misma lógica de la holgura complementaria de Kuhn-Tucker del tema 14, y no es una analogía: es el mismo teorema aplicado al caso lineal.

Cómo leer el dual en la tabla del símplex

No hace falta resolver el dual por separado. En la tabla óptima del primal:

$$y_i^{\ast }=(z_j-c_j)\text{ de la columna de la holgura }{s}_i$$

Y al revés: resolviendo el dual se obtienen de la misma manera las variables del primal. Por eso, cuando un problema tiene muchas más restricciones que variables, se resuelve el dual y se lee el primal: es más rápido.

Símplex dual

Existe además una variante del algoritmo, el símplex dual, que trabaja manteniendo la optimalidad y buscando la factibilidad, al revés que el símplex habitual. Su utilidad práctica aparece en el tema 19: cuando cambia un término independiente $b_i$, la tabla deja de ser factible pero sigue siendo óptima, y el símplex dual la repara en pocas iteraciones sin empezar de cero.

4. Ejemplo económico resuelto

Problema. Volvemos a la carpintería del tema 16:

$$\max z=70x_1+50x_2\text{s.a.}4x_1+3x_2\le 240,2x_1+x_2\le 100,x_1,x_2\ge 0$$

Formula el dual, resuélvelo y verifica los teoremas.

Paso 1. Escribir el dual. Hay 2 restricciones, luego 2 variables duales: $y_1$ (precio de una hora de carpintería) e $y_2$ (precio de una hora de acabado). Y hay 2 variables primales, luego 2 restricciones duales, una por producto.

$$\min w=240y_1+100y_2$$ $$\text{s.a.}\{\begin{array}{ll}4y_1+2y_2\ge 70& \text{(mesa)}\\ 3y_1+y_2\ge 50& \text{(estanterıˊa)}\\ y_1,y_2\ge 0& \end{array}$$

Cómo leer cada restricción. La primera dice: una mesa consume 4 horas de carpintería y 2 de acabado; el valor imputado de esos recursos, $4y_1+2y_2$, debe ser al menos el margen de la mesa, 70 €. Si valiera menos, a la empresa le compensaría fabricar más mesas.

Paso 2. Resolver el dual. Como es un problema de mínimo con restricciones $\ge$, podría resolverse por dos fases. Pero al ser de dos variables, es más rápido por vértices.

Corte de las dos restricciones (con igualdad):

$$\{\begin{array}{l}4y_1+2y_2=70\\ 3y_1+y_2=50\end{array}$$

Multiplicando la segunda por 2 y restando la primera:

$$6y_1+2y_2-4y_1-2y_2=100-70⟹2y_1=30⟹y_1=15$$ $$y_2=50-3(15)=5$$

Los dos son no negativos. Candidato: $(15,5)$, con

$$w=240(15)+100(5)=3600+500=4100$$

Otros vértices. Con $y_2=0$: la primera exige $y_1\ge 17,5$, la segunda $y_1\ge 16,67$; manda 17,5, punto $(17,5;0)$ con $w=4200$. Con $y_1=0$: la primera exige $y_2\ge 35$, la segunda $y_2\ge 50$; manda 50, punto $(0,50)$ con $w=5000$.

Vértice	$w$
$(15,5)$	4100
$(17,5;0)$	4200
$(0,50)$	5000

Óptimo dual: $y_1^{\ast }=15$, $y_2^{\ast }=5$, $w^{\ast }=4100$ €.

Paso 3. Verificar la dualidad fuerte.

$$z^{\ast }=4100=w^{\ast }✓$$

Y coincide con los valores que ya aparecían en la fila $z$ de la tabla óptima del tema 16: 15 bajo $s_1$ y 5 bajo $s_2$. No hacía falta resolver nada: el dual estaba dentro de la tabla del primal.

Paso 4. Verificar la holgura complementaria.

En el primal, $x_1^{\ast }=30$ y $x_2^{\ast }=40$, y los dos recursos se agotan: $s_1^{\ast }=s_2^{\ast }=0$.

• $y_1^{\ast }(240-240)=15\cdot 0=0✓$
• $y_2^{\ast }(100-100)=5\cdot 0=0✓$

Y por el otro lado, como los dos productos se fabrican, sus restricciones duales deben ser igualdades:

• Mesa: $4(15)+2(5)=60+10=70=c_1✓$
• Estantería: $3(15)+5=45+5=50=c_2✓$

Todo cuadra.

Paso 5. Usar los precios sombra para decidir. Con $y_1=15$ e $y_2=5$:

• Alquilar una hora más de carpintería compensa si cuesta menos de 15 €.
• Un turno extra de acabado, si sale por menos de 5 € la hora.
• Con presupuesto limitado, conviene ampliar antes la carpintería: rinde el triple.

Paso 6. Valorar un producto nuevo. Un cliente propone fabricar un armario que consumiría 5 horas de carpintería y 2 de acabado, con un margen de 80 €. ¿Interesa?

El valor imputado de los recursos que consumiría es

$$5(15)+2(5)=75+10=85\text{ €}$$

Y su margen es 80 €. Como $85>80$, el armario destruiría 5 € de beneficio por unidad: consumiría recursos que rinden más en las mesas y estanterías. Hay que rechazarlo, o negociar un margen superior a 85 €.

Esta decisión se ha tomado sin volver a resolver nada. Es el uso más valioso de la dualidad en la práctica: evaluar alternativas nuevas con los precios sombra ya calculados.

5. Errores típicos

Confundir el sentido de las desigualdades al construir el dual. Con primal de máximo y restricciones $\le$, el dual es de mínimo con restricciones $\ge$. Cambiar uno solo de los dos sentidos da un problema que no tiene nada que ver.

Olvidar trasponer la matriz. El dual usa ${\mathbf{A}}^{\top }$: las filas del primal son las columnas del dual. Es el mismo error de orden que en el tema 6, y aquí produce un dual con dimensiones incoherentes.

Intercambiar $\mathbf{b}$ y $\mathbf{c}$ a medias. Los términos independientes del primal son los coeficientes objetivo del dual, y viceversa. Los dos a la vez.

Poner una variable dual $\ge 0$ cuando la restricción primal era de igualdad. Las restricciones $=$ dan variables duales libres de signo, y eso cambia la solución.

Interpretar el precio sombra fuera de su rango. $y_i$ dice cuánto vale una unidad más en el margen. Si se añaden 500 horas, la base cambia y el precio deja de ser válido. Hasta dónde vale es exactamente el análisis de sensibilidad del tema 19.

Dar precio sombra positivo a un recurso que sobra. La holgura complementaria lo prohíbe. Si un cálculo lo produce, hay un error.

Creer que hay que resolver el dual aparte. La tabla óptima del primal ya lo contiene. Resolver el dual por separado solo tiene sentido cuando es computacionalmente más barato.

6. Ejercicios

Ejercicio 1 · Construir el dual

básico

Escribe el dual de:

$$\max z=5x_1+4x_2+3x_3$$$$\text{s.a.}2x_1+3x_2+x_3\le 5,4x_1+x_2+2x_3\le 11,3x_1+4x_2+2x_3\le 8,x_j\ge 0$$

Ver solución

Tres restricciones $⟹$ tres variables duales $y_1,y_2,y_3$. Tres variables primales $⟹$ tres restricciones duales.

$$\min w=5y_1+11y_2+8y_3$$$$\text{s.a.}\{\begin{array}{l}2y_1+4y_2+3y_3\ge 5\\ 3y_1+y_2+4y_3\ge 4\\ y_1+2y_2+2y_3\ge 3\\ y_1,y_2,y_3\ge 0\end{array}$$

Comprobación de la trasposición. La primera restricción dual lleva los coeficientes $(2,4,3)$, que son la primera columna de la matriz primal, es decir, los consumos del producto $x_1$ en los tres recursos. Correcto.

Ejercicio 2 · Leer precios sombra en la tabla

básico

La tabla óptima de un primal de máximo con dos recursos es:

$$\begin{array}{cccccc}\text{Base}& x_1& x_2& s_1& s_2& b\\ x_2& 0& 1& 0,4& -0,2& 12\\ x_1& 1& 0& -0,1& 0,3& 8\\ z_j-c_j& 0& 0& 6& 2& 400\end{array}$$

Da la solución primal, la dual, reconstruye los recursos disponibles y comprueba la dualidad fuerte.

Ver solución

Solución primal: $x_1=8$, $x_2=12$, $s_1=s_2=0$ (no básicas), $z^{\ast }=400$.

Solución dual: los $z_j-c_j$ de las columnas de holgura:

$$y_1^{\ast }=6,y_2^{\ast }=2$$

Reconstruir $\mathbf{b}$. Las columnas de holgura de la tabla óptima contienen ${\mathbf{B}}^{-1}$, y las variables básicas cumplen ${\mathbf{x}}_B={\mathbf{B}}^{-1}\mathbf{b}$. Con las filas en el orden en que aparecen en la base, $(x_2,x_1)$:

$$\left(\begin{array}{cc}0,4& -0,2\\ -0,1& 0,3\end{array}\right)\left(\begin{array}{c}{b}_1\\ b_2\end{array}\right)=\left(\begin{array}{c}12\\ 8\end{array}\right)$$$$\{\begin{array}{l}0,4b_1-0,2b_2=12\\ -0,1b_1+0,3b_2=8\end{array}⟺\{\begin{array}{l}2b_1-b_2=60\\ -b_1+3b_2=80\end{array}$$

De la primera, $b_2=2b_1-60$. Sustituyendo en la segunda:

$$-b_1+6b_1-180=80⟹5b_1=260⟹b_1=52,b_2=44$$

Dualidad fuerte.

$$w^{\ast }=b_1{y}_1^{\ast }+b_2{y}_2^{\ast }=52(6)+44(2)=312+88=400=z^{\ast }✓$$

Interpretación. El recurso 1 vale 6 € por unidad y el 2 vale 2 €. Los dos están agotados —sus holguras son cero—, y ampliar el primero rinde el triple que ampliar el segundo.

Detalle a retener. El valor óptimo $z^{\ast }=w^{\ast }$ se lee directamente en la esquina de la tabla: la dualidad fuerte lo garantiza sin necesidad de reconstruir nada. La reconstrucción de $\mathbf{b}$ solo hace falta si se quiere recuperar el problema original, y se apoya en que las columnas de holgura guardan ${\mathbf{B}}^{-1}$.

Ejercicio 3 · Holgura complementaria para resolver

medio

Un primal de máximo tiene solución óptima $x_1^{\ast }=0$, $x_2^{\ast }=6$, $x_3^{\ast }=4$ para

$$\max z=4x_1+6x_2+5x_3$$$$\text{s.a.}{x}_1+2x_2+x_3\le 16,2x_1+x_2+3x_3\le 18,x_j\ge 0$$

Encuentra los precios sombra sin resolver el dual por símplex.

Ver solución

Paso 1. Comprobar qué restricciones saturan.

$$\text{R1: }0+12+4=16=16\text{satura}$$$$\text{R2: }0+6+12=18=18\text{satura}$$

Las dos se agotan, así que la holgura complementaria no obliga a que ningún $y_i$ sea cero: los dos pueden ser positivos.

Paso 2. Usar la otra mitad de la holgura complementaria. Los productos que sí se fabrican tienen su restricción dual con igualdad. Aquí $x_2>0$ y $x_3>0$:

$$\text{(de }{x}_2):2y_1+y_2=6$$$$\text{(de }{x}_3):y_1+3y_2=5$$

Paso 3. Resolver el sistema. De la primera, $y_2=6-2y_1$. Sustituyendo:

$$y_1+18-6y_1=5⟹-5y_1=-13⟹y_1=2,6$$$$y_2=6-5,2=0,8$$

Paso 4. Comprobar la restricción dual del producto que NO se fabrica. Como $x_1^{\ast }=0$, su restricción dual debe cumplirse (no necesariamente con igualdad):

$$y_1+2y_2\ge 4?2,6+1,6=4,2\ge 4✓$$

Se cumple con holgura de 0,2. Coherente: el producto 1 no se fabrica porque los recursos que consume valen 4,2 € y su margen es solo 4 €.

Paso 5. Verificar la dualidad fuerte.

$$z^{\ast }=0+6(6)+5(4)=36+20=56$$$$w^{\ast }=16(2,6)+18(0,8)=41,6+14,4=56✓$$

Precios sombra: $y_1^{\ast }=2,6$ €/unidad del recurso 1, $y_2^{\ast }=0,8$ €/unidad del recurso 2.

Lo que se ha ahorrado. Conociendo qué variables primales son positivas, la holgura complementaria convierte el dual en un sistema lineal pequeño. Es la forma habitual de obtener precios sombra a mano cuando ya se conoce la solución primal.

Ejercicio 4 · Decidir con precios sombra

avanzado

Una fábrica de conservas resuelve su plan mensual y obtiene:

$$z^{\ast }=18400\text{ €},y_{\text{materia prima}}^{\ast }=3,20\text{ €/kg},y_{\text{horas}}^{\ast }=0,y_{\text{envases}}^{\ast }=1,50\text{ €/unidad}$$

Responde, justificando cada decisión con los teoremas:

1. Un proveedor ofrece 2000 kg extra de materia prima a 2,80 €/kg. ¿Interesa?
2. El jefe de planta pide autorización para 100 horas extra a 14 €/hora. ¿Interesa?
3. Un cliente propone una conserva nueva que consumiría 0,8 kg de materia prima, 0,5 horas y 1 envase por unidad, con precio de venta 6 € y coste variable adicional de 1 €. ¿Interesa fabricarla?
4. ¿Qué recursos están agotados y cuáles sobran?

Ver solución

4 (primero, porque explica lo demás). Por holgura complementaria:

• Materia prima: $y>0⟹$ agotada.
• Horas: $y=0⟹$ sobran horas. La planta tiene capacidad ociosa.
• Envases: $y>0⟹$ agotados.

1. Materia prima extra. Cada kg adicional aporta 3,20 € de beneficio y cuesta 2,80 €: gana 0,40 € por kg.

$$\text{Ganancia estimada}=2000\times (3,20-2,80)=800\text{ €}$$

Interesa, con dos reservas importantes:

• El precio sombra vale en el margen. Con 2000 kg más, es probable que otro recurso (los envases) se convierta en el cuello de botella y el precio sombra de la materia prima caiga a cero antes de agotar los 2000 kg. La ganancia real será menor o igual que 800 €.
• Hasta cuántos kg sigue valiendo 3,20 € lo dice el rango de validez del análisis de sensibilidad (tema 19). Sin ese dato, la respuesta prudente es «interesa, pero comprobando hasta qué cantidad».

2. Horas extra. El precio sombra de las horas es cero: ya sobran. Una hora más aporta 0 € de beneficio y costaría 14 €.

$$\text{Peˊrdida}=100\times (0-14)=-1400\text{ €}$$

No interesa en absoluto. Es el error clásico de gestión que la dualidad evita: ampliar un recurso que no es el cuello de botella. Da igual lo barato que sea.

3. Producto nuevo. Margen unitario: $6-1=5$ €.

Valor imputado de los recursos que consumiría:

$$0,8(3,20)+0,5(0)+1(1,50)=2,56+0+1,50=4,06\text{ €}$$

Nótese que las horas no cuentan: consumir tiempo de una planta con capacidad ociosa no tiene coste de oportunidad.

Como $5>4,06$, el margen supera el valor de lo que desplaza: interesa fabricarla, con una ganancia de 0,94 € por unidad respecto al plan actual.

En términos duales: su restricción dual, $0,8y_1+0,5y_2+y_3\ge 5$, se incumple ($4,06<5$). Una restricción dual incumplida es exactamente la señal de que el plan actual ya no es óptimo y que ese producto debe entrar en la base.

Cuánto se puede fabricar ya no lo dice la dualidad: hay que reoptimizar añadiendo la columna nueva al problema. Pero la dualidad ha respondido lo primero y más importante —si merece la pena mirarlo siquiera— con tres multiplicaciones.

7. Qué desbloquea

Necesitas antes:

• El algoritmo símplex: conceptos, teoremas fundamentales y funcionamiento — tema 16
• Tipología de soluciones, degeneración y método de las dos fases — tema 17

Te abre la puerta a:

• Análisis de sensibilidad y casos de logística — tema 19

8. Recursos externos

• OCW UPV/EHU — Investigación Operativa. Programación Lineal. Dualidad con interpretación económica y símplex dual; es el desarrollo más ajustado a 21.411.
• OCW Unizar — Modelos de Investigación Operativa. Incluye scripts para construir problemas duales, útiles para comprobar la formulación antes de resolver.
• OCW UC3M — Investigación Operativa. Dualidad e interpretación económica, además de flujo en redes como aplicación.
• LINDO. Su informe de solución da directamente los dual prices: comparar con los precios sombra calculados a mano es la comprobación más rápida.