Exercises in Linear Programming

Linear Algebra – Review

1. Solve the following system using Gaussian elimination:

\begin{aligned}2x_{1} & − & 3x_{2} & + & 4x_{3} & = & 5 \\ 6x_{1} & + & 7x_{2} & − & 8x_{3} & = & 9 \\ 10x_{1} & + & x_{2} & + & 2x_{3} & = & 21 \end{aligned}

2. Invert the matrix of coefficients of the system in the preceding question.

3. The same as the two preceding questions for the following systems: i.

\begin{aligned}5x_{1} & − & 7x_{2} & − & 11x_{3} & = & 9 \\ −9x_{1} & + & 17x_{2} & + & 2x_{3} & = & −10 \\ 7x_{1} & − & x_{2} & − & 51x_{3} & = & 7 \end{aligned}

ii.

\begin{matrix}y_{1} & + & 5y_{2} & + & 6y_{3} & + & 7y_{4} = & 17 \\ −2y_{1} & − & 8y_{2} & + & 4y_{3} & + & 9y_{4} = & −19 \\ 3y_{1} & + & 15y_{2} & + & 21y_{3} & − & 12y_{4} = & 26 \\ 2y_{1} & + & 10y_{2} & + & 12y_{3} & + & 19y_{4} = & −1 \end{matrix}

4. Find the general solution of the following system by expressing some of the variables in terms of the others:

x_{1} + 3x_{2} − 5x_{3} + 8x_{4} + 2x_{5} − x_{3} = 9
4x_{1} − 2x_{2} + 6x_{3} − 7x_{4} − x_{5} + 3x_{3} = 3
−3x_{1} + 5x_{2} − 7x_{3} + 9x_{4} + 4x_{5} − 4x_{3} = −1
6x_{1} + 4x_{2}  + 3x_{4} + 4x_{5} + x_{3} = 14

The Diet Problem

5. Consider the two foods problem studied in class. Suppose it becomes necessary to satisfy certain requirements with respect to an additional nutritional element – crude fat. Food A is known to contain 20 units of crude fat per unit of food, and food B – 17 units per unit. The minimum daily requirements of crude fat are 550 units.

i. Show geometrically that the optimal solution of the problem presented in class is still optimal for the modified problem.

ii. Use LINDO towards the same end. First enter the model presented in class and run it. Then make the necessary changes and run again to obtain the same result.

iii. Find geometrically for what range of minimum daily requirements of crude fat the solution found in class is still optimal for the modified problem.

iv. Select a value of minimum daily requirements of crude fat outside the range found in the preceding part, and solve the modified problem geometrically.

v. Do the same using LINDO. (Again, do not enter the whole problem anew, just make the necessary changes.)

vi. Find geometrically the range of minimum daily requirements of crude fat for which the other three constraints are irrelevant (namely, dropping those constraints does not yield a better optimum).

vii. Now suppose that with respect to crude fat there are maximum daily requirements rather than minimum daily requirements. For what range of maximum daily requirements does the problem have no feasible solutions? What is the optimal solution for values outside this range?

The Production and Transportation Examples

6. Consider the production problem presented in class.

i. Employ elementary considerations to show that the solution we found when disregarding the last two activities is in fact optimal for the full problem. (Here is an example of an “elementary consideration”: Decreasing the level of activity 3 by 1 unit, and increasing that of activity 1 by 0.8 units, we produce more for the same cost.)

ii. Use LINDO to verify our results.

iii. Show that, moreover, for any value of the parameter k, the optimal production plan does not include any usage of activities 3 and 4.

7. i. Suppose the production problem is changed as follows. The company can employ workers for up to 500 hours a week at the price of $1 per hour, but every hour above that costs $1.5. Can the modified problem be solved by linear programming methods?

ii. Same question for the following modification of the original problem. If the company pumps over 1,800 barrels of heavy petrol, it is paid an extra $0.5 per barrel in the range 1,800-2,200 and an extra $0.25 per barrel in the range 2,200-2,500.

iii. Same for the following modification. Due to unemployment in the market, in addition to the goal of reaching the required quota, the company is required by the government to use as much manpower as possible.

8. i. Solve the transportation problem presented in class using elementary considerations. For example, we claim that at the optimal point we necessarily have x_{11} = 0. Indeed, suppose this is not the case, perform the following changes and show that a better solution is obtained.

a. Decrease x_{11} by some (small) positive amount.

b. Increase x_{12} by the same amount.

c. Decrease x_{22} (or x_{32}) by the same amount.

d. Increase x_{21} (or x_{31}, respectively) by the same amount. Continue this way to arrive at the optimal solution.

ii. Use LINDO to verify your results.

Summary

9. The Interpolation Theorem of Lagrange states that, given any n (distinct) points x_{1}, x_{2}, …, x_{n} on the real line, and any real values f_{1}, f_{2}, …, f_{n}, there exists a (unique) polynomial P, of degree not exceeding n − 1, such that P (x_{i}) = f_{i}, 1 ≤ i ≤ n. In other words, given any real function f and n points on the line, there exists a polynomial P of degree not exceeding n − 1, coinciding with f at all these points. Now consider the following problem: We are given a function f and n points x_{1}, x_{2}, …, x_{n}, and we want to find a polynomial P of degree not exceeding m which is “as close as possible” to f at all the prescribed n points. (Thus, for m = n − 1 the polynomial P must be the interpolation polynomial, and the problem is interesting only if m < n − 1.) Here the distance d(f, P) between f and P is measured by:

d(f, P) = max{|P (x_{i}) − f(x_{i})| : 1 ≤ i ≤ n} .

Present the problem as a linear programming problem.

10. The following well-known formula in probability theory enables one to compute the probability of the union of finitely many events A_{1}, A_{2}, …, A_{n} when the probabilities of all intersections of some of these events are known:

\begin{aligned}P ( ∪_{i=1}^{n} A_{i}) = & ∑_{i=1}^{n} P (A_{i}) − ∑_{1≤i<j≤n} P (A_{i} ∩ A_{j}) + ∑_{1≤i<j<k≤n} P (A_{i} ∩ A_{j} ∩ A_{k}) − … \\ & + (−1)^{n−1}P ( ∩_{i=1}^{n} A_{i}) . \end{aligned}

Now if not all the terms on the right hand side are known, then the left hand side is not uniquely determined in general. Let r be a number between 1 and n − 1, and suppose the probabilities of all intersections of up to r of the sets A_{1}, A_{2}, …, A_{n} are known, and we want to know the size of the range of possible values of P (∪_{i=1}^{n}A_{i}) in the worst case. Namely, define:

E(r, n) = sup (P ( ∪_{i=1}^{n} A_{i}) − P ( ∪_{i=1}^{n} B_{i})) ,

where the supremum is taken over all events A_{1}, A_{2}, …, A_{n} and B_{1}, B_{2}, …, B_{n} in all probability spaces, satisfying

P (A_{i_{1}} ∩ A_{i_{2}} ∩ … ∩ A_{i_{k}}) = P (B_{i_{1}} ∩ B_{i_{2}} ∩ … ∩ B_{i_{k}})

for every 1 ≤ k ≤ r and 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n.

i. Explain how the problem can be represented as a linear programming problem for any n and r.

ii. Use LINDO to solve the problem for the case n = 2, r = 1.

11. Refer to the preceding problem. A k-atom of the collection A_{1}, A_{2}, …, A_{n} is an intersection of k of the A_{i}’s and the complements of the other n − k A_{i}’s. The collection A_{1}, A_{2}, …, A_{n} is symmetric if all k-atoms have the same probability for every 1 ≤ k ≤ n. It can be proved that, restricting ourselves to symmetric collections, we still obtain the same value of E(r, n). Explain how this result can be of use for calculating E(r, n).

12. Refer again to problem 10. Another result relating to E(r, n) states that it is the optimum of the following linear programming problem:

max x_{1} + x_{2} + … + x_{n}

subject to:

\begin{matrix}\binom{j}{j}x_{j} + \binom{j + 1}{j}x_{j+1} + … + \binom{n}{j}x_{n} = 0, & 1 ≤ j ≤ r, \\ −1 ≤ x_{i_{1}} + x_{i_{2}} + … + x_{i_{k}} ≤ 1, & 1 ≤ i_{1} < i_{2} < … < i_{k} ≤ n . \end{matrix}

i. Construct the machinery required to let you use this result for calculating E(r, n) for any n and r (at least in principle).

ii. Employ this result to calculate E(r, n) using LINDO for as many values of n and r as possible.

The Simplex Method

13. i. Use the simplex method to solve the following problem:

max 4x_{1} + 3x_{2} + 7x_{3}

subject to:

\begin{aligned}x_{1} & + & 2x_{2} & + & 5x_{3} & + & x_{4} & & & = & 8, \\ 4x_{1} & + & 2x_{2} & + & 3x_{3} & & & + & x_{5} & = & 11, \end{aligned}

x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ≥ 0 .

ii. Solve the same problem by evaluating the objective function at finitely many points.

14. Solve the following problems using the simplex method: i. max 3x_{1} − 2x_{2} − x_{3} subject to:

4x_{1}  − 2x_{3} + x_{4}  = 12,
3x_{1} + 8x_{2} − 4x_{3}  + x_{5}  = 10,
−x_{1} + 2x_{2} + 3x_{3}  + x_{6} = 7,

x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} ≥ 0 . ii. max −x_{1} − x_{2} + x_{3} − x_{4} + x_{5} − x_{6} subject to:

x_{1}  + 6x_{3} + x_{4}  = 9,
3x_{1} − 4x_{2} + 2x_{3}  + x_{5}  = 2,
x_{1} + 2x_{2} + 2x_{3}  + x_{6} = 6,

x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} ≥ 0 . iii. min x_{1} + x_{2} + x_{3} subject to:

x_{1} − x_{4} − 2x_{6} = 5,
x_{2}  + 2x_{4} − 3x_{5} + x_{6} = 3,
x_{3} + 2x_{4} − 5x_{5} + 6x_{6} = 5,

x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} ≥ 0 . iv. max 4x_{1} + 6x_{2} + x_{3} + 3x_{4} subject to:

\begin{aligned}x_{1} & + & 2x_{2} & + & 3x_{3} & + & 5x_{4} & ≤ & 17, \\ 2x_{1} & + & 3x_{2} & − & x_{3} & + & 7x_{4} & ≤ & 19, \\ 3x_{1} & + & 2x_{2} & + & 4x_{3} & − & 2x_{4} & ≤ & 14, \end{aligned}

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0 . v. min x_{1} − 2x_{2} + 3x_{3} subject to:

\begin{aligned}−2x_{1} & + & x_{2} & + & 3x_{3} & = & 2, \\ 2x_{1} & + & 3x_{2} & + & 4x_{3} & = & 1, \end{aligned}

x_{1}, x_{2}, x_{3} ≥ 0 . vi. max x_{4} − x_{5} subject to:

2x_{2} − x_{3} − x_{4} + x_{5} ≥ 0,
−2x_{1}  + 2x_{3} − x_{4} + x_{5} ≥ 0,
x_{1} − 2x_{2}  − x_{4} + x_{5} ≥ 0,
x_{1} + x_{2} + x_{3}  = 1,

x_{1}, x_{2}, x_{3}, x_{4}, x_{5} ≥ 0 . vii. max −2x_{1} − x_{2} + x_{3} + x_{4} subject to:

\begin{aligned}x_{1} & − & 2x_{2} & + & 2x_{3} & − & x_{4} & = & 2, \\ 2x_{1} & + & x_{2} & − & 3x_{3} & + & x_{4} & = & 6, \\ x_{1} & + & x_{2} & + & x_{3} & + & x_{4} & = & 7, \end{aligned}

x_{1}, x_{2}, x_{3}, x_{4} ≥ 0 .

15. Solve the following problems using the simplex method. Note that in each of them some of the variables are unrestricted.

i. max x_{1} + 3x_{2} + x_{3} subject to:

\begin{aligned}5x_{1} & + & 3x_{2} & & & ≤ & 3, \\ x_{1} & + & 2x_{2} & + & 4x_{3} & ≤ & 4. \end{aligned}

ii. max x_{8} subject to:

2x_{1} + x_{2} + x_{3}  = 10,
−44x_{1} − 42x_{2}  + x_{4}  + x_{8} = −183,
36x_{1} − 102x_{2}  + x_{5}  + x_{8} = 17,
−164x_{1} + 298x_{2}  + x_{6}  + x_{8} = 1517,
−12x_{1} − 6x_{2}  + x_{7} + x_{8} = −79,

x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7} ≥ 0 (x_{8} unrestricted). iii. max 2x_{1} − x_{2} − x_{3}

subject to:

x_{1} + 2x_{2} + x_{3} = 16,
x_{1} − x_{2} − 2x_{3} = 6,
x_{1}  ≤ 5,
x_{2}  ≥ 4,
x_{3} ≤ −2.

16. Consider the following problem:

max \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_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7} ≥ 0 .

Try to solve the problem using the simplex method. Each time there are two possibilities of changing the basic variables (with the same effect on the value of the objective function), take your pivot term at the first possible row. (For example, at the first stage, x_{1} becomes a basic variable instead of x_{5} and not instead of x_{6}, even though both choices seem equally plausible.) Show that after six pivot operations we revert to the original situation, so that the algorithms leads in this case to an infinite loop, and does not solve the problem.

17. Write procedures implementing the various steps of solving a general linear programming problem using the simplex method:

i. A procedure which, given any linear programming problem, brings it to standard form.

ii. A procedure which, given a linear programming problem in canonical form, performs a single pivot step.

iii. A procedure which, given a linear programming problem in standard form, writes down another linear programming problem, in canonical form, whose solution brings the first problem to canonical form.

18. i. Suppose a linear programming problem in standard form is not redundant and has no degenerate solutions. Is it possible that at that step in the first stage of the simplex method when w attains the value 0 for the first time, there are still artificial variables in the basis?

ii. Suppose the simplex method is applied to a linear programming problem in standard form, and at each step there is exactly one term which may serve as the pivot term. Is cycling possible for this problem?

iii. A linear programming problem in canonical form is given. Show that if n = m + 1 then at most one step of the simplex method is required to solve the problem.

Convex Sets

19. Prove that a subset A of R^{n} is convex if and only if every convex combination α_{1}u^{(1)} + α_{2}u^{(2)} + … + α_{k}u^{(k)}, with α_{1}, α_{2}, …, α_{k} ≥ 0 and α_{1} + α_{2} + … + α_{k} ≤ 1, of points u^{(1)}, u^{(2)}, …, u^{(k)} in A belongs to A as well.

21. Prove that any ball in R^{n} and, more generally, any ellipsoid in R^{n}, is convex. (Here an ellipsoid is a set of the form

E = \{(x_{1}, x_{2}, …, x_{n}) : \frac{(x_{1} − c_{1})^{2}}{a_{1}^{2}} + \frac{(x_{2} − c_{2})^{2}}{a_{2}^{2}} + … + \frac{(x_{n} − c_{n})^{2}}{a_{n}^{2}} ≤ 1\}

with arbitrary real numbers c_{1}, c_{2}, …, c_{n} and positive a_{1}, a_{2}, …, a_{n}.)

22. i. Describe explicitly all convex sets in R. Conclude that the cardinality of the set of all convex sets in R is ℵ.

ii. Show that there are 2^{ℵ} convex sets in R^{2}.

23. Prove the following closure properties of convex sets:

i. The intersection of any family of convex sets is convex.

ii. Given any family {A_{i} : i ∈ I} of convex sets, their algebraic sum

∑_{i∈I} A_{i} = {∑_{i∈F} a_{i} : F ⊆ I, |F | < ∞, a_{i} ∈ A_{i} ∀ i ∈ F }

is also convex.

iii. If A ⊆ R^{n} is convex, then for any d ∈ R and v ∈ R^{n} the set dA + v = {du + v : u ∈ A} is convex.

iv. The closure of a convex set is convex. v. The interior of a convex set is convex. vi. The cartesian product A_{1}×… A_{k} of convex sets A_{i} ⊆ R^{n_{i}}, 1 ≤ i ≤ k,

is a convex set in R^{n_{1}+...+n_{k}}.

24. Prove the equivalence of the following two definitions of the convex hull of a set A ⊆ R^{n}: a. conv(A) = ∩{C ⊆ R^{n} : C convex, C ⊇ A} . b. conv(A) = {α_{1}u^{(1)}+…+α_{k}u^{(k)} : α_{1}, …, α_{k} ≥ 0, α_{1}+…+α_{k} = 1} .

25. Prove that for any A ⊆ R^{n}, the set

A^{∗} = {v ∈ R^{n} : ⟨u, v⟩ ≤ 1}

is convex (where ⟨·, ·⟩ denotes the standard inner product on R^{n}).

26. Let A_{1} = V_{1} + u_{1} and A_{2} = V_{2} + u_{2} be two translates of linear subspaces V_{1} and V_{2} of R^{n}. When is A_{1} ∪ A_{2} a convex set?

27. i. Given points u^{(1)}, u^{(2)}, …, u^{(k)} and v in R^{n}, present the problem of determining whether or not v is a convex combination of the vectors u^{(i)} as a linear programming problem.

ii. Prove that if v is a convex combination of the vectors u^{(i)}, then it is can be represented as a convex combination of n + 1 (or less) of them.

Duality

28. i. Consider the production problem considered in class and the linear programming problem modeling it. Show that the dual problem may be interpreted as modeling a real-world problem, closely related to the original problem.

ii. Solve both the primal and the dual problem directly and explain your results.

iii. Same for the transportation problem considered in class.

29. Let x^{0} and y^{0} be optimal solutions of the primal and dual problems, respectively. Show that:

a. If x_{j}^{0} > 0, then (A^{t}y^{0})_{j} = c_{j}. b. If y_{i}^{0} > 0, then (Ax^{0})_{i} = b_{i}.

30. We proved that, if both the primal and the dual problems have feasible solutions, then any possible value of the objective function of the primal does not exceed any possible value of the objective function of the dual. Now, since the dual of the dual is the primal, any possible value of the objective function of the dual does not exceed any possible value of the objective function of the primal. Is it? Explain.

31. Suppose a constraint is added to the primal problem. What are the possible effects of the change on both the primal and the dual problems? Base your answer on simple considerations, and explain how they correspond to the theory.

32. Write down the dual of the linear programming problem of 14.iv. Solve the problem directly. How does your solution correspond to the solution obtained there and to the duality theorem?

33. Generalize the proof of the duality theorem to the case where some of the constant terms b_{i} may be negative. (Hint: Multiply by −1 those equations with negative b_{i}’s, add artificial variables, use the simplex method to drive the problem to a solution, and translate the final simplex table into corresponding equalities.)

34. Show that neither the following problem nor its dual have feasible solutions:

max x_{1}

subject to:

\begin{aligned}2x_{1} & − & 3x_{2} & ≤ & 6, \\ −3x_{1} & + & \frac{9}{2}x_{2} & ≤ & −18, \end{aligned}

x_{1}, x_{2} ≥ 0 .

The Distribution Problem

35. For each of the following distribution problems, either find a feasible solution or show that one does not exist:

i.

10 2 12 5 15
8 15 1 4 23
8 20 5 0 12
21 10 13 6

ii.

3 3 0 2 1 7
3 2 2 0 1 6
4 4 1 1 0 8
0 1 5 2 3 4
6 5 6 3 4

∞ ∞ ∞ 0 0 0 14
0 0 ∞ ∞ ∞ ∞ 10
∞ ∞ 0 0 ∞ ∞ 5
0 ∞ ∞ ∞ ∞ ∞ 5
6 7 2 12 3 4

iv.

10 5 5 0 5 5 5 5
15 6 4 3 9 0 5 5
0 3 5 10 10 3 0 18
0 8 10 10 1 4 8 30
4 2 10 8 5 2 2 26
20 19 14 21 10 12 20

36. Write a computer program implementing the algorithm presented in class for solving the distribution problem. Given supplies, demands and capacities, the output of the program should be either a feasible distribution schedule, or a text explaining why such a schedule does not exist.

37. Consider the following assignment problem. There are n individuals, each of whom needs to perform exactly one out of n given jobs. Each of the individuals is competent for some of the jobs. It is required to determine whether or not it is possible to assign the individuals to jobs, in such a way that all jobs will be performed, and if so – to provide such an assignment.

i. Formulate the problem as a distribution problem.

ii. Determine whether or not the following problem admits a feasible assignment. If yes – find one, otherwise – find sets R and C as in the theorem. (In the table, a “+” mark at the (i, j)th entry signifies that the individual I_{i} is able to perform job J_{j}, and a blank – that he is unable.)

J_{1} J_{2} J_{3} J_{4} J_{5} J_{6} J_{7} J_{8}
I_{1}  +  +
I_{2}  +  +
I_{3}  +  +  +
I_{4} +  + +
I_{5}  + +  +
I_{6} +  +
I_{7}  +  +  +
I_{8}  + +  + +

iii. Same for the following competence matrix:

J_{1} J_{2} J_{3} J_{4} J_{5} J_{6} J_{7} J_{8}
I_{1}  + +  +
I_{2}  +  +
I_{3}  + + + +
I_{4} + +  +  +
I_{5}  + +  +
I_{6}  + +
I_{7} +  + + +  + +
I_{8} +  +  + +

38. i. Explain the connection between the problem discussed in the preceding question and the following matching problem. A group of n boys and n girls is given, with some relation specifying which boys and girls know each other. It is required to find a matching between the boys and the girls, namely a 1-1 function from the set of boys onto that of the girls, taking each boy to a girl he knows.

ii. Prove the following (well-known) theorem. If, in the setup of the preceding part, for every 1 ≤ k ≤ n and every set of k boys, the boys in this set know jointly at least k girls, then there exists a matching between the boys and the girls. Note that the condition is obviously necessary. (Your proof should use the theory developed in class.)

iii. Consider the generalization whereby the number of girls is ln instead of n, and we wish to match to each of the boys l girls (distinct from those assigned to all other boys). Explain how this problem may be viewed as a distribution problem, and formulate and prove a necessary and sufficient condition for the existence of a feasible solution.

The Transportation Problem

39. Solve the following transportation problems:

i.

5 6 7 5 22
8 3 8 4 23
7 11 5 9 17
31 11 12 8

ii.

5 12 1 9 3 27
3 5 12 10 14 16
8 4 9 3 3 18
10 1 6 6 3 14
26 25 6 13 5

iii.

6 2 3 9 9 0 14
10 10 13 16 7 4 30
12 6 8 4 11 8 25
2 2 3 3 2 7 45
4 6 7 4 9 3 50
26 27 32 12 33 20

3 6 6 4 15 15 9 25
14 6 9 2 7 3 6 25
10 5 7 15 12 9 10 25
10 3 10 5 5 5 13 25
9 1 12 7 9 3 5 25
20 10 10 20 10 10 5

40. i. Solve the following transportation problem by first adding a fourth destination with demand equal to the surplus of 3 and 0 shipping costs to this destination:

6 4 5 9 8 3 2 16 8 8 6

ii. Show that, attempting to apply the transportation problem algorithm to the original data table, we obtain a distribution problem, some of whose feasible solutions are not optimal for the transportation problem.

41. i. Suppose a standard transportation problem with total supply equal to total demand has been solved, yielding some minimal cost shipping flow. Does the solution remain optimal if all costs c_{ij}, j = 1, 2, …, n, of shipping from source i to all destinations are changed by the same amount?

ii. Same if all costs c_{ij}, i = 1, 2, …, m, of shipping from all sources to destination j are changed by the same amount.

iii. Same as the preceding two parts in case the total supply exceeds the total demand.

42. Solve the following transportation problems, where infinite values of c_{ij} indicate that there is no route from source i to destination j, and negative values indicate (say) government subsidies:

8 3 -2 5 35
6 -3 7 ∞ 23
9 -1 ∞ 5 37
42 17 13 23

ii.

9 -2 ∞ 4 -3 47
4 -5 22 ∞ 21 36
10 2 ∞ -3 8 26
12 3 26 ∞ 13 41
29 45 26 14 29

43. i. Explain how you can solve by the transportation problem algorithm a transportation problem with total demand exceeding total supply, where all existing supply must be distributed. Exemplify on one of the transportation problems you solved in Problem 39 by reducing some of the available supply.

ii. Same if, in addition, there is a penalty of p_{j} per unit of unmet demand at destination j.

44. Explain how you can solve by the transportation problem algorithm a transportation problem in which the numbers c_{ij} are the net profits per unit shipped from each source to each destination. Exemplify on the data table of Problem 39.b.

45. Write a computer program implementing the algorithm presented in class for solving the transportation problem. Given supplies, demands and prices, the output of the program should be either a minimal cost transportation schedule (or an explanation why there is no feasible schedule).

Integer Programming

46. Consider the following problem:

max 9x_{1} + 2x_{2}

subject to:

\begin{aligned}5x_{1} & + & x_{2} & ≤ & 24, \\ x_{1} & + & 2x_{2} & ≤ & 20, \end{aligned}

x_{1}, x_{2} ≥ 0 and integral.

i. Find the optimal solution of the problem without the integral constraints graphically or by means of the simplex algorithm.

ii. Show that, replacing the value of each variable at the optimal point by its integer value, we obtain a feasible solution of the problem with integral constraints.

iii. Find the optimal solution of the problem with integral constraints. Show that its distance from the point obtained in part i is by far larger than that of the point obtained in part ii.

47. Formulate integer, or mixed integer, programming models for the following problems:

i. A manufacturer has L units of a product he may sell at n market. To be able to sell at the ith market, an initial cost of c_{i} is required. The demand at the ith market is d_{i}, and the expected profit per unit is p_{i}. Which markets should the manufacturer develop, and what amount should he sell in each so as to maximize profits?

ii. max 5x_{1} + 3x_{2} + x_{3} + 7x_{4}

subject to:

\begin{matrix}3x_{1} + 5x_{2} + x_{3} + 2x_{4} ≤ 27, \\ x_{1}, x_{2}, x_{3}, x_{4} ≥ 0 , \end{matrix}

and at least one of the following sets of constraints:

\{ \begin{matrix}2x_{1} & + & 3x_{2} & − & x_{3} & + & 7x_{4} & ≤ & 19, \\ 3x_{1} & + & 2x_{2} & + & 4x_{3} & − & 2x_{4} & ≤ & 14, \end{matrix}
\{ \begin{matrix}5x_{1} & − & 4x_{2} & − & 2x_{3} & − & 3x_{4} & ≥ & 23, \\ 5x_{1} & + & x_{2} & − & 7x_{3} & + & x_{4} & ≤ & 54 . \end{matrix}

48. Solve the following integer programming problems using Gomory’s Cutting Plane Algorithm:

i. max x_{1} + 2x_{2}

subject to:

\begin{aligned}x_{1} & + & x_{2} & ≤ & 12, \\ 4x_{1} & + & 7x_{2} & ≤ & 56, \\ x_{1} & + & 3x_{2} & ≤ & 21, \end{aligned}

x_{1}, x_{2} ≥ 0 and integral.

ii. max 2x_{1} + x_{2}

subject to:

\begin{aligned}x_{1} & − & 2x_{2} & ≥ & −6, \\ 3x_{1} & + & x_{2} & ≤ & 13, \end{aligned}

x_{1}, x_{2} ≥ 0 and integral. iii. max x_{1} − x_{2} subject to:

\begin{aligned}x_{1} & − & x_{2} & ≥ & −1, \\ 4x_{1} & + & 3x_{2} & ≤ & 6, \end{aligned}

x_{1}, x_{2} ≥ 0 and integral. iv. min 4x_{1} − x_{2} − 2x_{3} subject to:

\begin{aligned}x_{1} & & & − & x_{3} & ≥ & −12, \\ 2x_{1} & + & 3x_{2} & & & ≤ & 28, \end{aligned}

x_{1}, x_{2}, x_{3} ≥ 0 and integral. v. min 4x_{1} − x_{2} − 2x_{3} subject to:

\begin{aligned}x_{1} & & & − & x_{3} & = & −12, \\ 2x_{1} & + & 3x_{2} & & & = & 28, \end{aligned}

x_{1}, x_{2}, x_{3} ≥ 0 and integral.

49. Solve the following problems employing the Branch-and-bound Algorithm:

i. min x_{1} + 3x_{2} subject to:

\begin{aligned}2x_{1} & + & x_{2} & ≥ & 4, \\ 5x_{1} & + & x_{2} & ≥ & 8, \end{aligned}

x_{1}, x_{2} ≥ 0, x_{2} integer. ii. max x_{1} + 3x_{2} subject to:

\begin{aligned}x_{1} & + & 4x_{2} & ≤ & 7, \\ 2x_{1} & + & 5x_{2} & ≤ & 10, \end{aligned}

x_{1}, x_{2} ≥ 0, x_{1} integer. iii. max 21x_{1} + 12x_{2} + 32x_{3}

subject to:

\begin{aligned}5x_{1} & + & 3x_{2} & + & 9x_{3} & ≤ & 37, \\ 7x_{1} & + & 3x_{2} & + & 3x_{3} & ≤ & 14, \end{aligned}

x_{1}, x_{2} ≥ 0, x_{1} integer.

50. A parcel delivery company seeks to maximize its daily revenues. On a specific day, the delivery orders are for items of volumes 2, 3, 4, 6 and 8. The revenues for the deliveries are $10, $14, $31, $48 and $60, respectively. The available car can deliver a total volume of 11.

i. Use Branch-and-bound to find which items should be delivered.

ii. Use LINDO to verify your answer.

51. Consider the traveling salesman problem. Write a computer program which, given a matrix of distances representing a particular instance of the problem, translates the problem into the language of integer programminggskip.

Applications in Game Theory

52. Opine on the following definition of a fair game: A two-person zero-sum game is fair if the sum of all entries of the payoff matrix is 0.

53. Show that few matrices admit saddle points, as follows:

i. Write a computer program which, given m and n, finds (approximately) the probability that a random m × n payoff matrix contains a saddle point. Here, by a random matrix we mean a matrix whose entries are chosen independently from any continuous distribution. (You may take the uniform distribution on [0, 1], for example.)

ii. (requires Probability Theory) Calculate the probability in question. In particular, show that it descends to 0 as max{m, n} → ∞ (and min{m, n} ≥ 2).

54. Show that, if the payoff matrix of a game is anti-symmetric (i.e., satisfies A^{t} = −A), then the value of the game is 0.

55. i. Show that, if the sum of the entries in each column of the payoff matrix is non-negative, then the value of the game is non-negative as well.

ii. Show that, if the sum of the entries in each row and each column of the payoff matrix is 0, then the value of the game is 0 fair.

56. Let v be the value of a game, y^{0} an optimal strategy for P_{2}, and x^{0} a strategy for P_{1} such that x^{0}^{t}Ay^{0} = v. Is x^{0} necessarily an optimal strategy for P_{1}?

57. Let A and B be m × n matrices, considered as payoff matrices of two games. Prove or disprove: The value of the game whose payoff matrix is A + B depends only on the values of the two initial games.

58. Solve the games with the following payoff matrices:

i. ( \begin{matrix}2 & 7 \\ 4 & 3 \end{matrix} )

ii. ( \begin{matrix}6 & 4 & 3 \\ 2 & 8 & 9 \end{matrix} )

iii. ( \begin{matrix}9 & 5 & −3 & 4 \\ −2 & −1 & 8 & 6 \end{matrix} )

iv. ( \begin{matrix}−4 & 2 \\ 3 & 0 \\ 5 & −6 \\ 2 & 1 \end{matrix} )

v. ( \begin{matrix}0 & 8 & −3 & −2 \\ 5 & 2 & 4 & −5 \\ −1 & 4 & 6 & 9 \end{matrix} )

59. If a payoff matrix contains a dominated row or column, then that row or column may be deleted without changing the (reasonable) options of the players. Show that “usually” only few matrices contain such rows or columns, as follows:

i. Write a computer program which, given m and n, finds (approximately) the probability that a random m×n payoff matrix contains a dominated row or column.

ii. (requires Probability Theory) Find an upper bound on the probability in question. This bound should show, in particular, that this probability descends to 0 as min{m, n} → ∞ in such a way that m and n are not “very far” apart. (For example, the condition C_{1}n ≤ m ≤ C_{2}n for arbitrary fixed constants C_{1}, C_{2} > 0 is sufficient.)