The RedBrand Company produces a tomato product at three plants. This product can be shipped directly to the company’s two customers, or it can first be shipped to the company’s two warehouses and then...

The RedBrand Company produces a tomato product at three plants. This product can be shipped directly to the company’s two customers, or it can first be shipped to the company’s two warehouses and then to the customers. Figure 5.17 is a network representation of RedBrand’s problem. Nodes 1, 2, and 3 represent the plants (these are the suppliers, denoted by S), nodes 4 and 5 represent the warehouses (these are the transshipment points, denoted by T), and nodes 6 and 7 represent the customers (these are the demanders, denoted by D). Note that we allow the possibility of some shipments among plants, among warehouses, and among customers. Also, some arcs have arrows on both ends, which means that flow is allowed in either direction.

The cost of producing the product is the same at each plant, so RedBrand is concerned with minimizing the total shipping cost incurred in meeting customer demands. The production capacity of each plant (in tons per year) and the demand of each customer are shown in Figure 5.17. For example, plant 1 (node 1) has a capacity of 200, and customer 1 (node 6) has a demand of 400. In addition, the cost (in thousands of dollars) of shipping a ton of the product between each pair of locations is listed in Table 5.7, where a blank indicates that RedBrand cannot ship along that arc. We also assume that at most 200 tons of the product can be shipped between any two nodes. This is the common arc capacity. RedBrand wants to determine a minimum-cost shipping schedule.