DPK Easter Term 2005 OPTIMIZATION (D2)

Example Sheet It is recommended that you attempt about the first half of this sheet for your first

supervision and the remainder for your second supervision. An additional example sheet is available for revision and further study.

1. Minimize each of the following functions in the region specified.

(i) 3x in {x : x ⩾ 0}; (ii) x^{2} − 2x + 3 in {x : x ⩾ 0}; (iii) x^{2} + 2x + 3 in {x : x ⩾ 0}. For each of the following functions specify the set Λ of λ values for which the function has a finite minimum in the region specified, and for each λ ∈ Λ find the minimum value and (all) optimal x. (iv) λx subject to x ⩾ 0; (v) λx subject to x ∈ ℝ; (vi) λ_{1}x^{2} + λ_{2}x subject to x ∈ ℝ; (vii) λ_{1}x^{2} + λ_{2}x subject to x ⩾ 0; (vii) (λ_{1} − λ_{2})x subject to 0 ⩽ x ⩽ M.

2. Use the Lagrangian Sufficiency Theorem to:

(i)  minimize x_{1}^{2} + 2x_{2}^{2}
subject to x_{1} + 3x_{2} = b;
(ii)  maximize x_{1} + 2x_{2} + x_{3}
subject to x_{1}^{2} + x_{2}^{2} + x_{3}^{2} ⩽ 1,
x_{1} ⩾ 0, x_{2} ⩾ 0, x_{3} ⩾ 0;
(iii)  minimize x_{1} − x_{2} + x_{3}^{2}
subject to x_{1}^{2} + x_{2}^{2} + x_{3} = 1;
(iv)  maximize 2 tan^{−1} x_{1} + x_{2}
subject to x_{1} + x_{2} ⩽ b_{1},
− ln x_{2} ⩽ b_{2}, x_{1} ⩾ 0, x_{2} ⩾ 0,
(here b_{1}, b_{2} are constants with b_{1} − e^{−b_{2}} ⩾ 0).

3. Consider the following problems:

(a) minimize c^{⊤}x subject to Ax = b;

(b) minimize c^{⊤}x subject to Ax ⩽ b;
(c) minimize c^{⊤}x subject to Ax = b, x ⩾ 0;
(d) minimize c^{⊤}x subject to Ax ⩽ b, x ⩾ 0.

In each case

(i) find the set Λ of values for the Lagrange multipliers λ for which the Lagrangian has a finite minimum (subject to the appropriate regional constraint, if any); (ii) for each value of λ ∈ Λ calculate the minimum of the Lagrangian and write down

the dual problem; (iii) write down the necessary and sufficient conditions for optimality; (iv) verify that the dual of the dual is the primal problem.

4. Suppose that a linear programming problem is written in the two equivalent forms

minimize c^{⊤}x subject to Ax ⩽ b, x ⩾ 0,

where A is an m × n matrix, c, x ∈ ℝ^{n}; and

minimize c_{e}^{⊤}x_{e} subject to A_{e}x_{e} = b, x_{e} ⩾ 0,

where, after the addition of slack variables and the extension of the matrix A and vector c in the appropriate way, A_{e} is m × (n + m), and c_{e}, x_{e} ∈ ℝ^{n+m}. Use your answers to the previous question to write down the dual problem to both versions of the problem and show that the dual problems are equivalent to each other.

5. Consider the (primal) linear programming problem P:

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

(i) Solve P graphically in the x_{1}-x_{2} plane.

(ii) Introduce slack variables x_{3}, x_{4} x_{5} and write the problem in equality form. How many basic solutions of the constraints are there? Determine the values of x = (x_{1}, …, x_{5})^{⊤} and of the objective function at each of the basic solutions. Which of the basic solutions are feasible? Are all the basic solutions non-degenerate?

2 (iii) Write down the dual problem in inequality form with variables λ_{1}, λ_{2} and λ_{3}; add

slack variables λ_{4} and λ_{5} and determine the values of λ = (λ_{1}, …, λ_{5})^{⊤} and of the dual objective function at each of the basic solutions to the dual. Which of these are feasible for the dual?

(iv) Show that for each basic solution x to the problem P there is exactly one basic solution λ to the dual giving the same values of the primal and dual objective functions and satisfying complementary slackness (λ_{i}x_{i+2} = 0, i = 1, 2, 3 and x_{j}λ_{j+3} = 0, j = 1, 2). For how many of these matched pairs (x, λ) is x feasible for the primal problem and λ feasible for the dual?

(v) Solve the problem P using the simplex algorithm starting with the initial basic feasible solution x_{1} = x_{2} = 0. Try both choices of the variable to introduce into the basis on the first step. Compare the objective rows of the various tableaux generated with appropriate basic solutions of the dual problem. What do you observe?

6. Use the simplex algorithm to solve

maximize 3x_{1} + x_{2} + 3x_{3}

subject to 2x_{1} + x_{2} + x_{3} ⩽ 2
x_{1} + 2x_{2} + 3x_{3} ⩽ 5
2x_{1} + 2x_{2} + x_{3} ⩽ 6
x_{1}, x_{2}, x_{3} ⩾ 0,

Each row of the final tableau is the sum of scalar multiples of the rows of the initial tableau. Explain how to determine the scalar multipliers directly from the final tableau.

Let P(ϵ) be the linear programming problem when the right-hand side b = (2, 5, 6)^{⊤} is replaced by the perturbed vector b (ϵ) = (2 + ϵ_{1}, 5 + ϵ_{2}, 6 + ϵ_{3})^{⊤}. Give a formula, in terms of ϵ = (ϵ_{1}, ϵ_{2}, ϵ_{3})^{⊤}, for the optimal value for P(ϵ) when the ϵ_{i} are small. For what ranges of values for ϵ_{1}, ϵ_{2}, ϵ_{3} does your formula hold?

7. Apply the simplex algorithm to

maximize x_{1} + 3x_{2}

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

Explain what happens with the help of a diagram.

8. Use the two-phase algorithm to solve:

maximize − 2x_{1} − 2x_{2}

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

[Hint: You should get x_{1} = \frac{9}{16}, x_{2} = \frac{1}{16}. Note that it is possible to choose the first pivot column so that Phase I lasts only one step, but this requires a different choice of pivot column than the one specified by the usual rule-of-thumb.]

9. Use the two-phase algorithm to solve:

minimize 13x_{1} + 5x_{2} − 12x_{3}

subject to 2x_{1} + x_{2} + 2x_{3} ⩽ 5
3x_{1} + 3x_{2} + x_{3} ⩾ 7
x_{1} + 5x_{2} + 4x_{3} = 10
x_{1}, x_{2}, x_{3} ⩾ 0.

10. Consider the problem minimize 2x_{1} + 3x_{2} + 5x_{3} + 2x_{4} + 3x_{5}

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

Write down the dual problem, and solve this graphically. Hence deduce the optimal solution to the primal problem.

11. Consider the three equations in six unknowns given by Ax = b where

A = ( \begin{matrix}2 & 1 & 1 & 1 & 0 & 0 \\ 1 & 2 & 3 & 0 & 1 & 0 \\ 2 & 2 & 1 & 0 & 0 & 1 \end{matrix} ) , b = ( \begin{matrix}2 \\ 5 \\ 6 \end{matrix} ) .

Choose B = {1, 3, 6} and write Ax = b in the form A_{B}x_{B} + A_{N}x_{N} = b where x_{B} = (x_{1}, x_{3}, x_{6})^{⊤}, x_{N} = (x_{2}, x_{4}, x_{5})^{⊤} and the matrices A_{B} and A_{N} are constructed appropriately.

4

Now write c^{⊤}x = c_{B}^{⊤}x_{B} + c_{N}^{⊤}x_{N} and hence write c^{⊤}x in terms of the matrices A_{B}, A_{N} and the variables x_{N} (i.e., eliminate x_{B} ).

Compute A_{B}^{−1} and hence calculate the basic solution having B as basis. For c = (3, 1, 3, 0, 0, 0)^{⊤} write c^{⊤}x in terms of the non-basic variables. Prove directly from the formula for c^{⊤}x that the basic solution that you have computed is optimal for the problem maximize c^{⊤}x subject to Ax = b, x ⩾ 0.

Compare your answer to your answer to Question 6 and confirm that the final tableau had rows corresponding to the equation x_{B} + A_{B}^{−1}A_{N}x_{N} = A_{B}^{−1}b. Why is it not fair to say that the simplex algorithm is just a complicated way to invert a matrix?

12. Consider the problem in Question 5 and add the constraint x_{1} + 3x_{2} ⩽ 6. Apply the simplex algorithm putting x_{2} into the basis at the first stage. Show that the solution at x_{1} = 0, x_{2} = 2 is degenerate. Try each of the possibilities for the variable leaving the basis. Explain, with a diagram, what happens.

13. In the previous example the additional constraint was redundant (it did not change the feasible set). Can degeneracy occur without redundant equations?

14. Show that introducing slack variables in a linear programming problem does not change the extreme points of the feasible set by proving that x is an extreme point of the set \{x : Ax ⩽ b, x ⩾ 0\} if and only if \binom{x}{z} is an extreme point of the set \{\binom{x}{z} : Ax + z = b, x ⩾ 0, z ⩾ 0\}.

15. Give sufficient conditions for strategies p and q to be optimal for a two-person zero-sum game with payoff matrix A and value v.

Two players fight a duel: they face each other 2n−1 paces apart and each has a single bullet in his gun. At a signal each may fire. If either is hit or if both fire the game ends; otherwise, both advance one pace and may again fire. The probability of either hitting his opponent if he fires after the ith pace forward (i = 0, 1, …, n − 1) is (i + 1) /n. If a player survives after his opponent has been hit his payoff is +1 and his opponent’s payoff is −1. The payoff is 0 if neither or both are hit. The guns are silent so that neither knows whether or not his opponent has fired.

Show that, if n = 4, the strategy ‘shoot after taking one step’ is optimal for both, but that if n = 5 a mixed strategy is optimal. [Hint: (0, \frac{5}{11}, \frac{5}{11}, 0, \frac{1}{11}).] 16. By considering the payoff matrix

A = ( \begin{matrix}0 & −2 & 3 & 0 \\ 2 & 0 & 0 & −3 \\ −3 & 0 & 0 & 4 \\ 0 & 3 & −4 & 0 \end{matrix} )

show that optimal strategies for a two-person zero-sum game are not necessarily unique. Find all the optimal strategies.

17. The n × n matrix of a two-person zero-sum game is such that the row and column sums all equal s. Show that the game has value s/n. [Hint: Guess a solution and show that it is optimal.]

18. Find optimal strategies for both players and the value of the game which has payoff matrix

A = ( \begin{matrix}1 & 4 \\ 3 & 2 \end{matrix} ) .

[You may like to try to compare the effort required to solve this by

(a) seeking strategies and a value which satisfy the optimality conditions;

(b) direct solution of Player I’s original minimax problem; and

(c) using the simplex method on one of the player’s problems after transforming it as suggested in lectures.]

19. Find a maximal flow and a minimal cut for the network below with a source at node 1 and a sink at node n.

•  •  •  • • •  • ............................................................................. ................................................................................................................................................................................................................................................ .................................................................................. ...................................................................................................................................................................................................................................................................................................  ............................................................................. ..................................................................................  ............................................................................. .................................................................................................. 5 5  2  1 43 2  2 2  1 5 1  n ......................................................................................................... ........................................................................................... .............. ........................................................................................................................... .............. ......................................................................................................... .............. ................................................................................................ .............. ................................................................................................ ..............  ..................................................................... ................................................................................................. ........................................................................................... .............. ......................................................................................................... ..............................................................................................................................^{.......................................................................................................}  ^{.......................................................................................................}

20. Devise rules for a version of the Ford–Fulkerson algorithm which works with undirected arcs.

As a consequence of a drought, an emergency water supply must be pumped from Oxbridge to Camford along the network of pipes shown in the figure. The numbers against

6

.............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................  ............................................................................. ............................................................................. ............................................................................. ............................................................................. Oxbridge  Camford 10 1 8 14 4  7 11 9 2 13  5  12 3 6 15  •  • • • •  •  • • • •

the pipes show their maximal capacities, and each pipe may be used in either direction. Find the maximal flow and prove that it is maximal.

21. How would you augment a directed network to incorporate restrictions on node capacity (the total flow permitted through a node) in maximal-flow problems?

The road network between two towns A and B is represented in the diagram below. Each road is marked with an arrow giving the direction of the flow, and a number which represents its capacity. Each of the nodes of the graph represents a village. The total flow into a village cannot exceed its capacity (the number in the circle at the node). Obtain the maximal flow from A to B.

The Minister of Transport intends to build a by-pass around one of the villages, whose effect would be to completely remove the capacity constraint for that village. Which village should receive the by-pass if the intention is to increase the maximal flow from A to B by as much as possible? What would the new maximal flow be?

................................................................. 10..................................... ........................................................................ ..............25 .......................................................... ........................................................................ ..............11 .......................................................... ........................................................................ ..............15 .......................................................... ............................................................................................................ .............. 7.............................................................................................. ............................................................................................................ ..............10 .............................................................................................. ................................................... .............. 5 ..................................... ................................................... .............. 5 .....................................  ................................................... .............. 5 .....................................  ......................................................................................8 ............................................................................................................10 ...................... ..................................................10 ......................  .................................................................................................................... 20 ........................................................................................ ................................................................................................................................................. 8 ..................................................................................................................... ................................................................................. .............. 15 ................................................................... ................................................................................. .............. 12................................................................... ................................................................................. .............. 10................................................................... ........................................................................................... ^{...........................................................................................}  ^{...........................................................................................} ...........................................................................................  ...........................................................................................  ..........................................................................................._{...........................................................................................}_{...........................................................................................}  _{...........................................................................................} A  B 12  13 30  25 10 15  16

22. By finding a suitable potential on the nodes of the network (i.e., a set of suitable node numbers), show that the flow illustrated below is a minimal-cost circulation. [Each arc is labelled with the flow, x_{ij}, and with a triple of numbers giving the constants (c_{ij}^{−}, c_{ij}^{+}, d_{ij}) for that arc.]

................................................................................................................ .............. (2, 4, 3) 3 .................................................................................................. ................................................................................................................ .............. (2, 4, 2) 2.................................................................................................. ..............................................................................................................................(1, 5, 2) 4 .................................................................................................. ................................................................................................................ .............. (0, ∞, −6) 5................................................................................................................................................................................................ (2, 5, 2) 2 .................................................................. ................................................................................ .............. (0, 1, 4) 1.................................................................. ................................................................................ .............. (1, 4, 0) 1 .................................................................. .............................................................................................. (1, 4, 3) 2.................................................................. .....................................................................  .....................................................................^{.....................................................................}^{.....................................................................}  ^{.....................................................................} 1 2  3  4 5 .......................................................................... .............. (c_{ij}^{−}, cij^{+}, d_{ij}) x_{ij} ............................................................

23. Consider the problem of assigning lecturers L_{1}, …, L_{n} to courses C_{1}, …, C_{n} so as to minimize student dissatisfaction. The dissatisfaction felt by students if lecturer L_{i} gives course C_{j} is d_{ij}, and each lecturer must give exactly one course. Show how to formulate this problem as a problem of minimizing the cost of a circulation in a network. (Can you be sure that your network problem has an optimal flow of the appropriate kind?) For the example of 3 lecturers and 3 courses with dissatisfaction matrix

( \begin{matrix}6 & 3 & 1 \\ 8 & 12 & 5 \\ 3 & 11 & 7 \end{matrix} )

find an optimal flow through the appropriate network (by guessing) and compute node numbers for each node so that the optimality conditions are satisfied.

24. Sources 1, 2, 3 stock candy floss in amounts of 20, 42 18 tons respectively. The demand for candy floss at destinations 1, 2, 3 are 39, 34, 7 tons respectively. The matrix of transport costs per ton is

( \begin{matrix}7 & 4 & 9 \\ 8 & 12 & 5 \\ 3 & 11 & 7 \end{matrix} )

with the (ij) entry corresponding to the route i → j. Find the optimal transportation scheme and the minimal cost by applying the transportation algorithm starting from (a) an assignment given by the NW method, and (b) an assignment given by the greedy algorithm.

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

8