Chapter 4.12, Problem 3P

Explanation of Solution

Solving the LP using Big M method:

Given,

$\min z=3x_1+x_2$

Subject to,

$\begin{array}{l}{\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}\ge \text{3}\\ {\text{2x}}_{\text{1}}{\text{+x}}_{\text{2}}\le \text{4}\\ {\text{x}}_{\text{1}}{\text{+x}}_{\text{2}}\\ {\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=3x}}_{\text{1}}{\text{+x}}_{\text{2}}{\text{-MA}}_{\text{1}}{\text{-MA}}_{\text{2}}\text{+0}{\text{.S}}_{\text{1}}\text{+0}{\text{.S}}_{\text{2}}$

Subject to

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

Iteration 1:

		$c_j$	-3	1	0	0	-M	-M
$3\times 1+2=5$	$\begin{array}{l}\\ B.V\end{array}$	$\begin{array}{l}\\ b_j\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}\\ S_2\end{array}$	$\begin{array}{l}\\ A_1\end{array}$	$\begin{array}{l}\\ A_2\end{array}$	Min Ratio
$-M$	$A_1$	3	1	1	-1	0	1	0	3
0	$S_2$	4	2	1	0	1	0	0	2
-M	$A_2$	3	1	1	0	0	0	1	3
Zj			-2M	-2M	M	0	-M	-M
$C_j-Z_j$			3+2M	1+2M	-M	0	0	0

Iteration 2:

		$c_j$	3	1	0	0	-M	-M
$\begin{array}{l}\\ C_j-Z_j\end{array}$	$\begin{array}{l}\\ B\end{array}$