山东大学 运筹学60题 (包含全部题型)

目录Chapter2  Linearprogramming  2Solution：  4Chapter3  Simplex  6Solution:  7Chapter4  SensitivityAnalysisandduality  11Solution：  14Chapter5  Network  18Solution:  20Chapter6  IntegerProgramming  23Solution:  25Chapter7  NonlinearProgramming  28Solution:  28Chapter8  Decisionmakingunderuncertainty  29Solution:  31Chapter9  Gametheory  34Solution：  36Chapter10  Markovchains  39Solution:  41Chapter11  Deterministicdynamicprogramming  43Solution:  43ExpandedProjects  44Chapter2  Linearprogramming1.Afirmmanufactureschickenfeedbymixingthreedifferentingredients.Eachingredientcontainsthreekeynutrientsprotein,fatandvitamin.Theamountofeachnutrientcontainedin1kilogramofthethreebasicingredientsissummarizedinthefollowingtable:IngredientProtein(grams)Fat(grams)Vitamin(units)12511235245101603327190ThecostsperkilogramofIngredients1,2,and3are$0.55,$0.42and$0.38,respectively.Eachkilogramofthefeedmustcontainatleast35gramsofprotein,aminimumof8gramsoffatandamaximumof10gramsoffatandatleast200unitsofvitamins.Formulatealinearprogrammingmodelforfindingthefeedmixthathastheminimumcostperkilogram.2.Forasupermarket,thefollowingclerksarerequired:DaysMin.numberofclerksMon20Tue16Wed13Thu16Fri19Sat14Sun12Eachclerkworks5consecutivedaysperweekandmaystartworkingonMonday,WednesdayorFriday.Theobjectiveistofindthesmallestnumberofclerksrequiredtocomplywiththeaboverequirements.Formulatetheproblemasalinearprogrammingmodel.3.ConsiderthefollowingLPproblem:(a)Sketchthefeasibleregion.(b)Findtwoalternativeoptimalextreme(corner)points.(c)Findaninfinitesetofoptimalsolutions.4.Apowerplanthasthreethermalgenerators.Thegenerators’generationcostsare$36/MW,$30/MW,and$25/MW,respectively.Theoutputlimitationforthegeneratorsisshowninthetable.Somemoment,thepowerdemandforthisplantis360MW,pleasesetupanLPoptimizationmodelandfindouttheoptimaloutputforeachgenerator(withlowestoperationcost).GeneratorGenerationlowerlimitGenerationhigherlimit1502002501503501505.UsetheGraphicalSolutiontofindtheoptimalsolutionstothefollowingLP:Solution：1.Letx1=theamountofIngredient1mixedin1kilogramofthechickenfeedx2=theamountofIngredient2mixedin1kilogramofthechickenfeedx3=theamountofIngredient3mixedin1kilogramofthechickenfeedTheLPmodelis:2.Let x1=numberofclerksstartworkingonMondayx2=numberofclerksstartworkingonWednesdayx3=numberofclerksstartworkingonFridayTheLPmodelis:3.(a)(b)Thetwoalternativeoptimalextremepointsare(4,3)and(6,3/2).(c)Theinfinitesetofoptimalsolutions:{λ(4,3)(1−λ)(6,3/2):0≤λ≤14.Model:Solution:x1=60(MW);x2=150(MW);x3=150(MW)5.Accordingtothefigure,thesolutionis:x1=0;x2=0Chapter3  Simplex1.Showthatiftiesarebrokeninfavoroflower-numberedrows,thencyclingoccurswhenthesimplexmethodisusedtosolvethefollowingLP:2.UsethesimplexalgorithmtofindtwooptimalsolutionstothefollowingLP:3.UsetheBigMmethodtofindtheoptimalsolutiontothefollowingLP:4.UsethesimplexalgorithmtofindtwooptimalsolutionstothefollowingLP.5.Foralinearprogrammingproblem:Findtheoptimalsolutionusingthesimplexalgorithm.Solution:1.Herearethepivots:ZX1X2X3X4S1S2S3RHS13-1600000091-9-21000011/3-2-1/301000-9-1920011BV={S1,S2,S3}.X2nowentersinRow1yieldingthefollowingtableau.ZX1X2X3X4S1S2S3RHS1120-3-21000091-9-210000-2011/3-1/3100000001011BV={X2,S2,S3}.WenowenterX3intothebasisinRow2.ZX1X2X3X4S1S2S3RHS1600-103000-9101-29000-2011/3-1/3100000001011BV={X2,X3,S3}.WenowenterX4intothebasisinRow1.ZX1X2X3X4S1S2S3RHS1-3100-212000-9101-290001-1/3101/3-200000001011BV={X4,X3,S3}.X1nowentersbasisinRow2.ZX1X2X3X4S1S2S3RHS10030-160000-2911-90001-1/3101/3-200000001011BV={X4,X1,S3}.WenowchoosetoenterS1inRow1.ZX1X2X3X4S1S2S3RHS10-21210-30000-2911-900011/3-2-1/30100002-9-10911BV={S1,X1,S3}.S2wouldnowenterbasisinRow2.Thiswillbringusbacktotheinitialtableau,socyclinghasoccurred.2.Standardform:Tableau:zx1x2x3s1s2rhsBasicvalableRatio1-3-1000z=00113106s1=66/1=605*360115s2=1515/5=3zx1x2x3s1s2rhsBasicvalableRatio10050115z=15002/59/51-1/53s1=3013/56/501/53x1=3So:z=15;x1=3;x2=0;x3=03.Standardform:=>Tableau:zx1x2s1s2a1rhsBasicvalableRatio1-5100M0021001601110040120105=>zx1x2s1s2a1rhsBasicvalableRatio1(-5-2M)1-M000-6Mz=-6M02*10016a1=630111004s1=440120105s2=55=>zx1x2s1s2a1rhsBasicvalableRatio107/2005/2M15z=15011/2001/23x1=3001/210-1/21s1=1003/201-1/22s2=2So,thesolutionisz=15,x1=3,x2=04.Standardform:zx1x2x3s1s2rhsBasicvalableRatio1-3-1000z=00113106s1=66/1=605*360115s2=1515/5=3zx1x2x3s1s2rhsBasicvalableRatio1050115z=15002/59/51-1/53s1=37.5013/5*6/501/53x1=35zx1x2x3s1s2rhsBasicvalableRatio1050115z=15002/59/51-1/53s1=37.505/31201/35x2=55So,thesolutionisz=15,x1=0,x2=5orz=15,x1=3,x2=05.Optimalsolution:RowZX1X2S1S2S3bBasicVariable010003/41/213Z10001-1/8-1/43/2S1200103/8-1/45/2X230100-1/41/21X1Chapter4  SensitivityAnalysisandduality1.Considerthefollowinglinearprogram(LP):(a).Determinetheshadowpriceforb2,theright-handsideoftheconstraintx2≤b2.(b).Determinetheallowablerangetostayoptimalforc1,thecoefficientofx1intheobjectivefunctionZ=c1x13x2.(c).Determinetheallowablerangetostayfeasibleforb1,theright-handsideoftheconstraint2x1x2≤b1.2.ThereisaLPmodelasfollowing,TheoptimalsimplextableauisZX1X2S1S2S310003/41/21310010105/20013/21）Givethedualproblemoftheprimalproblem.2）IfC2increasesfrom4to5,willtheoptimalsolutionchange?Why?3）Ifb2changesfrom12to15,willtheoptimalsolutionchange?Why?3.ThereisaLPmodelasfollowing1)giveitsdualproblem.2)Usethegraphicalsolutiontosolvethedualproblem.4.Youhaveaconstraintthatlimitstheamountoflaboravailableto40hoursperweek.Ifyourshadowpriceis$10/hourforthelaborconstraint,andthemarketpriceforthelaboris$11/hour.Shouldyoupaytoobtainadditionallabor?5.ConsiderthefollowingLPmodelofaproductionplanoftablesandchairs:Max 3T2C  (profit)Subjecttotheconstraints:2TC≤100  (carpentryhrs)TC≤80  (paintinghrs)T≤40T,C≥0  (non-negativity)1)Drawthefeasibleregion.2)Findtheoptimalsolution.3)Doestheoptimalsolutionchangeiftheprofitcontributionfortableschangedfrom$3to$4pertable?4)Whatifpaintinghoursavailablechangedfrom80to100?6.Foralinearprogrammingproblem:SupposeC2risingfrom4to5,iftheoptimalsolutionwillchange?Explainthereason.7.Foralinearprogrammingproblem:Supposeb2risingfrom12to15,iftheoptimalsolutionwillchange?Explainthereason.8.Foralinearprogrammingproblem:Calculatetheshadowpriceofallofthethreeconstraints.9.1)Usethesimplexalgorithmtofindtheoptimalsolutiontothemodelbelow (10points)2)Forwhichobjectivefunctioncoefficientvaluerangesofx1andx2doesthesolutionremainoptimal?(10points)3)Findthedualofthemodel; (5points)4)Findtheshadowpricesofconstraints.(5points)5)Ifx1andx2areallintegers,usingthebranch-and-boundtosolveit.(15points)10.AfactoryisgoingtoproduceProductsI,IIandIIIbyusingrawmaterialsAandB.Therelateddataisshownbelow:RawmaterialproductIIIIIIRawmaterialavailableAB6353459(kg)8(kg)Profit($)3141)Pleasearrangeproductionplantomaketheprofitmaximization.(15)2)Writethedualproblemoftheprimalproblem.(5)3)IfonemorekgofrawmaterialAisavailable,howmuchthetotalprofitwillbeincreased?(5)4)IftheprofitofproductIIchangesfrom1to2，willtheoptimalsolutionchange?(5)Solution：1.(a)Theshadowpriceforb2is2.5.Replacetheconstraintx2≤2bytheconstraintx2≤3.Thenewoptimalsolutionis(x1,x2)=(0.5,3)withZ=9.5.Thus,aunitincreaseinb2leadstoa2.5unitincreaseinZ.(b)Theallowablerangetostayoptimalis0≤c1≤6.TheobjectivefunctionZ=c1x13x2isparalleltotheconstraintboundaryequation2x1x2=4whenc1=6.TheobjectivefunctionZ=c1x13x2isparalleltotheconstraintboundaryequationx2=2whenc1=0.(c)Theallowablerangetostayfeasibleis2≤b1<∞.Theright-handsideb1canbedecreaseduntiltheconstraintboundaryequation2x1x2 =4intersectsthesolution(x1,x2)=(0,2).Thisoccurswhenb1=2.Theright-handsideb1canbeincreasedwithoutintersectingasolution.2.1)thedualproblem:2)whenC2changesfrom4to5,theoptimalbasicvariablewillnotchange,becausethecoefficientofthenonbasicvariableremainpositive.3)whenb2changesfrom12to15,theoptimalbasicvariablewillnotchange.3.1）thedualproblemoftheprimalproblemis：2）usingthegraphicalsolution,theoptimalsolutionofthedualproblemis:w=19/5,y1=8/5,y2=-1/5.4.No.Ifyouobtainoneadditionallabor,youshouldpay$11.Butbytheshadowprice,youcanonlyearn$10.Soweshouldnotpaytoobtainadditionallabor.5.2)TheoptimalsolutionisT=20,C=60andthemaximumprofitis180.3)Iftheprofitcontributionfortableschangedfrom$3to$4pertable,therewillbetwooptimalsolutions,saysT=20,C=60andT=40,C=20,andthemaximumprofitis200.4)BecausepaintinghrsisaconstraintconditionforT=20,C=60,sotheoptimalsolutionwillchange.ThenewoptimalsolutionisT=0,C=100,andthemaximumprofitis200.6.Parameteriscalculatedbelow:Ifc2risingfrom4to5,then ，and >0，sotheoptimalsolutionwillnotchange.7.Ifb2risingfrom12to15,everyelementof =[9/8,29/8,1/4]islargethenzero,sotheoptimalsolutionwillnotchange.8.Shadowpriceiscalculatedby 。9.1)Step1:Introduceslackvariabless1,s2fortwoinequalitiesandwegetthestandardformofLP,Row0: z-5x1-2x2=0Row1: 3x1x2s1=12Row2: x1x2s2=5Step2:Theinitialbfsis{s1=12,s2=5}andz=0.x1hasthelargestnegativecoefficient,sox1willenterthebasicvariables.Row1isthewinnerofratiotestandweshoulduseEROtomakex1abasicvariableinRow1.Row0: z–1/3x25/3s1=20Row1: x11/3x21/3s1=4Row2:   x2s2=1.5Step3:Thecurrentbfsis{x1=4,s2=1.5}andz=20. x1hasthelargestnegativecoefficient,sox1willenterthebasicvariables.Row1isthewinnerofratiotestandweshoulduseEROtomakex1abasicvariableinRow1.Row0: z1/3s25/3s1=20.5Row1: x11/3s1-1/3s2=3.5Row2:  x2s2=1.5Step4:sincenonegativecoefficientinRow0,theoptimalsolutionisZ=20.5,whichoccuratthebfs{x1=3.5,x2=1.5}.2)BV={x1,x2},thenB=[3,1;1,1],cbv=[5,2].Ifthecoefficientofx1changesfrom5to5d,thenthecbv*B-1willbe:[5d,2]*[0.5,-0.5;-0.51.5]=[1.50.5d,0.5-0.5d].TheBVwillremainoptimalifandonlyif1.50.5d0and0.5-0.5d0,then-3d1.Thecoefficientrangeofx1shouldbe2c16.Ifthecoefficientofx2changesfrom2to2d,thenthecbv*B-1willbe:[5,2d]*[0.5,-0.5;-0.51.5]=[1.5-0.5d,0.51.5d].TheBVwillremainoptimalifandonlyif1.5-0.5d0and0.51.5d0,then-1/3d3.Thecoefficientrangeofx1shouldbe5/3c25.3)4)TheoptimalsolutionofdualLPis{y1=1.5,y2=0.5}.Sotheshadowpriceofconstraint1is1.5andthatofconstraint2is0.5.5)10.1)theoptimalsolutionisX1=1/3,X3=7/5,Z=33/5.2)thedualproblemis:3)zwillincreaseto34/5.4)theoptimalsolutionwillnotchange.Chapter5  Network1.UsingtheDijkstra’sAlgorithmanddynamicprogrammingmethodtofindtheshortestpathofgraphbelow(22points).2.Duringthenextfourmonths,aconstructionfirmmustcompletethreeprojects.Project1mustbecompletedwithinthreemonthsandrequires8monthsoflabor.Project2mustbecompletedwithinfourmonthsandrequires10monthsoflabor.Project3mustbecompletedattheendoftwomonthsandrequires12monthsoflabor.Eachmonth,8workersareavailable.Duringagivenmonth,nomorethan6workerscanworkonasinglejob.Formulateamaximum-flowproblemthatcouldbeusedtodeterminewhetherallthreeprojectscanbecompletedontime.3..ForthenetworksinthefollowingFigure,findthemaximumflowfromsourcetosink.4.Findtheshortestpathfromnode1tonode5inthefigureusingnetworkmodel(Dijkstra’sAlgorithm)5.UseDijkstra’salgorithmtofindtheshortestpathanditslengthfromnode1to6:6.Thereareseveralavailableroutesbetweencity1andcity6,asshowninthefollowingfigure.Thenumberassociatedwitheacharcisthetravellingcostofthearc.1)FormulateasanMCNFPtheproblemoffindingtheminimumcostroutefromcity1tocity6.2)Findtheminimumspanningtree.7.WritethemainstepsofDijkstraalgorithmtofindtheshortestpathfromthestartpointtotheterminalpoint.Solution:1.a)Dijkstra’sAlgorithmStartfromnode1,step1:thenode2willbemarkedbypermanentlabel.[0550*900770]Step2:[0550*900770*123013401600]Step3:[0550*900770*min(1230,1280)min(1340,1470)min(1600,1600)][0550*900*770*123013401600]Step4:[0550*900*770*min(1230,1480)min(1340,1660)min(1600,1560)][0550*900*770*1230*13401560]Step5:[0550*900*770*1230*1340*156018402020]Step6:[0550*900*770*1230*1340*1560min(1840,1880)min(2020,2280) ][0550*900*770*1230*1340*1560*1840,2020]Step6:[0550*900*770*1230*1340*1560*min(1840,2390)min(2020,1870) ][0550*900*770*1230*1340*1560*1840*,1870]Step7:[0550*900*770*1230*1340*1560*1840*,1870*2870]Step9:[0550*900*770*1230*1340*1560*1840*,1870*min(2870,3260)][0550*900*770*1230*1340*1560*1840*,1870*2870*]Workbackwardfromnode10,wegettheshortestpath:1-2-5-8-10b)dynamicprogrammingmethodStage1:node1;stage2:node2-4;stage3:5-7,stage4:8-9,stage5:10Stage4computation:f4(8)=1030; f4(9)=1390;Stage3computation:f3(5)=min{c58f4(8)=1640* shortestpathfrom5to10:5-8-10c59f4(9)=2180}f3(6)=min{c68f4(8)=1570* shortestpathfrom6to10:6-8-10c69f4(9)=2330}f3(7)=min{c78f4(8)=1820  shortestpathfrom7to10:7-9-10c79f4(9)=1660*}Stage2computation:f2(2)=min{c25f3(5)=2320* shortestpathfrom2to10:2-5-8-10c26f3(6)=2360c27f3(7)=2710}f2(3)=min{c35f3(5)=2220* shortestpathfrom3to10:3-5-8-10c36f3(6)=2330c37f3(7)=2320}f2(4)=min{c45f3(5)=2150* shortestpathfrom4to10:4-5-8-10c46f3(6)=2270c47f3(7)=2490}Stage1computation:f1(1)=min{c12f2(2)=2870* shortestpathfrom1to10:1-2-5-8-10c13f2(3)=3120c14f2(4)=2920}2.AllarcsfrommonthiworkerstoProjectjhaveacapacityof6.Allprojectscanbecompletedifandonlyifthemaximumflowfromsourcetosinkequals30.3.Maximumflowis45.MinCutSet={1,3,andsi}. CapacityofCutSet=201510=45.4.5.Thelengthoftheshortestpathis16，theshortestpathis1-2-3-6.6.1)Letxij=Arc(i,j)belongstotheminimumcostroute,0or1minz=x123x243x13x234x342x52x452x464x56S.T x12x13=1x12x52-x24-x23=0x13x23-x35=0x24x54-x46=0x35-x52-x54-x56=0x46x56=1xij=0or1,1)MSTlength=7, MSTisChapter6  IntegerProgramming1.Eastinghousesellsairconditioners.Theannualdemandforairconditionersineachregionofthecountryisasfollows:East,100,000;South,150,000;Midwest,110,000;West,90,000.Eastinghouseisconsideringbuildingtheairconditionersinfourdifferentcities:NewYork,Atlanta,Chicago,andLosAngeles.ThecostofproducinganairconditionerinacityandshippingittoaregionofthecountryisgiveninTable18.Anyfactorycanproduceasmanyas150,000airconditionersperyear.TheannualfixedcostofoperatingafactoryineachcityisgiveninthefollowingTable.Atleast50,000unitsoftheMidwestdemandforairconditionersmustcomefromNewYork,oratleast50,000unitsoftheMidwestdemandmustcomefromAtlanta.FormulateanintegerprogrammingwhosesolutionwilltellEastinghousehowtominimizetheannualcostofmeetingdemandforairconditioners.2.Usethebranch-and-boundmethodtofindtheoptimalsolutiontothefollowingIP:3.Atamachinetoolplant,fivejobsmustbecompletedeachday.Thetimeittakestodoeachjobdependsonthemachineusedtodothejob.Ifamachineisusedatall,thereisasetuptimerequired.TherelevanttimesaregiveninthefollowingTable.Thecompany’sgoalistominimizethesumofthesetupandmachineoperationtimesneededtocompletealljobs.FormulateanIP.4.Stockcoisconsideringfourinvestments.Investment1willyieldanetpresentvalue(NPV)of$16000;investment2,anNPVof$22000;investment3,anNPVof$12000;andinvestment4,anNPVof$8000.Eachinvestmentrequiresacertaincashoutflowatthepresenttime:investment1,$5000;investment2,$7000;investment3,$4000;andinvestment4,$3000.Currently,$14000isavailableforinvestment.FormulateanIPwhosesolutionwilltellStockcohowtomaximizethePVobtainedfrominvestments1-4.