Chapter 6.7, Problem 2P

Explanation of Solution

a.

Duel of the LP:

Maximize, ${\text{z=-2x}}_{\text{1}}{\text{-x}}_{\text{2}}{\text{+x}}_{\text{3}}$

Subject to the constraints,

$\begin{array}{c}{\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+x}}_{\text{3}}\le \text{3}\\ {\text{x}}_{\text{2}}{\text{+3x}}_{\text{3}}\ge 2\\ x_1+x_3=0\end{array}$

And $x_1,x_2,x_3\ge 0$

In the above LP formulation, all $\ge$ constraints can be converted to $\le$ type by multiplying both sides by -1. Then the LP becomes,

Maximize, ${\text{z=-2x}}_{\text{1}}{\text{-x}}_{\text{2}}{\text{+x}}_{\text{3}}$

Subject to the constraints,

$\begin{array}{c}{\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+x}}_{\text{3}}\le \text{3}\end{array}$

Explanation of Solution

b.

Optimal solution of Dual of the LP:

Minimize, $z=3x_1-2x_2$

Subject to the constraints,

$x_1+x_3\ge -2$

In the above, $\text{b1=-2<0}$

The LP problem is converted to canonical form by adding surplus, slack, and artificial variables in appropriate places.

• The user should add slack variable ${\text{S}}_{\text{1}}$, as the constraint -1 is of type “$\le$”.
• The user should subtract the surplus variable ${\text{S}}_2$ and add artificial variable ${\text{A}}_{\text{1}}$, as the constraint -2 of type “$\ge$”.
• The user should add slack variable ${\text{S}}_3$, as the constraint -3 is of type “$\le$”.

After introducing slack, surplus, artificial variables

Minimize, ${\text{Z=3x}}_{\text{1}}{\text{-2x}}_{\text{2}}{\text{+0x}}_{\text{3}}{\text{'+0x}}_{\text{3}}{\text{''+0S}}_{\text{1}}{\text{+0S}}_{\text{2}}{\text{+0S}}_{\text{3}}{\text{+MA}}_{\text{1}}$

Subject to the constraints,

$\begin{array}{c}-x_1-x_3\text{'}+x_3\text{'}\text{'}+S_1=2\\ -x_1+x_2-S_2+A_1=1\\ x_1-3x_2+x_3\text{'}-x_3\text{'}\text{'}+S_3=1\end{array}$

And $x_1,x_2,x_3\text{'},x_3\text{'}\text{'},S_1,S_2,S_3,A_1\ge 0$

Iteration-1		$C_j$	3	-2	0	0	0	0	0	M	Min Ratio
B	$C_B$	$X_B$	$x_1$	$x_2$	$x_3\text{'}$	$x_3\text{'}\text{'}$	$S_1$	$S_2$	$S_3$	$A_1$	$\frac{{\text{X}}_{\text{B}}}{{\text{x}}_{\text{2}}}$
$S_1$	0	2	-1	0	-1	1	1	0	0	0	…
$A_1$	$M$	1	-1	(1)	0	0	0	-1	0	1	$\frac{1}{1}=1\to$
$S_3$	0	1	1	-3	1	-1	0	0	1	0	…
-M	$A_2$	1	0	1/2	0	-1/2	0	1		2
$\text{Z=M}$		$Z_j$	-M	$\text{M}$	0	0	0	-M	0	M
		$Z_j-C_j$	-M-3	$\text{M+2}\uparrow$	0	0	0	-M	0	0

Positive maximum $Z_j-C_j$ is $\text{M+2}$ and its column index is 2