I am trying to minimize this linear program by combining the duality principle and the graphical method:

\begin{array}{ll} \min & 2x_1+3x_2+3x_3+6x_4+4x_5\\ \text{Subject to:} & 2x_1+x_2-2x_3+3x_4-2x_5=-1\\ &x_1+3x_2+x_3+2x_4+x_5=1\\ & x_1,x_2,x_3,x_4,x_5\ge0 \end{array}

I can't seem to find an example of how to approach this, can anyone show me how I would go about this?


1 Answer 1


The dual problem is:

objective function

$\text{max} \ -y_1+y_2$


$2y_1+y_2 \leq 2$

$y_1+3y_2 \leq 3$

$-2y_1+y_2 \leq 3$

$3y_1+2y_2 \leq 6$

$-2y_1+y_2 \leq 4$

$y_1,y_2$ are unrestricted.

You have to solve every constraint for $y_2$. Then you can draw the constraints in a $y_1-y_2$-coordinate system. If you consider the inequality-signs you will get a solution space.

Now you set the objective function equal to zero and solve the equation for $y_2$. After you have drawn it in the coordinate system you have to move it parallel till you just touch the solution space.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .