0
31kviews
Prove that dual of dual is primal, with suitable example. Also explain the interpretation of optimal solution solved by using duality for the primal problem.
1 Answer
1
943views

Consider a simple example:

There is a small company in which has recently become engaged in the production of office furniture. The company manufactures tables, desks and chairs. The production of a table requires 8 kgs of wood and 5 kgs of metal and is sold for \$80; a desk uses 6 kgs of wood and 4 kgs of metal and is sold for \$60; and a chair requires 4 kgs of both metal and wood and is sold for \$50. We would like to determine the revenue maximizing strategy for this company, given that their resources are limited to 100 kgs of wood and 60 kgs of metal.

Max. $Z = 80x_1 + 60x_2 + 50x_3 \\ 8X_1 + 6X_2 + 4X_3 ≤ 100 \\ 5X_1 + 4X_2 + 4X_3 ≤ 60 \\ X_1, X_2, X_3≥ 0$

Where $X_1, X_2, X_3$ are the number of tables, desks and chairs to be manufactured.

The dual of this problem would be:

Min. $W = 100Y_1 + 60Y_2 \\ 8Y_1 + 5Y_2≥80 \\ 6Y_1 + 4Y_2 ≥ 60 \\ 4Y_1 + 4Y_2 ≥ 50 \\ Y_1, Y_2≥ 0$

Expressing in standard form by multiplying throughout by ‘-1’:

Max. $(-W) = -100Y_1- 60Y_2 \\ -8Y_1 -5Y_2≤-80 \\ -6Y_1 -4Y_2≤-60 \\ -4Y_1 -4Y_2≤-50 \\ Y_1, Y_2≥ 0$

Finding the dual of the above system (dual of the dual):

Min. $(–Z) = -80x_1 - 60x_2 - 50x_3 \\ -8X_1 - 6X_2 - 4X_3 ≥ -100 \\ -5X_1 - 4X_2 - 4X_3 ≥ -60 \\ X_1, X_2, X_3 ≥ 0$

Expressing in standard form by multiplying throughout by ‘-1’:

Max. $Z = 80x_1 + 60x_2 + 50x_3 \\ 8X_1 + 6X_2 + 4X_3 ≤ 100 \\ 5X_1 + 4X_2 + 4X_3 ≤ 60 \\ X_1, X_2, X_3≥ 0$

Which is the original set of expressions itself.

So we have proved that dual of the dual is the primal itself.

Now consider the dual set of expressions:

Min. $W = 100Y_1 + 60Y_2 \\ 8Y_1 + 5Y_2 ≥ 80 6Y_1 + 4Y_2 ≥ 60 4Y_1 + 4Y_2 ≥ 50 Y_1, Y_2 ≥ 0$

The solution to the above set of expressions can be explained as follows:

Supposing there is a much bigger company which has been the lone producer of the same type of furniture for many years, as the company mentioned above. They don't appreciate the competition from this new company; so they have decided to tender an offer to buy all of their competitor's resources and therefore put them out of business. The challenge for this large company then is to develop a linear program which will determine the appropriate amount of money that should be offered for a unit of each type of resource, such that the offer will be acceptable to the smaller company while minimizing the expenditures of the larger company.

Please log in to add an answer.