#5 Explain in your on words the example in the text which asserts Lemma 2 below. That is, that circuits can be eliminated. That a solution S of the transportation problem will be based on edges E(S) which have no circuits. That is, spanning tree or forest. Lemma 1 Let S be a solution to a transportation problem involving a set of edges E(S) that contains a circuit. Then there is another solution S* that costs the same or less than S, where E(S*) is a subset of E(S) containing no circuits. 4.5 THE TRANSPORTATION PROBLEM In this section we apply our knowledge of spanning trees, network flows, and match- ings developed in the previous sections to study network flows in which there is a cost charged to flow along an edge. We will consider networks whose underlying graphs are bipartite, as in the matching networks in Section 4.4. Similar to the matching problems, the edges here have unlimited capacity and the vertices have supplies and demandsnow integers larger than 1. We refer to the supply vertices as warehouses and the demand vertices as stores. The bipartite graph G =(X, Y, E) is assumed to be complete, with an edge (i, j) from each warehouse W; to each store S;. What is new is that there is a cost Cij charged for shipping an item on edge (i, j). The goal is to find a routing of all the items from warehouses to stores that minimizes the transportation costs. See the sample problem in Figure 4.17. This optimization problem is appropriately called the Transportation Problem. It was one of the first optimization problems studied in operations research. Warehouse i has a supply of size si, and store j has a demand of size d;. We assume that the total supplies, summed over all warehouses, are adequate to meet the demand at all the stores. A solution to a transportation problem specifies the amount Xij to ship on each edge (i, j) so that the total shipments leaving each warehouse do not exceed the warehouse's supply and the total shipments arriving at each store equal the demand of that store. The goal is to find, among all solutions, a minimum-cost solution. A mathematical statement of the transportation problem is minimize cijXij such that CRUCIAL OBSERVATION xij 0 While spanning trees do not appear anywhere in the statement of the problem, it turns out that they are central to solving this problem: The set of edges used for shipments in the optimal solution form a spanning tree