Obtain Dual Solution from Primal problem using Simplex

13.1k Views Asked by At

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 ?

1

There are 1 best solutions below

0
On BEST ANSWER

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.