transportation assignment and transshipment problems ppt

• My presentations

Auth with social network:

Download presentation

We think you have liked this presentation. If you wish to download it, please recommend it to your friends in any social system. Share buttons are a little bit lower. Thank you!

Presentation is loading. Please wait.

Transportation, Transshipment, and Assignment Problems

Published by Rosamond Montgomery Modified over 5 years ago

Similar presentations

Presentation on theme: "Transportation, Transshipment, and Assignment Problems"— Presentation transcript:

Transportation Assignment and Transshipments Problems

BA 452 Lesson B.4 Binary Fixed Costs 11ReadingsReadings Chapter 7 Integer Linear Programming.

1 1 BA 452 Lesson B.2 Transshipment and Shortest Route ReadingsReadings Chapter 6 Distribution and Network Models.

1 1 Slides by John Loucks St. Edward’s University Modifications by A. Asef-Vaziri.

Chapter 10, Part A Distribution and Network Models

1 1 Slide © 2011 Cengage Learning. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole.

Transportation, Assignment, and Transshipment Problems

Transportation, Transshipment and Assignment Models and Assignment Models.

1 Department of Business Administration SPRING Management Science by Asst. Prof. Sami Fethi © 2007 Pearson Education.

6-1 Copyright © 2013 Pearson Education, Inc. Publishing as Prentice Hall Transportation, Transshipment, and Assignment Problems Chapter 6.

1 1 Slide © 2001 South-Western College Publishing/Thomson Learning Anderson Sweeney Williams Anderson Sweeney Williams Slides Prepared by JOHN LOUCKS QUANTITATIVE.

1 Lecture 3 MGMT 650 Sensitivity Analysis in LP Chapter 3.

1 1 Slide © 2008 Thomson South-Western. All Rights Reserved Slides by JOHN LOUCKS St. Edward’s University.

Kerimcan OzcanMNGT 379 Operations Research1 Integer Linear Programming Chapter 8.

Linear Programming Network Flow Problems Transportation Assignment Transshipment Production and Inventory.

Linear Programming Example 5 Transportation Problem.

BA 452 Lesson B.1 Transportation 1 1Review We will spend up to 30 minutes reviewing Exam 1 Know how your answers were graded.Know how your answers were.

1 1 Slide © 2006 Thomson South-Western. All Rights Reserved. Slides prepared by JOHN LOUCKS St. Edward’s University.

About project

© 2024 SlidePlayer.com Inc. All rights reserved.

Chapter 6 Transportation, Transshipment, and Assignment Problems

Jul 13, 2012

650 likes | 2.39k Views

Introduction to Management Science 8th Edition by Bernard W. Taylor III. Chapter 6 Transportation, Transshipment, and Assignment Problems. Chapter Topics. The Transportation Model Computer Solution of a Transportation Problem The Assignment Model Computer Solution of the Assignment Model.

Share Presentation

• model formulation minimize
• special form
• linear programming model formulation
• computer solution
• excel qm exhibit

Presentation Transcript

Introduction to Management Science 8th Edition by Bernard W. Taylor III Chapter 6 Transportation, Transshipment, and Assignment Problems Chapter 6 - Transportation, Transshipment, and Assignment Problems

Chapter Topics • The Transportation Model • Computer Solution of a Transportation Problem • The Assignment Model • Computer Solution of the Assignment Model Chapter 6 - Transportation, Transshipment, and Assignment Problems

Overview • Part of a larger class of linear programming problems known as network flow models. • Possess special mathematical features that enabled development of very efficient, unique solution methods. • Methods are variations of traditional simplex procedure. • Detailed description of methods is contained in CD-ROM Module B, Transportation and Assignment Solution Methods. • Text focuses on model formulation and solution with Excel and QM for windows. Chapter 6 - Transportation, Transshipment, and Assignment Problems

The Transportation Model Characteristics • A product is transported from a number of sources to a number of destinations at the minimum possible cost. • Each source is able to supply a fixed number of units of the product, and each destination has a fixed demand for the product. • The linear programming model has constraints for supply at each source and demand at each destination. • All constraints are equalities in a balanced transportation model where supply equals demand. • Constraints contain inequalities in unbalanced models where supply does not equal demand. Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Problem Definition and Data • Problem: How many tons of wheat to transport from each grain elevator to each mill on a monthly basis in order to minimize the total cost of transportation? • Data: Grain ElevatorSupplyMill Demand 1. Kansas City 150 A. Chicago 200 2. Omaha 175 B. St. Louis 100 3. Des Moines 275 C. Cincinnati 300 Total 600 tons Total 600 tons Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Model Formulation (1 of 2) Minimize Z = $6x1A + 8x1B + 10x1C + 7x2A + 11x2B + 11x2C + 4x3A + 5x3B + 12x3C subject to: x1A + x1B + x1C = 150 x2A + x2B + x2C = 175 x3A + x3B + x3C = 275 x1A + x2A + x3A = 200 x1B + x2B + x3B = 100 x1C + x2C + x3C = 300 xij 0 xij = tons of wheat from each grain elevator, i, i = 1, 2, 3, to each mill j, j = A,B,C Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Model Formulation (2 of 2) Figure 6.1 Network of Transportation Routes for Wheat Shipments Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel (1 of 3) Exhibit 6.1 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel (2 of 3) Exhibit 6.2 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel (3 of 3) Exhibit 6.3 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel QM (1 of 3) Exhibit 6.4 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel QM (2 of 3) Exhibit 6.5 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with Excel QM (3 of 3) Exhibit 6.6 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with QM for Windows (1 of 3) Exhibit 6.7 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with QM for Windows (2 of 3) Exhibit 6.8 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transportation Model Example Computer Solution with QM for Windows (3 of 3) Exhibit 6.9 Chapter 6 - Transportation, Transshipment, and Assignment Problems

The Transshipment Model Characteristics • Extension of the transportation model. • Intermediate transshipment points are added between the sources and destinations. • Items may be transported from: • Sources through transshipment points to destinations • One source to another • One transshipment point to another • One destination to another • Directly from sources to to destinations • Some combination of these Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transshipment Model Example Problem Definition and Data (1 of 2) • Extension of the transportation model in which intermediate transshipment points are added between sources and destinations. • Data: Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transshipment Model Example Problem Definition and Data (2 of 2) Figure 6.2 Network of Transshipment Routes Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transshipment Model Example Model Formulation Minimize Z = $16x13 + 10x14 + 12x15 + 15x23 + 14x24 + 17x25 + 6x36 + 8x37 + 10x38 + 7x46 + 11x47 + 11x48 + 4x56 + 5x57 + x58 subject to: x13 + x14 + x15 = 300 x23+ x24 + x25 = 300 x36 + x37 + x38 = 200 x46+ x47 + x48 = 100 x56 + x57 + x58 = 300 x13 + x23 - x36 - x37 - x38 = 0 x14 + x24 - x46 - x47 - x48 = 0 x15 + x25 - x56 - x57 - x58 = 0 xij 0 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transshipment Model Example Computer Solution with Excel (1 of 2) Exhibit 6.10 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Transshipment Model Example Computer Solution with Excel (2 of 2) Exhibit 6.11 Chapter 6 - Transportation, Transshipment, and Assignment Problems

The Assignment Model Characteristics • Special form of linear programming model similar to the transportation model. • Supply at each source and demand at each destination limited to one unit. • In a balanced model supply equals demand. • In an unbalanced model supply does not equal demand. Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Problem Definition and Data • Problem: Assign four teams of officials to four games in a way that will minimize total distance traveled by the officials. Supply is always one team of officials, demand is for only one team of officials at each game. • Data: Table 6.1 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Model Formulation Minimize Z = 210xAR + 90xAA + 180xAD + 160xAC + 100xBR + 70xBA + 130xBD + 200xBC + 175xCR + 105xCA + 140xCD + 170xCC + 80xDR + 65xDA + 105xDD + 120xDC subject to: xAR + xAA + xAD + xAC = 1 xij 0 xBR + xBA + xBD + xBC = 1 xCR + xCA + xCD + xCC = 1 xDR + xDA + xDD + xDC = 1 xAR + xBR + xCR + xDR = 1 xAA + xBA + xCA + xDA = 1 xAD + xBD + xCD + xDD = 1 xAC + xBC + xCC + xDC = 1 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with Excel (1 of 3) Exhibit 6.12 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with Excel (2 of 3) Exhibit 6.13 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with Excel (3 of 3) Exhibit 6.14 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with Excel QM Exhibit 6.15 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with QM for Windows (1 of 2) Exhibit 6.16 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Assignment Model Example Computer Solution with QM for Windows (2 of 2) Exhibit 6.17 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Example Problem Solution Transportation Problem Statement • Determine linear programming model formulation and solve using Excel: Chapter 6 - Transportation, Transshipment, and Assignment Problems

Example Problem Solution Model Formulation Minimize Z = $8x1A + 5x1B + 6x1C + 15x2A + 10x2B + 12x2C + 3x3A + 9x3B + 10x3C subject to: x1A + x1B + x1C = 120 x2A + x2B + x2C = 80 x3A + x3B + x3C = 80 x1A + x2A + x3A 150 x1B + x2B + x3B 70 x1C + x2C + x3C 100 xij 0 Chapter 6 - Transportation, Transshipment, and Assignment Problems

Example Problem Solution Computer Solution with Excel Chapter 6 - Transportation, Transshipment, and Assignment Problems

• More by User

Chapter 7 Transportation, Assignment and Transshipment Problems to accompany Operations Research: Applications & Al

Chapter 7 Transportation, Assignment and Transshipment Problems to accompany Operations Research: Applications & Algorithms, 4th edition, by Wayne L. Winston. Description.

1.63k views • 79 slides

Transportation and Assignment Problems

Transportation and Assignment Problems. The Transportation Model Solution of a Transportation Problem The Assignment Model Solution of the Assignment Model. Transportation and Assignment Problems Overview.

2.76k views • 58 slides

Chapter 10 Transportation and Assignment Models

Chapter 10 Transportation and Assignment Models. Learning Objectives. Students will be able to Structure special LP problems using the transportation and assignment models. Use the N.W. corner, VAM, MODI, and stepping-stone method.

883 views • 37 slides

The Transportation and Assignment Problems

The Transportation and Assignment Problems. Chapter 9: Hillier and Lieberman Chapter 7: Decision Tools for Agribusiness Dr. Hurley’s AGB 328 Course. Terms to Know.

734 views • 43 slides

Chapter 7: Transportation, assignment and transshipment problems

Chapter 7: Transportation, assignment and transshipment problems. Consists of nodes representing a set of origins and a set of destinations . An arc is used to represent the route from each origins to each destinations. Each origin has a supply and each destination has a demand.

1.56k views • 53 slides

Assignment 6 Sample problems

Assignment 6 Sample problems. Consider the following scratch program :. When the flag is clicked, how many times will the meow sound happen before everything stops? . When the flag is clicked, how many times will the meow sound happen before everything stops ? The answer is 11.

423 views • 32 slides

Chapter 6: Transportation, Assignment, and Transshipment Problems

Chapter 6: Transportation, Assignment, and Transshipment Problems. A network model is one which can be represented by a set of nodes, a set of arcs, and functions (e.g. costs, supplies, demands, etc.) associated with the arcs and/or nodes.

1.08k views • 40 slides

Chapter 7 Transportation, Assignment, and Transshipment Problems

Chapter 7 Transportation, Assignment, and Transshipment Problems. Math 305 2008. Special Types of LPs. Have used linear programming to formulate and solve two types of problem:

477 views • 11 slides

Transportation, Assignment, and Transshipment Problems

Transportation, Assignment, and Transshipment Problems. Chapter 7. Transportation, Assignment, and Transshipment Problems.

1.31k views • 19 slides

Chapter 10 Transportation, Transshipment, and Assignment Problems

Introduction to Management Science 8th Edition by Bernard W. Taylor III. Chapter 10 Transportation, Transshipment, and Assignment Problems. Chapter Topics. The Transportation Model Computer Solution of a Transportation Problem The Assignment Model

757 views • 35 slides

Logistics and Tools: Transportation and Transshipment Models

Logistics and Tools: Transportation and Transshipment Models. Transportation. Rail low-value, high-density, bulk products, raw materials, intermodal containers not as economical for small loads, slower, less flexible than trucking Trucking main mode of freight transport in U.S.

559 views • 14 slides

Chapter 6 Problems

Chapter 6 Problems. Whose excited? No one? Ok, well here we go anyways…. #6 – HW PROBLEM. ANSWER. #17 – like #18 on HW. Answer #17 – like #18 on HW. #22 – HW Problem. #22 ANSWER. #30 and #32 – like #32 on HW. #38 – Like #36 on HW. Consider the IQ Model N(100,16)

206 views • 13 slides

543 views • 34 slides

Transportation, Assignment, and Transshipment

Transportation, Assignment, and Transshipment. Professor Ahmadi. Chapter 7 Transportation, Assignment, and Transshipment Problems. The Transportation Problem: The Network Model and a Linear Programming Formulation The Assignment Problem: The Network Model and a Linear Programming Formulation

590 views • 33 slides

Chapter 7 Transportation, Assignment and Transshipment Problems

Chapter 7 Transportation, Assignment and Transshipment Problems. Applications of Network Optimization. Applications. Physical analog of nodes. Physical analog of arcs. Flow. Communication systems. phone exchanges, computers, transmission facilities, satellites. Cables, fiber optic

1.61k views • 155 slides

1.64k views • 155 slides

377 views • 32 slides

Management Science Chapter 5 Transportation, Assignment, and Transshipment Problems

Management Science Chapter 5 Transportation, Assignment, and Transshipment Problems. Transportation, Assignment, and Transshipment Problems.

407 views • 34 slides

Transportation and Assignment Problems. Applications of Network Optimization. Applications. Physical analog of nodes. Physical analog of arcs. Flow. Communication systems. phone exchanges, computers, transmission facilities, satellites. Cables, fiber optic links, microwave

471 views • 35 slides

• Preferences

Chapter 7 Transportation, Assignment, and Transshipment Problems - PowerPoint PPT Presentation

Chapter 7 Transportation, Assignment, and Transshipment Problems

Bbc has two plants, each of which can produce 50 tons per week. ... example: bbc. initial transportation tableau ... example: bbc. phase i: minimum-cost procedure ... – powerpoint ppt presentation.

• Transportation Problem
• Network Representation and LP Formulation
• Transportation Simplex Method
• Assignment Problem
• Hungarian Method
• The Transshipment Problem
• A network model is one which can be represented by a set of nodes, a set of arcs, and functions (e.g. costs, supplies, demands, etc.) associated with the arcs and/or nodes.
• Transportation, assignment, and transshipment problems of this chapter, as well as the shortest route, minimal spanning tree, and maximal flow problems (Chapter 9) and PERT/CPM problems (Chapter 10) are all examples of network problems.
• Each of the three models of this chapter (transportation, assignment, and transshipment models) can be formulated as linear programs and solved by general purpose linear programming codes.
• For each of the three models, if the right-hand side of the linear programming formulations are all integers, the optimal solution will be in terms of integer values for the decision variables.
• However, there are many computer packages (including The Management Scientist) which contain separate computer codes for these models which take advantage of their network structure.
• The transportation problem seeks to minimize the total shipping costs of transporting goods from m origins (each with a supply si) to n destinations (each with a demand dj), when the unit shipping cost from an origin, i, to a destination, j, is cij.
• The network representation for a transportation problem with two sources and three destinations is given on the next slide.
• Network Representation
• LP Formulation
• The LP formulation in terms of the amounts shipped from the origins to the destinations, xij , can be written as
• Min ??cijxij
• s.t. ?xij each origin i
• ?xij dj for each destination j
• xij 0 for all i and j
• LP Formulation Special Cases
• The following special-case modifications to the linear programming formulation can be made
• Minimum shipping guarantee from i to j
• Maximum route capacity from i to j
• Unacceptable route
• Remove the corresponding decision variable.
• Delivery Cost Per Ton
• Northwood Westwood Eastwood
• Plant 1 24 30 40
• Plant 2 30 40 42
• Partial Spreadsheet Showing Problem Data
• Partial Spreadsheet Showing Optimal Solution
• Optimal Solution
• 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
• Partial Sensitivity Report (first half)
• Partial Sensitivity Report (second half)
• The transportation simplex method requires that the sum of the supplies at the origins equal the sum of the demands at the destinations.
• If the total supply is greater than the total demand, a dummy destination is added with demand equal to the excess supply, and shipping costs from all origins are zero. (If total supply is less than total demand, a dummy origin is added.)
• When solving a transportation problem by its special purpose algorithm, unacceptable shipping routes are given a cost of M (a large number).
• A transportation tableau is given below. Each cell represents a shipping route (which is an arc on the network and a decision variable in the LP formulation), and the unit shipping costs are given in an upper right hand box in the cell.
• The transportation problem is solved in two phases
• Phase I -- Obtaining an initial feasible solution
• Phase II -- Moving toward optimality
• Phase I The Minimum-Cost Procedure can be used to establish an initial basic feasible solution without doing numerous iterations of the simplex method.
• Phase II The Stepping Stone Method - using the MODI Method for evaluating the reduced costs - may be used to move from the initial feasible solution to the optimal one.
• Phase I - Minimum-Cost Method
• Step 1 Select the cell with the least cost. Assign to this cell the minimum of its remaining row supply or remaining column demand.
• Step 2 Decrease the row and column availabilities by this amount and remove from consideration all other cells in the row or column with zero availability/demand. (If both are simultaneously reduced to 0, assign an allocation of 0 to any other unoccupied cell in the row or column before deleting both.) GO TO STEP 1.
• Phase II - Stepping Stone Method
• Step 1 For each unoccupied cell, calculate the reduced cost by the MODI method described on an upcoming slide.
• Select the unoccupied cell with the most negative reduced cost. (For maximization problems select the unoccupied cell with the largest reduced cost.) If none, STOP.
• Phase II - Stepping Stone Method (continued)
• Step 2 For this unoccupied cell generate a stepping stone path by forming a closed loop with this cell and occupied cells by drawing connecting alternating horizontal and vertical lines between them.
• Determine the minimum allocation where a subtraction is to be made along this path.
• Step 3 Add this allocation to all cells where additions are to be made, and subtract this allocation to all cells where subtractions are to be made along the stepping stone path.
• (Note An occupied cell on the stepping stone path now becomes 0 (unoccupied). If more than one cell becomes 0, make only one unoccupied make the others occupied with 0's.)
• GO TO STEP 1.
• MODI Method (for obtaining reduced costs)
• Associate a number, ui, with each row and vj with each column.
• Step 1 Set u1 0.
• Step 2 Calculate the remaining ui's and vj's by solving the relationship cij ui vj for occupied cells.
• Step 3 For unoccupied cells (i,j), the reduced cost cij - ui - vj.
• Initial Transportation Tableau
• Since total supply 100 and total demand 80, a dummy destination is created with demand of 20 and 0 unit costs.
• Phase I Minimum-Cost Procedure
• Iteration 1 Tie for least cost (0), arbitrarily select x14. Allocate 20. Reduce s1 by 20 to 30 and delete the Dummy column.
• Iteration 2 Of the remaining cells the least cost is 24 for x11. Allocate 25. Reduce s1 by 25 to 5 and eliminate the Northwood column.
• Phase I Minimum-Cost Procedure (continued)
• Iteration 3 Of the remaining cells the least cost is 30 for x12. Allocate 5. Reduce the Westwood column to 40 and eliminate the Plant 1 row.
• Iteration 4 Since there is only one row with two cells left, make the final allocations of 40 and 10 to x22 and x23, respectively.
• Phase II Iteration 1
• MODI Method
• 1. Set u1 0
• 2. Since u1 vj c1j for occupied cells in row 1, then
• v1 24, v2 30, v4 0.
• 3. Since ui v2 ci2 for occupied cells in column 2, then u2 30 40, hence u2 10.
• 4. Since u2 vj c2j for occupied cells in row 2, then
• 10 v3 42, hence v3 32.
• MODI Method (continued)
• Calculate the reduced costs (circled numbers on the next slide) by cij - ui vj.
• Unoccupied Cell Reduced Cost
• (1,3) 40 - 0 - 32 8
• (2,1) 30 - 24 -10 -4
• (2,4) 0 - 10 - 0 -10
• Stepping Stone Method
• The stepping stone path for cell (2,4) is (2,4), (1,4), (1,2), (2,2). The allocations in the subtraction cells are 20 and 40, respectively. The minimum is 20, and hence reallocate 20 along this path. Thus for the next tableau
• x24 0 20 20 (0 is its current allocation)
• x14 20 - 20 0 (blank for the next tableau)
• x12 5 20 25
• x22 40 - 20 20
• The other occupied cells remain the same.
• Phase II - Iteration 2
• The reduced costs are found by calculating the ui's and vj's for this tableau.
• 1. Set u1 0.
• 2. Since u1 vj cij for occupied cells in row 1, then
• v1 24, v2 30.
• 3. Since ui v2 ci2 for occupied cells in column 2, then u2 30 40, or u2 10.
• 10 v3 42 or v3 32 and, 10 v4 0 or v4 -10.
• (1,4) 0 - 0 - (-10) 10
• (2,1) 30 - 10 - 24 -4
• The most negative reduced cost is -4 determined by x21. The stepping stone path for this cell is (2,1),(1,1),(1,2),(2,2). The allocations in the subtraction cells are 25 and 20 respectively. Thus, the new solution is obtained by reallocating 20 on the stepping stone path.
• Stepping Stone Method (continued)
• Thus, for the next tableau
• x21 0 20 20 (0 is its current allocation)
• x11 25 - 20 5
• x12 25 20 45
• x22 20 - 20 0 (blank for the next tableau)
• Phase II - Iteration 3
• v1 24 and v2 30.
• 3. Since ui v1 ci1 for occupied cells in column 2, then u2 24 30 or u2 6.
• 6 v3 42 or v3 36, and 6 v4 0 or v4 -6.
• (1,3) 40 - 0 - 36 4
• (1,4) 0 - 0 - (-6) 6
• (2,2) 40 - 6 - 30 4
• Since all the reduced costs are non-negative, this is the optimal tableau.
• An assignment problem seeks to minimize the total cost assignment of m workers to m jobs, given that the cost of worker i performing job j is cij.
• It assumes all workers are assigned and each job is performed.
• An assignment problem is a special case of a transportation problem in which all supplies and all demands are equal to 1 hence assignment problems may be solved as linear programs.
• The network representation of an assignment problem with three workers and three jobs is shown on the next slide.
• s.t. ?xij 1 for each agent i
• ?xij 1 for each task j
• xij 0 or 1 for all i and j
• Note A modification to the right-hand side of the first constraint set can be made if a worker is permitted to work more than 1 job.
• Number of agents exceeds the number of tasks
• Number of tasks exceeds the number of agents
• Add enough dummy agents to equalize the
• number of agents and the number of tasks.
• The objective function coefficients for these
• new variable would be zero.
• LP Formulation Special Cases (continued)
• The assignment alternatives are evaluated in terms of revenue or profit
• Solve as a maximization problem.
• An assignment is unacceptable
• An agent is permitted to work a tasks
• Linear Programming Formulation
• Min 50x1136x1216x1328x2130x2218x23
• 35x3132x3220x3325x4125x4214x43
• x11x21x31x41 1
• x12x22x32x42 1
• x13x23x33x43 1
• The Hungarian method solves minimization assignment problems with m workers and m jobs.
• Special considerations can include
• number of workers does not equal the number of jobs -- add dummy workers or jobs with 0 assignment costs as needed
• worker i cannot do job j -- assign cij M
• maximization objective -- create an opportunity loss matrix subtracting all profits for each job from the maximum profit for that job before beginning the Hungarian method
• Step 1 For each row, subtract the minimum number in that row from all numbers in that row.
• Step 2 For each column, subtract the minimum number in that column from all numbers in that column.
• Step 3 Draw the minimum number of lines to cover all zeroes. If this number m, STOP -- an assignment can be made.
• Step 4 Subtract d (the minimum uncovered number) from uncovered numbers. Add d to numbers covered by two lines. Numbers covered by one line remain the same. Then, GO TO STEP 3.
• Finding the Minimum Number of Lines and Determining the Optimal Solution
• Step 1 Find a row or column with only one unlined zero and circle it. (If all rows/columns have two or more unlined zeroes choose an arbitrary zero.)
• Step 2 If the circle is in a row with one zero, draw a line through its column. If the circle is in a column with one zero, draw a line through its row. One approach, when all rows and columns have two or more zeroes, is to draw a line through one with the most zeroes, breaking ties arbitrarily.
• Step 3 Repeat step 2 until all circles are lined. If this minimum number of lines equals m, the circles provide the optimal assignment.
• Initial Tableau Setup
• Since the Hungarian algorithm requires that there be the same number of rows as columns, add a Dummy column so that the first tableau is
• A B C Dummy
• Westside 50 36 16 0
• Federated 28 30 18 0
• Goliath 35 32 20 0
• Universal 25 25 14 0
• Step 1 Subtract minimum number in each row from all numbers in that row. Since each row has a zero, we would simply generate the same matrix above.
• Step 2 Subtract the minimum number in each column from all numbers in the column. For A it is 25, for B it is 25, for C it is 14, for Dummy it is 0. This yields
• Westside 25 11 2 0
• Federated 3 5 4 0
• Goliath 10 7 6 0
• Universal 0 0 0 0
• Step 3 Draw the minimum number of lines to cover all zeroes. Although one can "eyeball" this minimum, use the following algorithm. If a "remaining" row has only one zero, draw a line through the column. If a remaining column has only one zero in it, draw a line through the row.
• Step 4 The minimum uncovered number is 2. Subtract 2 from uncovered numbers add 2 to all numbers covered by two lines. This gives
• Westside 23 9 0 0
• Federated 1 3 2 0
• Goliath 8 5 4 0
• Universal 0 0 0 2
• Step 3 Draw the minimum number of lines to cover all zeroes.
• Step 4 The minimum uncovered number is 1. Subtract 1 from uncovered numbers. Add 1 to numbers covered by two lines. This gives
• Westside 23 9 0 1
• Federated 0 2 1 0
• Goliath 7 4 3 0
• Universal 0 0 0 3
• Step 3 The minimum number of lines to cover all 0's is four. Thus, there is a minimum-cost assignment of 0's with this tableau. The optimal assignment is
• Subcontractor Project Distance
• Westside C 16
• Federated A 28
• Goliath (unassigned)
• Universal B 25
• Total Distance 69 miles
• Transshipment problems are transportation problems in which a shipment may move through intermediate nodes (transshipment nodes)before reaching a particular destination node.
• Transshipment problems can be converted to larger transportation problems and solved by a special transportation program.
• Transshipment problems can also be solved by general purpose linear programming codes.
• The network representation for a transshipment problem with two sources, three intermediate nodes, and two destinations is shown on the next slide.
• xij represents the shipment from node i to node j
• s.t. ?xij for each origin i
• ?xik - ?xkj 0 for each intermediate
• Thomas Industries and Washburn Corporation supply three firms (Zrox, Hewes, Rockwright) with customized shelving for its offices. They both order shelving from the same two manufacturers, Arnold Manufacturers and Supershelf, Inc.
• Currently weekly demands by the users are 50 for Zrox, 60 for Hewes, and 40 for Rockwright. Both Arnold and Supershelf can supply at most 75 units to its customers.
• Additional data is shown on the next slide.
• Decision Variables Defined
• xij amount shipped from manufacturer i to supplier j
• xjk amount shipped from supplier j to customer k
• where i 1 (Arnold), 2 (Supershelf)
• j 3 (Thomas), 4 (Washburn)
• k 5 (Zrox), 6 (Hewes), 7 (Rockwright)
• Objective Function Defined
• Minimize Overall Shipping Costs
• Min 5x13 8x14 7x23 4x24 1x35 5x36 8x37
• 3x45 4x46 4x47
• Constraints Defined
• Amount Out of Arnold x13 x14 75
• Amount Through Thomas x13 x23 - x35 - x36 - x37 0
• Amount Through Washburn x14 x24 - x45 - x46 - x47 0
• Amount Into Zrox x35 x45 50
• Amount Into Hewes x36 x46 60
• Amount Into Rockwright x37 x47 40
• Non-negativity of Variables xij 0, for all i and j.
• Optimal Solution (from The Management Scientist )
• Objective Function Value 1150.000
• Variable Value Reduced Costs
• X13 75.000 0.000
• X14 0.000 2.000
• X23 0.000 4.000
• X24 75.000 0.000
• X35 50.000 0.000
• X36 25.000 0.000
• X37 0.000 3.000
• X45 0.000 3.000
• X46 35.000 0.000
• X47 40.000 0.000
• Optimal Solution (continued)
• Constraint Slack/Surplus Dual Prices
• 1 0.000 0.000
• 2 0.000 2.000
• 3 0.000 -5.000
• 4 0.000 -6.000
• 5 0.000 -6.000
• 6 0.000 -10.000
• 7 0.000 -10.000
• OBJECTIVE COEFFICIENT RANGES
• Variable Lower Limit Current Value Upper Limit
• X13 3.000 5.000 7.000
• X14 6.000 8.000 No Limit
• X23 3.000 7.000 No Limit
• X24 No Limit 4.000 6.000
• X35 No Limit 1.000 4.000
• X36 3.000 5.000 7.000
• X37 5.000 8.000 No Limit
• X45 0.000 3.000 No Limit
• X46 2.000 4.000 6.000
• X47 No Limit 4.000 7.000
• RIGHT HAND SIDE RANGES
• Constraint Lower Limit Current Value Upper Limit
• 1 75.000 75.000 No Limit
• 2 75.000 75.000 100.000
• 3 -75.000 0.000 0.000
• 4 -25.000 0.000 0.000
• 5 0.000 50.000 50.000
• 6 35.000 60.000 60.000
• 7 15.000 40.000 40.000

PowerShow.com is a leading presentation sharing website. It has millions of presentations already uploaded and available with 1,000s more being uploaded by its users every day. Whatever your area of interest, here you’ll be able to find and view presentations you’ll love and possibly download. And, best of all, it is completely free and easy to use.

You might even have a presentation you’d like to share with others. If so, just upload it to PowerShow.com. We’ll convert it to an HTML5 slideshow that includes all the media types you’ve already added: audio, video, music, pictures, animations and transition effects. Then you can share it with your target audience as well as PowerShow.com’s millions of monthly visitors. And, again, it’s all free.

About the Developers

PowerShow.com is brought to you by  CrystalGraphics , the award-winning developer and market-leading publisher of rich-media enhancement products for presentations. Our product offerings include millions of PowerPoint templates, diagrams, animated 3D characters and more.