Chapter 4.12, Problem 6P

Explanation of Solution

Solving the LP using Big M method:

Given,

Minimize $\begin{array}{l}{\text{minz=x}}_{\text{1}}{\text{+x}}_{\text{2}}\\ {\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}\text{=2}\\ {\text{2x}}_{\text{1}}{\text{+2x}}_{\text{2}}\text{=4}\\ {\text{x}}_{\text{1}}{\text{,x}}_{\text{2}}\ge \text{0}\end{array}$

Subject to,

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

After introducing the artificial variables,

Maximize,

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

Subject to,

  $\begin{array}{l}{\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{+A}}_{\text{1}}\text{=2}\\ {\text{2x}}_{\text{1}}{\text{+2x}}_{\text{2}}{\text{+A}}_{\text{2}}\text{=4}\\ {\text{x}}_{\text{1}}{\text{,x}}_{\text{2}}{\text{,A}}_{\text{1}}{\text{,A}}_{\text{2}}\ge \text{0}\end{array}$

Construct the simplex tabular as follows:

		$C_j$	-1	-1	-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}\\ A_1\end{array}$	$\begin{array}{l}\\ A_2\end{array}$	Min Ratio $\frac{x_b}{x_1}$
$A_1$	$-M$	2	1	1	1	0	$\frac{2}{1}=2$
$A_2$	$-$