Chapter 4.12, Problem 2P

Explanation of Solution

Solving the LP using Big M method:

Given,

$\min z=2x_1+3x_2$

Subject to,

$\begin{array}{l}2x_1+x_2\ge 4\\ x_1-x_2\ge -1\\ x_1,x_2\ge 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{minz=2x}}_{\text{1}}{\text{+3x}}_{\text{2}}\text{+0}{\text{.S}}_{\text{1}}\text{+0}{\text{.S}}_{\text{2}}\text{+M}{\text{.A}}_{\text{1}}$

Subject to

$\begin{array}{l}2x_1+x_2-S_1+A_1=4\\ -x_1+x_2+S_2=1\\ x_1,x_2,S_1,S_2,A_1\ge 0\end{array}$

Iteration 1:

		$c_j$	-3	1	0	0	-M
B	CB	XB	$\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}$	Min Ratio
A1	M	4	2	1	-1	0	1	$\frac{X_B}{X_1}$
S1	0	1	-1	1	0	1	0	$\frac{4}{2}=2$
Z=0		$Z_j$	2M	M	-M	0	M
		$C_j-Z_j$	-2M+2	-M+3	M	0	0

Negative minimum ${\text{C}}_{\text{j}}{\text{-Z}}_{\text{j}}$ is -2M+2 and column index is 1