资源描述:
《Chapter 3 Introduction to Linear Programming 第3章线性规划简介》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、CollegeofManagement,NCTUOperationResearchIFall,2008Chapter3IntroductiontoLinearProgrammingßUsually(atleastfornow)dealwiththeproblemsofallocatinglimitedresourcesamongcompetingactivitiesinthebestpossible(optimal)way.ßRequiresallfunctionstobelinearfunctions.ßExam
2、ple:TheWYNDORGLASSCO.VTwonewproducts¾Product1:aluminum-framewindow¾Product2:wood-framewindowVThreeplants¾Plant1producesaluminumframes¾Plant2produceswoodframes¾Plant3producestheglassandassemblestheproductsVInterviewandgatheringdatayieldthefollowinginformation:P
3、lantProduct1Product2CapacityAvailable11042021233218Profit(thousands)35VDefiningvariablesandformulatingthemodelJinY.WangChap3-1CollegeofManagement,NCTUOperationResearchIFall,2008ßHowtosolveaLPproblem–TheGraphicSolutionVRecalltheWyndorProblemMaxZ=3x1+5x2S.T.x1≤4
4、2x2≤123x1+2x2≤18x1,x2≥0VThefirststepistoidentifythevaluesof(x1,x2)thatarepermittedbytherestrictions.VTheresultingregionofpermissiblevaluesof(x1,x2),calledthefeasibleregion.VThen,weneedtopickoutthepointinthisfeasibleregionthatmaximizesthevalueofZ=3x1+5x2.ßTakea
5、lookattheORTutorintheCD-ROMVInstalltheprogramandtryitout.JinY.WangChap3-2CollegeofManagement,NCTUOperationResearchIFall,2008ßTheLinearProgrammingModelVThekeytermsareresourcesandactivities.¾mdenotesthenumberofresources;ndenotesthenumberofactivities.VOnceagain,t
6、hemostcommontypeofapplicationoflinearprogramminginvolvesallocatingresourcestoactivities.VBacktoourWyndorexampleWyndorExampleGeneralProblem3Plantsmresources2productsnactivitiesProductionrateofproductj,xjLevelofactivityj,xjProfitZOverallmeasureofperformanceZßOur
7、StandardFormoftheModelVSomecommonlyusedsymbols:¾Z=valueofoverallmeasureofperformance¾xj=levelofactivityj¾cj=increaseinZthatwouldresultfromeachunitincreaseinlevelofactivityj¾bi=amountofresourceithatisavailableforallocationtoactivities¾aij=amountofresourceiconsu
8、medbyeachunitofactivityjMaxZ=c1x2+c2x2+…+cnxnS.T.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2……………am1x1+am2x2+…+amnxn≤bmx1,x2,…,xn≥0ORnMax∑cjxjj=1nS.T.∑aijxj≤bi,i=1,2,…,mj=1xj≥0,j=