A gas company owns a pipeline network, sections of which are used to pump natural gas from its main field to its distribution center. The network is shown below, where the direction of the arrows indicates the only direction in which the gas can be pumped. The pipeline links of the system are numbered one through six, and the intermediate nodes are large pumping stations. At the present time, the company nets 1200 mcf (million cubic feet) of gas per month from its main field and must transport that entire amount to the distribution center. The following are the maximum usage rates and costs associated with each link:

123456 Maximum usage: mef/month 500 900 700 400 600 1000 Tariff: S/mef 20 25 10 15 20 40 The gas company wants to find those usage rates that minimize total cost of transportation. 3 5