Exercise 2.3 (Bloody network)
A transportation problem is a special kind of (single-commodity min-cost) network-flow prob-
lem. There are certain nodes v called supply nodes which have net supply bu > O. The other
nodes v are called demand nodes, and they have net supply b
< 0. There are no nodes with
0, and all arcs point from supply nodes to demand nodes.
A simplified example is for matching available supply and demand of blood, in types A, B,
AB and O. Suppose that we have su units of blood available, in types v E {A, B, AB, 0}. Also,
we have requirements d, by patients of different types V € {A, B, AB, 0} . It is very important
to understand that a patient of a certain type can accept blood not just from their own type.
Do some research to find out the compatible blood types for a patient; don’t make a mistake
lives depend on this! In this spirit, if your model allocates any blood in an incompatible fashion, you
will receive a grade of F on this problem. At
Describe a linear-optimization problem that satisfies all of the patient demand with com-
patible blood. You will find that type O is the most versatile blood, then both A and B, followed
by AB. Factor in this point when you formulate your objective function, with the idea of having
the left-over supply of blood being as versatile as possible.
Using Multi-commodityFlow.ipynb (see Appendix A.4) with a single commodity only (that
is, K := 1), set up and solve an example of a blood-distribution problem.