Chapter 4.12, Problem 5P

Explanation of Solution

Solving the LP using Big M method:

Given,

Minimize ${\text{z=x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+0x}}_{\text{3}}$

Subject to,

$\begin{array}{l}{\text{2x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+x}}_{\text{3}}\text{=4}\\ {\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+2x}}_{\text{3}}\text{=2}\end{array}$

First the user has to rewrite the problem for maximization as follows,

Maximize,

${\text{z=-x}}_{\text{1}}{\text{-x}}_{\text{2}}{\text{+0x}}_{\text{3}}{\text{-MA}}_{\text{1}}{\text{-MA}}_{\text{2}}$

Construct the simplex tabular as follows:

		$C_j$	-1	-1	0	-M	-M
$\begin{array}{l}\\ B\end{array}$	$\begin{array}{l}\\ C_b\end{array}$	$\begin{array}{l}\\ x_b\end{array}$	$\begin{array}{l}\\ x_1\end{array}$	$\begin{array}{l}\\ x_2\end{array}$	$\begin{array}{l}\\ x_3\end{array}$	$\begin{array}{l}\\ A_1\end{array}$	$\begin{array}{l}\\ A_2\end{array}$	Min Ratio $\frac{x_b}{x_3}$
$A_1$	$-M$	4	2	1	1	1	0	$\frac{4}{1}=4$
$A_2$	$-M$	2	1	1	2	0	1	$\frac{2}{2}=1$
z=0		$z_j$	-3M	-2M	-3M	-M	-M
		$c_j-z_j$	$3M-1$	2M-1	3M	0	0

The current solution is:

${\text{x}}_{\text{1}}{\text{=0=x}}_{\text{2}}{\text{=x}}_{\text{3}}{\text{-x}}_{\text{4}}{\text{,s}}_{\text{1}}{\text{=60,s}}_{\text{2}}\text{=150,z=0}$

Here, the entering variable is x₃; this is because the smallest z₃ is -3M.

To find the entering variable, locate the b_i’s that have corresponding positive elements in the entering variables column and from the following ratios