Matching pennies. In this simple two-player game, the players (call them R and C) each

Consider the following linear program. maximize 5x + 3y \(\begin{array}{r} 5 x-2 y \geq 0 \\ x+y \leq 7 \\ x \leq 5 \\ x \geq 0 \\ y \geq 0 \end{array}\) Plot the feasible region and identify the optimal solution.

Duckwheat is produced in Kansas and Mexico and consumed in New York and California. Kansas produces 15 shnupells of duckwheat and Mexico 8. Meanwhile, New York consumes 10 shnupells and California 13. The transportation costs per shnupell are $4 from Mexico to New York, $1 from Mexico to California, $2 from Kansas to New York, and $3 and from Kansas to California. Write a linear program that decides the amounts of duckwheat (in shnupells and fractions of a shnupell) to be transported from each producer to each consumer, so as to minimize the overall transportation cost.

A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, upto the maximum available limits given below. Material 1 has density 2 tons/cubic meter, maximum available amount 40 cubic meters, and revenue $1,000 per cubic meter. Material 2 has density 1 ton/cubic meter, maximum available amount 30 cubic meters, and revenue $1,200 per cubic meter. Material 3 has density 3 tons/cubic meter, maximum available amount 20 cubic meters, and revenue $12,000 per cubic meter. Write a linear program that optimizes revenue within the constraints.

Moe is deciding how much Regular Duff beer and how much Duff Strong beer to order each week. Regular Duff costs Moe $1 per pint and he sells it at $2 per pint; Duff Strong costs Moe $1.50 per pint and he sells it at $3 per pint. However, as part of a complicated marketing scam, the Duff company will only sell a pint of Duff Strong for each two pints or more of Regular Duff that Moe buys. Furthermore, due to past events that are better left untold, Duff will not sell Moe more than 3,000 pints per week. Moe knows that he can sell however much beer he has. Formulate a linear program for deciding how much Regular Duff and how much Duff Strong to buy, so as to maximize Moes profit. Solve the program geometrically

The Canine Products company offers two dog foods, Frisky Pup and Husky Hound, that are made from a blend of cereal and meat. A package of Frisky Pup requires 1 pound of cereal and1.5 pounds of meat, and sells for $7. A package of Husky Hound uses 2 pounds of cereal and1 pound of meat, and sells for $6. Raw cereal costs $1 per pound and raw meat costs $2 per pound. It also costs $1.40 to package the Frisky Pup and $0.60 to package the Husky Hound. A total of 240,000 pounds of cereal and 180,000 pounds of meat are available each month. The only production bottleneck is that the factory can only package 110,000 bags of Frisky Pup per month.Needless to say, management would like to maximize profit. (a) Formulate the problem as a linear program in two variables. (b) Graph the feasible region, give the coordinates of every vertex, and circle the vertex maximizing profit. What is the maximum profit possible?

Give an example of a linear program in two variables whose feasible region is infinite, but such that there is an optimum solution of bounded cost

Find necessary and sufficient conditions on the reals a and b under which the linear program max x + y ax + by 1 x, y 0 (a) Is infeasible. (b) Is unbounded. (c) Has a unique optimal solution

You are given the following points in the plane: (1, 3), (2, 5), (3, 7), (5, 11), (7, 14), (8, 15), (10, 19). You want to find a line ax + by = c that approximately passes through these points (no line is a perfect fit). Write a linear program (you don’t need to solve it) to find the line that minimizes the maximum absolute error, \(\max _{1 \leq i \leq 7}\left|a x_{i}+b y_{i}-c\right| .\)

A quadratic programming problem seeks to maximize a quadratric objective function (with terms like 3x 2 1 or 5x1x2) subject to a set of linear constraints. Give an example of a quadratic program in two variables x1, x2 such that the feasible region is nonempty and bounded, and yet none of the vertices of this region optimize the (quadratic) objective.

For the following network, with edge capacities as shown, find the maximum flow from S to T, along with a matching cut.

Write the dual to the following linear program. \(\begin{array}{r} \max x+y \\ 2 x+y \leq 3 \\ x+3 y \leq 5 \\ x, y \geq 0 \end{array}\)

For the linear program \(\begin{array}{r} \max x_{1}-2 x_{3} \\ x_{1}-x_{2} \leq 1 \\ 2 x_{2}-x_{3} \leq 1 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}\) prove that the solution \(\left(x_{1}, x_{2}, x_{3}\right)=(3 / 2,1 / 2,0)\) is optimal.

Matching pennies. In this simple two-player game, the players (call them R and C) each choose an outcome, heads or tails. If both outcomes are equal, C gives a dollar to R; if the outcomes are different, R gives a dollar to C. (a) Represent the payoffs by a 2 2 matrix. (b) What is the value of this game, and what are the optimal strategies for the two players?

The pizza business in Little Town is split between two rivals, Tony and Joey. They are each investigating strategies to steal business away from the other. Joey is considering either lowering prices or cutting bigger slices. Tony is looking into starting up a line of gourmet pizzas, or offering outdoor seating, or giving free sodas at lunchtime. The effects of these various strategies are summarized in the following payoff matrix (entries are dozens of pizzas, Joeys gain and Tonys loss). For instance, if Joey reduces prices and Tony goes with the gourmet option, then Tony will lose 2 dozen pizzas worth of business to Joey. What is the value of this game, and what are the optimal strategies for Tony and Joey?

Find the value of the game specified by the following payoff matrix. (Hint: Consider the mixed strategies (1/3, 0, 0, 1/2, 1/6, 0, 0) and (2/3, 0, 0, 1/3).)

A salad is any combination of the following ingredients: (1) tomato, (2) lettuce, (3) spinach, (4) carrot, and (5) oil. Each salad must contain: (A) at least 15 grams of protein, (B) at least 2 and at most 6 grams of fat, (C) at least 4 grams of carbohydrates, (D) at most 100 milligrams of sodium. Furthermore, (E) you do not want your salad to be more than 50% greens by mass. The nutritional contents of these ingredients (per 100 grams) are ingredient energy protein fat carbohydrate sodium (kcal) (grams) (grams) (grams) (milligrams) tomato 21 0.85 0.33 4.64 9.00 lettuce 16 1.62 0.20 2.37 8.00 spinach 371 12.78 1.58 74.69 7.00 carrot 346 8.39 1.39 80.70 508.20 oil 884 0.00 100.00 0.00 0.00 Find a linear programming applet on the Web and use it to make the salad with the fewest calories under the nutritional constraints. Describe your linear programming formulation and the optimal solution (the quantity of each ingredient and the value). Cite the Web resources that you used.

Consider the following network (the numbers are edge capacities). (a) Find the maximum flow f and a minimum cut. (b) Draw the residual graph Gf (along with its edge capacities). In this residual network, mark the vertices reachable from S and the vertices from which T is reachable. (c) An edge of a network is called a bottleneck edge if increasing its capacity results in an increase in the maximum flow. List all bottleneck edges in the above network. (d) Give a very simple example (containing at most four nodes) of a network which has no bottleneck edges. (e) Give an efficient algorithm to identify all bottleneck edges in a network. (Hint: Start by running the usual network flow algorithm, and then examine the residual graph.)

There are many common variations of the maximum flow problem. Here are four of them. (a) There are many sources and many sinks, and we wish to maximize the total flow from all sources to all sinks. (b) Each vertex also has a capacity on the maximum flow that can enter it. (c) Each edge has not only a capacity, but also a lower bound on the flow it must carry. (d) The outgoing flow from each node u is not the same as the incoming flow, but is smaller by a factor of (1 u), where u is a loss coefficient associated with node u. Each of these can be solved efficiently. Show this by reducing (a) and (b) to the original max-flow problem, and reducing (c) and (d) to linear programming.

Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine whether the solution does indeed give a maximum flow.

Consider the following generalization of the maximum flow problem. You are given a directed network G = (V, E) with edge capacities {ce}. Instead of a single (s,t) pair, you are given multiple pairs (s1,t1),(s2,t2), . . . ,(sk,tk), where the si are sources of G and the ti are sinks of G. You are also given k demands d1, . . . , dk. The goal is to find k flows f (1) , . . . , f (k) with the following properties: f (i) is a valid flow from si to ti . For each edge e, the total flow f (1) e + f (2) e + + f (k) e does not exceed the capacity ce. The size of each flow f (i) is at least the demand di . The size of the total flow (the sum of the flows) is as large as possible. How would you solve this problem?

An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that finds a critical edge in a network.

In a particular network G = (V, E) whose edges have integer capacities \(c_e\), we have already found the maximum flow f from node s to node t. However, we now find out that one of the capacity values we used was wrong: for edge (u, v) we used \(c_{uv}\) whereas it should have been \(c_{u v}-1\). This is unfortunate because the flow f uses that particular edge at full capacity: \(f_{uv}\) = \(c_{uv}\). We could redo the flow computation from scratch, but there’s a faster way. Show how a new optimal flow can be computed in O(|V|+|E |) time.

A vertex cover of an undirected graph G = (V, E ) is a subset of the vertices which touches every edge-that is, a subset \(S \subset V\) such for that edge \(\{u, v\} \in E\), one or both of u, v are in S. Show that the problem of finding the minimum vertex cover in a bipartite graph reduces to maximum flow. (Hint: Can you relate this problem to the minimum cut in an appropriate network?)

Direct bipartite matching. We’ve seen how to find a maximum matching in a bipartite graph via reduction to the maximum flow problem. We now develop a direct algorithm. Let \(G=\left(V_{1} \cup V_{2}, E\right)\) be a bipartite graph (so each edge has one endpoint in \(V_1\) and one endpoint in \(V_2\)), and let \(M \in E\) be a matching in the graph (that is, a set of edges that don’t touch). A vertex is said to be covered by M if it endpoint of one of the edges in M. An alternating path is a path of odd length that starts and ends with a non-covered vertex, and whose edges alternate between M and E ? M. (a) In the bipartite graph below, a matching M is shown in bold. Find an alternating path. (b) Prove that a matching M is maximum if and only if there does not exist an alternating path with respect to it. (c) Design an algorithm that finds an alternating path in O(|V|+|E |) time using a variant of breadth-first search. (d) Give a direct \(O(|V| \cdot|E|)\) algorithm for finding a maximum matching in a bipartite graph.

The dual of maximum flow. Consider the following network with edge capacities. (a) Write the problem of finding the maximum flow from S to T as a linear program. (b) Write down the dual of this linear program. There should be a dual variable for each edge of the network and for each vertex other than S, T.

In a satisfiable system of linear inequalities a11x1 + + a1nxn b1 . . . am1x1 + + amnxn bm we describe the jth inequality as forced-equal if it is satisfied with equality by every solution x = (x1, . . . , xn) of the system. Equivalently, P i ajixi bj is not forced-equal if there exists an x that satisfies the whole system and such that P i ajixi < bj . For example, in x1 + x2 2 x1 x2 2 x1 1 x2 0 the first two inequalities are forced-equal, while the third and fourth are not. A solution x to the system is called characteristic if, for every inequality I that is not forced-equal, x satisfies I without equality. In the instance above, such a solution is (x1, x2) = (1, 3), for which x1 < 1 and x2 < 0 while x1 + x2 = 2 and x1 x2 = 2. (a) Show that any satisfiable system has a characteristic solution. (b) Given a satisfiable system of linear inequalities, show how to use linear programming to determine which inequalities are forced-equal, and to find a characteristic solution.

Show that the change-making problem (Exercise 6.17) can be formulated as an integer linear program. Can we solve this program as an LP, in the certainty that the solution will turn out to be integral (as in the case of bipartite matching)? Either prove it or give a counterexample.

A linear program for shortest path. Suppose we want to compute the shortest path from node s to node t in a directed graph with edge lengths \(l_{e}>0\). (a) Show that this is equivalent to finding an s - t flow f that minimizes \(\sum_{e} l_{e} f_{e}\) subject to size( f) = 1. There are no capacity constraints. (b) Write the shortest path problem as a linear program. (c) Show that the dual LP can be written as \(\begin{array}{l}\max x_{s}-x_{t}\\x_{u}-x_{v} \leq l_{u v} \text{ for all } (u, v) \in E\end{array}\) (d) An interpretation for the dual is given in the box on page 223. Why isn't our dual LP identical to the one on that page?

Hollywood. A film producer is seeking actors and investors for his new movie. There are n available actors; actor i charges si dollars. For funding, there are m available investors. Investor j will provide pj dollars, but only on the condition that certain actors Lj {1, 2, . . . , n} are included in the cast (all of these actors Lj must be chosen in order to receive funding from investor j). The producers profit is the sum of the payments from investors minus the payments to actors. The goal is to maximize this profit. (a) Express this problem as an integer linear program in which the variables take on values {0, 1}. (b) Now relax this to a linear program, and show that there must in fact be an integral optimal solution (as is the case, for example, with maximum flow and bipartite matching).

Halls theorem. Returning to the matchmaking scenario of Section 7.3, suppose we have a bipartite graph with boys on the left and an equal number of girls on the right. Halls theorem says that there is a perfect matching if and only if the following condition holds: any subset S of boys is connected to at least |S| girls. Prove this theorem. (Hint: The max-flow min-cut theorem should be helpful.)

Consider the following simple network with edge capacities as shown