Question

Find the dual program of the following linear programming problem.

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑍 = 30𝑥1 − 50𝑥2 + 10𝑥3

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

3𝑥1 + 2𝑥2 − 𝑥3 ≥ 44

𝑥1 − 𝑥2 + 𝑥3 = 7

𝑥1 𝑖𝑠 𝑢𝑛𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑, 𝑥2 ≥ 0, 𝑥3 ≥ 0,

Answer 1

In order to apply the dual simplex method, convert Min Z to Max Z and all ≥ constraint to ≤ constraint by multiply -1.

Max Z=-30x1+50x2-10x3

subject to

-3x1-2x2+x3≤-44

x1-x2+x3=7

and  x1 𝑖𝑠 𝑢𝑛𝑐𝑜𝑛𝑠𝑡𝑟𝑎𝑖𝑛𝑒𝑑, x2,x3≥0;

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate

1. As the constraint-1 is of type '≤' we should add slack variable S1

2. As the constraint-2 is of type '=' we should add artificial variable A1

After introducing slack,artificial variables

Max Z=-30x1+50x2-10x3+0S1-MA1

subject to

-3x1-2x2+x3+S1=-44

x1-x2+x3+A1=7

and x1,x2,x3,S1,A1≥0

Here not all Zj-Cj≥0. (BecauseZ1-C1=-M+30)

Hence, method fails to get optimal basic feasible solution.