Maximize $z = 2x_1- x_2+3x_3$

Subject to $x_1-2x_2+x_3 ≥ 4 \\ 2x_1+x_3 ≤ 10 \\ X_1+x_2 + 3x_3 =20 \\ X_1, x_3 ≤ 0, x_2 \text {unrestricted }.$

Mumbai University > COMPS > Sem 4 > Applied Mathematics 4

Marks : 05

Year : MAY 2015

Since, $x_2$ is unrestricted, let $x_2=x_2^1-x_2”$

since objective is of maximization type, we convert all constraints to “≤” type.

Maximize $z=2x_1-(x_2’-x_2’’)+3x_3$

Constraints

$ i) x_1-2x_2+x_3 \geq 4 \\ \therefore -x_1+2x_2-x_3 \leq 4 \\ \therefore -x_1+2(x_2' -x_3")-x_3 \leq -4\\ ii) 2x_1+0x_2+x_3 \leq 10 \\ 2x_1+0(x_2'-x_2")+ x_3 \leq 10 \\ iii) x_1+x_2+3x_3=20$

It can be written as,

$x_1+x_2+3x_3 ≤ 20 \space\space \&\space\space x_1+x_2+3x_3 ≥ 20 \\ x_1+x_2+3x_3 ≤ 20 \space\space \& \space\space -x_1-x_2-3x_3 ≤ -20 \\ \therefore x_1+(x_2'-x_2")-3x_3\leq 20 \space\space\& \space\space \\ -x_1-(x_2'-x_2")-3x_3 \leq -20 $

So primal is

Maximize $z=2x_1-1x_2’+1x_2”+3x_3$

Constraints

$i) -1x_1+2x_2'-2x_2"-1x_3 \leq -4 \\ ii) 2x_1+0x_2'-0x_2"+1x_3 \leq 10 \\ iii) 1x_1+1x_2'-1x_2" +3x_3 \leq 20 \\ -1x_1-1x_2'+1x_2" -3x_3 \leq -20\\ iv) x_1,x_2',x_2", x_3 \geq 0$

the dual of above primal is

Minimize,

$w=-4y_1+10y_2+20y_3'-20y_3" \\ i.e \\ w=-4y_1+10y_2+20(y_3'-y_3")$

Constraints

$i) -1y_1+2y_2 + 1y_3' -1y_3" \geq 2 \\ i.e \\ -y_1+2y_2+(y_3'-y_3") \geq 2 \\ ii) 2y_1+0y_2+1y_3'-1y_3" \geq -1 \\ i.e -2y_1-1y_3'+1y_3" \leq 1\\ i.e. -2y_1-(y_3'-y_3") \leq 1\\ iii) -2y_1-0y_2-1y_3 + 1y_3" \geq 1\\ i.e. -2y_1-(y_3'-y_3") \geq 1\\ iv) -1y_1+1y_2 +3y_3'-3y_3" \geq 3\\ i.e. -y_1+y_2+3(y_3'-y_3") \geq 3 \\ v) y_1,y_2,y_3',y_3" \geq 0$

put $y_3”-y_3” =y_3$ where $y_3$ is unrestricted.

$\therefore $ the dual is

Minimize $w=-4y_1+10y_2+20y_3$

Constraints:

$ i) -y_1+2y_2+y_3 ≥ 2 \\ ii) -2y_1-y_3 ≤ 1 \\ iii)-2y_1-y_3 ≥ 1 \\ iv)-y_1+y_2+3y_3 ≥ 3\\ v) y_1,y_2 ≥ 0, y_3 \text { is unrestricted. }$

Combining (2) and (3) constraints, The dual is

Minimize $w=-4y_1+10y_2+20y_3$

constraints

$i)-y_1+2y_2+y_3 ≥ 2 \\ ii)-2y_1-y_3=1 \\ iii)-y_1+y_2+3y_3 ≥ 3 \\ iv)y_1,y_2 ≥ 0, y_3\text { is unrestricted.} $