Problems for Chapter 7

Section 7.5 Problems for Chapter 7

The simplex pivoter may be found here:

Hint.

🔗

Exercises Exercises

1.

Consider the following capacitated network:

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(a)

Find $\varphi(v_i)$ for each vertex, and compute $\displaystyle \sum_{i=1}^7\varphi(v_i)\text{.}$

🔗

(b)

Classify each vertex as a source, sink or intermediate vertex.

🔗

(c)

Add two vertices and as few edges as possible to extend this flow to a flow with a unique source and unique sink

🔗

2.

For each of the following capacitated networks, find the max-flow and min-cut on these networks as shown in Section 7.2.

🔗

(a)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(b)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(c)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(d)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

3.

Consider the max-flow min-cut problem Exercise 7.5.2 $\textbf{(a)}\text{.}$

🔗

(a)

Write out the noncanonical maximization problem which would compute the max-flow.

🔗

(b)

Record this problem in a Tucker tableau, then record the dual variable using $\ec{\mu_i}$ to denote dual variables associated with vertex equality constraints and $y_{ij}$ to denote the dual variables for edge inequality constraint.

🔗

(c)

Verify that the max-flow and min-cut you found are feasible solutions to these problems (using the convention that $\mu_k=0$ if $v_k\in V_1\text{,}$ $\mu_k=-1$ if $v_k\in V_2$ and $y_{ij}=1$ if $v_i\in V_1, v_j\in V_2$ and $y_{ij}=0$ otherwise.)

🔗

(d)

Argue that any cut corresponds to a feasible solution to this dual problem.

🔗

(e)

How can we tell both the flow and cut found in Exercise 7.5.2 $\textbf{a}$ are optimal? (Think duality.)

🔗

4.

Over a month at a hospital many patients are in need of blood transfusions. They had available blood from 47 donors with type A blood, 33 donors with type B blood, 46 donors with type AB and 44 donors with type O. There were 38 patients with type A blood, 39 patients with type B blood, 49 patients with type AB and 43 patients with type O. Type A patients can only receive type A or O, type B patients can receive only type B or O, type O patients can receive only type O, and type AB patients can receive any of the four types.

🔗

(a)

Construct a capacitated network which models the distributions of blood type from donors to patients with a unique source and sink, with no edges into the source or out of the sink.

🔗

(b)

Find a max-flow for this network.

🔗

(c)

Find a min-cut for this network.

🔗

(d)

If not all patients were able to receive blood, explain to the financial backers and hospital administrators, who may not have taken any math in awhile, why this was the case.

🔗

(e)

There’s little a hospital can do about the blood types of incoming patients. If reaching out to potential donors, what blood types should be prioritized?

🔗

5.

Let $N$ be a capacitated network with a unique source and sink, with no edges going into the source or out of the sink. Let $x_{ij}$ be a flow on this network with value $f\text{,}$ and $(V_1, V_2)$ be a cut of this network. Then prove that

\begin{equation*} f=\sum_{v_i\in V_1, v_j\in V_2}x_{ij}-\sum_{v_i\in V_1, v_j\in V_2}x_{ji}. \end{equation*}

🔗

Hint.

What is the sum $\displaystyle \sum_{j\in V_2}\varphi(v_j)\text{?}$ How can rewriting this as a double sum help?

🔗

6.

Let $N$ be a capacitated network with a unique source and sink, with no edges going into the source or out of the sink.

🔗

(a)

Given an example for $N$ such that $N$ has nonunique max-flows.

🔗

(b)

Given an example for $N$ such that $N$ has nonunique min-cuts.

🔗

(c)

Let $x_{ij}$ denote any max-flow for $N$ with value $f$ and $(V_1, V_2)$ denote any min-cut (not necessarily produced by $x_{ij}$ and Definition 7.2.12). Let $(V_1', V_2')$ be the cut generated $x_{ij}$ via Definition 7.2.12.

🔗

Prove that $x_{ij}=c_{ij}$ for any $v_i\in V_1, v_j=V_2\text{.}$

🔗

Hint.

Use Exercise 7.5.5.

🔗

(d)

Let $x_{ij}, x'_{ij}$ be two distinct max-flows on $N\text{,}$ and $(V_1, V_2), (V'_1, V'_2)$ be the cuts produced by Definition 7.2.12 on with these flows respectively. Prove that $(V_1, V_2) = (V'_1, V'_2)\text{.}$

🔗

Hint.

Use previous part.

🔗

7.

For each of the following, find the shortest path from $v_s$ to $v_d$ using Definition 7.3.7.

🔗

(a)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(b)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(c)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(d)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

8.

Consider Exercise 7.5.7 $\textbf{(a)}\text{.}$ Model this problem as a linear optimization problem and solve.

🔗

9.

Let $N$ be a weighted network with positive weights. For the following, prove or find a counterexample:

🔗

(a)

Let $x,y,z\in V\text{.}$ Prove that the value of the shortest path from $x$ to $z$ is the sum of the value of the shortest path from $x$ to $y$ plus the value of the shortest path from $y$ to $z\text{.}$

🔗

(b)

Suppose there was an edge going into $v_s\text{,}$ then Definition 7.3.7 fails.

🔗

10.

For each of the following, find the minimum cost-flows for $F=8$ and $F=10\text{.}$ Interpret each ordered pair $(c_{ij}, w_{ij})$ as (capacity,cost).

🔗

(a)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(b)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

(c)

$A Network Flow depicting several islands with bridges and carrying capacity.$

🔗

11.

Model Exercise 7.5.10 $\textbf{a}$ as a linear optimization problem.

🔗

12.

For each problem in Exercise 6.5.1, draw a weighted capacitated network where the transportation problem may be solved by solving an appropriate min-cost flow problem. State what the value $F$ of the flow should be. Do not solve the problem.

🔗

13.

For each problem in Exercise 6.5.9, draw a weighted capacitated network where the transportation problem may be solved by solving an appropriate min-cost flow problem. State what the value $F$ of the flow should be. Do not solve the problem.

🔗

Prev Top Next