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
1.
Give a max flow formulation that determines a distribution
that satisfies the demands of a maximum number of patients.
Draw the directed graph and put the edge capacity above each edge.
Your network should have 10 vertices:
a source (named 0), a supply node for each of the four blood types
(named 1 to 4), a demand node for each blood type (named 5 to 8),
and a sink (named 9).