Exercise 4.1

Consider the linear programming problem:

minimize ⁡ x1 − x2 subject to 2x1 + 3x2 − x3 + x4 ≤ 0 3x1 + x2 + 4x3 − 2x4 ≥ 3 − x1 − x2 + 2x3 + x4 = 6 x1 ≤ 0 x2,x3 ≥ 0.

Write down the corresponding dual problem.

Answers

The dimension of the original optimization problem is n = 4; thus, the nominal number of constraints will be m′ = 4 in the dual problem. Similarly, the original constraint has m = 3 constraints; the nominal dimension of the dual problem is thus n′ = 3. Using the definition of the dual problem on page 142, we convert the problem as follows:

minimize  x1 − x2 subject to 2x1 + 3x2 − x3 + x4 ≤ 0 3x1 + x2 + 4x3 − 2x4 ≥ 3 −x1 − x2 + 2x3 + x4 = 6 x1 ≤ 0 x2 ≥ 0 x3 ≥ 0 x4 free maximize 0p1 + 3p2 + 6p3 subject top1 ≤ 0 p2 ≥ 0 p3 free 2p1 + 3p2 − p3 ≥ 1 3p1 + p2 − p3 ≤−1 −p1 + 4p2 + 2p3 ≤ 0 p1 − 2p2 + p3 = 0.

For the sake of competness, we rewrite the dual problem in a more conventional way.

maximize  3p2 + 6p3 subject to 2p1 + 3p2 − p3 ≥ 1 3p1 + p2 − p3 ≤−1 − p1 + 4p2 + 2p3 ≤ 0 p1 − 2p2 + p3 = 0 p1 ≤ 0 p2 ≥ 0.
User profile picture
2022-03-15 11:03
Comments