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

duality-theoremsoperations researchsimplex

Maximize $$ z = 2x_1 -x_2 +x_3$$

Subject to constraints $$2x_1 + 3x_2 -5x_3 \ge 4$$
$$-x_1 +9x_2 -x_3 \ge 3$$
$$4x_1 +6x_2 +3x_3 \le 8$$
And $x_1, x_2, x_3 \ge 0$

I managed to solve this through simplex method(by 2 stage method) but I was asked solve it using dual simplex method, I found out that this cannot be solved by dual simplex since it doesn't meet the maximization optimality condition here which is the reduced costs in the z-row(or the values in the z-row in the initial table) must be always lesser than $0$ which is not the case here as coefficient of $x_2$ is 2 in the z-row.

Still our teacher says it can be solved by introducing another constraint which is $x_1 + x_3 \le M$ (where M is sufficiently large), now I am at a loss how to proceed further ?

I know the answer will be quiet huge and time taking but any type of help will be greatly appreciated.

Best Answer

Find the optimal solution by the dual simplex algorithm

  1. Add the artificial constraint $x_1 + x_3 \le M$ to the problem.
  2. Write the problem in canonical form.
  3. Add a slack variable to each inequality.
  4. 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
Related Question