Chapter 4.12, Problem 4P

Explanation of Solution

Solving the LP using Big M method:

Given,

${\text{minz=3x}}_{\text{1}}$

Subject to,

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

Introduce slack variables S₁, S₂ of cost coefficients zero each, surplus variable S₃ and artificial variable A₁ of cost coefficient Big M

After introducing slack variables, the LP problem becomes,

$\text{Maxz=-3+0}{\text{.x}}_{\text{2}}\text{+0}{\text{.S}}_{\text{1}}{\text{-MA}}_{\text{1}}{\text{-MA}}_{\text{2}}$

Subject to

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

Iteration 1:

		$c_j$	-3	0	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}\\ S_1\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$	6	2	1	-1	1	0	$\frac{6}{2}=3$
$A_2$	$-M$	4	(3)	2	0	0	1	$\frac{4}{3}=\frac{4}{3}\to$
z=0		$z_j$	-5M	-3M	M	-M	-M
		$c_j-z_j$	$5M-3\uparrow$	3M	-M	0	0

$\begin{array}{l}{\text{Entering=x}}_{\text{1}}{\text{, Departin=A}}_{\text{2}}\text{, Key Element=3}\hfill \\ \begin{array}{l}{\text{R}}_{\text{2}}\left(\text{new}\right){\text{=R}}_{\text{2}}\left(\text{old}\right){\text{÷3=R}}_{\text{2}}\left(\text{old}\right)\end{array}\hfill \end{array}$