数据、模型与决策（第12版）课件 第6章运输、转运与指派问题

Transportation,Transshipment,andAssignmentProblemsChapter6Copyright©2016PearsonEducation,Inc.ChapterTopicsTheTransportationModelComputerSolutionofaTransportationProblemTheTransshipmentModelTheAssignmentModelComputerSolutionofanAssignmentProblemCopyright©2016PearsonEducation,Inc.OverviewPartofaclassofLPproblemsknownasnetworkflowmodels.Specialmathematicalfeaturesthatpermitveryefficient,uniquesolutionmethods(variationsoftraditionalsimplexprocedure).DetaileddescriptionofmethodsiscontainedonthecompanionwebsiteTextfocusesonmodelformulationandsolutionwithExcelandQMforwindows.WebsiteModuleBaddressestransportationandassignmentsolutionmethodsCopyright©2016PearsonEducation,Inc.TheTransportationModel:CharacteristicsAproductistransportedfromanumberofsourcestoanumberofdestinationsattheminimumpossiblecost.Eachsourceisabletosupplyafixednumberofunitsoftheproduct,andeachdestinationhasafixeddemandfortheproduct.Thelinearprogrammingmodelhasconstraintsforsupplyateachsourceanddemandateachdestination.Allconstraintsareequalitiesinabalancedtransportationmodelwheresupplyequalsdemand.Constraintscontaininequalitiesinunbalancedmodelswheresupplydoesnotequaldemand.Copyright©2016PearsonEducation,Inc.TransportationModelExampleProblemDefinitionandData Howmanytonsofwheattotransportfromeachgrainelevatortoeachmillonamonthlybasisinordertominimizethetotalcostoftransportation?GrainElevator

Supply

Mill

Demand1.KansasCity 150 A.Chicago 2202.Omaha175 B.St.Louis 1003.DesMoines 275 C.Cincinnati 300Total600tonsTotal600tonsCopyright©2016PearsonEducation,Inc.TransportationModelExampleTransportationNetworkRoutesFigure6.1NetworkoftransportationroutesforwheatshipmentsCopyright©2016PearsonEducation,Inc.MinimizeZ=$6x1A+8x1B+10x1C+7x2A+11x2B+11x2C+ 4x3A+5x3B+12x3Csubjectto: x1A+x1B+x1C=150 x2A+x2B+x2C=175x3A+x3B+x3C=275x1A+x2A+x3A=200x1B+x2B+x3B=100x1C+x2C+x3C=300xij

0xij=tonsofwheatfromeachgrainelevator,i,i=1,2,3,toeachmillj,j=A,B,CTransportationModelExampleModelFormulationCopyright©2016PearsonEducation,Inc.TransportationModelExampleComputerSolutionwithExcel(1of4)Exhibit6.1Objectivefunction=D5+D6+D7DecisionvariablesincellsC5:E7=C7+D7+E7CostarrayincellsK5:M7Copyright©2016PearsonEducation,Inc.Exhibit6.2TransportationModelExampleComputerSolutionwithExcel(2of4)SupplyconstraintsDemandconstraintsCopyright©2016PearsonEducation,Inc.TransportationModelExampleComputerSolutionwithExcel(3of4)Exhibit6.3Copyright©2016PearsonEducation,Inc.TransportationModelExampleComputerSolutionwithExcel(4of4)Figure6.2Transportationnetworksolutionforwheat-shippingexampleCopyright©2016PearsonEducation,Inc.TransportationModelExampleComputerSolutionwithExcelQM(1of3)Exhibit6.4Copyright©2016PearsonEducation,Inc.Exhibit6.5TransportationModelExampleComputerSolutionwithExcelQM(2of3)1.Clickon“ExcelQM,”then“Bchapter”toaccessthemacromenu2.Enterdatavaluesforproblems;initiallythisarrayisblankCopyright©2016PearsonEducation,Inc.Exhibit6.6TransportationModelExampleComputerSolutionwithExcelQM(3of3)Clickon“Data”tabandthen“Solver”Copyright©2016PearsonEducation,Inc.Exhibit6.7TransportationModelExampleComputerSolutionwithQMforWindows(1of4)UseanystartingmethodCopyright©2016PearsonEducation,Inc.Exhibit6.8TransportationModelExampleComputerSolutionwithQMforWindows(2of4)Notesthat“multipleoptimalsolutions”existCopyright©2016PearsonEducation,Inc.Exhibit6.9TransportationModelExampleComputerSolutionwithQMforWindows(3of4)Copyright©2016PearsonEducation,Inc.Exhibit6.10TransportationModelExampleComputerSolutionwithQMforWindows(4of4)SensitivityanalysisoftransportationscenarioAddednewrowtoreflectdemand>supplyChangeincostCopyright©2016PearsonEducation,Inc.Extensionofthetransportationmodel.Intermediatetransshipmentpointsareaddedbetweenthesourcesanddestinations.Itemsmaybetransportedfrom:SourcesthroughtransshipmentpointstodestinationsOnesourcetoanotherOnetransshipmentpointtoanotherOnedestinationtoanotherDirectlyfromsourcestodestinationsSomecombinationoftheseTheTransshipmentModelCharacteristicsS1S2D1T1T2Copyright©2016PearsonEducation,Inc. Extensionofthetransportationmodelinwhichintermediatetransshipmentpointsareaddedbetweensourcesanddestinations.TransshipmentModelExampleProblemDefinitionandData1.Nebraska2.ColoradoShippingCostsCopyright©2016PearsonEducation,Inc.Figure6.3Networkoftransshipmentroutes

TransshipmentModelExampleTransshipmentNetworkRoutesCopyright©2016PearsonEducation,Inc.MinimizeZ= $16x13+10x14+12x15+15x23+14x24

+17x25+6x36+8x37+10x38+7x46+11x47

+11x48+4x56+5x57+12x58subjectto: x13+x14+x15=300 x23+x24+x25=300 x36+x46+x56=200 x37+x47+x57=100 x38+x48+x58=300 x13+x23-x36-x37-x38=0 x14+x24-x46-x47-x48=0 x15+x25-x56-x57-x58=0 xij

0TransshipmentModelExampleModelFormulationSupplyconstraintsforfarmsinNebraskaandColoradoDemandconstraintsattheChicago,St.LouisandCincinnatimillsCopyright©2016PearsonEducation,Inc.TransshipmentModelExampleComputerSolutionwithExcel(1of3)Exhibit6.11Objectivefunction=SUM(B6:D6)=SUM(B6:B7)=SUM(C13:C15)=SUM(C13:E13)CostarraysConstraintsfortransshipmentflows;i.e.,shipmentsin=shipmentsoutCopyright©2016PearsonEducation,Inc.TransshipmentModelExampleComputerSolutionwithExcel(2of3)Exhibit6.12TransshipmentconstraintsincellsC20:C22Copyright©2016PearsonEducation,Inc.TransshipmentModelExampleNetworkSolutionforWheatShipping(3of3)Figure6.4Transshipmentnetworksolutionforwheat-shippingexampleCopyright©2016PearsonEducation,Inc.Specialformoflinearprogrammingmodelsimilartothetransportationmodel.Supplyateachsourceanddemandateachdestinationlimitedtooneunit.Inabalancedmodelsupplyequalsdemand.Inanunbalancedmodelsupplydoesnotequaldemand.TheAssignmentModelCharacteristicsCopyright©2016PearsonEducation,Inc.AssignmentModelExampleProblemDefinitionandData Problem:Assignfourteamsofofficialstofourgamesinawaythatwillminimizetotaldistancetraveledbytheofficials.Supplyisalwaysoneteamofofficials,demandisforonlyoneteamofofficialsateachgame.Copyright©2016PearsonEducation,Inc.MinimizeZ= 210xAR+90xAA+180xAD+160xAC+100xBR +70xBA

+130xBD+200xBC+175xCR+105xCA+140xCD

+170xCC+80xDR+65xDA+105xDD+120xDCsubjectto: 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 AssignmentModelExampleModelFormulationCopyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithExcel(1of3)Exhibit6.13ObjectivefunctionDecisionvariables,C5:F8=C5+D5+E5+F5=D5+D6+D7+D8MileagearrayCopyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithExcel(2of3)Exhibit6.14SimplexLPCopyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithExcel(3of3)Exhibit6.15Copyright©2016PearsonEducation,Inc.AssignmentModelExampleAssignmentNetworkSolutionFigure6.5AssignmentnetworksolutionforACCofficialsCopyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithExcelQMExhibit6.16Copyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithQMforWindows(1of2)Exhibit6.17Copyright©2016PearsonEducation,Inc.AssignmentModelExampleComputerSolutionwithQMforWindows(2of2)Exhibit6.18Copyright©2016PearsonEducation,Inc. Aconcretecompanytransportsconcretefromthreeplantstothreeconstructionsites.Thesupplycapacitiesofthethreeplants,thedemandrequirementsatthethreesites,andthetransportationcostspertonareasfoll