La dualidad es un concepto fundamental en la programación lineal que establece una relación muy interesante entre dos problemas asociados: el problema primal y el problema dual. Esta relación no solo es teóricamente fascinante sino también muy útil desde el punto de vista práctico. Vamos a desglosarlo:

Problema Primal

Consideremos un problema de programación lineal típico, el cual llamamos el problema "primal". Este puede ser de maximización o minimización. Por ejemplo, un problema de maximización se ve así:

\begin{align*}
\text{Maximizar: } z = \mathbf{c}^T \mathbf{x} \\
\text{sujeto a: } \mathbf{A} \mathbf{x} \leq \mathbf{b} \\
\mathbf{x} \geq \mathbf{0}
\end{align*}

donde:

• $\mathbf{c}$ es el vector de variables de decisión.
• $\mathbf{x}$ es el vector de variables de decisión.
• $\mathbf{A}$ es la matriz de coeficientes de las restricciones.
• $\mathbf{b}$ es el vector de términos constantes del lado derecho de las restricciones.

Problema Dual

Asociado a cada problema primal, hay un problema dual correspondiente. Si el primal es un problema de maximización, entonces el dual será de minimización, y viceversa. La formulación del problema dual depende de la estructura del problema primal. Para el problema primal de maximización mencionado, el dual sería:

\begin{align*}
\text{Minimizar: } w = \mathbf{b}^T \mathbf{y} \\
\text{sujeto a: } \mathbf{A}^T \mathbf{y} \geq \mathbf{c} \\
\mathbf{y} \geq \mathbf{0}
\end{align*}

donde $\mathbf{y}$ es el vector de variables duales.

Interpretación Económica

Las variables del problema dual pueden interpretarse como precios sombra o costos marginales asociados a los recursos en las restricciones del problema primal. Por ejemplo, en un problema de producción, $y_i$​ podría representar el costo por unidad adicional del recurso $i$.

Teorema de la Dualidad Fuerte

Si existe una solución óptima para el problema primal (o dual), entonces también existe una solución óptima para el dual (o primal), y los valores de las funciones objetivo en estas soluciones son iguales. Esto significa que resolver el problema primal o el dual lleva al mismo resultado óptimo en términos de valor de la función objetivo.

Implicaciones Prácticas

La dualidad proporciona un marco para la verificación de soluciones y análisis de sensibilidad. Saber cómo afectan los cambios en los parámetros de recursos (como en $b$) al valor óptimo puede ser crítico para la toma de decisiones.

Uso de la Dualidad en la Solución de Problemas

En la práctica, a veces puede ser más fácil resolver el problema dual que el primal, especialmente cuando el dual tiene una estructura más sencilla o cuando las técnicas de solución disponibles son más adecuadas para el formato del dual.

---

Ejemplo

Problema Primal

Supongamos que una empresa produce dos tipos de productos: A y B. El producto A aporta un beneficio de $100 por unidad y el producto B aporta un beneficio de $150 por unidad. La empresa dispone de dos recursos principales para la producción: mano de obra y materiales. Cada unidad de A requiere 3 horas de mano de obra y 2 kg de materiales, mientras que cada unidad de B requiere 5 horas de mano de obra y 3 kg de materiales. La empresa dispone de 120 horas de mano de obra y 100 kg de materiales.

\begin{align*}
\text{Maximizar: } z = 100x + 150y \\
\text{sujeto a: } \\
3x + 5y \leq 120 \\
2x + 3y \leq 100 \\
x, y \geq 0
\end{align*}

Problema Dual

El problema dual asociado se enfoca en los recursos (mano de obra y materiales), considerando los precios sombra de estos recursos. Las variables duales $u$ y $v$ representarán el valor por hora de mano de obra y el valor por kilogramo de material, respectivamente.

\begin{align*}
\text{Minimizar: } w = 120u + 100v \\
\text{sujeto a: } \\
3u + 2v \geq 100 \\
5u + 3v \geq 150 \\
u, v \geq 0
\end{align*}

• $u$ (precio sombra de la mano de obra) indica cuánto aumentaría el beneficio total si se dispusiera de una hora adicional de mano de obra.
• $v$ (precio sombra de los materiales) muestra el incremento en el beneficio si se pudiera usar un kilogramo adicional de material.

Uso del Dual en la Planificación de Recursos:

Los valores de $u$ y $v$ ayudan a determinar si vale la pena invertir más en ciertos recursos. Si el precio sombra de un recurso es alto, puede justificarse una inversión adicional en ese recurso.

Teorema de Dualidad

El valor óptimo del primal (beneficio máximo que se puede obtener) es igual al valor óptimo del dual (costo mínimo de los recursos necesarios para lograr ese beneficio).

\begin{align*}
\text{Maximizar: } z = \mathbf{c}^T \mathbf{x} \\
\text{sujeto a: } \mathbf{A} \mathbf{x} \leq \mathbf{b} \\
\mathbf{x} \geq \mathbf{0}
\end{align*}

\begin{align*}
\text{Minimizar: } w = \mathbf{b}^T \mathbf{y} \\
\text{sujeto a: } \mathbf{A}^T \mathbf{y} \geq \mathbf{c} \\
\mathbf{y} \geq \mathbf{0}
\end{align*}

Relación de Debilidad

Supongamos que $x$ es una solución factible para el primal y $y$ es una solución factible para el dual. Comparando las restricciones y comparándolas entre ellas podemos observar que:

\mathbf{c}^T \mathbf{x} \leq \mathbf{y}^T \mathbf{A} \mathbf{x} \leq \mathbf{y}^T \mathbf{b}

Cuando $x$ y $y$ son soluciones óptimas para sus respectivos problemas, las desigualdades se convierten en igualdades:

\mathbf{c}^T \mathbf{x} = \mathbf{y}^T \mathbf{b}

Este resultado implica que los valores óptimos de las funciones objetivo del primal y del dual son iguales, lo cual valida la dualidad fuerte. Si uno de los problemas tiene una solución óptima, el otro también debe tenerla, y los valores óptimos deben ser iguales.

---

Problema de Examen: Optimización de la Producción

Una fábrica produce dos tipos de productos electrónicos: tabletas (T) y teléfonos (F). El proceso de fabricación de ambos productos requiere dos tipos de recursos: tiempo de ensamblaje y componentes electrónicos. Cada tableta que se produce requiere 2 horas de ensamblaje y 3 componentes electrónicos. Cada teléfono requiere 1 hora de ensamblaje y 2 componentes electrónicos. La fábrica dispone de un máximo de 800 horas de ensamblaje y 1000 componentes electrónicos por mes.

Los beneficios obtenidos por cada tableta y teléfono vendidos son $50 y $30, respectivamente.

Objetivo:

Maximizar el beneficio total de la fábrica.

Preguntas del Problema

1. Formulación del Modelo

• Formula el problema de programación lineal para maximizar el beneficio total.

\begin{align}
\text{Maximizar: } z = 50T + 30F \\
\text{sujeto a: } \\
\ 2·T + 1·F \leq 800 \text{[horas]} \\
\ 3·T + 2·F \leq 1000 \text{[componentes]} \\

\mathbf{T} \geq \mathbf{0} \\
\mathbf{F} \geq \mathbf{0} \\

\end{align}

2. Solución Utilizando el Método Simplex

Resuelve el problema utilizando el método simplex. Describe cada paso del proceso, incluyendo la tabla simplex inicial y las operaciones de fila necesarias para alcanzar la solución óptima.

\begin{align}
\text{Max: } z = 50T + 30F \\
 \\
\ 2·T + 1·F + h_s =  800  \\
\ 3·T + 2·F + c_s = 1000  \\
\end{align}

\begin{array}{c|cccc|c}
    &   T &   F & s_1 & s_2 & \text{RHS} \\
                                          \\
z   & -50 & -30 &   0 &   0 & 0            \\
s_1 &   2 &   1 &   1 &   0 & 800           \\
s_2 &   3 &   2 &   0 &   1 & 1000           \\
                                              \\
\end{array}