Chapter 17 Supplement.docx
- 文档编号:6066872
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:43
- 大小:387.70KB
Chapter 17 Supplement.docx
《Chapter 17 Supplement.docx》由会员分享,可在线阅读,更多相关《Chapter 17 Supplement.docx(43页珍藏版)》请在冰点文库上搜索。
Chapter17Supplement
SupplementtoChapter17
MOREABOUTTHESIMPLEXMETHOD
Chapter17(appearingonthebook’sCD-ROM)describesthecentralrolethatthesimplexmethodplaysinsolvinglinearprogrammingproblems.Forexample,theExcelSolverusesthismethodexclusivelyforsolvingallsuchproblems.Powerfulstate-of-the-artsoftwarepackagesforlinearprogrammingalsoemploythismethod,alongwithsupplementarytechniques.Trulymassivelinearprogrammingproblemswithmany,manythousandsoffunctionalconstraintsanddecisionvariablesnowarebeingsolvedbythesimplexmethod.
Chapter17discussestheconceptsthatmakethesimplexmethodsuchatremendouslyefficientsolutionprocedure,butdoesnotdelveintothedetailsofthemethod.Thissupplementintroducesyoutothenutsandboltsofthesimplexmethod.
1.TheSimplexMethodwithTwoDecisionVariables
Thesimplexmethodisanalgebraicprocedurethatexaminesasequenceofcornerpointsuntilthebestone(theoptimalsolution)isfound.However,whentheproblemhasjusttwodecisionvariables,thesimplexmethodcanbesimplifiedtoageometricprocedurethatexaminesthesecornerpointsgraphically.Thissectionfocusesonthelatterprocedure.LetusbeginwiththeexampleoftheWyndorGlassCo.casestudyintroducedinSection2.2.
HowtheSimplexMethodSolvestheWyndorProblem
Section17.2discussesthekeyrolethatcornerpointsplayinsearchingforanoptimalsolutionfortheWyndorproblem(oranyotherlinearprogrammingproblem).Figure17.12showsthefeasibleregionforthisproblemandhighlightsthecornerpoints.Foryoureaseofreference,thisfigureisreproducedhererelabeledasFigure1.
Figure1Thefivecornerpointsarethekeyfeasiblesolutionsforthe
Wyndorproblem.
HereiswhatthesimplexmethoddoeswithFigure1tosolvetheWyndorproblem.
1.Itbeginsbyexaminingthecornerpointattheorigin,(0,0),andconcludesthatthisisnotanoptimalsolution.
2.Itthenmovestothecornerpoint,(0,6),andconcludesthatthisalsoisnotanoptimalsolution.
3.Itthenmovestothecornerpoint,(2,6),andconcludesthatthisistheoptimalsolution,soitstops.
ThissequenceofcornerpointsexaminedisshowninFigure2.
Nowletuslookattherationalebehindthesethreestepsandtheconclusionsdrawn.
Whystartwiththecornerpointattheorigin,(0,0)?
Simplybecausethisisaconvenientplacetobegin.(Whensolvingforcornerpointsalgebraically,thisonecanbeidentifiedwithoutdoinganyalgebra.)Theonlysituationwhere(0,0)cannotbechosenastheinitialcornerpointiswhenitliesoutsidethefeasibleregionandsoisnotacornerpoint.Inthiscase,anyrealcornerpointcanbechoseninstead.
Atstep1,howisthesimplexmethodabletoconcludethat(0,0)isnotanoptimalsolution?
Itdoesthisbycheckingthetwoadjacentcornerpoints,
(4,0)and(0,6).BothofthesepointsarebetterbecausetheyproducehighervaluesofProfit(theobjectivefunction)than(0,0).So(0,0)cannotbeoptimal.
Theonlysituationwhere(0,0)wouldbeoptimaliswhenneitheradjacentcornerpointisbetter.CheckhowthiswouldhappeniftheobjectiveinthemodelwerechangedtominimizeCost=3D+5W.
Instep2,whydoesthesimplexmethodmoveto(0,6)?
WepointedoutinSection17.2thatonekeytotheefficiencyofthesimplexmethodisthatitonlymovestoadjacentcornerpoints.Therefore,from(0,0),theonlyalternativesaretomovenexttoeither(4,0)or(0,6).(4,0)givesProfit=1,200and(0,6)givesProfit=3,000.Bothareanimprovementover(0,0)withProfit=0,soeitheralternativewouldmoveustowardanoptimalsolution.Sincewewanttomovetowardanoptimalsolutionasquicklyaspossible,wechoosethebetteradjacentcornerpoint(theonewiththelargervalueofProfit),namely,(0,6).(Furtherdiscussionofthiscriterionandanalternatecriterionforselectingtheadjacentcornerpointisgivenintheboxentitled"WhichAdjacentCornerPointShouldBeChosen?
".)
WhichAdjacentCornerPointShouldBeChosen?
Whenthesimplexmethodisreadytomovefromthecurrentcornerpointtoanadjacentcornerpoint,eitherofthefollowingcriteriacanbeusedtochoosetheadjacentcornerpoint.
TheBestAdjacentCornerPointCriterion:
Choosethebestadjacentcornerpoint,i.e.,theonewiththemostfavorablevalueoftheobjectivefunction.(MostfavorablemeanslargestwhentheobjectiveistomaximizeProfit,whereasitmeanssmallestwhentheobjectiveistominimizeCost.)
TheBestRateofImprovementCriterion:
Determinethe"rateofimprovement"foreachadjacentcornerpoint.Thisrateofimprovementisdefinedastheimprovementinthevalueoftheobjectivefunctionperunitofdistancemovedalongtheedgeofthefeasibleregionfromthecurrentcornerpointtotheadjacentcornerpoint.(ImprovementinthisvaluemeansincreaseinProfitwhentheobjectiveistomaximizeProfit,anditmeansdecreaseinCostwhentheobjectiveistominimizeCost.)Choosetheadjacentcornerpointwiththebest(largest)rateofimprovement.
Toillustratethesecondcriterion,considertheWyndorexamplewhenthecurrentpointis(0,0)andtheadjacentcornerpointsare(4,0)and(6,0).Sincetheobjectivefunctiontobemaximizedis
Profit=300D+500W,eachunitincreaseinDincreasesProfitby300,whereaseachunitincreaseinWincreasesProfitby500.Therefore,therateofimprovementfrommovingfrom(0,0)toward(4,0)is300,andtherateofimprovementfrommovingfrom(0,0)toward(0,6)is500.Since500islargerthan300,thiscriterionsaystoselect(0,6)astheadjacentcornerpointtomovetonext.
Thealgebraicformofthesimplexmethodnormallyusesthebestrateofimprovementcriterion.Thereasonisthatthealgebraicprocedurehasaveryefficientmethodforidentifyingratesofimprovementwithoutevensolvingalgebraicallyfortheadjacentcornerpointsandcalculatingtheirvaluesoftheobjectivefunction.(Thismethodusesaspecialdefinitionforunitofdistance,aswewillclarifyinSection4.)
However,thebestrateofimprovementcriterionisnotveryconvenientforthegraphicalformofthesimplexmethodbeingpresentedhere.Exceptwhenthecurrentcornerpointis(0,0),thiscriterionusuallywouldrequiresomewhatmoreworkthanthebestadjacentcornerpointcriterion.Therefore,wewillusethebestadjacentcornerpointcriterionwhenapplyingthesimplexmethodgraphically.
Tofinishstep2,(0,6)isnotoptimalbecauseoneofitsadjacentcornerpoints,(2,6),isbetterthan(0,6).Profit=3,600for(2,6)islargerthanProfit=3,000for(0,6).
Tobeginstep3,thesimplexmethodnotesthat(0,6)hasthetwoadjacentcornerpoints,(0,0)and(2,6).(0,0)wasjustexaminedanddiscardedbeforemovingto(0,6),so(2,6)becomestheautomaticchoicetomovetonext.(Oncethedecisionhasbeenmadetobeginmovingaroundtheboundaryofthefeasibleregionineithertheclockwiseorcounter-clockwisedirection,allsubsequentmovementwillbeinthesamedirection.)
Howdoesthesimplexmethodthenconcludethat(2,6)istheoptimalsolution?
Thereasonisthatbothadjacentcornerpoints,(0,6)and(4,3),arenotbetterthan(2,6).Wealreadyknowfromthepreviousworkthat(0,6)isnotasgood.Furthermore,(4,3)givesProfit=2,700,whichislessthanProfit=3,600for(2,6).Since(4,3)isworsethan(2,6),continuingtomoveclockwisebeyond(4,3)cannotpossiblyleadtoacornerpointbetterthan(2,6).
ASummaryoftheSimplexMethod
Theprocedureforthesimplexmethodwejustillustratedistypical.Hereisasummaryforproblemswitheithertwoormoredecisionvariables.
GettingStarted:
Selectsomecornerpointastheinitialcornerpointtobeexamined.Thischoicecanbemadearbitrarily.However,iftheoriginisacornerpointofthefeasibleregion,thisisaconvenientchoice.Whereveryouchoosetostart,labelit(temporarily)asthecurrentcornerpointandcontinueasdescribedinthefollowingstep.
CheckingforOptimality:
Checkeachofthecornerpointsadjacenttothecurrentcornerpoint.Ifnoneoftheadjacentcornerpointsarebetter(asmeasuredbythevalueoftheobjectivefunction)thanthecurrentcornerpoint,thenstopbecausethecurrentcornerpointisanoptimalsolution.(Anyadjacentcornerpointwithavalueoftheobjectivefunctionequaltothisoptimalvaluealsoisanoptimalsolution.)However,ifoneormoreoftheadjacentcornerpointsarebetterthanthecurrentcornerpoint,thencontinueasdescribedinthenextstep.
MovingOn:
Oneoftheadjacentcornerpointsthatisbetterthanthecurrentcornerpointneedstobeselectedasthenextcurrentpointtobeexamined.Whenexecutingthisproceduregraphically,choosethebestadjacentcornerpointaccordingtothevalueofProfit.(Whenexecutingthisprocedurealgebraically,asdescribedinSection4,thebestrateofimprovementcriterionisusedinsteadtomakethischoice.)LabelitthenewcurrentcornerpointandreturntotheCheckingforOptimalitystepabove.
Thesethreestepsapplyequallywellwhethertheproblemhastwodecisionvariablesormorethantwo.However,whentherearejusttwodecisionvariables,theprocedurecanbestreamlinedsomewhat,asfollows.
AShortcutwithJustTwoDecisionVariables:
Whenthecurrentcornerpointstillistheinitialcornerpoint,theMovingOnstepleadstoselectingoneoftheadjacentcornerpointsasthenextcornerpointtobeexamined.Thiscornerpointisreachedbymovingfromtheinitialcornerpointalongtheboundaryofthefeasibleregionineithertheclockwiseorcounter-clockwisedirection.Theprocedurethereafterinvolvesm
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Chapter 17 Supplement