简化版英文运筹学案例.docx

简化版英文运筹学案例.docx

《简化版英文运筹学案例.docx》由会员分享，可在线阅读，更多相关《简化版英文运筹学案例.docx（15页珍藏版）》请在冰点文库上搜索。

简化版英文运筹学案例

一、LP

1.Example2.3-1（UrbanRenewalModel）

ThecityofErstvilleisfacedwithaseverebudgetshortage.Seekingalong-termsolution,thecitycouncilvotestoimprovethetaxbasebycondemninganinner-cityhousingareaandreplacingitwithamoderndevelopment.

Theprojectinvolvestwophases:

（1）demolishingsubstandardhousestoprovidelandforthenewdevelopment,and

（2）buildingthenewdevelopment.Thefollowingisasummaryofthesituation.

1.Asmanyas300substandardhousescanbedemolished.Eachhouseoccupiesa.25-acrelot.Thecostofdemolishingacondemnedhouseis$2000.

2.Lotsizesfornewsingle-,double-,triple-,andquadruple-familyhomes（units）are.18,.28,.4,and.5acre,respectively.Streets,openspace,andutilityeasementsaccountfor15%ofavailableacreage.

3.Inthenewdevelopmentthetripleandquadrupleunitesaccountforatleast25%ofthetotal.Singleunitsmustbeatleast20%ofallunitsanddoubleunitsatleast10%.

4.Thetaxleviedperunitforsingle,double,triple,andquadrupleunitsis$1000,$1900,$2700,and$3400,respectively.

5.Theconstructioncostperunitforsingle-,double-,triple-,andquadruple-familyhomesis$50,000,$70,000,$130,000,and$160,000,respectively.Financingthroughalocalbankcanamounttoamaximumof$15million.

Howmanyunitsofeachtypeshouldbeconstructedtomaximizetaxcollection?

Mathematicalmodel:

x1=Numberofunitsofsingle-familyhomes

x2=Numberofunitsofdouble-familyhomes

x3=Numberofunitsoftriple-familyhomes

x4=Numberofunitsofquadruple-familyhomes

x5=Numberofoldhomestobedemonished

Thecompletemodelthusbecomes

Maxz=1000x1+1900x2+2700x3+3400x4

Subjectto

.18x1+.28x2+.4x3+.5x4-.2125x5

x5

Solution:

Totaltaxcollection=z=$343,965

Numberofsinglehomes=x1=35.83

36units

Numberofdoublehomes=x2=98.53

99units

Numberoftriplehomes=x3=44.79

45units

Numberofquadruplehomes=x4=0units

Numberofhomesdemonished=x5=244.49

245units

1.Example2.3-2（CurrencyArbitrageModel）

Supposethatacompanyhasatotalof5milliondollarsthatcanbeexchangedforeuros（€），Britishpounds（£），yen（￥）,andKuwaitidinars（KD）.Currencydealerssetthefollowinglimitsontheamountofanysingletransaction:

5milliondollars,3millioneuros,3.5millionpounds,100millionyen,and2.8millionKDs.Thetablebelowprovidestypicalspotexchangerates.Thebottomdiagonalratesarethereciprocalofthetopdiagonalrates.Forexample,rate（€$）=1/rate（$€）=1/.769=1.30.

$

€

£

￥

KD

$

1

.769

.625

105

.342

€

1/.769

1

.813

137

.445

£

1/.625

1/.813

1

169

.543

￥

1/105

1/137

1/169

1

.0032

KD

1/.342

1/.445

1/.543

1/.0032

1

Isitpossibletoincreasethedollarholdings（abovetheinitial$5million）bycirculatingcurrenciesthroughthecurrencymarket?

MathematicalModel:

Forthepurposeofdevelopingthemodelandsimplifyingthenotation,thefollowingnumericcodeisusedtorepresentthecurrencies.

Currency

$

€

£

￥

KD

Code

1

2

3

4

5

Define

Amountincurrencyiconvertedtocurrencyj,iandj=1,2,…,5

Thecompletemodelisnowgivenas

Maximizez=y

Subjectto

Solution:

Theoptimumsolutionis:

Solution

Interpretation

y=5.09032

Finalholdings=$5,090,320

Netdollargain=$90,320,which

representsa1.8064%rateofreturn

x12=1.46206

Buy$1,462,060worthofeuros

x15=5

Buy$5,000,000worthofKD

x25=3

Buy€3,000,000worthofKD

x31=3.5

Buy£3,500,000worthofdollars

x32=0.931495

Buy£931,495worthofeuros

x41=100

Buy￥100,000,000worthofdollars

x42=100

Buy￥100,000,000worthofeuros

x43=100

Buy￥100,000,000worthofpounds

x53=2.085

BuyKD2,085,000worthofpounds

x54=.96

BuyKD960,000worthofyen

3.Example2.3-7（CrudeOilRefiningandGasolineBlending）

ShaleOil,locatedontheislandofAruba,hasacapacityof1,500,000bblofcrudeoilperday.Thefinalproductsfromtherefineryincludethreetypesofunleadedgasolinewithdifferentoctanenumbers（ON）:

regularwithON=87,premiumwithON=89,andsuperwithON=92.Therefiningprocessencompassesthreestages:

（1）adistillationtowerthatproducesfeedstock（ON=82）attherateof.2bblperbblofcrudeoil,

（2）acrackerunitthatproducesgasolinestock（ON=98）byusingaportionofthefeedstockproducedfromthedistillationtowerattherateof.5bblperbbloffeedstock,and（3）ablenderunitthatblendsthegasolinestockfromthecrackerunitandthefeedstockfromthedistillationtower.Thecompanyestimatesthenetprofitperbarrelofthethreetypesofgasolinetobe$6.70,$7.20,and$8.10,respectively.Theinputcapacityofthecrackerunitis200,000barrelsoffeedstockaday.Thedemandlimitsforregular,premium,andsupergasolineare50,000,30,000,and40,000barrelsperday.Developamodelfordeterminingtheoptimumproductionschedulefortherefinery.

MathematicalModel:

Let

=bbl/dayofinputstreamiusedtoblendfinalproductj,i=1,2;j=1,2,3

Thecompletemodelisthussummarizedas

Maximize

Subjectto

Solution:

Theoptimumsolutionisz=1,482,000,x11=20,625,x21=9375,x12=16,875,x22=13,125,x13=15,000,x23=25,000.Thistranslatesto

Dailyprofit=$1,482,000

Dailyamountofregulargasoline=x11+x21=20625+9375=30,000bbl/day

Dailyamountofpremiumgasoline=x12+x22=16875+13125=30,000bbl/day

Dailyamountofregulargasoline=x13+x23=15000+25000=40,000bbl/day

Thesolutionshowsthatregulargasolineproductionis20,000bbl/dayshortofsatisfyingthemaximumdemand.Thedemandfortheremainingtwogradesissatisfied.

Exercise

（1）（page65,Ex6）TrafficLightControl（StarkandNicholes,1972）Automobiletrafficfromthreehighways,H1,H2,andH3,muststopandwaitforagreenlightbeforeexitingtoatollroad.Thetollsare$3，$4，and$5forcarsexitingfromH1,H2,andH3,respectively.TheflowratesfromH1,H2,andH3are500,600,and400carsperhour.Thetrafficlightcyclemaynotexceed2.2minutes,andthegreenlightonfor10seconds.Thetollgatecanhandleamaximumof510carsperhour.Assumingthatnocarsmoveonyellow,determinetheoptimalgreentimeintervalforthethreehighwaysthatwillmaximizetollgaterevenuepertrafficcycle.

（2）（page65,Ex8）LevelingtheTerrainforaNewHighway（StarkandNicholes,1972）TheArkansasHighwayDepartmentisplanninganew10-milehighwayonuneventerrainasshownbytheprofileinFigure2.10.Thewidthoftheconstructionterrainisapproximately50yards.Tosimplifythesituation,theterrainprofilecanbereplacedbyastepfunctionasshowninthefigure.Usingheavymachinery,earthremovedfromhighterrainishauledtofilllowareas.Therearealsotwoburrowpits,IandII,locatedattheendsofthe10-milestretchfromwhichadditionalearthcanbehauled,ifneeded.PitIhasacapacityof20,000cubicyardsandpitIIacapacityof15,000cubicyards.ThecostsofremovingearthfrompitsIandIIare,respectively,$1.50and$1.90percubicyard.Thetransportationcostpercubicyardpermileis$.15andthecostofusingheavymachinerytoloadhaulingtrucksis$.20percubicyard.ThismeansthatacubicyardfrompitIhauledonemilewillcostatotalof（1.5+.20）+1*.15=$1.85andacubicyardhauledonemilefromahilltoafillareawillcost.20+1*.15=$.35.Developaminimumcostplanforlevelingthe10-milestretch.

（3）（page66,Ex9）Militaryplanning（ShepardandAssociates,1988）TheRedArmy（R）istryingtoinvadetheterritorydefendedbytheBlueArmy（B）.Bluehasthreedefenselinesand200regularcombatunitsandcandrawalsoonareversepoolof200units.Redplanstoattackontwofronts,northandsouth,andBluehassetupthreeeast-westdefenselines,I,II,andIII.ThepurposeofdefenselinesIandIIistodelaytheRedArmyattackbyatleast4daysineachlineandtomaximizethetotaldurationofthebattle.TheadvancetimeoftheRedArmyisestimatedbythefollowingempiricalformula:

Battledurationindays=a+b

Theconstantsaandbareafunctionofthedefenselineandthenorth/southfrontasthefollowingtableshows:

a

b

I

II

III

I

II

III

Northfront

.5

.75

.55

8.8

7.9

10.2

Southfront

1.1

1.3

1.5

10.5

8.1

9.2

TheBlueArmyreserveunitscanbeusedindefenselinesIIandIIonly.TheallocationofunitsbytheRedArmytothethreedefenselinesisgiveninthefollowingtable.

NumberofRedArmyattackunits

DefenseLineI

DefenseLineII

DefenseLineIII

Northfront

30

60

20

Southfront

30

40

20

HowshouldBlueallocateitsresourcesamongthethreedefenselinesandthenorth/southfronts?

（4）（page67,Ex12）.AllocationofAircrafttoRoutes.Considertheproblemofassigningaircrafttofourroutesaccordingtothefollowingdata:

Numberofdailytripsonroute

Aircrafttype

Capacity（passengers）

Numberofaircraft

1

2

3

4

1

50

5

3

2

2

1

2

30

8

4

3

3

2

3

20

10

5

5

4

2

Dailynumberofcustomers

1000

2000

900

1200

Theassociatedcosts,includingthepenaltiesforlosingcustomersbecauseofspaceunavailability,are

Operatingcost（$）pertriponroute

Aircrafttype

1

2

3

4

1

1000

1100

1200

1500

2

800

900

1000

1000

3

600

800

800

900

Penalty（$）perlostcustomer

40

50

45

70

Determinetheoptimumallocationofaircrafttoroutesanddeterminetheassociatednumberoftrips.

二、GraphTheory

1.Example6.3-3（Three-JugPuzzle）

An8-gallonjugisfilledwithfluid.Giventwoempty5-and3-gallonjugs,wewanttodividethe8gallonsoffluidintotwoequalpartsusingthethreejugs.Noothermeasuringdevicesareallowed.Whatthesmallestnumberoftransfers（decantations）needed