Solve dual of linear program without simplex

Question

I have a linear program and need to determine and solve the dual program. The primal program is

$\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}$

So by trying to follow this (very good!) post i got the dual problem as

$\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}$

The solution is $y^*:=(0;4;2;0)$, which yields $g(y^*) = 36$. That's exactly the result i would expect, since it's the same result i get by solving the primal program (by drawing).

Since i can't draw the dual program i did some research and got to know that one might use the simplex-algorithm to solve it. But that looks like a little bit to much.. maybe there is some more elegant/basic way to get to the result?

Answer 1

The solution of the primal is $x_{opt}^{T}=(4,3)$.

From the complementary slackness theorem we know:

$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$ are the slack variables of the primal problem.

$z_j$ are the slack variabales of the dual problem.

First constraint

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

Thus $y_1=0$

Fourth constraint

$x_2 \leq 5$

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

Thus $y_4=0$

Both $x_i$ are greater than $0$. Thus $z_1=z_2=0$. We can take the first and second constraints and transform them into equations:

$-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$

Now the solution is obvious.