4a transportasi & penugasan

Transportation and Assignment Models

Chapter OutlineIntroductionSetting Up a Transportation ProblemDeveloping an Initial Solution:Northwest Corner RuleStepping-Stone Method: Finding a Least-Cost SolutionMODI Method

Chapter Outline - continuedVogels Approximation Method: Another Way to Find an Initial SolutionUnbalanced Transportation ProblemsDegeneracy in Transportation ProblemsMore Than One Optimal SolutionFacility Location Analysis

Learning ObjectivesStudents will be able toStructure special linear programming problems using the transportation and assignment models.Use the northwest corner method and Vogels approximation method to find initial solutions to transportation problems.Apply the stepping-stone and MODI methods to find optimal solutions to transportation problems.

Learning Objectives - continuedSolve the facility location problem and other application problems with the transportation model.Solve assignment problems with the Hungarian (matrix reduction) method.

Specialized ProblemsTransportation ProblemDistribution of items from several sources to several destinations. Supply capacities and destination requirements known.Assignment ProblemOne to one assignment of people to jobs, etc.

Specialized algorithms save time!

Transportation ProblemDes Moines(100 units)capacityCleveland(200 units)requiredBoston(200 units)requiredEvansville(300 units)capacityFt. Lauderdale(300 units)capacityAlbuquerque(300 units)required

Transportation Costs

Unit Shipping Cost:1Unit, Factory to Warehouse

Total Demand and Total Supply

Transportation Table For Executive Furniture Corp.

Initial Solution Using the Northwest Corner RuleStart in the upper left-hand cell and allocate units to shipping routes as follows:Exhaust the supply (factory capacity) of each row before moving down to the next row.Exhaust the demand (warehouse) requirements of each column before moving to the next column to the right.Check that all supply and demand requirements are met.

Initial SolutionNorth West Corner Rule100200100100200

The Stepping-Stone Method1. Select any unused square to evaluate.2. Begin at this square. Trace a closed path back to the original square via squares that are currently being used (only horizontal or vertical moves allowed).3. Place + in unused square; alternate - and + on each corner square of the closed path.4. Calculate improvement index: add together the unit cost figures found in each square containing a +; subtract the unit cost figure in each square containing a -.5. Repeat steps 1 - 4 for each unused square.

Stepping-Stone Method - The Des Moines-to-Cleveland RouteDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity300200200700300300100543357489200100100100200-+-++-Start

Stepping-Stone MethodAn Improved SolutionDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity300200200700300300100543357489100100200200100

Third and Final SolutionDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity300200200700300300100543357489100200100200100

MODI Method: 5 Steps1. Compute the values for each row and column: set Ri + Kj = Cij for those squares currently used or occupied.2. After writing all equations, set R1 = 0.3. Solve the system of equations for Ri and Kj values.4. Compute the improvement index for each unused square by the formula improvement index: Cij - Ri - Kj 5. Select the largest negative index and proceed to solve the problem as you did using the stepping-stone method.

Vogels Approximation For each row/column of table, find difference between two lowest costs. (Opportunity cost)Find greatest opportunity cost.Assign as many units as possible to lowest cost square in row/column with greatest opportunity cost.Eliminate row or column which has been completely satisfied.Begin again, omitting eliminated rows/columns.

Vogels ApproximationDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity300200200700300300100543357489121423200

Vogels ApproximationDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity30020020070030030010054335748911423200100

Vogels ApproximationDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity3002002007003003001005433574894123200100100

Vogels ApproximationDes Moines(D)Evansville(E)Ft Lauderdale(F)WarehouseReq.Albuquerque(A)Boston(B)Cleveland(C)FactoryCapacity300200200700300300100543357489200100100100200

Special Problems in Transportation MethodUnbalanced ProblemDemand Less than SupplyDemand Greater than Supply DegeneracyMore Than One Optimal Solution

Unbalanced ProblemDemand Less than SupplyFactory 1Factory 2Factory 3Customer RequirementsCustomer 1Customer 2DummyFactoryCapacity15080150380801301708516710910153

Unbalanced ProblemSupply Less than DemandFactory 1Factory 2DummyCustomer RequirementsCustomer 1Customer 2Customer 3FactoryCapacity15080150380801301708516710910153

DegeneracyFactory 1Factory 2Factory 3Customer RequirementsCustomer 1Customer 2Customer 3FactoryCapacity100100100300801201005433574891001008020

Degeneracy - Coming Up!Factory 1Factory 2Factory 3Customer RequirementsCustomer 1Customer 2Customer 3FactoryCapacity1508050280801307085167109101537080505030

Stepping-Stone Method - The Des Moines-to-Cleveland Route

The Assignment Method1. subtract the smallest number in each row from every number in that rowsubtract the smallest number in each column from every number in that column2. draw the minimum number of vertical and horizontal straight lines necessary to cover zeros in the table if the number of lines equals the number of rows or columns, then one can make an optimal assignment (step 4)

The Assignment Method continued3. if the number of lines does not equal the number of rows or columnssubtract the smallest number not covered by a line from every other uncovered numberadd the same number to any number lying at the intersection of any two linesreturn to step 24. make optimal assignments at locations of zeros within the tablePG 10.13b

Hungarian MethodInitial Table

Person

Project

1

2

3

Adams

11

14

6

Brown

8

10

11

Cooper

9

12

7

Hungarian MethodRow Reduction

Person

Project

1

2

3

Adams

5

8

0

Brown

0

2

3

Cooper

2

5

0

Hungarian MethodColumn Reduction

Person

Project

1

2

3

Adams

5

6

0

Brown

0

0

3

Cooper

2

3

0

Hungarian MethodTestingCovering Line 2Covering Line 1

Person

Project

1

2

3

Adams

5

6

0

Brown

0

0

3

Cooper

2

3

0

Hungarian MethodPersonProject123Adams340Brown005Cooper010Revised Opportunity Cost Table

Hungarian MethodPersonProject123Adams340Brown005Cooper010TestingCovering Line 1Covering Line 2Covering Line 3

Hungarian MethodAssignments

Person

Project

1

2

3

Adams

6

Brown

10

Cooper

9