7 Linear Programming and Reductions
Ex.7.1
The maximum value of 31 is achieved at x = 5, y = 2 (figure omitted).
Ex.7.2
Let x be the amount of buckwheat shipped from Kansas to New York and 15 - x the amount
shipped from Kansas to California. Let y be the amount shipped from Mexico to New York and 8
- y the amount shipped from Mexico to California. This gives us the following linear
programming problem:
minimize 2x + 3(15-x) + y + 4(8-y)
subject to:
x + y = 10
x, y ≥ 0
We can easily solve to find the minimum shipping cost is 43, occurring when x = 10, y = 0.
Ex.7.3
Let x, y, and z be the cubic meters of material 1, material 2, and material 3 carried, respectively.
This gives us the LP:
maximize 1000x + 1200y + 12000z
subject to:
x + y + z ≤ 60
2x + 3y + z ≤ 100 harusnya 2x + y + 3z <= 100
0 ≤ x ≤ 40
0 ≤ y ≤ 30
0 ≤ z ≤ 20
The maximum value of 296000 is achieved when x = 0, y = 30, z = 20.
Ex.7.4
Let x be Regular Duff and y be Duff Strong. This gives us the LP:
maximize x + 1.5y
subject to:
x - 2y ≥ 0
x + y ≤ 3000
x, y ≥ 0
The maximum value of 3500 is achieved when x = 2000, y = 1000. P.S. It seems this problem
should have one more constraint.
Ex.7.5
a) Let x be Frisky Pup and y be Husky Hound. This gives us the LP:
maximize (7×1-1×2-1.5×1-4×6) + (1×2-2×1-0.6)y
subject to:
2x + 1.5y ≤ 240000
1.5x + y ≤ 180000
x ≤ 110000
x, y ≥ 0
b) Figure omitted. The maximum profit is 222000, achieved when x = 60000, y = 90000.
Ex.7.6
For example, consider this LP:
maximize y - 2x
subject to:
x ≥ 100
y≤x
x, y ≥ 0
The maximum value of 100 is achieved when x = 100, y = 100.
Ex.7.7
a) For any a and b, the LP is always feasible.
b) ab = 0.
c) ab ≠ 0, a ≠ b.
Ex.7.8
In addition to a, b, c, we add 8 more variables: ei for 1 ≤ i ≤ 7 and me, representing absolute error
at each sampling point and the maximum absolute error, respectively. This gives the LP:
minimize me
subject to:
for i = 1,...,7:
ei ≥ axi + byi - c
ei ≥ -(axi + byi - c)
me ≥ ei
Ex.7.9
For example, consider this simple problem:
maximize xy
subject to:
x + y ≤ 10
x, y ≥ 0
By the geometric mean inequality, xy reaches its maximum value of 25 when x = y = 5.
Ex.7.10
The maximum flow is 13, and the corresponding minimum cut is ({S,C,F,A,B,D,E,G,T}, {}).
Ex.7.11
The dual LP is:
minimize 3s + 5t
subject to:
2s + t ≥ 1
s + 3t ≥ 1
s, t ≥ 0
The optimal value is 2.2, achieved when x = 0.8, y = 1.4 (primal problem) or s = 0.4, t = 0.2
(dual problem).
Ex.7.12
1 + 3x1 ⇒ -x2 ≤ 1/2 - 3/2x1, and since x3 ≥ 0, we have -x2 ≤ x3 - 3x1 ≤ 1/2 - 3/2x1.
Ex.7.13
a) Omitted.
b) Let the strategies for R and C be {x1, x2} and {y1, y2}, where x1, y1 are the probabilities of
choosing heads, and x2, y2 are the probabilities of choosing tails. This gives us the following LP
and its dual:
max z min w
s.t. z ≤ x1 - x2 s.t. w ≥ y1 - y2
z ≤ -x1 + x2 w ≥ -y1 + y2
x1 + x2 = 1 y1 + y2 = 1
x1, x2 ≥ 0 y1, y2 ≥ 0
It's easy to see that the value of this game is 0, and the optimal strategy is {x1, x2} = {y1, y2} =
{1/2, 1/2}.
Ex.7.14
Let Joey's and Tony's strategies be {x1, x2} and {y1, y2, y3}, respectively. We have these LPs:
max z min w
s.t. z ≤ 2x1 - x2 s.t. w ≥ 2y1 - y3
z ≤ -2x1 w ≥ -2y1 - y2 + y3
z ≤ -x1 + 3x2 y1 + y2 + y3 = 1
x1 + x2 = 1 y1, y2, y3 ≥ 0
x1, x2 ≥ 0
The solution is that the value of the game is -1, and the optimal strategies are {x1, x2} = {1/2,
1/2}, {y1, y2, y3} = {0, 2/3, 1/3}.
Ex.7.15
Using LINGO to solve, we get value = -1/3.
Ex.7.16
We set up the model in LINGO as follows:
min = cal;
cal = t*21 + l*16 + s*371 + c*346 + o*884;
t*0.85 + l*1.62 + s*12.78 + c*8.39 >= 15;
t*0.33 + l*0.2 + s*1.58 + c*1.39 + o*100 >= 2;
t*0.33 + l*0.2 + s*1.58 + c*1.39 + o*100 <= 6;
t*4.64 + l*2.37 + s*74.69 + c*80.7 >= 4;
t*9 + l*8 + s*7 + c*508.2 <= 100; l + s <= t + c + o;
Note that in LINGO all variables are assumed to be non-negative by default, so no need to add
non-negativity constraints. The optimal solution is {t, l, s, c, o} = {5.88, 5.84, 0.04, 0, 0}, in
units of 100 grams, with a calorie value of 232.5 kilocalories.
Ex.7.17
a) The maximum flow is 11, and the corresponding minimum cut is ({S, A, B}, {C, D, T}).
b) Figure omitted. The set of nodes reachable from S is {A, B}, and the set of nodes that can
ini si china salah pengertian yg ditanya bukan nodes that can reach T but nodes from
reach T is {S, A, B, C, D}. which T is reachable so T = {C}
c) The bottleneck edges are: e(A, C) and e(B, C).
d) Omitted.
e) Let the original graph be G(V, E) and the residual graph be R(V, F). Then a bottleneck edge
e(i, j) has the following properties: e(i, j) ∈ E, and in the residual graph R, S → i and j → T
(where S → i means there exists a path from vertex S to i, and similarly for j → T). Thus, adding
e(i, j) to R would form an augmenting path, thereby increasing the maximum flow. Based on
these properties, all bottleneck edges can be found in linear time using the following steps: First,
perform DFS in the residual graph R with S as the source to find the set I of vertices reachable
from S; then perform DFS in the reverse graph RT with T as the source to find the set J of
vertices that can reach T; finally, traverse the edge set E, and for any edge e(i, j), if i ∈ I and j ∈
J, then e(i, j) is a bottleneck edge.
Ex.7.18
a) Add a new vertex S connected to all original sources, and a new vertex T with all original
sinks connected to it, then find the maximum flow from S to T. Of course, the capacities of these
newly added edges must be sufficiently large, which can be set to INFINITE.
b) Split each vertex v into two vertices v1 and v2, add an edge e(v1, v2), and set the capacity of
e(v1, v2) to the original capacity of vertex v. Then change edges ending at v in the original graph
to end at v1, and edges starting from v to start from v2. After this processing, it becomes a
standard maximum flow problem.
c) Add one more constraint for each edge in the LP model.
d) Modify the flow conservation constraints accordingly.
Ex.7.19
First, from the given maximum flow solution, we can easily obtain the residual graph R(V, F),
then perform DFS in R with S as the source: if there exists a directed path S → T, according to
the augmenting path theorem, we can definitely construct a larger flow; otherwise, the solution is
indeed optimal.
Ex.7.20
Associate k variables f(1)e, f(2)e, ..., f(k)e with each edge, where f(i)e represents the flow on
edge e originating from source si. Then the size of flow f(i) is the sum of all branches starting
from si and converging at ti, which is Σ(u,ti)∈E f(i)(u,ti). We can establish the LP:
maximize Σi f(i)
subject to:
∀e∈E: f(1)e + f(2)e + ... + f(k)e ≤ ce
∀v∈V: Σ(u,v)∈E f(i)(u,v) = Σ(v,w)∈E f(i)(v,w)
f(i) = Σ(u,ti)∈E f(i)(u,ti) ≥ di
f(i)e ≥ 0
Ex.7.21
First, find the maximum flow and construct the residual graph R(V, F). Clearly, the capacity of a
"critical edge" e(i, j) must be fully utilized, which means that in the residual graph R, there is
only a reverse edge between vertices (i, j), i.e., e(j, i) ∈ F, e(i, j) ∉ F. However, not all vertex
pairs with only reverse edges in the residual graph are critical edges, so we need to eliminate
those that are not critical edges using the following method: Perform DFS in R with S as the
source, and let the set of reverse edges traversed be E'. Then for all e(j, i) ∈ E', (i, j) is definitely
not a critical edge (Why? Draw a picture and you'll understand). So, if the set of all vertex pairs
with only reverse edges in the residual graph is L, and the set of vertex pairs corresponding to the
edge set E' obtained after DFS is U, then C = L - U is the set of critical edges we're looking for.
Ex.7.22
Based on Ex.7.21, we know that with the maximum flow known, we can determine whether an
edge is a critical edge in linear time. So, if e(u, v) is not a critical edge, then the modified
maximum flow f' = f, otherwise f' = f - 1.
Ex.7.23
Consider a bipartite graph G(U, E, V), where vertex sets U and V are disjoint. Let the minimum
vertex cover of graph G be C, and set L = U ∩ C, R = V ∩ C, M = U - L, N = V - R. After
adding a source S and a sink T, we get the flow network as shown below:
[Description of the bipartite graph diagram]
In the diagram above, since L ∪ R is the minimum vertex cover, there are no edges from M to
N. Now observe the part marked with shadows in the diagram; it forms a cut (S ∪ M ∪ R, L ∪
N ∪ T) with the rest of the graph. It's easy to see that the number of cut edges in this cut is
exactly equal to the number of vertices in the minimum vertex cover. So finding the minimum
vertex cover L ∪ R is transformed into finding the minimum cut (S ∪ M ∪ R, L ∪ N ∪ T).
Moreover, this also shows that in a bipartite graph, the number of vertices in the minimum vertex
cover equals the number of edges in the maximum matching, because their flow models are
exactly the same. PS. We can also prove this from another perspective: Let the number of
vertices in the minimum vertex cover C be m, and the number of edges in the maximum
matching be n. First, from the properties of matching, it's easy to know that m ≥ n. Looking back
at the figure above, we can see that for any k vertices in L, they must be connected to at least k
vertices in N. Otherwise, we could find fewer than k vertices in N to replace the k vertices in L,
thereby getting a smaller vertex cover. Similarly, any k vertices in R must be connected to at
least k vertices in M. By Hall's theorem, we know that this means a vertex cover of size m must
correspond to a matching of size m, so n ≥ m. Thus, m = n, which proves the statement.
Ex.7.24
a) For example, the path D → F → B → E → A → H → C → I.
b) If there exists an alternating path P, let PM be the set of edges in P that belong to M, and PNM
be the set of edges in P that do not belong to M. By the definition of an alternating path, edges in
PNM are exactly one more than edges in PM, i.e., |PNM| - |PM| = 1. So in M, replacing PM with
PNM would construct a matching with one more edge than the original. This proves that there
cannot exist an alternating path in a maximum matching, but this only proves one direction of the
proposition. We also need to prove that if matching M does not have an alternating path, it must
be a maximum matching. Note that an alternating path is actually equivalent to an augmenting
path in the maximum flow model: If M has no alternating path, then there is no augmenting path
in the residual graph R of M in the flow model, which means M must be a maximum matching.
c) First, to ensure the alternating property of the alternating path, all edges need to be directed.
For any edge e(i, j) ∈ E, if e(i, j) ∉ M, then the direction is set as i → j, otherwise the direction is
set as j → i (the graph obtained after this processing is actually the residual graph of matching M
in the flow model). Then perform BFS starting from the set of unmatched vertices in V1, and if a
vertex in V2 that is not covered by M is visited, an alternating path is found.
d) Iteratively search for alternating paths, and each time an alternating path is found, the size of
M increases by 1. Since |M| ≤ min(|V1|, |V2|), the maximum number of iterations is min(|V1|,
|V2|). Since each iteration takes O(|V| + |E|) time, the total time complexity is O(min(|V1|, |V2|) ·
(|V| + |E|)).
Ex.7.25
a) From the given flow network, we get the LP and its dual LP as follows:
max fSA + fSB min 3y1 + 2y2 + y3 + y4 + y5
s.t. fSA - fAB - fAT = 0 s.t. y1 + y6 ≥ 1
fSB + fAB - fBT = 0 y2 + y7 ≥ 1
fSA ≤ 1 y3 - y6 + y7 ≥ 0
fSB ≤ 2 y4 - y6 ≥ 0
fAB ≤ 3 y5 - y7 ≥ 0
fAT ≤ 1 y1, y2, y3, y4, y5, y6, y7 ≥ 0
fBT ≤ 2
fSA, fSB, fAB, fAT, fBT ≥ 0
b) As above, using LINGO, we can solve to find that both have an optimal value of 2.
c) Let me write out the answer first; as for why it takes this form, you'll understand after the next
two questions:
min Σe∈E ceye
s.t. ∀e(s,u)∈E: ys + yu ≥ 1
∀e(u,t)∈E: yu + yt ≥ 1
∀e(u,v)∈E, u≠s, v≠t: yu - yv + ye ≥ 0
d) If a path is s → u1 → u2 → ... → un → t, then from the LP above, we have:
ys + yu1 ≥ 1
yu1 - yu2 + y(u1,u2) ≥ 0
yu2 - yu3 + y(u2,u3) ≥ 0
...
yun - yt + y(un,t) ≥ 0
Adding all these inequalities gives ys + y(s,u1) + y(u1,u2) + ... + y(un,t) - yt ≥ 1.
e) Let a cut in the flow network be (L, R), where s ∈ L, t ∈ R. Then the meaning of these
variables can be: For an edge e, if ye = 1, it indicates that e is an edge from L to R; for a vertex u,
yu = 1 indicates that u ∈ L, and yu = 0 indicates that u ∈ R. It's easy to observe that when these
variables are assigned such meanings, they indeed correspond to the constraints in the dual LP,
and the objective function is exactly to find the minimum cut.
Ex.7.26
a) First, we need to clarify that since all constraints are linear, each constraint corresponds to a
half-space, and these half-spaces together form the feasible region, which must be convex. This
means that if {x} and {y} are both feasible solutions, then any point {z} = ω{x} + (1-ω){y} on
the line connecting them is also a feasible solution. Now, let the not forced-equal inequalities in
the satisfiable system S be ie1, ie2, ie3, ..., ie4. By the definition of not forced-equal inequalities,
there must exist a solution {x1} such that ie1 is not at equality, and similarly, there exist {x2},
{x3}, ..., {xn} such that ie2, ie3, ..., ie4 are not at equality, respectively. We can take {xa} as the
arithmetic mean of {x1}, {x2}, ..., {xn}. By the previous conclusion, {xa} is also a solution to S,
and it's easy to see that {xa} can make ie1, ie2, ..., ien all not at equality, which proves the
statement.
b) Add a variable bi (with bi ≥ 0) to the left side of the i-th inequality, and establish an LP with
the objective function to maximize Σbi. Since this LP might be unbounded, we can add the
constraint bi ≤ ci, where ci is some positive constant. If bi = 0 in the optimal solution, then the
i-th inequality is forced-equal; otherwise, it's not forced-equal (to be proven).
Ex.7.27
Let ci be the number of coins with value xi used. This gives us the integer linear programming
problem:
minimize Σxici
subject to:
Σxici ≥ v
ci ≥ 0
Of course, we can't use a general LP model to solve this, as that would likely give a fractional
solution that has no meaning.
Ex.7.28
a) Let the shortest path length be s. We need to prove that s ≤ Σlefe, and that equality can be
achieved in some cases. We know that f can be decomposed into one or more paths p1, p2, p3, ...,
pn (see Ex.7.31.c). Since size(f) = 1, this means that Σlefe is not less than some weighted average
of the lengths of these paths, and since these paths are not shorter than s, we can deduce that s ≤
Σlefe. Moreover, if we take the shortest path as the flow path, then s = Σlefe, which shows that
equality can be achieved in the inequality above.
b) Just write it out as follows:
min Σlefe
s.t. Σ(s,u)∈E fsu = 1
Σ(v,t)∈E fvt = 1
∀u∈V, u≠s, u≠t:
Σ(w,u)∈E fwu - Σ(u,v)∈E fuv = 0
∀e∈E: fe ≥ 0
c) Note that in the LP above, apart from the final fe ≥ 0, each vertex corresponds to one
constraint, for a total of |V| constraints. For each vertex v ∈ E, multiply the constraint
corresponding to that vertex by a coefficient xv, and then add all the constraint equations to get
Σ(u,v)∈E (xu - xv)fuv = xs - xt. Relating this to the objective function min Σlefe in the LP
above, it's easy to see that its dual LP is as shown in the problem.
d) This problem is about finding the shortest path in a directed graph, whereas the previous one
was about finding the shortest path in an undirected graph.
Ex.7.29
a) Use xi to represent whether to hire actor i, and yj to represent whether to get funding from
boss j. This gives us the ILP:
maximize Σj yj - Σi pjxi
subject to:
for j ∈ [1,n]:
yj ≤ Σi∈Lj xi
xi, yj ∈ {0,1}
b) Here we only need to explain that for any non-integer solution, there exists a better integer
solution. Since yi is determined by xi (in the optimal case), we only need to consider xi. First, if
all non-integer solutions xi are less than 1, and if the current profit is negative, then setting xi = 0
would give a better integer solution. Otherwise, if the current profit is positive, let r = max xi;
obviously 0 < r < 1. Now we multiply each xi by a scaling factor 1/r to get a new solution x'i.
Note that in this new solution, some elements become 1. It's easy to see that the profit
corresponding to x'i is also 1/r times the profit corresponding to xi, because the new y'i can also
be increased to 1/r times the original. So x'i is better than xi. Now consider the case where some
elements of xi are 1. Let f = max{xi | xi < 1}. Then either multiplying all elements of xi that are
less than one by a scaling factor 1/f, or setting all elements of xi that are less than one to 0,
whichever is better, will give a better solution x'i (the detailed derivation is omitted here).
Through the above explanation, we know that for any non-integer solution, after several
transformations like these, we can eventually get a better integer solution.
Ex.7.30
The necessity of the condition is obvious: if there exists a perfect matching, then any subset S of
boys must be connected to at least |S| different girls, otherwise a girl would have to be matched
with multiple boys. Now let's prove the sufficiency: if any subset S of boys is connected to at
least |S| different girls, then there must exist a perfect matching. Consider any cut (L, R) in the
flow model of this bipartite matching, where s ∈ L, t ∈ R. Suppose there are b boys and g girls
in L, so there are n - b boys and n - g girls in R. Thus, s is connected to all n - b boys in R, and all
g girls in L are connected to t. Furthermore, the b boys in L are connected to at least b girls in
total. Excluding the g girls in L, these b boys are connected to at least b - g girls in R. Adding up
all these connecting edges, we get that the number of forward edges between this cut (L, R) is at
least (n - b) + g + (b - g) = n. Since this cut is arbitrary, this indicates that any cut is at least n. By
the max-flow min-cut theorem, the maximum flow of this model is n, which means there must
exist a perfect matching.
Ex.7.31
a) The Ford-Fulkerson algorithm finds the maximum flow by searching for augmenting paths in
the residual graph (it seems that the book doesn't mention the name of this algorithm). If the first
augmenting path found is S → A → B → T, and the next is S → B → A → T, then each time
only one augmenting path with a flow of 1 is found, requiring a total of 2000 iterations.
b) Similar to Ex.4.13, here we can use Dijkstra's algorithm based on the fact that if a path s → r
→ t → ... has capacity c, then the path s → r → ... must have capacity greater than or equal to c.
Now we modify Dijkstra's algorithm. Let cp(v) represent the maximum capacity value of all
paths from s to v. First initialize all cp(v) to 0, then modify the update process as follows:
for all edges (u,v) ∈ E:
if cp(v) < min(cp(u), c(u,v))
cp(v) = min(cp(u), c(u,v))
c) Consider a minimum cut. It's easy to see that each cut edge e corresponds exactly to a path pe
such that pe passes through edge e, and the flow on pe equals c(e). These pe together make up
the maximum flow. Because the number of cut edges cannot exceed |E|, we know that the
maximum flow can be composed of no more than |E| paths.
d) Since the maximum flow F can be composed of no more than |E| paths, the "fattest" path must
have a flow no less than F/|E|. Let ct be the maximum flow in the residual graph after the t-th
iteration. We have the relation:
ct+1 ≤ ct - ct/|E|
Referring to Section 5.4 of the book, we know the number of iterations is O(|E| log F).
