数据、模型与决策(运筹学)课后习题和案例答案006

Chapter6

TransportationandAssignmentProblems

ReviewQuestions

6.1-1 TheCEOisconcernedaboutescalatingcosts,inparticulartheshippingcostsforpeas.

6.1-2 KimBakerisbeingaskedtolookatthecurrentshippingplanandseeiftheycandevelopanewonethatwouldreducethetotalshippingcosttoanabsoluteminimum.

6.2-1 Transportationproblemsingeneralareconcernedwithdistributinganycommodityfromanygroupofsupplycenters,calledsources,toanygroupofreceivingcenters,calleddestinations,insuchawayastominimizethetotaldistributioncost.

6.2-2 Thedataneededforatransportationproblemarethesupplies,demands,andunitcosts.

6.2-3 FormulatingaproblemasatransportationproblemonlyrequiresfillingoutatableintheformatofTable6.5.

6.2-4 Atransportationproblemwillhavefeasiblesolutionsifandonlyifthesumofitssuppliesequalsthesumofitsdemands.

6.2-5 Aslongasallitssuppliesanddemandshaveintegervalues,anytransportationproblemwithfeasiblesolutionsisguaranteedtohaveanoptimalsolutionwithintegervaluesforallitsdecisionvariables.

6.2-6 Thetransportationsimplexmethodandnetworksimplexmethodcansolvethemfaster.

6.3-1 A≤signinsteadofan=signisusedintherespectivecellsandthecorrespondingconstraintsintheSolverdialogbox.

6.3-2 Insteadofademandrow,thereisbothaminimumrowandamaximumrow.ThenconstraintsareenteredsothatShipped≥MinimumandShipped≤Maximum.

6.4-1 Theareasofapplicationinthissectionaredistributingnaturalresources,productionscheduling,designingschoolattendancezones,meetingenergyneeds,andchoosinganewsitelocation.

6.4-2 Minimizethetotalcostofmeetingthewaterneedsofthefourcitiestheyserve.

6.4-3 Thesourcesaretheproductionofjetenginesonregulartimeandovertimeineachofthefourmonths.Thedestinationsaretheirinstallationineachofthefourmonths.

6.4-4 Distancesplaytheroleofunitcosts.

6.4-5 Minimizethetotalcostofmeetingalltheenergyneeds.

6.5-1 Thethreekeyfactorsare(1)thecostoftransportingtheoilfromitssourcestoalltherefineries,includingthenewone;(2)thecostoftransportingfinishedproductfromalltherefineries,includingthenewone,tothedistributioncenters;and(3)operatingcostsforthenewrefineries.

6.5-2 Thenewrefinerywillhaveagreatimpactontheoperationoftheentiredistributionsystem,includingdecisionsonhowmuchtoshiptoandfromeachrefinery(newandold).

6.5-3 Threetransportationproblemsweresolvedtocomparetotalshippingcostsforcrudeoilwitheachpotentialchoiceofanewrefinerysite,andthreeweresolvedtocomparetotalshippingcostsforfinishedproductwitheachpotentialchoiceofanewrefinerysite.Thisresultedinsixtotalproblems.

6.5-4 Managementmustconsidernon-financialfactorsaswell,suchasclosenesstocorporateheadquartersandwhetherthereareanycosttrendsortrendsinthemarketplacethatmightalterthepictureinthefuture.

6.6-1 Givenasetoftaskstobeperformedandasetofassigneesthatareavailabletoperformthesetasks,theproblemistodeterminewhichassigneeshouldbeassignedtoeachtask.

6.6-2 (1)Thenumberofassigneesandthenumberoftasksarethesame;(2)eachassigneeistobeassignedtoexactlyonetask;(3)eachtaskistobeperformedbyexactlyoneassignee;(4)thereisacostassociatedwitheachcombinationofanassigneeperformingatask;and(5)theobjectiveistodeterminehowalltheassignmentshouldbemadetominimizethetotalcost.

6.6-3 (1)Identifytheassigneesandtasks,and(2)constructacosttablethatgivesthecostassociatedwitheachcombinationofanassigneeperformingatask.

6.6-4 Whenanassignmentproblemisdescribedasatransportationproblem,thesourcesareassignments,thedestinationsaretasks,andthesuppliesanddemandsareallequalto1.

6.6-5 TheHungarianmethodsolvesassignmentproblemswell.

6.7-1 Whenformulatingthespreadsheetmodel,aconstraintisincludedintheSolverdialogboxthatsetstheassignee/taskcombinationequalto0.

6.7-2 Ifanassigneewillperformmorethanonetask,thesupplyischangefrom1tothegreateramountthatcanbeperformed.

6.7-3 Ifataskwillbeperformedbymorethanoneassignee,thedemandischangedfrom1tothegreateramount.

Problems

6.1 a)

b)

6.2 a)

b)

6.3 a)

UnitCost($)

Destination(RetailOutlet)

1

2

3

4

Supply

1

500

600

400

200

10

Source

2

200

900

100

300

20

(Plant)

3

300

400

200

100

20

4

200

100

300

200

10

Demand

20

10

10

20

b)

6.4 a)

UnitCost($)

Destination(DistributionCenter)

1

2

3

4

Supply

Source

1

500

750

300

450

12

(Plant)

2

650

800

400

600

17

3

400

700

500

550

11

Demand

10

10

10

10

b)

6.5

6.6

6.7

6.8

6.9

AllowableRange

Destination

Sacramento

SaltLakeCity

RapidCity

Albuquerque

Source

Bellingham

449to∞

492to528

570to∞

516to888

Eugene

–∞to367

401to437

473to∞

770to∞

AlbertLea

267to∞

331to∞

–∞to472

601to1,036

Theserangestellmanagementhowmucheachindividualcostcanchangewithoutchangingtheoptimalsolution.

6.10

a) Theoptimalsolutionwouldchangebecausethedecreaseof$30millionisoutsidetheallowabledecreaseof$20million.

b) Theoptimalsolutionwouldremainthesamesincetheallowableincreaseis∞.

c) PercentageofallowabledecreaseforCalorietoSanGo=(230–215)/20=75%.

PercentageofallowableincreaseforSacrontoLosDevils=(145–130)/∞=0%.

Sum=75%≤100%,sobythe100%-ruletheoptimalsolutionwillnotchange.

d) PercentageofallowabledecreaseforsupplyatSacron=(0.5/2.5)=20%.

PercentageofallowabledecreasefordemandatHollyglass=(0.5/1.5)=33.3%.

Sum=53.3%≤100%,sobythe100%ruleforsimultaneouschanges,theshadowpriceswillremainvalid.

6.11

6.12

6.13

6.14

6.15

6.16

6.17 a) TheFeasibleSolutionsPropertyguaranteesthat,sincethesumofthesuppliesandthesumofthedemandsareequal,theproblemwillhavefeasiblesolutions.

b) TheIntegerSolutionPropertyguaranteesthat,sincesuppliesanddemandsareintegers,theresultingoptimalsolutionswillbeintegers.SuppliesandDemandsare1,sotheonlypossiblevaluesofvariablesinanoptimalsolutionare0or1.

c) Thiscanbeinterpretedasanassignmentproblemsinceallthesuppliesanddemandsareequalto1.Eachsourceshipsoneunit(theassignee)toonedestination(thetask).

d)

e)

6.18 a)

b)

6.19 a)

b)

6.20 a) Thisproblemfitsasanassignmentproblemwithshipsasassigneesandportsasassignments.

b)

6.21

6.22 a) Theproblemfitsintotheformatforanassignmentproblemwithswimmersbeingassignedtostrokes.Thetimesoftheswimmersreplacethecostsofatraditionalproblem.

b)

6.23

6.24

Cases

6.1 Option1(ShippingbyRail):

Option2(ShippingbyShip):

Option3(ShippingbyBestAvailableforeachRoute):

Whencomparingthethreeoptions,itisbesttousethecombinationplan,whileshippingentirelybyrailleadstothehighestcosts.

Ifcostsofshippingbywaterareexpectedtoriseconsiderablymorethanforshippingbyrail,staywithrailanduseOption1.Ifthereverseistrue,thenuseOption2.Ifthecostcomparisonswillremainroughlythesame,useOption3.Option3isclearlythemostfeasiblebutmaynotbechosenifitistoologisticallycumbersome.Moreknowledgeofthesituationisnecessarytodeterminethis.

6.2 a) $20millionissavedincomparisonwiththeresultsinFigure6.13byshipping20millionfewerbarrelstoCharlestonand20millionmoretoSt.Louis.

b) $40millionissavedincomparisonwiththeresultsinFigure6.17.

Thecostofshippingbothcrudeoilandfinishedproductunderthisplanis$940million+$1,390million=$2,330millionor$2.33billion—asavingsof$60millioncomparedtotheoriginalresultsinTable6.20.

c) $35millionissavedincomparisonwiththeresultsinpart(b).

$75millionissavedincomparisonwiththeresultsinFigure6.17.

d) Thissolutioncosts$40millionmorethanthesolutioninpart(a).

Thissolutioncosts$20millionmorethanthesolutionisFigure6.13.

Thetotalcostofshippingbothcrudeoilandfinishedproductunderthisplanis$1,355million+$980million=$2,335millionor$2.335billion.Thisis$5millionmorethanthecostofthecombinedtotalobtainedinpart(b),but$55millionlessthanthetotalinTable6.20.

e) Thetwotransportationproblems(shippingtorefineriesandshippingtodistributionscenters)arecombinedintoasinglemodel.Theamountshippedtotherefineriesisconstrainedtobenomorethancapacity:TotalReceived(D16:G16)≤Capacity(D18:G18).Thetotalshippedoutoftherefineriesisconstrainedtoequalthetotalamountshippedin:ShippedOut(H31:H34)=ShippedIn(J31:J34).Thegoalistominimizethetotalcombinedcost(inJ45)whichisthesumofthetwointermediatecosts(inJ20andJ39).

Thetotalcombinedcostis$2,320millionor$2.32billion,whichis$10millionlessthaninpart(b),$15millionlessthaninpart(d),and$70millionlessthaninTable6.20.

f) IftheLosAngelesrefineryischoseninstead,thenthecombinedshippingcostis$2,450million.

IftheGalvestonrefineryischoseninstead,thenthecombinedshippingcostis$2,470million.

Site

TotalCost

ofShipping

CrudeOil

TotalCost

ofShipping

FinishedProduct

OperatingCost

forNew

Refinery

Total

Variable

Cost

LosAngeles

$880million

$1.57billion

$620million

$3.07billion

Galveston

870million

1.60billion

570million

3.12billion

St.Louis

950million

1.37billion

530million

2.92billion

g) Answerswillvary.

6.3 a) Assignonescientisttoeachofthefiveprojectstomaximizethetotalnumberofbidpoints.

TomaximizethescientistspreferencesyouwanttoassignDr.TsaitoleadprojectUp,Dr.KvaaltoleadprojectStable,Dr.ZunertoleadprojectChoice,Dr.MickeytoleadprojectHope,andDr.RollinstoleadprojectRelease.

b) Dr.Rollinsisnotavailable,sohis“Supply”incellI14isreducedtozero.Sincenowmustallowaprojecttonotbedone,theconstraintsinrows15to17becomeTotalAssigned(B15:F15)≤Demand(B17:F17)ratherthan=.

ProjectUpwouldnotbedone.

c) SinceDr.ZoonerorDr.Mickeycanleadtwoprojects,their“Supply”incolumnIischangedto2andthecorrespondingconstraintchangedto≤(inordertoallowthemtodoeitheroneortwoprojects).

Dr.KvaalleadsprojectStable,Dr.ZunerleadsprojectChoice,Dr.TsaileadsprojectRelease,andDr.MickeyleadstheprojectsHopeandUp.

d) UnderthenewbidsofDr.Zunertheassignmentdoesnotchange:

e) CertainlyDr.ZunercouldbedisappointedthatsheisnotassignedtoprojectStable,especiallywhensheexpressedahigherpreferenceforthatprojectthanthescientistassigned.Theoptimalsolutionmaximizesthepreferencesoverall,butindividualscientistsmaybedisappointed.Weshouldthereforemake