DPK Easter Term 2005 OPTIMIZATION (D2)

Additional Example Sheet These questions are for further practice and revision.

1. Use the Lagrangian Sufficiency Theorem to:

minimize \frac{v_{1}}{x_{1}} + \frac{v_{2}}{x_{2}}
subject to c_{1}x_{1} + c_{2}x_{2} = c,
x_{1} ⩾ a_{1}, x_{2} ⩾ a_{2},

where c_{1}, c_{2}, a_{1}, a_{2}, v_{1}, v_{2} and c are positive constants, with c ⩾ a_{1}c_{1} + a_{2}c_{2}.

2. A gambler at a horse race has an amount b to bet. The gambler assesses p_{i}, the probability that horse i will win, and knows that s_{i} has been bet on horse i by others, for i = 1, …, n. The total amount bet on the race is shared out in proportion to the bets on the winning horse, and so the gambler’s optimal strategy is to choose (x_{1}, …, x_{n}) to

maximize ∑_{i=1}^{n} \frac{p_{i}x_{i}}{s_{i} + x_{i}} subject to ∑_{i=1}^{n} x_{i} = b, x_{i} ⩾ 0, 1 ⩽ i ⩽ n,

where x_{i} is the amount the gambler bets on horse i.

Find the form of the gambler’s optimal strategy. Deduce that if b is small enough, the optimal strategy is to bet only on the horses for which the ratio p_{i}/s_{i} is maximal.

3. Consider the problem:

maximize 3x_{1} + 6x_{2} − x_{3}
subject to − x_{1} + 4x_{2} − x_{3} ⩽ 2
2x_{1} + x_{2} + x_{3} ⩽ 5
−x_{1} + x_{2} + 2x_{3} ⩽ 1
x_{1}, x_{2}, x_{3} ⩾ 0.

Write down the dual problem and find its solution. Now replace the second constraint by 2x_{1} + x_{2} + x_{3} ⩽ 5 + t. Find the new maximum for small values of t. For what range of values of t is this solution valid?

4. Use the simplex algorithm to solve:

minimize 5x_{1} − 3x_{2}  = f
subject to 2x_{1} − x_{2} + 3x_{3} ⩽ 4
x_{1} + x_{2} + 2x_{3} ⩽ 5
2x_{1} − x_{2} + x_{3} ⩽ 1
x_{1}, x_{2}, x_{3} ⩾ 0.

Write down the dual problem, and solve it by inspection of the final tableau for the primal. If the constraints on the right-hand side of the above problem are changed to 4+ϵ_{1}, 5+ϵ_{2}, 1 + ϵ_{3} respectively, for small ϵ_{1}, ϵ_{2}, ϵ_{3}, by how much does the optimal value of f change?

5. A linear programming problem in the form maximize c^{⊤}x subject to Ax ⩽ b, x ⩾ 0, is solved using the simplex algorithm, starting from the initial b.f.s. given by setting the slack variables z = b and x = 0, to give the optimal tableau

∗ ∗ ∗
x_{1} x_{2} x_{3} z_{1} z_{2} z_{3}
x_{2}  0 1 0 \frac{1}{2} −\frac{1}{3}  \frac{1}{6}  \frac{5}{2}
x_{3}  0 0 1 \frac{1}{2} 0 −\frac{1}{2}  \frac{5}{2}
x_{1}  1 0 0 −\frac{3}{2}  \frac{2}{3}  \frac{7}{6}  \frac{5}{2}
Payoff 0 0 0 −\frac{1}{2} −1 −\frac{3}{2} −\frac{85}{2}

Determine the matrix A and the vectors b and c.

6. A classical example of a degenerate linear programming problem (due to Beale) which ’cycles’ in the simplex algorithm is

Minimize − \frac{3}{4}x_{1} + 150x_{2} − \frac{1}{50}x_{3} + 6x_{4}
subject to  \frac{1}{4}x_{1} − 60x_{2} − \frac{1}{25}x_{3} + 9x_{4} + x_{5}  = 0
\frac{1}{2}x_{1} − 90x_{2} − \frac{1}{50}x_{3} + 3x_{4}  + x_{6}  = 0
x_{3}  + x_{7} = 1, x_{i} ⩾ 0

Show that the algorithm can cycle through the bases:

(x_{5}, x_{6}, x_{7}) → (x_{1}, x_{6}, x_{7}) → (x_{1}, x_{2}, x_{7})
↑  ↓
(x_{4}, x_{5}, x_{7}) ← (x_{3}, x_{4}, x_{7}) ← (x_{2}, x_{3}, x_{7}).

Find the optimal solution.

2 7. Consider the problem

minimize ∑_{i=1}^{n} |x_{i}| subject to Ax ⩽ b,

where x = (x_{1}, …, x_{n})^{⊤}, A is an m×n matrix and b ∈ ℝ^{m}. Show how to convert the problem so that the optimal solution may be found by solving a standard linear programming problem. What happens if you replace minimize by maximize?

8. In another version of the game Undercut, each player selects a number from 1, 2, 3, 4. The players reveal their numbers and the player with the smaller number wins a number of pounds equal to the absolute value of the difference in the numbers, unless the numbers are either adjacent, when the player with the larger number wins £4, or equal, when the game is tied with payoff zero. Find all the optimal strategies for the game.

9. Formulate the problem of finding a maximum flow through a network as a linear programming problem. How many variables and constraints may be needed for a problem with n nodes? Show that the dual problem has a solution in which the variables take only two values and explain the significance of this result.

10. (König-Egerváry Theorem) Consider an m × n matrix A in which each entry is either 0 or 1. Say that a set of lines (rows or columns of the matrix) covers the matrix if each 1 belongs to some line of the set. Say that a set of 1’s is independent if no pair of 1’s of the set lies in the same line. Use the max-flow min-cut theorem to show that the maximal number of independent 1’s equals the minimum number of lines that cover the matrix.

11. (Menger’s Theorem) Derive the vertex form of Menger’s Theorem which states that if A and B are nodes of an undirected network then the maximum number of nodedisjoint paths from A to B which can be chosen simultaneously is equal to the minimum number of nodes whose removal disconnects A and B. [Two paths from A to B are node disjoint if the only two nodes that they have in common are A and B. The removal of a set of nodes S disconnects A and B if any path from A to B passes through at least one node of S.]

12. Suppose that N is a network with vertices 0, 1, 2, …, 2n, 2n+1, where 0 is the source and 2n + 1 is the sink, such that

(a) for each i = 1, …, n, there is an edge (0, i) of capacity 1; (b) for each j = n + 1, …, 2n, there is an edge (j, 2n + 1) of capacity 1;

(c) the only other edges have capacity n and are of the form (i, j) with i ∈ {1, …, n}

and j ∈ {n + 1, …, 2n}, and for each subset I ⊂ {1, …, n} the number of distinct vertices j such that an edge (i, j) exists for some i ∈ I is not less that |I|, the number of elements in I. Prove that any maximal flow in N has value n.

Hence show (the Hall ‘Marriage Theorem’) that if we have a set of n boys and a set of n girls, such that every subset B of the boys between them know at least |B| of the girls, then they can pair off, each boy with a girl he knows.

13. A manufacturer has to supply {5, 7, 9, 6} units of a good in each of the next four months. He can produce up to 8 units each month on ordinary time at costs {1, 3, 4, 2} per unit, and up to 3 extra each month on overtime at costs {2, 5, 7, 4} per unit (where costs are given for each of the next four months). Storage costs are 1 per unit per month. He desires to schedule production to minimize costs over the four-month period. Formulate his problem as a transportation problem (with 8 sources and 5 destinations) and solve it.

Comments on this example sheet may be sent to: d.p.kennedy@statslab.cam.ac.uk 7 April 2005

4