Question

Solve the following LP problems using the Simplex Method
maximize $P=70x_1+50x_2$
subject to $4x_1+3x_2\le 240$
$2x_1+x_2\le 100$
$x_1,x_2\ge 0$

Answer 1

Maximise $P={70x}_1+50x_2$

Subject to${4x}_1+{3x}_2\le 240$

${2x}_1+x_2\ge 0$, $x_1,x_2\ge 0$

The problem is converted to canonical form by adding slack surplus and artificial variables as appropriate.

1.As the constant -1 is of type $(\le )$ we should add slack variable$s_1$

2.As the constant -2 is of type $(\le )$ we should add slack variable$s_2$

After introducing slack variables

Max $z={70x}_{1+}{50x}_2+{0S}_1+{0S}_2$

Subject to ${4x}_1+{3x}_2+S_1=240$

${2x}_1+x_2+S_2=100$

$x_1,x_2{,S}_1{,S}_2\ge 0$

Interation 1		$c_j$	70	50	0	0
B	$c_B$	$c_B$	$x_1$	$x_2$	$s_1$	$s_2$	Min Ratio $X_B/x_1$
$s_1$	0	240	4	3	1	0	$\frac{240}{4}=60$
$s_2$	0	100	(2)	1	0	1	$\frac{100}{2}=50$
z=0		$z_j$	0	0	0	0
		$c_j-z_j$	$70\uparrow$	50	0	0

Positive maximum $c_j-z_j$ is 70 and its column index is 1. So the entering variable is $x_1$

Minimum ratio is 50 and its row index is 2

So, the leaving basis variable is $s_2$

$\therefore$ The pivot element is 2

Entering =$x_1$, Departing=$s_2,$ Key Element=2

$R_2$(new)=$R_2$(old)/2

$R_1$(new)=$R_1\left(old\right)-4R_2\left(new\right)$

Interation-2		$c_j$	70	50	0	0
B	$c_B$	$x_B$	$x_1$	$x_2$	$s_1$	$s_2$	Min Ratio ${\alpha }_B/x_2$
$s_1$	0	40	0	(1)	1	-2	$\frac{40}{1}=40\to$
$x_1$	70	50	1	$\frac{1}{2}$	0	$\frac{1}{2}$	$\frac{50}{1/2}=100$
$z=3500$		$z_j$	70	35	0	35
		$c_j$	0	$15\uparrow$	0	-35

Positive maximum $c_j-z_j$ is 15 and its coloumn index is 2

So entering variable is $x_2$

Minimum ratio is 40 and its row index is 1.So leaving bases variable is $s_1$

$\therefore$ The pivot element is 1

Entering =$x_2$, Department =$s_1$, key element=1

$R_1$(new)=$R_1$(old)

$R_2\left(new\right)=R_2\left(old\right)-\frac{1}{2}{R}_1\left(new\right)$

Interation-3		$c_j$	70	50	0	0
B	$c_B$	$x_B$	$x_1$	$x_2$	$s_1$	$s_2$
$x_2$	50	40	0	1	1	-2
$x_1$	70	30	1	0	$\frac{-1}{2}$	$3/2$
$z=4100$		$z_j$	70	50	15	5
		$c_j-z_j$	0	0	-15	-5

Since all$c_j-z_j\le 0$

Hence optional solution is arrived with value of variables

as $x_1=30$,$x_2=40$

Max $z=4100$