USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

INTERPRETING PRIMAL-DUAL OPTIMAL SOLUTIONS

As has been said earlier, the solution values of the primal can be read directly from the optimal solution table of the dual. The reverse of this also is true, The following two properties of primal-dual should be understood.

Primal-Dual Property 1. If feasible solution exists for both primal and dual problems, then both problems n optimal solution for which the objective function values are equal. A peripheral relationship is that, problem has an unbounded solution, its. dual has no feasible solution.

Primal-Dual Property 2. The optimal values for decision variables in one problem are read from row (0) of the optimal table for the other problem. The following steps are involved in reading the solution values be primal from the optimal solution table of the dual:-

Step I. The slack-surplus variables in the dual problem are associated with the basic variables of the primal in the optimal solution. Hence, these slack-surplus variables have to be identified in the dual problem.

Step II. Optimal value of basic primal variables can be directly read from the elements in the index row corresponding to the columns of the slack-surplus variables with changed signs.

Step III. Values of the slack variables of the primal can be read from the index row under the non-basic variables of the dual solution with changed signs.

Step IV. Value of the objective function is same for primal and dual problems.

Step I. Convert the minimisation into a maximisation problem.

Maximise Z*= 2y1 – 3y2 + 5 y3

Step II. Make RHS of constraints positive,

– 2 y1 – 4 y2 + y3 ≥ – 2 is rewritten as

2 y1 + 4 y2 – y3 ≤ 2

Step III. Make the problem as N + S coordinates problem

Maximise Z* = 2 y1 – 3 y2 + 5 y3 + 0S1 + 0S2 + 0S3 – MA1 – MA3

Subject to – 2y1 + 3 y2 – S1 + A1 = 5

2 y1 + 4 y2 – y2 + S2 = 2

y1 + 3 y3 – S3 + A3 = 3

y1, y2, y3, S1, S2, S3 , A1, A3 ≥ 0

Step IV. Make N coordinates assume 0 values,

y1 = y2 = y3=S1 = S3 =0,

A1 = 5, S2 = 2, A3 = 3 is the basic feasible solution, This can be represented in the table as follows.

Initial Solution

Cj

2

-3

-5

0

0

0

-M

-M

Min Ratio

CB

Basic Variables

Solution Variables

y1

y2

y3

S1

S2

S3

A1

A2

M

A1

5

-2

3

0

-1

0

0

1

0

0

S2

2

2

4

-1

0

1

0

0

0

M

A2

3

1

0

3

0

0

-1

0

1

Zj

 

 

M

-3M

-3M

M

0

M

-M

-M

 

(Cj-Zj)

 

2-M

-3+3M

-5+3M

-M

0

-M

0

0

 

 

Step V. Cj Zj is + ve under some columns, it is not the optimal solution, Perform the optimality test.