Consider the following multicommodity flow problem. An auto company has two factories and three distributors. There are two products to be shipped from the factories to the distribution centers: luxury cars and economy cars. The supplies at the factories, demands at the distributors, and the unit profits (to be marimized for each product shipped from factory to distributor are shown in Figure 1 and Table 1. In addition, there are restrictions on the total amount of product to be shipped on two of the links: at most 30 cars of either type can be shipped from factory 1 to distributor 1 and from factory 1 to distributor 3. 20 20 100 40 251 120 20 501 30 90 210 41 2 10 80 20 15 2 70 302 40 140 10 10 3) 20 Product ! Product 2 Figure 1: Transportation problem parameters. Center 1 Plant 1 100 Plant 2 80 Demand 20 Luxury Economy 2 3 Supply 1 2 3 Supply 120 90 25 40 20 30 50 70 140 15 20 40 10 30 10 10 20 40 20 Table 1: Transportation problem parameters. Let Iy be the number of luxury cars shipped from plant i to distributor j and Yij be the number of economy cars shipped from plant i to distributor 3. The capacity constraints are thus 111 + 911 S 30 013+y13