4a transportasi & penugasan

Click here to load reader

Post on 19-Jul-2016

8 views

Category:

Documents

4 download

Embed Size (px)

DESCRIPTION

Riset Operasional

TRANSCRIPT

  • 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