Max $z=2x_1 + 3x_2 + 5x_3$

Subject to

$x_1 + x_2 – x_3 - 5 \\ x_1 + x_2 + 4x_3 = 10 \\ -6x_1 + 7x_2 – 9x_3 \leq 4 $

& $x_1, x_2 \geq 0$ and $x_3$ is unrestricted.

Mumbai University > COMPS > Sem 4 > Applied Mathematics 4

Marks : 05

Year : MAY 2014

Since $x_3$ is unrestricted, Let $x_3=x_3’-x_3’’.$

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

Objective

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

Constraints

$i) x_1+x_2-x_3 \geq -5 \\ \therefore -x_1-x_2+(x_3-x_3") \leq 5\\ \therefore -x_1-x_2 + x_3' -x_3" \leq 5\\ ii) x_1+x_2+4x_3=10 \\ \therefore x_1+ x_2 +4x_3 \leq 10 \space \&\space x_1+x_2 + 4x_3 \geq 10 \\ \therefore x_1+ x_2 + 4(x_3'-x_3")\leq 10 \space \&\space \\ -x_1-x_2-4(x_3'-x_3")\leq -10 \\ \therefore x_1+x_2+4x_3'-4x_3" \leq 10 \space \&\space \\ -x_1-x_2-4x_3'+4x_3" \leq -10\\ iii) -6x_1+7x_2 -9x_3 \leq 4\\ \therefore -6x_1+7x_2- 9(x_3'-x_3")\leq4 \\ \therefore -6x_1+7x_2 -9x_3'+9x_3" \leq 4 \\ iv) x_1,x_2,x_3’,x_3’’ ≥ 0$

the Dual of above primal is objective.

Minimize $w=5y_1+10y_2^1-10y_2’’+4y_3.$

i.e. $w=5y_1+10(y_2^1-10y_2’’)+4y_3.$

Constraints

i)

$$-1y_1+1y_2’-1y_2’’-6y_3 ≥ 2$$

i.e. $ -y_1+(y_2’-y_2’’)-6y_3 ≥ 2 $

ii)

$$-1y_1+1y_2’-1y_2’’+7y_3 ≥ 3$$

i.e. $ -y_1+(y_2’-y_2’’)+7y_3 ≥ 3 $

iii)

$$1y_1+4y_2’-4y_2’’-9y_3 ≥ 5$$

i.e. $ y_1+4(y_2’-y_2’’)-9y_3 ≥ 5 $

iv)

$$-1y_1-4y_2’+4y_2’’+9y_3 ≥ -5$$

i.e. $ -y_1-4(y_2’-y_2’’)+9y_3 ≥ -5 $

i.e. $y_1+4(y_2’-y_2’’) - 9y_3 ≥ 5$

put $y_2= y_2’ -y_2’’,$ where $y_2$ is unrestricted.

therefore, Objective: Minimize $w= w=5y_1+10y_2+4y_3.$

Constraints:

$$-y_1+y_2-6y_3 ≥ 2 \\ -y_1+y_2+7y_3 ≥ 3\\ y_1+4y_2-9y_3 ≥ 5 \\ y_1+4y_2-9y_3 ≥ 5 $$

Combining constraints (iii) and (iv) the dual is

Objective: Minimize $w=5y_1+10y_2+4y_3$

$$ i)-y_1+y_2-6y_3 ≥ 2 \\ ii) -y_1+y_2+7y_3 ≥ 3 \\ iii) y_1+4y_2-9y_3=5$$

$y_1, y_3 ≥ 0 , y_2$ is unrestricted