[Math] Maximization with the Dual using the Simplex Method.

duality-theoremsoptimizationsimplex

I have an exam in a few hours. I need to understand the solution to the following question

Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function.

The constraints are

$4x_1 + 3x_2 ≤ 600;$

$x_1 + x_2 ≤ 160;$

$3x_1 + 7 x_2 ≤ 840;$

$x_1,x_2≥0.$

Also the answer should be in the "Dual". If its possible please do it in the Algebraic method. If not I would just like the solution using the tableau method and how do you arrive to the solution.(PS: Any help would be great. )

Best Answer

First of all, to solve this with the simplex method (tableau method) the inequalities of the contraints should be equalities. So you have to use slack variables.

$$4x_1+3x_2 \leq 600$$ $$x_1+x_2 \leq 160$$ $$3x_1+7x_2 \leq 840$$ $$x_1,x_2 \geq 0$$

$$\Downarrow$$

$$4x_1+3x_2 +x_3 = 600$$ $$x_1+x_2 +x_4 =160$$ $$3x_1+7x_2 +x_5= 840$$ $$x_1,x_2,x_3, x_4, x_5 \geq 0$$

Then can you continue by creating the tableau?

As regards the Algebraic method:

Draw the $x_1$-axis and the $x_2$-axis. Then from the first contraint you get:

$4x_1+3x_2 \leq 600 : \text{ when } x_1=0 \Rightarrow x_2=200 \text{ and when } x_2=0 \Rightarrow x_1=150$. So you get the line as below, and since it is $\leq 600$ the feasible region is below this line. enter image description here Can you do this for the other contraints and find the solution? You should also keep in mind that $x_1, x_2 \geq 0$

Find the optimal solution by the dual simplex algorithm

Add the artificial constraint $x_1 + x_3 \le M$ to the problem.
Write the problem in canonical form.
Add a slack variable to each inequality.
Write a simplex tableau for the problem. \begin{equation*} \begin{array}{lrrrl} \max & z = 2 x_1 & - x_2 & + x_3 & \\ \text{s.t.} & - 2 x_1 & - 3 x_2 & + 5 x_3 & \le - 4 \\ & x_1 & - 9 x_2 & + x_3 & \le - 3 \\ & 4 x_1 & + 6 x_2 & + 3 x_3 & \le 8 \\ & x_1 & & + x_3 & \le M \end{array} \\ x_1, x_2, x_3 \ge 0 \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & -2 & -3 & -5 & 1 & 0 & 0 & 0 & -4 \\ x_5 & 1 & -9 & 1 & 0 & 1 & 0 & 0 & -3 \\ x_6 & 4 & 6 & 3 & 0 & 0 & 1 & 0 & 8 \\ x_7 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \end{array} \end{equation*} Perform a pivot operation using $y_{7?}$ as a pivot to make all entries in the last row positive. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & \color{red}{1} & 0 & \color{red}{1} & 0 & 0 & 0 & 1 & M \\ \hline & \color{red}{-2} & 1 & \color{red}{-1} & 0 & 0 & 0 & 0 & 0 \\ \text{ratio} & \color{red}{2/1=2} & & \color{red}{1/1=1} & & & & & \end{array} \end{equation*} Here, we should choose the maximum ratio. Therefore, we choose $y_{71}$ as a pivot element in the initial tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} x_7 & 1^* & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & -2 & 1 & -1 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \end{equation*} We apply the dual simplex algorithm to the following tableau. \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & -3 & 7 & 1 & 0 & 0 & 2 & 2M -4 \\ x_5 & 0 & -9 & 0 & 0 & 1 & 0 & -1 & -M -3 \\ x_6 & 0 & 6 & -1 & 0 & 0 & 1 & -4^* & -4M +8 \\ x_1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & M \\ \hline & 0 & 1 & 1 & 0 & 0 & 0 & 2 & 2M \\ \text{ratio} & & & 1 & & & & 1/2 & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_5 & 0 & -21/2^* & 1/4 & 0 & 1 & -1/4 & 0 & -5 \\ x_7 & 0 & -3/2 & 1/4 & 0 & 0 & -1/4 & 1 & M -2 \\ x_1 & 1 & 3/2 & 3/4 & 0 & 0 & 1/4 & 0 & 2 \\ \hline & 0 & 4 & 1/2 & 0 & 0 & 1/2 & 0 & 4 \\ \text{ratio} & & 8/21 & & & & 2 & & \end{array} \end{equation*} \begin{equation*} \begin{array}{rrrrrrrr|l} & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 & \\ \hline x_4 & 0 & 0 & 13/2 & 1 & 0 & 1/2 & 0 & 0 \\ x_2 & 0 & 1 & -1/42 & 0 & -2/21 & 1/42 & 0 & 10/21 \\ x_7 & 0 & 0 & 3/14 & 0 & -1/7 & -3/14 & 1 & M-9/7 \\ x_1 & 1 & 0 & 11/14 & 0 & 1/7 & 3/14 & 0 & 9/7 \\ \hline & 0 & 0 & 25/42 & 0 & 8/21 & 17/42 & 0 & 44/21 \end{array} \end{equation*} Hence, the optimal solution of the primal problem is $(\dfrac97,\dfrac{10}{21},0)^T$, with an optimal value of $\dfrac{44}{21}$.

Find the optimal solution by GNU Octave

I post the Octave code for you to verify the optimal solution shown above.

octave:1> c = [2 -1 3]';
octave:2> A = [2 3 -5; -1 9 -1; 4 6 3];
octave:3> b = [4 3 8]';
octave:4> [x_max,z_max] = glpk(c,A,b,[0,0,0]',[],"UUL","CCC")
x_max =

   1.28571
   0.47619
   0.00000

z_max =  2.0952

[Math] Linear Program without simplex method

Hint: The dual program is

$$\begin{array}{}\texttt{min} \quad 200y_1+100y_2\\ \\ 3y_1+y_2\geq 3 \\ 4y_1+3y_2\geq 6 \\ 2y_1+2y_2\geq 2 \\ \\ y_1,y_2 \geq 0\end{array}$$

This program can be solved graphically. See here how it works.

Finally you apply the complementary slackness theorem to obtain the solution of the primal problem:

$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m$

$s_i^* \text{ are the optimal values of the slack variables of the primal problem.}$

$z_j^* \text{ are the optimal values of the slack variabales of the dual problem.}$

Best Answer

Related Solutions

[Math] How to solve this operation research problem using dual simplex method

Find the optimal solution by the dual simplex algorithm

Find the optimal solution by GNU Octave

[Math] Linear Program without simplex method

Related Question