Transcription
Transportation,Transshipment, andAssignment ProblemsChapter 6Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-1Chapter Topics The Transportation Model Computer Solution of a Transportation Problem The Transshipment Model The Assignment Model Computer Solution of an Assignment ProblemCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-21
Overview Part of a class of LP problems known as network flow models. Special mathematical features that permit very efficient, uniquesolution methods (variations of traditional simplex procedure). Detailed description of methods is contained on the companionwebsite Text focuses on model formulation and solution with Excel andQM for windows. Web site Module B addresses transportation and assignmentsolution methodsCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3The Transportation Model: Characteristics A product is transported from a number of sources to a number ofdestinations at the minimum possible cost. Each source is able to supply a fixed number of units of theproduct, and each destination has a fixed demand for theproduct. The linear programming model has constraints for supply at eachsource and demand at each destination. All constraints are equalities in a balanced transportation modelwhere supply equals demand. Constraints contain inequalities in unbalanced models where supplydoes not equal demand.Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-42
Transportation Model ExampleProblem Definition and DataHow many tons of wheat to transport from each grainelevator to each mill on a monthly basis in order tominimize the total cost of transportation?Grain ElevatorSupply1. Kansas City150A. Chicago2202. Omaha175B. St. Louis100C. Cincinnati3003. Des MoinesTotal275600 tonsMillTotalDemand600 tonsTransport Cost from Grain Elevator to Mill ( /ton)Grain ElevatorA. ChicagoB. St. LouisC. Cincinnati1. Kansas City 6 8 102. Omaha711113. Des Moines4512Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-5Transportation Model ExampleTransportation Network RoutesFigure 6.1 Network of transportation routes for wheat shipmentsCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-63
Transportation Model ExampleModel FormulationMinimize Z 6x1A 8x1B 10x1C 7x2A 11x2B 11x2C 4x3A 5x3B 12x3Csubject to:x1A x1B x1C 150x2A x2B x2C 175x3A x3B x3C 275x1A x2A x3A 200x1B x2B x3B 100x1C x2C x3C 300xij 0xij tons of wheat from each grain elevator, i, i 1, 2, 3,to each mill j, j A,B,CCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-7Transportation Model ExampleComputer Solution with Excel (1 of 4)Objective function C7 D7 E7 D5 D6 D7Decision variablesin cells C5:E7Cost array incells K5:M7Exhibit 6.1Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-84
Transportation Model ExampleComputer Solution with Excel (2 of 4)Supply constraintsDemand constraintsCopyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.26-9Transportation Model ExampleComputer Solution with Excel (3 of 4)Exhibit 6.3Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-105
Transportation Model ExampleComputer Solution with Excel (4 of 4)Figure 6.2 Transportation network solution for wheat-shipping exampleCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-11Transportation Model ExampleComputer Solution with Excel QM (1 of 3)Exhibit 6.4Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-126
Transportation Model ExampleComputer Solution with Excel QM (2 of 3)1. Click on “Add Ins,” then “Excel QM”or “Taylor” to access the macro menu3. Click on “Data,”“Solver,” and then“Solve.”2. Enter data valuesfor problems; initiallythis array is blankCopyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.56-13Transportation Model ExampleComputer Solution with Excel QM (3 of 3)Click on “Data” tab and then “Solver”Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.66-147
Transportation Model ExampleComputer Solution with QM for Windows (1 of 4)Use any startingmethodExhibit 6.7Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-15Transportation Model ExampleComputer Solution with QM for Windows (2 of 4)Exhibit 6.8Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-168
Transportation Model ExampleComputer Solution with QM for Windows (3 of 4)Exhibit 6.9Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-17Transportation Model ExampleComputer Solution with QM for Windows (4 of 4)Change in costAdded new row to reflectdemand supplySensitivity analysis oftransportation scenarioExhibit 6.10Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-189
The Transshipment ModelCharacteristics Extension of the transportation model. Intermediate transshipment points are added between the sourcesand 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 destinations Some combination of theseS1T1S2T2Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallD16-19Transshipment Model ExampleProblem Definition and DataExtension of the transportation model in whichintermediate transshipment points are added betweensources and destinations.Shipping CostsFarm1. Nebraska2. Colorado3. Kansas City 1615Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallGrain Elevator4. Omaha10145. Des Moines12176-2010
Transshipment Model ExampleTransshipment Network RoutesFigure 6.3Network of transshipment routesCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-21Transshipment Model ExampleModel FormulationMinimize Z 16x13 10x14 12x15 15x23 14x24 17x25 6x36 8x37 10x38 7x46 11x47 11x48 4x56 5x57 12x58subject to:x13 x14 x15 300x23 x24 x25 300x36 x46 x56 200x37 x47 x57 100x38 x48 x58 300x13 x23 - x36 - x37 - x38 0x14 x24 - x46 - x47 - x48 0x15 x25 - x56 - x57 - x58 0xij 0Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallSupply constraints for farmsin Nebraska and ColoradoDemand constraints atthe Chicago, St. Louisand Cincinnati mills6-2211
Transshipment Model ExampleComputer Solution with Excel (1 of 3) SUM(B6:B7)Objective function SUM(B6:D6)Cost arrays SUM(C13:C15) SUM(C13:E13)Constraints for transshipment flows;i.e., shipments in shipments outCopyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.116-23Transshipment Model ExampleComputer Solution with Excel (2 of 3)Transshipmentconstraints incells C20:C22Exhibit 6.12Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-2412
Transshipment Model ExampleNetwork Solution for Wheat Shipping (3 of 3)Figure 6.4 Transshipment network solution for wheat-shipping exampleCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-25The Assignment ModelCharacteristics Special form of linear programming model similar to thetransportation model. Supply at each source and demand at each destinationlimited to one unit. In a balanced model supply equals demand. In an unbalanced model supply does not equal demand.Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-2613
Assignment Model ExampleProblem Definition and DataProblem: Assign four teams of officials to four games ina way that will minimize total distance traveled by theofficials. Supply is always one team of officials, demand isfor only one team of officials at each game.Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-27Assignment Model ExampleModel FormulationMinimize Z 210xAR 90xAA 180xAD 160xAC 100xBR 70xBA 130xBD 200xBC 175xCR 105xCA 140xCD 170xCC 80xDR 65xDA 105xDD 120xDCsubject to:xAR xAA xAD xAC 1xBR xBA xBD xBC 1xCR xCA xCD xCC 1xDR xDA xDD xDC 1xAR xBR xCR xDR 1xAA xBA xCA xDA 1xAD xBD xCD xDD 1xAC xBC xCC xDC 1Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hallxij 06-2814
Assignment Model ExampleComputer Solution with Excel (1 of 3)Objective functionDecisionvariables,C5:F8 C5 D5 E5 F5 D5 D6 D7 D8Mileage arrayExhibit 6.13Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-29Assignment Model ExampleComputer Solution with Excel (2 of 3)Exhibit 6.14Simplex LPCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3015
Assignment Model ExampleComputer Solution with Excel (3 of 3)Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.156-31Assignment Model ExampleAssignment Network SolutionFigure 6.5 Assignment network solution for ACC officialsCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3216
Assignment Model ExampleComputer Solution with Excel QMCopyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.166-33Assignment Model ExampleComputer Solution with QM for Windows (1 of 2)Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.176-3417
Assignment Model ExampleComputer Solution with QM for Windows (2 of 2)Copyright 2013 Pearson Education, Inc. Publishing as Prentice HallExhibit 6.186-35Example Problem SolutionTransportation Problem StatementA concrete company transports concrete from threeplants to three construction sites. The supply capacities ofthe three plants, the demand requirements at the threesites, and the transportation costs per ton are as follows:Plant123Demand (tons)Construction siteABC 8 5 6151012391015070100Supply (tons)1208080Determine the linear programming model formulation andsolve using Excel.Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3618
Example Problem SolutionModel FormulationMinimize Z 8x1A 5x1B 6x1C 15x2A 10x2B 12x2C 3x3A 9x3B 10x3Csubject to:x1A x1B x1C 120x2A x2B x2C 80x3A x3B x3C 80x1A x2A x3A 150x1B x2B x3B 70x1C x2C x3C 100xij 0Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-37Example Problem SolutionComputer Solution with ExcelCopyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3819
All rights reserved. No part of this publication may be reproduced, stored in a retrievalsystem, or transmitted, in any form or by any means, electronic, mechanical, photocopying,recording, or otherwise, without the prior written permission of the publisher.Printed in the United States of America.Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall6-3920
2 Copyright 2013 Pearson Education, Inc. Publishing as Prentice Hall 6-3 Overview Part of a class of LP problems known as network flow models. Special mathematical .
