Direction: Natural gas once extracted from a source is purified for commercial use at natural gas plants. From gas plants it is pumped to various destinations through pipelines. There are pumping stations, at intermediate places to maintain recommended pressure in the pipelines. The pumping stations do not produce or process any natural gas. They pump out exactly the quantity they receive from plants or other pumping stations. The following figure depicts a network gas pipelines. The circles denote the locations of gas plants, pumping stations or cities with big demand for natural gas. One location can be only one of these three. The numbers on the arrows are the capacities (in appropriate units) of the pipeline that carry gas in the direction of the arrow. Currently the demand supply situation is such that the capacity utilization of the pipelines is very close to 100%.