Enthusiastic celebration of a sunny day at a prominent
northeastern university has resulted in the arrival at the
university's medial clinic of 169 students in need of emergency
treatment. Each of the 169 students requires a transfusion of
one unit of whole blood. The clinic has supplies of 170 units of
whole blood. The number of units of blood available in each of
the four major blood groups and the distribution of patients among
the groups is summarized below.
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.Blood type A B O AB Supply 46 34 45 45 Demand 39 38 42 50
Give a maxflow formulation that determines a distribution that satisfies the demands of a maximum number of patients.
1.
Draw a directed graph model for the problem,
putting the edge capacity above each edge,
leaving room to fill in flow values later.
Your network should have 10 vertices:
a source (named 0), a supply node for each of the four blood types
(named 1 to 4 for A, B, O, and AB, respectively), a demand node for each blood type (named 5 to 8 for A, B, O, and AB, respectively),
and a sink (named 9).
2.
Solve the maxflow problem using the Ford-Fulkerson
augmenting path algorithm.
Do the first augmentation on the path 0-2-8-9. (This will
force you to use a backwards edge at some point during
the rest of the algorithm.)
Afterwards, always choose the augmenting path with the fewest
number of edges, breaking
ties in favor of the lexicographically smallest path (e.g., choose
0-2-7-9 over 0-4-6-9). List each of the augmenting paths below.
Also, write and circle the final flow values on each edge in the network
above.
3.
Calculate a min s-t cut in the network above, i.e., list the vertices
on the source side of the cut.
4.
Use the min cut to deduce a rigorous and concise explanation of why not all
of the patients can receive blood from the
available supply. Your explanation should be understandable to
the hospital administrators who have no knowledge of network flow theory.