Duality: additional examples#

Maximisation problem#

The primal problem is given by:

Max. J(x)=x1+4x2

subject to:

(1)#x1+2x252x1+x2=4x1x21x1,x20

Note that the constraint x1x21 is the same as x1+x21.

Since there are three primal constraints (one equality and two inequalities), there are three dual variables for the problem. We will call them λ1, μ1, and μ2 (again, we could use whatever variable names we want).

The dual problem is:

Min. F(λ,μ)=5μ1+4λ1μ2

subject to:

(2)#μ1+2λ1μ212μ1+λ1+μ24μ1,μ20

The variable λ1 is unrestricted in sign (free).

The solution to the primal problem is:

x1=1.666667
x2=0.666667
J(x)=4.33333

The active constraints are 2x1+x2=4 and x1+x2=1.

The shadow prices (Lagrange multipliers) for these active constraints are: λ1=1.666667 and μ2=2.333333.

The solution to the dual problem is:

μ1=0
μ2=2.333333
λ1=1.666667
F(λ,μ)=4.333333

Conclusions:

  • The optimum value of the primal and the dual objective function is equal to 4.333333.

  • The optimal values of the decision variables of the dual problem are equal to the Lagrange multipliers of the primal problem.

  • Likewise, the shadow prices (Lagrange multipliers) of the dual problem are equal to the solution of the primal problem.

Illustrative example of the perspective switch in duality (lunch ingredients)#

An illustrative small example of the relationship between primal and dual linear programs will show that these two problems arise from two different perspectives on the same application. As an example, we introduce a diet problem.

Johanna is deciding what to purchase for lunch. She has two choices:

  1. Soup, which costs 2.80€ per portion,

  2. Salad with fresh vegetables, which costs 3.20€ per portion.

In this lunchroom, it is possible to purchase a fraction of an item if the client wishes. Also, the farmer can sell a fraction of a vegetable to the owner of the lunchroom.

The soup ingredients are: onion, carrot, and tomato. The ingredients for the salad are onion, carrot, and apple. The amount of the ingredients is specified in recipes presented in the table below:

Ingredient

Soup (x1)

Salad (x2)

Onion

1

0.5

Carrot

2.5

3

Tomato

2

0

Apple

0

1

Cost

2.80

3.20

Johanna’s dietary requirements:

  • Onion: 0.5

  • Carrot: 4

  • Tomato: 1.5

  • Apple: 1.5

Johanna wants to minimise the lunch cost by finding the least expensive combination of soup and fresh salad that meets her requirements, whereby she needs at least 0.5 onion, 4 carrots, 1.5 tomatoes, and 1.5 apples for lunch.

This decision problem can be formulated as an LP problem as follows:

Min. 2.80x1+3.20x2

subject to:

(3)#x1+0.5x20.52.5x1+3x242x11.5x21.5x1,x20

By applying the linear programming method to this problem, we can find easily that the unique solution is x1=0.75 and x2=1.5, i.e. it means 3/4 portion soup and 1.5 portion salad.

The value of the cost function for the optimal solution is 2.80×0.75+3.20×1=6.90.

There are 2 active constraints: 2x11.5 and x21.5.

The shadow price is 1.40 for the active constraint 2x11.5, i.e., the cost will be 8.30 if the wish would be to eat at least 2.5 tomatoes.

The shadow price is 3.20 for the active constraint x21.5, i.e., the cost will be 10.10 if the wish would be to eat at least 2.5 apples.

Let us have a look at this problem from the perspective of the farmer who supplies the lunchroom with vegetables. The owner of the lunchroom needs to buy at least 0.5 onion, 4 carrots, 1.5 tomatoes, and 1.5 apples.

The farmer wants to maximise his revenues. His decision problem is: How can I set the prices per onion, carrot, tomato, and apple so that the lunchroom owner will buy them from me, and my revenue is maximised?

The lunchroom owner will buy vegetables only if the total cost of soup is below 2.80€ and for the salad, below 3.20€.

These restrictions impose the following constraints on the prices μ1,μ2,μ3,μ4 for onions, carrots, tomatoes, and apples:

1μ1+2.5μ2+2μ3+0μ42.80
0.5μ1+3μ2+0μ3+1μ43.20

Clearly, all the prices for all these vegetables should be non-negative.

The revenue of the farmer is (0.5μ1+4μ2+1.5μ3+1.5μ4) and it should be maximised. This gives us the following dual problem:

Max. F(μ)=0.5μ1+4μ2+1.5μ3+1.5μ4

subject to:

(4)#1μ1+2.5μ2+2μ32.800.5μ1+3μ2+μ43.20μ1,μ2,μ3,μ40

By applying the linear programming method to this dual problem, we can find easily that the unique solution is μ1=0,μ2=0,μ3=1.40,μ4=3.20.

It may seem strange that the farmer charges nothing for onion (μ1=0) and carrot (μ2=0). He charges 1.40€ per tomato and 3.20€ per apple. It is better for him to give onions and carrots for free and charge as much as possible for tomatoes and apples.