Dualidad. ¿Es este el correcto Dual a este L.P. Primal?

Question

Dado un problema:

Encontrar el doble:

$$Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ \ \ \ \ x_1 \geq 0\\ \end{Bmatrix}$$

i) Introducir una variable de holgura ($+x_3$) en el 2º restricción

$$Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \quad \quad2x_1 -x_2 \quad \quad \quad \quad \ = 1\\ \quad \quad \quad \quad x_1 +3x_2 + x_3 \quad \quad =9\\ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad x_1 \geq 0\\ \end{Bmatrix}$$

iii) el Problema se convierte en un problema de minimización con $\geq$ restricciones

iv) se Multiplican las restricciones por $y_1,y_2$

$$Doble =\begin{Bmatrix} min \ \ \ \ y_1 + 9y_2 \\ s.t. \ \ \ \ 2y_1 + y_2 \geq5\\ \quad \quad \quad \quad \quad-y_2+3y_2 \geq -6\\ \quad \quad \quad y_2 \geq 0\\ \end{Bmatrix}$$

v) Cambio de signo de $(-)$ $(+)$en la segunda restricción

$$Doble =\begin{Bmatrix} min \ \ \ \ y_1 + 9y_2 \\ s.t. \ \ \ \ 2y_1 + y_2 \geq5\\ \quad \quad \quad \quad \quad y_2-3y_2 \leq 6\\ \quad \quad \quad y_2 \geq 0\\ \end{Bmatrix}$$

Es esto correcto o me estoy perdiendo algo?

Gracias

Answer 1

Tal vez vale la pena hablar a través de donde el doble. Esto tomará un tiempo, pero esperemos que el doble no parece tan misterioso cuando hayamos terminado.

Supongamos que queremos utilizar las restricciones del primal como una forma de encontrar un límite superior en el valor óptimo de la primaria. Si multiplicamos la primera restricción por $9$, la segunda restricción por $1$, y añadirlos juntos, llegamos $9(2x_1 - x_2) + 1(x_1 +3 x_2)$ para el lado izquierdo y $9(1) + 1(9)$ para la mano derecha. Desde la primera restricción es una igualdad y la segunda es una desigualdad, esto implica $$19x_1 - 6x_2 \leq 18.$$ Pero desde $x_1 \geq 0$, también es cierto que $5x_1 \leq 19x_1$, y por lo $$5x_1 - 6x_2 \leq 19x_1 - 6x_2 \leq 18.$$ Por lo tanto, $18$ es un-límite superior en el valor óptimo del problema primal.

Seguro que podemos hacer algo mejor que eso, sin embargo. En lugar de sólo una suposición $9$ $1$ como los multiplicadores, dejemos que sean variables. Por lo tanto estamos buscando multiplicadores $y_1$ $y_2$ a la fuerza $$5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9).$$

Now, in order for this pair of inequalities to hold, what has to be true about $y_1$ and $y_2$? Let's take the two inequalities one at a time.

---

The first inequality: $5x_1 - 6x_2 \leq y_1(2x_1-x_2) + y_2(x_1 + 3x_2)$

We have to track the coefficients of the $x_1$ and $x_2$ variables separately. First, we need the total $x_1$ coefficient on the right-hand side to be at least $5$. Getting exactly $5$ would be great, but since $x_1 \geq 0$, anything larger than $5$ would also satisfy the inequality for $x_1$. Mathematically speaking, this means that we need $2y_1 + y_2 \geq 5$.

On the other hand, to ensure the inequality for the $x_2$ variable we need the total $x_2$ coefficient on the right-hand side to be exactly $-6$. Since $x_2$ could be positive, we can't go lower than $-6$, and since $x_2$ could be negative, we can't go higher than $-6$ (as the negative value for $x_2$ would flip the direction of the inequality). So for the first inequality to work for the $x_2$ variable, we've got to have $-y_1 + 3y_2 = -6$.

---

The second inequality

: $y_1(2x_1-x_2) + y_2(x_1 + 3x_2) \leq y_1(1) + y_2(9)$

Here we have to track the $y_1$ and $y_2$ variables separately. The $y_1$ variables come from the first constraint, which is an equality constraint. It doesn't matter if $y_1$ is positive or negative, the equality constraint still holds. Thus $y_1$ is unrestricted in sign. However, the $y_2$ variable comes from the second constraint, which is a less-than-or-equal to constraint. If we were to multiply the second constraint by a negative number that would flip its direction and change it to a greater-than-or-equal constraint. To keep with our goal of upper-bounding the primal objective, we can't let that happen. So the $y_2$ variable can't be negative. Thus we must have $y_2 \geq 0$.

Finally, we want to make the right-hand side of the second inequality as small as possible, as we want the tightest upper-bound possible on the primal objective. So we want to minimize $y_1 + 9y_2$.

---

Putting all of these restrictions on $y_1$ and $y_2$ together we find that the problem of using the primal's constraints to find the best upper-bound on the optimal primal objective entails solving the following linear program:

$$\begin{align*} \text{Minimize }\:\:\:\:\: y_1 + 9y_2& \\ \text{subject to }\:\:\:\:\: 2y_1 + y_2& \geq 5 \\ -y_1 + 3y_2& = -6\\ y_2 & \geq 0. \end{align*}$$

Y eso es el doble.

---

Es probablemente vale la pena resumir las implicaciones de este argumento para todas las posibles formas del primal y dual. La siguiente tabla es tomada de la página. 214 Introducción a la investigacion de Operaciones, 8th edition, por Hillier y Lieberman. Se refieren a esto como el hijo de puta de método, donde SOB representa Sensible, Raro o Extraño, dependiendo de la probabilidad de que uno podría encontrar que la limitación particular o variable de la restricción en la maximización o minimización del problema.

             Primal Problem                           Dual Problem
             (or Dual Problem)                        (or Primal Problem)

             Maximization                             Minimization

Sensible     <= constraint            paired with     nonnegative variable
Odd          =  constraint            paired with     unconstrained variable
Bizarre      >= constraint            paired with     nonpositive variable

Sensible     nonnegative variable     paired with     >= constraint
Odd          unconstrained variable   paired with     = constraint
Bizarre      nonpositive variable     paired with     <= constraint