Resolver el dual del programa lineal sin simplex

Question

Tengo un programa lineal y necesito determinar y resolver el programa dual. El programa primario es

$\begin{array}{lcl} \text{Maximize: }\\ f(x) := 6x_1+4x_2\\ \text{Subject to:}\\ -2x_1-4x_2 \leq -12\\ x_1+x_2 \leq 7\\ x_1 \leq 4\\ x_2 \leq 5\\ x_1 \geq 0; x_2\geq 0. \end{array}$

Así que al tratar de seguir este (¡muy bueno!) post Tengo el doble problema como

$\begin{array}{lcl} \text{Minimize: }\\ g(y) := -12y_1+7y_2+4y_3+5y_4\\ \text{Subject to:}\\ -2y_1+y_2+y_3 \geq 6\\ -4y_1+y_2+y_4 \geq 4\\ y_1 \geq 0; y_2\geq 0; y_3\geq 0; y_4\geq 0. \end{array}$

La solución es $y^*:=(0;4;2;0)$ , lo que da como resultado $g(y^*) = 36$ . Ese es exactamente el resultado que yo esperaría, ya que es el mismo que obtengo resolviendo el programa primal (por dibujo).

Como no puedo dibujar el programa dual he investigado un poco y he llegado a saber que se puede utilizar el algoritmo simplex para resolverlo. Pero eso parece un poco demasiado ¿quizás hay alguna forma más elegante/básica de llegar al resultado?

Answer 1

La solución del primal es $x_{opt}^{T}=(4,3)$ .

Por el teorema de la holgura complementaria sabemos:

$x_j\cdot z_j=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i\cdot s_i=0 \ \forall \ \ j=1,2, \ldots , m$

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

$z_j$ son las variabales de holgura del problema dual.

Primera restricción

$-2x_1-4x_2 +s_1= -12\Rightarrow -8-12+s_1=-12\Rightarrow s_1 >0$

Así, $y_1=0$

Cuarta restricción

$x_2 \leq 5$

$3+s_4=5 \Rightarrow s_4=2>0$

Así, $y_4=0$

Ambos $x_i$ son mayores que $0$ . Así, $z_1=z_2=0$ . Podemos tomar la primera y la segunda restricción y transformarlas en ecuaciones:

$-2y_1+y_2+y_3 = 6\\ -4y_1+y_2+y_4 = 4\\$

$0+y_2+y_3=6\\ 0+y_2+0=4$

Ahora la solución es obvia.