Answer to Question #258087 in Operations Research for Dut Machar

Question

onsider the following problem

Maximize          Z = 6x1+8x2

Subject to: 

                  5x1+2x2 ≤ 20

                  X1+2x2≤ 10

And

                 X1≥ 0, X2≥ 0

a. Construct the dual problem for this primal problem

b. Solve both the primal problem and the dual problem graphically. Identify the CPF solutions and corner-point infeasible solutions for both problems. Calculate the objective function values for all these solutions

c. Use the information obtained in part (b) to construct a table listing the complementary basic solutions for these problems.

d. Work through the simplex method step by step to solve the primal problem. After each iteration (including iteration 0), identify the BF solution for this problem and the complementary basic solution for the dual problem. Also identify the corresponding corner-point solutions.

Answer 1

a.

MIN Zy=20y1+10y2

subject to

5y1+y2≥62y1+2y2≥8

and y1,y2≥0

b.

primal problem:

CPF solutions:

intersection:

$5(10-2y)+2y=20$

$y=30/8=3.75$

$x=10-2\cdot 3.75=2.5$

corner points: (0, 5), (4, 0), (2.5, 3.75)

objective function:

for (0, 5): $z=40$

for (4,0): $z=24$

for (2.5, 3.75): $z=2.5\cdot 6+3.75\cdot 8=45$

So,

$z_{max}=45$ at $(2.5,3.75)$

corner-point infeasible solutions:

corner points:

(0,10): $z=80$

(10,0): $z=60$

dual problem:

CPF solutions:

intersection:

$2x+2(6-5x)=8$

$x=0.5$

$y=6-5\cdot 0.5=3.5$

corner points: (0, 6), (4, 0), (0.5, 3.5)

for (0, 6): $z=60$

for (4,0): $z=80$

for (0.5, 3.5): $z=0.5\cdot 20+3.5\cdot 10=45$

So,

$z_{min}=45$ at $(0.5,3.5)$

corner-point infeasible solutions:

corner points:

(0, 4): $z=40$

(1.2, 0): $z=24$

c)

primal problem basic solutions: complementary basic solutions:

for (4,0): $z=24$ for (4,0): $z=80$

for (0, 5): $z=40$ for (0, 6): $z=60$

for (2.5, 3.75): $z_{max}=45$ for (0.5, 3.5): $z_{min}=45$

d)

After introducing slack variables

Max Z=6x1+8x2+0S1+0S2

subject to

5x1+2x2+S1=20x1+2x2+S2=10

and x1,x2,S1,S2≥0

after iteration 1:

Negative minimum Zj-Cj is -8 and its column index is 2. So, the entering variable is x2.

Minimum ratio is 5 and its row index is 2. So, the leaving basis variable is S2.

∴ The pivot element is 2.

Entering =x2, Departing =S2, Key Element =2

after iteration 2:

Negative minimum Zj-Cj is -2 and its column index is 1. So, the entering variable is x1.

Minimum ratio is 2.5 and its row index is 1. So, the leaving basis variable is S1.

 ∴ The pivot element is 4.

Entering =x1, Departing =S1, Key Element =4

after iteration 3:

Since all Zj-Cj≥0

Hence, optimal solution is arrived with value of variables as :

x1=2.5,x2=3.75

Max Z=45