Transcription of Chapter 7
1 Chapter7 TheSimplexMethodInthischapter, ,youwillbeabletoidentifywhenaproblemhasa lternateoptimalsolutions(SOLVER nevertellsyouthis:italwaysgiveyouonlyone optimalsolution). ,wepointoutthateverylinearprogramcanbeco nvertedinto\standard"formMaxc1x1+c2x2+:: :+cnxnsubjecttoa11x1+a12x2+:::+a1nxn=b1: ::::::::am1x1+am2x2+:::+amnxn=bmx1 0;:::xn 0wheretheobjectiveismaximized, : Iftheproblemisminz,convertittomax z. Ifaconstraintisai1x1+ai2x2+:::+ainxn bi, +ai2x2+:::+ainxn+si=bi,wheresi 0. Ifaconstraintisai1x1+ai2x2+:::+ainxn bi, +ai2x2+:::+ainxn si=bi,wheresi 0. Ifsomevariablexjisunrestrictedinsign,rep laceiteverywhereintheformulationbyx0j x00j,wherex0j 0andx00j 2x1+3x2x1 3x2+2x3 3 x1+2x2 2x1urs;x2 0;x3 0 Letus 3x2x1 3x2+2x3+s1=3 x1+2x2 s2=2x1urs;x2 0;x3 0s1 0s2 0 Thelaststepistoconverttheunrestrictedvar iablex1intotwononnegativevariables:x1=x0 1 2x001 3x2x01 x001 3x2+2x3+s1=3 x01+x001+2x2 s2=2x01 0;x001 0;x2 0;x3 0s1 0s2 ,inthiscoursewesolve\byhand"onlythecasew heretheconstraintsareoftheform +x22x1+x2 4x1+2x2 3x1 0;x2 0 First,weconverttheproblemintostandardfor mbyaddingslackvariablesx3 0andx4 +x22x1+x2+x3=4x1+2x2+x4=3x1 0;x2 0x3 0.
2 X4 ,z=x1+x2or,equivalently,z x1 x2=0:Puttingthisequationtogetherwiththec onstraints, x1 x2=0 Row02x1+x2+x3=4 Row1x1+2x2+x4=3 Row2( ) ,whilesatisfyingtheseequationsand,inaddi tion,x1 0,x2 0,x3 0,x4 ,theequationsaresolvedintermsofthenonbas icvariablesx1, (otherthanthespecialvariablez) :Isthisanoptimalsolutionorcanweincreasez ?(Ourgoal)BylookingatRow0above, cientsinRow0hadbeennonnegative,wecouldha veconcludedthatthecurrentbasicsolutionis optimum,sincetherewouldbenowaytoincrease z(rememberthatallvariablesximustremain 0).Wehavejustdiscoveredthe cientinRow0, ,pickavariablexjwithanegativecoe ,say, ,somebasicvariablewillbecomenonbasic(the leavingvariable). , , x1 x2=0 Row02x1+x2+x3=4 Row1x1+2x2+x4=3 Row2 Thisyieldsz 12x2+13x3=2 Row0x1+12x2+12x3=2 Row132x2 12x3+x4=1 Row2withbasicsolutionx2=x3=0x1=2x4=1z=2: Now, x1 x2=0 Row02x1+x2+x3=4 Row1x1+2x2+x4= +x2+x4=3 Row0 3x2+x3 2x4= 2 Row1x1+2x2+x4=3 Row2withbasicsolutionx2=x4=0x1=3x3= 2z=3:Whichpivotshouldwechoose?
3 The rstone,ofcourse,sincethesecondyieldsanin feasiblebasicsolution!Indeed,remembertha twemustkeepallvariables ,wegetx3= ,beforeactuallyperformingthepivots?Thean sweris,bycomparingtheratiosRightHandSide EnteringVariableCoe cientinRows1and2of( ). ,youwillendupwithafeasiblebasicsolution( ), !Anegativepivotelementwouldnotbegoodeith er, ,i 1,wherethereisastrictlypositive\entering variablecoe cient",computetheratiooftheRightHandSide tothe\enteringvariablecoe cient". edthepivotelementbyRule2, , , ' rstpivot, 12x2+13x3=2 Row0x1+12x2+12x3=2 Row132x2 12x3+x4=1 Row2withbasicsolutionx2=x3=0x1=2x4=1z=2: Isthissolutionoptimal?No, ,sincetheratiosare21=2=4forRow1,and13=2= 23forRow2, +13x3+13x4=73 Row0x1+23x3 13x4=53 Row1x2 13x3+23x4=23 Row2withbasicsolutionx3=x4=0x1=53x2=23z= 73:NowRule1tellsusthatthisbasicsolutioni soptimal, 1 1000basicx3=4x4=3021104nonbasicx1=x2=001 2013z=010 121202basicx1=2x4=101121202nonbasicx2=x3 =00032 1211z=2100131373basicx1=53x2=2301023 1353nonbasicx3=x4=0001 132323z=73 Sincetheaboveexamplehasonlytwovariables, (x1=0;x2=0)withz= ,say, , :ifwewentanyfurther, 'sexactlywhatRule2ofthesimplexmethoddoes :theminimumratioruleidenti esthe , ,afterthe rstpivot,weareatthepoint(x1=2;x2=0).
4 Rule1discoversthatzcanbeincreasedbyincre asingx2whilekeepingx3= +x2=4untilwereachanotherconstraint!After pivoting,wereachtheoptimalpoint(x1=53;x2 =23).z=7/3x2x1z=0z= +x2 x3x1+3x3 63x1+x2+3x3 9x1 0;x2 0x3 ,Degeneracy,Unboudedness,In-feasibilityA lternateOptimalSolutionsLetussolveasmall variationoftheearlierexample,withthesame constraintsbutaslightlydi erentobjective:maxx1+12x22x1+x2 4x1+2x2 3x1 0;x2 0 Asbefore,weaddslacksx3andx4,andwesolveby thesimplexmethod, 1 12000basicx3=4x4=3021104nonbasicx1=x2=00 12013z=01001202basicx1=2x4=101121202nonb asicx2=x3=00032 1211z= ,thecoe ,weobservethat,ifweincreasex2(fromitscur rentvalueof0),thiswillnote ,ofcourse, ,wecanuseRule2andpivottogetadi erentbasicsolutionwiththesameobjectiveva luez= 1353nonbasicx3=x4=0001 132323z=2 Notethatthecoe ,wewouldrecovertheprevioussolution!
5 ,DEGENERACY,UNBOUDEDNESS, +x23x1+x2 6x1 x2 2x2 3x1 0;x2 0 Letussolvethisproblemusingthe{bynowfamil iar{ ,wecanchoosex1astheenteringvariable(Rule 1)andRow2asthepivotrow(theminimumratioin Rule2isatie,andtiesarebrokenarbitrarily) . 2 10000basicx3=6x4=2x5=30311006nonbasicx1= x2=001 10102z=0001001310 30204basicx1=2x3=0x5=30041 300nonbasicx2=x4=001 10102z=40010013 Notethatthisbasicsolutionhasabasicvariab le(namelyx3) , , 1404basicx1=2x2=0x5=300114 3400nonbasicx3=x4=0010141402z=4000 143413 Wegetexactlythesamesolution!Theonlydi erenceisthatwehaveinterchangedthenamesof anonbasicvariablewiththatofadegenerateba sicvariable(x2andx3).Rule1tellsusthesolu tionisnotoptimal, ,wegetthetableau:zx1x2x3x4x5 RHSB asicsolution100230135basicx1=1x2=3x4=400 10013nonbasicx3=x5=0010130 131z=5000 131434 ByRule1, ,afterall,degeneracydidnotpreventthesimp lexmethodto ,onotherexamples,degeneracymayleadtocycl ing, ,cyclingcanbeavoidedbychoosingtheenterin gvariablewithsmallestindexinRule1,amonga llthosewithanegativecoef- cientinRow0,andbybreakingtiesintheminimu mratiotestbychoosingtheleavingvariablewi thsmallestindex(thisisknownasBland'srule ).}}
6 Thisrule,althoughitguarantiesthatcycling willneveroccur,turnsouttobesomewhatine ,incommercialcodes,noe , : Althoughdegeneracyisfrequent,cyclingisex tremelyrare. Theprecisionofcomputerarithmetictakescar eofcyclingbyitself:roundo , +x2 x1+x2 1x1 2x2 2x1 0;x2 0 Solvingbythesimplexmethod,weget:zx1x2x3x 4 RHSB asicsolution1 2 1000basicx3=1x4=20 11101nonbasicx1=x2=001 2012z=010 5024basicx1=2x3=300 1113nonbasicx2=x4=001 2012z=4 Atthisstage,Rule1choosesx2astheenteringv ariable,butthereisnoratiotocompute, ,thevalueofzincreases(fromRow0)andtheval uesofthebasicvariablesincreaseaswell(fro mRows1and2).Thereisnothingtostopthemgoin go toin , :itisinfeasible, ,DEGENERACY,UNBOUDEDNESS,INFEASIBILITY95 Ifthereisanoptimalsolution, , ,evenifthetotalnumberofvariables,sayn,is greaterthanm, (theobjectivefunctionzismaximized).
7 ,indicatewhetherthelinearprogram(i)isunb ounded(ii)hasauniqueoptimumsolution(iii) hasanalternateoptimumsolution(iv)isdegen erate(inthiscase,indicatewhetheranyofthe aboveholds).(a)zx1x2s1s2 RHS103202001 2 10400 1012(b)zx1x2s1s2 RHS10 102200001 2501 2036(c)zx1x2s1s2 RHS1200180310 240 20110(d)zx1x2s1s2 RHS10020500 1114011 104 Exercise64 Supposethefollowingtableauwasobtainedint hecourseofsolvingalinearprogramwithnonne gativevariablesx1;x2; 2213c01 130 53 Giveconditionsona,bandcthatarerequiredfo rthefollowingstatementstobetrue:(i) (i)holdsintherestoftheexercise.(ii) (iii)Thelinearprogramisunbounded(forthis question,assumethatb>0).(iv)Thecurrrentb asicsolutionisoptimalandtherearealternat eoptimalsolutions(forthisquestion,assume a>0).Exercise65 Aplantcanmanufacture veproductsP1,P2,P3, (inhours),fori=1;2andj=1;:::; (inhours).
8 ThecompanycansellallitproducesofproductP jatapro tofsj,fori=1;:::; ts,butneveractuallydidforthefollowingrea son:Frompastexperience, ,theoptimalsolutionwillconsistofproducin gall , +3x2+x3 Subjecttox1+x2+x3 65x1+3x2+6x3 15x1;x2;x3 (a)Whatbasicsolutiondoesthistableaurepre sent?Isthissolutionoptimal?Whyorwhynot?( b) , :(a)Thesolutionisx1=3,x2;x3=0, (b)Itisnotunique(sincex2hasreducedcost0b utisnotbasic).Alternativefoundbypivoting inx2(questioncouldhaveaskedfordetailsons uchapivot)forsolutionx2=5,x1;x3=0,object ive15.
