Recuperación de la solución primaria óptima a partir de la solución dual

Question

Tengo problemas para encontrar la solución primaria óptima de un problema concreto a partir de su solución dual.

Primal:

$\texttt{Maximize} \ \ 10 x_1 + 24 x_2 + 20 x_3 + 20 x_4 + 25 x_5$

Sujeto a

$x_1 + x_2 + 2 x_3 + 3 x_4 + 5 x_5 \leq 19$

$2 x_1 + 4 x_2 + 3 x_3 + 2 x_4 + x_5 \leq 57$

$x_1, x_2, x_3, x_4, x_5 \geq 0$

Doble:

$\texttt{Minimize} \ \ 19 u_1 + 57 u_2$

Sujeto a

$u_1 + 2 u_2 \geq 10$

$u_1 + 4 u_2 \geq 24$

$2 u_1 + 3 u_2 \geq 20$

$3 u_1 + 2 u_2 \geq 20$

$5 u_1 + u_2 \geq 25$

$u_1, u_2 \geq 0$

Solución óptima del problema dual: (4,5).

Entonces, como todas las variables de holgura, excepto la segunda, no son cero, $x_1=x_3=x_4=x_5=0$ .

Sustituyendo esto tenemos: $x_2 \leq 19$ y $4 x_2 \leq 57$

Pero no consigo encontrar la respuesta al problema de maximización.

Answer 1

Debe cumplirse la siguiente condición:

$(A^T\cdot u^*-c)^T\cdot x^*=0$

Insertar los valores dados:

$\left[ \left( \begin{array}{} 1&2 \\ 1&4 \\ 2&3 \\ 3&2 \\ 5&1 \end{array} \right) \cdot \left( \begin{array}{} 4 \\ 5 \end{array} \right)-\left( \begin{array}{} 10 \\ 24 \\ 20 \\ 20 \\ 25 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0 $

$\left[ \left( \begin{array}{} 14 \\ 24 \\ 23 \\ 22 \\ 25 \end{array} \right) -\left( \begin{array}{} 10 \\ 24 \\ 20 \\ 20 \\ 25 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0 $

$\left[ \left( \begin{array}{} 4 \\ 0 \\ 3 \\ 2 \\0 \end{array} \right)\right]^T\cdot \left( \begin{array}{} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{array} \right)=0 $

Así, la ecuación es $4x_1+0x_2+3x_3+2x_4+0x_5=0$

Todo $x_i$ son mayores o iguales a cero. Entonces $x_1=x_3=x_4=0$ .

Y la condición $s_i\cdot u_i=0 \ \ \forall i \in \{1,2\}$ debe mantener. Ambos $u_i $ tienen un valor positivo. Así, $s_1=s_2=0$

$s_i$ son las variables de holgura del problema primario.

Las ecuaciones son:

$x_2+5x_5=19$

$4x_2+x_5=57$

Creo que puedes resolver este pequeño sistema de ecuaciones por tu cuenta.