Answer to Question #173501 in Linear Algebra for ANJU JAYACHANDRAN

Question

6(b) Write the dual of the following LPP after reducing it to canonical form. (4) 

 Min 3 1 4 2 3 3 Z = x + x + x

 Subject to 

 2x1 + 4x2 =12

 11 5x1 + 3x3 ≥

 6x1 + x2 ≥ 8

 x1

, x2

, x3 ≥ 0

Answer 1

Solution.

$z=3x_1+4x_2+3x_3 - min, \newline 2x_1+4x_2=12,\newline 5x_1+3x_3>=11, \newline 6x_1+x_2>=8, \newline x_1,x_2,x_3>=0.$

Reduce it to canonical form:

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

Introduce new variables $x_4, x_5,x_6:$

$2x_1+4x_2+x_6=12,\newline -5x_1-3x_3+x_4=-11, \newline -6x_1-x_2+x_5=-8. \newline$

then $z = Mx_6=\newline =M(12-2x_1-4x_2)=\newline =-2Mx_1-4Mx_2+12M - min$

Introduce new variable x_0:

$x_0=-2x_1-4x_2.$

We will have:

$x_0=12-2x_1-4x_2,$

$x_4=-11+5x_1+3x_3,\newline x_5=-8+6x_1+x_2,\newline x_6=12-2x_1-4x_2.$

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

$x_1=\frac{11}{5}-\frac{3}{5}x_3+\frac{1}{5}x_4.$

From here

$x_0=\frac{38}{5}-4x_2+\frac{6}{5}x_3-\frac{2}{5}x_4,$

$x_5=\frac{26}{5}+x_2-\frac{18}{5}x_3+\frac{6}{5}x_4,\newline x_6=\frac{38}{5}-4x_2+\frac{6}{5}x_3-\frac{2}{5}x_4.$

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

$x_2=\frac{19}{10}+\frac{3}{10}x_3-\frac{1}{10}x_4-\frac{1}{4}x_6, \newline x_0=0+x_6, \newline x_1=\frac{11}{5}-\frac{3}{5}x_3+\frac{1}{5}x_4,\newline x_5=\frac{71}{10}-\frac{33}{10}x_3+\frac{11}{10}x_4-\frac{1}{4}x_6.$

The expression for $x_0$

has positive elements, the plan is optimal.

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

$x_0=\frac{71}{5}+\frac{12}{5}x_3+\frac{1}{5}x_4,$

$x_1=\frac{11}{5}-\frac{3}{5}x_3+\frac{1}{5}x_4,$

$x_2=\frac{19}{10}+\frac{3}{10}x_3-\frac{1}{10}x_4,\newline x_5=\frac{71}{10}-\frac{33}{10}x_3+\frac{11}{10}x_4.$

Optimal plan:

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

So, min $z(x)=14\frac{1}{5}.$

Answer. min $z(x)=14\frac{1}{5}.$