Report

Review Review We will spend up to 30 minutes reviewing Exam 1 • Know how your answers were graded. • Know how to correct your mistakes. Your final exam is cumulative, and may contain similar questions. BA 452 Lesson B.1 Transportation 1 Readings Readings Chapter 6 Distribution and Network Models BA 452 Lesson B.1 Transportation 2 Overview Overview BA 452 Lesson B.1 Transportation 3 Overview Network Models are nodes, arcs, and functions (costs, supplies, demands, etc.) associated with the arcs and nodes, as in transportation, assignment, transshipment, and shortest-route problems. Transportation Problems are Resource Allocation Problems when outputs are fixed, and when outputs and inputs occur at different locations, so goods must be transported from origins to destinations. Transportation Problems with Modes of Transport re-interpret some of the different “origins” in a basic transportation problem to include not only location but modes of transportation (truck, rail, …). Assignment Problems are Transportation Problems when the “goods” are workers that are transported to jobs, and each worker either does all of a job or none of it, so the fraction completed is binary. BA 452 Lesson B.1 Transportation 4 Overview Tool Summary Write the objective of maximizing a minimum as a linear program. • For example, maximize min {2x, 3y} as maximize M subject to 2x > M and 3y > M. Define decision variable xij = units moving from origin i to destination j. Write origin constraints (with < or =): n x j 1 ij si i 1, 2, ,m Supply Write destination constraints (with < or =): m x i 1 ij dj j 1, 2, ,n Demand BA 452 Lesson B.1 Transportation 5 Overview Tool Summary Identify implicit assumptions needed to complete a formulation, such as all agents having an equal value of time. BA 452 Lesson B.1 Transportation 6 Network Models Network Models BA 452 Lesson B.1 Transportation 7 Network Models Network Models are nodes, arcs, and functions (costs, supplies, demands, etc.) associated with the arcs and nodes. Transportation, assignment, transshipment, and shortest-route problems are examples. BA 452 Lesson B.1 Transportation 8 Network Models Each of the four network models (transportation, assignment, transshipment, and shortest-route problems) can be formulated as linear programs and solved by general-purpose linear programming codes. For each of the four models, if the right-hand side of the linear programming formulations are all integers, the optimal solution will be integer values for the decision variables. There are many computer packages (including The Management Scientist) that contain convenient separate computer codes for these models, which take advantage of their network structure. But do not use such codes on exams because they lack the flexibility of the generalpurpose linear programming codes. BA 452 Lesson B.1 Transportation 9 Transportation Transportation BA 452 Lesson B.1 Transportation 10 Transportation Overview Transportation Problems are Resource Allocation Problems when outputs are fixed, and when outputs and inputs occur at different locations. Transportation Problems thus help determine the transportation of goods from m origins (each with a supply si) to n destinations (each with a demand dj) to minimize cost. BA 452 Lesson B.1 Transportation 11 Transportation Here is the network representation for a transportation problem with two sources and three destinations. 1 d1 2 d2 3 d3 c11 s1 c12 1 c13 c21 s2 2 c23 c22 Sources BA 452 Lesson B.1 Transportation Destinations 12 Transportation Notation: xij = number of units shipped from origin i to destination j cij = cost per unit of shipping from origin i to destination j si = supply or capacity in units at origin i dj = demand in units at destination j Linear programming formulation (supply inequality, demand equality). Min m n c x i 1 j 1 n ij ij x ij si i 1, 2, ,m Supply x ij dj = j 1, 2, ,n Demand j 1 m i 1 xij > 0 for all i and j BA 452 Lesson B.1 Transportation 13 Transportation Possible variations: • Minimum shipping guarantee from i to j: xij > Lij • Maximum route capacity from i to j: xij < Lij • Unacceptable route: Remove the corresponding decision variable. BA 452 Lesson B.1 Transportation 14 Transportation Question: Acme Block Company has orders for 80 tons of concrete blocks at three suburban locations: Northwood -25 tons, Westwood -- 45 tons, and Eastwood -- 10 tons. Acme has two plants, each of which can produce 50 tons per week. Delivery costs per ton from each plant to each suburban location are thus: Plant 1 Plant 2 Northwood 24 30 Westwood 30 40 Eastwood 40 42 Formulate then solve the linear program that determines how shipments should be made to fill the orders above. BA 452 Lesson B.1 Transportation 15 Transportation Answer: Linear programming formulation (supply inequality, demand equality). Variables: Xij = Tons shipped from Plant i to Destination j Objective: Min 24 X11 + 30 X12 + 40 X13 + 30 X21 + 40 X22 + 42 X23 Supply Constraints: X11 + X12 + X13 < 50 X21 + X22 + X23 < 50 Demand Constraints: X11 + X21 = 25 X12 + X22 = 45 X13 + X23 = 10 BA 452 Lesson B.1 Transportation 16 Transportation BA 452 Lesson B.1 Transportation 17 Transportation Define sources: Source 1 = Plant 1, Source 2 = Plant 2. Define destinations: 1 = Northwood, 2 = Westwood, 3 = Eastwood. Define costs: c11 = 24 c12 = 30 c13 = 40 c21 = 30 c22 = 40 c23 = 42 2+3=5 2x3 = 6 Define 2 supplies: s1 = 50, s2 = 50. Define 3 demands: d1 = 25, d2 = 45, d3 = 10. Define variables: Xij = number of units shipped from Source i to Destination j. Cost c13 = 40 Supply s1 = 50 Demand d2 = 45 BA 452 Lesson B.1 Transportation 18 Transportation Variable names: Xij = number of units shipped from Plant i to Destination j. Destination 1 = Northwood; 2 = Westwood; 3 = Eastwood Optimal shipments: From To Amount Cost Plant 1 Northwood 5 120 Plant 1 Westwood 45 1,350 Plant 2 Northwood 20 600 Plant 2 Eastwood 10 420 Total Cost = $2,490 BA 452 Lesson B.1 Transportation 19 Transportation BA 452 Lesson B.1 Transportation 20 Transportation Cost from Plant 1 to Northwood Variable names: Origin i = Plant i Destination 1 = Northwood Destination 2 = Westwood Destination 3 = Eastwood Optimal shipments: From To Amount Cost Plant 1 Northwood 5 120 Plant 1 Westwood 45 1,350 Plant 2 Northwood 20 600 Plant 2 Eastwood 10 420 Total Cost = $2,490 BA 452 Lesson B.1 Transportation 21 Transportation with Modes of Transport Transportation with Modes of Transport BA 452 Lesson B.1 Transportation 22 Transportation with Modes of Transport Overview Transportation Problems with Modes of Transport reinterpret some of the different “origins” in a basic transportation problem to include not only location but modes of transportation. For example, instead of “San Diego” as an origin specifying location, we have “San Diego by Truck” as an origin specifying both location and mode of transportation. BA 452 Lesson B.1 Transportation 23 Transportation with Modes of Transport Question: The Navy has 9,000 pounds of material in Albany, Georgia that it wishes to ship to three installations: San Diego, Norfolk, and Pensacola. They require 4,000, 2,500, and 2,500 pounds, respectively. Government regulations require equal distribution of shipping among the three carriers. The shipping costs per pound by truck, railroad, and airplane are: Mode Truck Railroad Airplane Destination San Diego Norfolk Pensacola $12 $6 $5 $20 $11 $9 $30 $26 $28 Formulate then solve the linear program that determines shipping arrangements (mode, destination, and quantity) that minimize the total shipping cost. BA 452 Lesson B.1 Transportation 24 Transportation with Modes of Transport BA 452 Lesson B.1 Transportation 25 Transportation with Modes of Transport Define the variables. We want to determine the pounds of material, xij , to be shipped by mode i to destination j. Variable names: San Diego Norfolk Pensacola Truck Railroad Airplane x11 x21 x31 x12 x22 x32 x13 x23 x33 Define the objective. Minimize the total shipping cost. Min: (shipping cost per pound for each mode-destination pairing) x (number of pounds shipped by mode-destination pairing). Min: 12x11 + 6x12 + 5x13 + 20x21 + 11x22 + 9x23 + 30x31 + 26x32 + 28x33 BA 452 Lesson B.1 Transportation 26 Transportation with Modes of Transport Define the constraints of equal use of transportation modes: (1) x11 + x12 + x13 = 3000 (2) x21 + x22 + x23 = 3000 (3) x31 + x32 + x33 = 3000 Define the destination material constraints: (4) x11 + x21 + x31 = 4000 (5) x12 + x22 + x32 = 2500 (6) x13 + x23 + x33 = 2500 BA 452 Lesson B.1 Transportation 27 Transportation with Modes of Transport Linear programming summary. Variables: Xij = Pounds shipped by Mode i to Destination j Objective: Min 12 X11 + 6 X12 + 5 X13 + 20 X21 + 11 X22 + 9 X23 + 30 X31 + 26 X32 + 28 X33 Mode (Supply equality) Constraints: X11 + X12 + X13 = 3000 X21 + X22 + X23 = 3000 X31 + X32 + X33 = 3000 Destination Constraints: X11 + X21 + X31 = 4000 X12 + X22 + X32 = 2500 X13 + X23 + X33 = 2500 BA 452 Lesson B.1 Transportation 28 Transportation with Modes of Transport Variable names: Truck Railroad Airplane San Diego Norfolk Pensacola X11 X12 X13 X21 X22 X23 X31 X32 X33 Units to San Diego by truck Solution Summary: • San Diego receives 1000 lbs. by truck and 3000 lbs. by airplane. • Norfolk receives 2000 lbs. by truck and 500 lbs. by railroad. • Pensacola receives 2500 lbs. by railroad. • The total shipping cost is $142,000. BA 452 Lesson B.1 Transportation 29 Transportation with Modes of Transport The Management Science Transportation module is not available. Remember, in that formulation, the supply constraints are inequalities. Min m n c x i 1 j 1 n x j 1 m x i 1 ij ij ij si i 1, 2, ,m Supply ij dj = j 1, 2, ,n Demand xij > 0 for all i and j But in Example 2, the “origins” are the modes of shipping, and the supply constraint on each mode is an equality. BA 452 Lesson B.1 Transportation 30 Assignment Assignment BA 452 Lesson B.1 Transportation 31 Assignment Overview Assignment Problems are Transportation Problems when the “goods” are workers that are transported to jobs, and each worker either does all of a job or none of it. Assignment Problems thus minimize the total cost of assigning of m workers (or agents) to m jobs (or tasks). The simplest way to model all-or-nothing in any linear program is to restrict the fraction of the job completed to be a binary (0 or 1) decision variable. BA 452 Lesson B.1 Transportation 32 Assignment An assignment problem is thus a special case of a transportation problem in which all supplies and all demands equal to 1; hence assignment problems may be solved as linear programs. And although the only sensible solution quantities are binary (0 or 1), the special form of the problem and of The Management Scientist guarantees all solutions are binary (0 or 1). BA 452 Lesson B.1 Transportation 33 Assignment Here is the network representation of an assignment problem with three workers (agents) and three jobs (tasks): 1 Agents c11 1 c12 c13 c21 2 Tasks c22 2 c23 c31 3 c33 c32 3 BA 452 Lesson B.1 Transportation 34 Assignment Notation: xij = 1 if agent i is assigned to task j 0 otherwise cij = cost of assigning agent i to task j Min m n c x i 1 j 1 n s.t. x j 1 m x i 1 ij ij ij 1 i 1, 2, ,m Agents ij 1 j 1, 2, ,n Tasks xij > 0 for all i and j BA 452 Lesson B.1 Transportation 35 Assignment Possible variations: • Number of agents exceeds the number of tasks: Extra agents simply remain unassigned. • An assignment is unacceptable: Remove the corresponding decision variable. • An agent is permitted to work t n x j 1 ij t i 1, 2, ,m tasks: Agents BA 452 Lesson B.1 Transportation 36 Assignment Question: Russell electrical contractors pay their subcontractors a fixed fee plus mileage for work performed. On a given day the contractor is faced with three electrical jobs associated with various projects. Given below are the distances between the subcontractors and the projects. Subcontractor Westside Federated Goliath Universal Projects A B C 50 36 16 28 30 18 35 32 20 25 25 14 Assume each subcontractor can perform at most one project. Formulate then solve the linear program that assigns contractors to minimize total mileage costs. BA 452 Lesson B.1 Transportation 37 Assignment Answer: West. Subcontractors 50 36 16 28 Fed. 18 35 Gol. Univ. A 20 25 Projects 30 B 32 C 25 14 BA 452 Lesson B.1 Transportation 38 Assignment Variable names: Westside Federated Goliath Universal Project A Project B Project C x11 x12 x13 x21 x22 x23 x31 x32 x33 x41 x42 x43 There will be 1 variable for each agent-task pair, so 12 variables all together. There will be 1 constraint for each agent and for each task, so 7 constraints all together. BA 452 Lesson B.1 Transportation 39 Assignment Variable names: Westside Federated Goliath Universal Project A Project B Project C x11 x12 x13 x21 x22 x23 x31 x32 x33 x41 x42 x43 Min 50x11+36x12+16x13+28x21+30x22+18x23 +35x31+32x32+20x33+25x41+25x42+14x43 s.t. x11+x12+x13 < 1 x21+x22+x23 < 1 Agents x31+x32+x33 < 1 x41+x42+x43 < 1 x11+x21+x31+x41 = 1 x12+x22+x32+x42 = 1 Tasks x13+x23+x33+x43 = 1 xij = 0 or 1 for all i and j BA 452 Lesson B.1 Transportation 40 Assignment Agent 1 capacity: x11+x12+x13 < 1 Westside Federated Goliath Universal Project A Project B Project C x11 x12 x13 x21 x22 x23 x31 x32 x33 x41 x42 x43 Task 3 done: x13+x23+x33+x43 = 1 BA 452 Lesson B.1 Transportation 41 Assignment Variable names: Westside x13 Federated Goliath Universal Project A Project B Project C x11 x12 x21 x31 x41 x22 x32 x42 x23 x33 x43 Optimal assignment: Subcontractor Project Distance Westside C 16 Federated A 28 Goliath (unassigned) Universal B 25 Total distance = 69 miles BA 452 Lesson B.1 Transportation 42 Assignment BA 452 Lesson B.1 Transportation 43 Assignment Projects A B C 50 36 Subcontractor Westside 16 Federated 28 30 18 Goliath 35 32 20 Universal 25 25 14 Optimal assignment: Subcontractor Project Distance Westside C 16 Federated A 28 Goliath (unassigned) Universal B 25 Total distance = 69 miles BA 452 Lesson B.1 Transportation 44 Assignment Question: Now change Example 3 to take into account the recent marriage of the Goliath subcontractor to your youngest daughter. That is, you have to assign Goliath one of the jobs. How should the contractors now be assigned to minimize total mileage costs? BA 452 Lesson B.1 Transportation 45 Assignment Alternative notation: WA = 0 if Westside does not get task A 1 if Westside does get task A and so on. Min s.t. 50WA+36WB+16WC+28FA+30FB+18FC +35GA+32GB+20GC+25UA+25UB+14UC WA+WB+WC < 1 FA+FB+FC <1 Agents GA+GB+GC = 1 UA+UB+UC < 1 WA+FA+GA+UA = 1 WB+FB+GB+UB = 1 Tasks WC+FC+GC+UC = 1 BA 452 Lesson B.1 Transportation 46 Assignment Goliath gets a task: GA+GB+GC = 1 Task A gets done: WA+FA+GA+UA=1 BA 452 Lesson B.1 Transportation 47 Assignment Optimal assignment: Subcontractor Project Distance Westside C 16 Federated (unassigned) Goliath B 32 Universal A 25 Total distance = 73 miles BA 452 Lesson B.1 Transportation 48 BA 452 Quantitative Analysis End of Lesson B.1 BA 452 Lesson B.1 Transportation 49