1
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you very much! This help's me a lot to understand the concept. Although i'm wondering if there is a way of solving the dual problem without using the primal problem solution? $\endgroup$ – nobody Apr 18 '16 at 4:00
  • $\begingroup$ @nobody The dual problem can be only be solved by using an algorithm like the simplex algorithm, if you don´t want to use the primal problem. But solving the primal problem by drawing was a good idea. An easier way is not available. $\endgroup$ – callculus Apr 18 '16 at 4:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.