Question

3. Solve the following LPP by the two-phase simplex method. (10) 

 Max 1 2 3 Z = x + x − x

 Subject to 4x1 + x2 + x3 = 4

3 2 6 x1 + x2 − x4 =

 x1

, x2

, x3 ≥ 0

Answer 1

Solution.

May be the condition of the task next:

$z=x_1+x_2-x_3 - max, \newline 4x_1+x_2+x_3=4,\newline 3x_1+2x_2-x_3=6, \newline x_1,x_2,x_3>=0.$

Introduce new variables $x_4, x_5:$

$4x_1+x_2+x_3+x_4=4, \newline 3x_1+2x_2-x_3+x_5=6,$

then $z = -Mx_4-Mx_5=\newline =-M(4-4x_1-x_2-x_3)-M(6-3x_1-2x_2+x_3)=\newline =7Mx_1+Mx_2-10M - max$

Introduce new variable x_0:

$x_0=7x_1+3x_2.$

We will have:

$x_0=-10+7x_1+3x_2,$

$x_4=4-4x_1-x_2-x_3,\newline x_5=6-3x_1-2x_2+x_3.$

This plan is not optimal because there are positive elements in the expression for $x_0$ . Select a new variable $x_1,$ then

$x_1=1-\frac{1}{4}x_2-\frac{1}{4}x_3-\frac{1}{4}x_4.$

From here

$x_0=-3+\frac{5}{4}x_2-\frac{7}{4}x_3-\frac{7}{4}x_4,$

$x_5=3-\frac{5}{4}x_2+\frac{7}{4}x_3+\frac{3}{4}x_4.$

The expression for $x_0$ has positive elements, the plan is not optimal. The largest coefficient is near $x_2$ , then choose $x_2$ as a new variable.

$x_2=\frac{12}{5}+\frac{7}{5}x_3+\frac{3}{5}x_4-\frac{4}{5}x_5, \newline x_0=0-x_4-x_5, \newline x_1=\frac{2}{5}-\frac{3}{5}x_3-\frac{2}{5}x_4+\frac{1}{5}x_5.$

The expression for $x_0$

has not positive elements, the plan is optimal.

We will deduce variables $x_4, x_5$ from basis:

$x_0=\frac{14}{5}-\frac{1}{5}x_3,$

$x_1=\frac{2}{5}-\frac{3}{5}x_3,$

$x_2=\frac{12}{5}+\frac{7}{5}x_3.$

Optimal plan:

$x_1=\frac{2}{5}, x_2=2\frac{2}{5}, x_3=0.$

So, max $z(x)=2\frac{2}{5}.$

Answer. max $z(x)=2\frac{2}{5}.$