The figure below describes the network and data of a minimum cost network flow problem. The data by the nodes represents its net supply or demand. For example, node 1 has a supply of 100 and node 7 has a demand of 25. The data along the arcs represent the capacities and unit costs. For example, at most 40 units can flow on the arc connecting node 5 to node 7, and each unit of this flow has a cost of $10. Flows on arcs must be nonnegative.

1. Formulate the minimum cost network flow problem algebraically as a linear program. Clearly identify the meaning of the decision variables.
2. Suppose now that there is a second commodity that needs to be shipped simultaneously on this network (in addition to the commodity described above). Node 2 has a supply of 25 units of commodity 2. Node 7 has a demand of 10 units of commodity 2 and node 8 has a demand of 15 units of commodity 2. The shipping costs are the same as for commodity 1. The arc capacities apply to the total shipment of commodities 1 and 2 on each arc. Clearly identify the meaning of the decision variables.
3. Now, ignore all supply, demand, and capacity data in the network. The only relevant data are the costs on the arcs that we shall interpret as distances. Formulate a linear program that seeks to find the shortest (least expensive) path connecting node 1 to node 8. Clearly identify the meaning of the decision variables.
4. Now, ignore all supply, demand, and cost data in the network. The only relevant data are the arc capacities. Formulate a linear program that seeks maximize the total flow from node 1 to node 8. Clearly identify the meaning of the decision variables.

.. 4 100, $45 30, $10 60, $30 7 Demand (-25) 2 75, $15 50, $10 40, $10 1 Supply (100) 40, $5 5 50, $30 100, $45 40, $25 50, $10 3 30, $5 40, $10 8 Demand (-75) 60, $8 80, $15 .. 4 100, $45 30, $10 60, $30 7 Demand (-25) 2 75, $15 50, $10 40, $10 1 Supply (100) 40, $5 5 50, $30 100, $45 40, $25 50, $10 3 30, $5 40, $10 8 Demand (-75) 60, $8 80, $15