Chapter 6.11, Problem 1P

Explanation of Solution

Given LP:

$\text{max z = }-{\text{2x}}_{\text{1}}-{\text{x}}_{\text{3}}$

$\begin{array}{c}\text{s}\text{.t}{\text{. x}}_{\text{1}}{\text{+x}}_{\text{2}}-{\text{x}}_{\text{3}}\ge \text{5}\\ {\text{x}}_{\text{1}}-2{\text{x}}_{\text{2}}{\text{+4x}}_{\text{3}}\ge 8\\ {\text{x}}_{\text{1}}{\text{, x}}_{\text{2}}{\text{, x}}_{\text{3}}\ge \text{0}\end{array}$

Simplex method to solve given LP:

The characteristic equations are,

$\begin{array}{l}{\text{z + 2x}}_{\text{1}}{\text{+ x}}_{\text{3}}\text{= 0}\hfill \\ -{\text{x}}_{\text{1}}-{\text{ x}}_{\text{2}}{\text{+ x}}_{\text{3}}{\text{+ e}}_{\text{1}}\text{= }-\text{5}\hfill \\ -{\text{x}}_{\text{1}}{\text{+ 2x}}_{\text{2}}-{\text{4x}}_{\text{3}}{\text{+ e}}_{\text{2}}\text{= }-\text{8}\hfill \end{array}$

After applying dual simplex,

z	$x_1$	$x_2$	$x_3$	$e_1$	$e_2$	RHS
1	2	0	1	0	0	0
0	-1	-1	1	1	0	-5
0	-1	2	-4	0	1	-8
Ratio	2		$\frac{1}{}$