1. There are 169 students who are in need of emergency treatment. Each of these students...

Transcribed Image Text:

1. There are 169 students who are in need of emergency treatment. Each of these 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. Blood type A BO AB Supply 45 Demand 46 34 45 39 38 42 50 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) (1 points) Give a max flow formulation that determines a distribution that satisfies the demands of a maximum number of patients (Explain why the solution to your formulation corresponds to the problem). Draw the directed graph and put the edge capacity above each edge. Your network should have 10 vertices: a source (named s), a supply node for each of the four blood types (named a, b, o, ab), a demand node for each blood type (named a', b', o', ab'), and a sink (named t). (b) (2 points) Solve the maximum flow problem using the Ford-Fulkerson algorithm. Do the first augmentation on the path s - b - ab' - t. List each of the augmenting paths below, and state the amount by which the path increases the current value of the flow. Also, write the final flow values on each edge in the network above. 1. There are 169 students who are in need of emergency treatment. Each of these 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. Blood type A BO AB Supply 45 Demand 46 34 45 39 38 42 50 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) (1 points) Give a max flow formulation that determines a distribution that satisfies the demands of a maximum number of patients (Explain why the solution to your formulation corresponds to the problem). Draw the directed graph and put the edge capacity above each edge. Your network should have 10 vertices: a source (named s), a supply node for each of the four blood types (named a, b, o, ab), a demand node for each blood type (named a', b', o', ab'), and a sink (named t). (b) (2 points) Solve the maximum flow problem using the Ford-Fulkerson algorithm. Do the first augmentation on the path s - b - ab' - t. List each of the augmenting paths below, and state the amount by which the path increases the current value of the flow. Also, write the final flow values on each edge in the network above.

Answer rating: 100% (QA)

a Max flow formulation Create a directed graph with vertices representing the source s supply nodes ... View the full answer