Transportation Problems - Lecture Note

Summary of Section 7.1 • Be able to define a (balanced) transportation problem. • Be able to construct a transportation tableau. • Look at possible solutions to a transportation problem. • Be able to use Excel to solve a basic transportation problem. Transportation Problems, Lecture 1 Here’s an example of a transportation problem: A company sends goods from two warehouses to three customers. Warehouse 1 has 50 units available, warehouse 2 has 40. Each customer wants 30 units. The shipping costs are given below. Formulate an LP to minimize costs to get goods to the customers. C1 C2 C3 W 1 15 35 25 W 2 10 50 40 Demand 30 30 30 Avail 50 40 It’s straightforward to convert this to an LP. Let xij be the number of units from warehouse i to customer j. Then we have 2 × 3 variables. Using our table, we can construct the LP: min z = 15x11 + 35x12 + 25x13 + 10x21 + 50x22 + 40x23 s.t. ≤ 50 ≤ 40 ≥ 30 ≥ 30 ≥ 30 x11 + x12 + x13 x21 + x22 + x23 x11 + x21 x12 + x22 x13 + x23 Outgoing from Warehouse 1 Outgoing from Warehouse 2 Incoming to Customer 1 Incoming to Customer 2 Incoming to Customer 3 Because of the structure of this problem, we can specialize the tableau to something called a transportation tableau. Cust 1 Cust 2 15 Cust 3 35 25 WH 1 50 10 50 40 WH 2 Demand Supply 40 30 30 1 30 ? Before we give algorithms to solve this, try getting a solution on your own (try to go as cheaply as possible!) The General Transportation Problem This is a specific case of a more general transportation problem: Sink 1 ··· Sink 2 c11 Sink n c12 c1n ··· Source 1 c21 s1 c22 c2n ··· Source 2 s2 .. . .. . cm1 cm2 ··· Source m Demand cmn d1 ··· d2 dn P sm P si = di • We have m supply points and n demand points. • In the standard problem, each supply point can distribute to any demand point (in particular, a supply point is not moving goods to another supply point). • Each supply point has a certain volume available (si ). • Each demand point needs a certain volume (di ). • There is a specific cost moving from i to j: cij • The amount of material moving from i to j is typically xij . Remember that this is just a summary of the underlying linear program: min z = m X n X cij xij i=1 j=1 such that: • Each supply constraint is met. That is, the sum of all product going out of supply point i should not exceed what is available. This is the sum from left to right in the table. n X j=1 2 xij ≤ si • Each demand constraint is met. That is, the sum of all incoming product to demand point j should meet or exceed what we need. This is the sum from top to bottom in the table. m X xij ≥ dj i=1 • All xij should be non-negative. Questions for the class • How many variables do we have? (mn) • How many equations do we have? (m + n) • If the following holds, do we have a solution? m X si < i=1 n X dj j=1 Definition: If the supply equals the demand for a given transportation problem, then the problem is said to be balanced. The techniques we develop will be for balanced problems. If the problem is not balanced, it is possible to introduce dummy or virtual supply or demand points to make the problem balanced. We’ll look at this later. Setting up a problem that is not balanced If the problem is not balanced, we may be able to introduce either a dummy warehouse or dummy customer so that the new problem is balanced. (Text example) Suppose we have two reservoirs of water supplying 3 cities. Each reservoir can supply 50 million gallons, and each city wants 40 million gallons. There is a penalty for not meeting the demand for each city: $20, $22, $23 respectively. The costs are given in the table below. Formulate this LP as a balanced transportation problem. Res 1 Res 2 Demand City 1 7 9 40 City 2 8 7 40 SOLUTION: 3 City 3 10 8 40 Avail 50 50 City 1 City 2 7 City 3 8 Avail 10 Res 1 50 9 7 8 Res 2 50 20 22 23 Dummy Demand 20 40 40 4 40 120 Summary: Balanced Transportation Problem and Tableau Now, we define a balanced transportation problem as: min z = m X n X cij xij i=1 j=1 such that: n X xij = si and j=1 m X xij = dj i=1 All xij should be non-negative. How do we ensure this is balanced? Total Supply = Total Demand m X i=1 si = n X dj j=1 What does that look like in the array? (The sum of the first m rows is the total supply, the sum of the last n rows is the demand). 5 Example PowerCo has three electric power plants (1, 2, 3) that supply the needs of four cities (A, B, C, D). See Table 1 for the amount of power available to each city. See Table 1 for the power demands in these cities which occur at the same time (2PM). The costs of sending a million kilowatt hours from the plant to the city depends on several factors, and the cost table is shown as well. Formulate an LP to minimize the cost of meeting each city’s peak demands. 1 2 3 Demand A B C D Supply 8 6 10 9 35 9 12 13 7 50 14 9 16 5 40 45 20 30 30 Now, the goal of the transportation problem is to “fill in the boxes”. Try one. Here’s an example (be sure your column and row sums match up!) Here is a possible distribution scheme. Calculate its cost: City A City B 8 Plant 1 6 10 9 Plant 2 10 9 13 7 5 50 9 16 10 45 20 Supply 35 12 14 Demand City D 25 45 Plant 3 City C 30 5 30 40 30 125 This cost is $1150.00. We’re going to see how to do these assignments in the next section, but in this section we look at having Excel compute a solution. In this case, we’ll treat the problem as any other linear program. Our class website has the example for the power distribution problem. Key Point: Notice how we organized the information from a typical transportation problem! 6 Handout for Class Try to find the cheapest way to distribute the power: City A City B 8 City C 6 City D 10 9 Plant 1 35 9 12 13 7 Plant 2 50 14 9 16 5 Plant 3 Demand Supply 40 45 20 30 7 30 125 Setting up and Solving in Excel Here is a good way to organize the power distribution problem. I’ve used one array of constants for the costs, and reserved space for the array of variables (xij ). Then we keep track of the supplies down the last column (sums), and the demands across the bottom row. The total cost is then a “dot product” between the cost array and variable array (as shown in the formula boxes). (NOTE: To type an equal sign and not have a formula, type a blank space first). You can download this from our class website as a template. To set up the solver: • We want to minimize cell J17 • The conditions are that the column sums (in cells D15 to G15) are equal to the demand (in cells D17 to G17), and the row sums (in cells H12-H14) are equal to the supply (in cells J12-14). All told, there are then 4+3=7 equality constraints. The solver should give you the following result: 8 In Class Exercise (7.1, #1) A company supplies goods from two warehouses to three customers (who still want 30 units each). Unfortunately, warehouse 1 and 40 units and warehouse 2 has 30 units so we cannot fulfill all the orders. The costs of shipping are the same as before. There will be a penalty for each unit of unmet customer demand: $90, $80, and $110 for customers 1, 2 and 3 respectively. Formulate a balanced transportation problem to minimize the shortage and shipping costs. SOLUTION: Have a virtual warehouse that will ship to the customers. That makes the tableau: Cust 1 Cust 2 15 Cust 3 35 25 Wh 1 40 10 50 40 Wh 2 30 90 80 110 Dummy Demand Supply 20 30 30 30 90 Part 2 Suppose that Warehouses 1 and 2 each have 50 units. Formulate a balanced transportation problem for this new situation. Cust 1 Cust 2 15 Cust 3 35 Virtual Cust 25 0 Wh 1 50 10 50 40 0 Wh 2 Demand Supply 50 30 30 30 10 9 90 Added HW for 7.1 7.1.13 One of the main products of the P & T Company is canned peas. The peas are prepared at three canneries (near Bellingham, WA; Eugene, OR; and Albert Lea, MN), and then shipped by truck to four distribution warehouses in the western US (Sacramento, Salt Lake City, Rapid City, and Albuquerque). Because the shipping costs are a major expense, management is initiating a study to reduce them as much as possible. For the upcoming season, an estimate has been made of the output from each cannery, and each warehouse has been allocated a certain amount from the total supply of peas. This information (in units of truckloads), along with the transportation costs, is given in the table below. There are 300 truckloads to be distributed. Use a spreadsheet to formulate this as a transportation problem, and solve it using the spreadsheet’s solver. You may use the spreadsheet on the class website as a template. 1 Cannery 2 3 Allocation Shipping Costs Warehouse 1 2 3 4 Output 464 513 654 867 75 352 416 690 791 125 995 682 388 685 100 80 65 70 85 7.1.14 In a balanced transportation problem, show that any supply constraint exactly equals the sum of the demand constraints, minus the sum of the other supply constraints. This shows that one row is a linear combination of the others. 10