2
$\begingroup$

I have been looking for an easy answer for this, but I wasnt able to find a strong answer. I will do it with an example:

Given this Primal Problem:

Max 14A + 7B

2A + 5B <= 18

5A + 2B <= 24

A, B >= 0

The solutions to the the primal problem are: A = 4, B= 2, Z = 70

The Dual problem should look similar to this :

Min 18y1 + 24y2

-2y1 -5y2 + h1 = -14
-5y1 -2y2 + h2 = -7

y1, y2, h1, h2 >= 0

I'm able to find the solutions for the dual problem alone, but how can I find it's optimal solution faster using the primal solution ?

$\endgroup$
  • $\begingroup$ Maybe you have a typo at the second constraint.. The optimal solution is $A^*=9,B^*=0,Z^*=126$. The second constraint is redudant. $\endgroup$ – callculus Jun 8 '15 at 5:02
  • $\begingroup$ Thanks, there is actually a typo, I will edit it $\endgroup$ – Ediolot Jun 8 '15 at 6:52
  • $\begingroup$ I´ve made an edit. The RHS of the dual problem was not right. $\endgroup$ – callculus Jun 8 '15 at 10:04
3
$\begingroup$

I write the primal problem with slack variables:

$Max \ 14A + 7B$

$2A + 5B +s_1= 18$

$5A + 2B +s_2 = 24$

$ A, B \geq 0$

If you insert the optimal values for A and B you will see, that $s_1=s_2=0$

The following equation must hold:

$c^T\cdot x^*=y^{*T}\cdot b$

$\begin{pmatrix} 14 & 7 \end{pmatrix}\cdot \begin{pmatrix} 4 \\ 2 \end{pmatrix}=\begin{pmatrix} y_1 & y_2 \end{pmatrix}\cdot \begin{pmatrix} 18 \\ 24 \end{pmatrix}$

This simplifies to $70=18y_1+24y_2 \quad \color{blue}{(1)}$

This is not very surprising. The optimal value of the dual problem has to be equal to the optimal value of the primal problem.

The next two condition lead you to the solution of the dual:

  1. $x_j\cdot h_j=0 \ \ \forall \ j \in 1,2$

  2. $s_i \cdot y_i=0 \ \ \forall \ i \in 1,2 $ (Not necessary here.)

Since $x_1$ and $x_2$ are not equal to zero, $h_1$ and $h_2$ have to be zero.

This gives the equation (first constraint):

$-2y_1-5y_2=-14$

Multiplying both sides by (-1)

$2y_1+5y_2=14 \quad \color{blue}{(2)}$

With (1) and (2) you have a small equation system. It can be solved.

$\endgroup$

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.