运筹学课件4-线性规划.ppt

Chapter3 IntroductiontoLinearProgramming Linearprogrammingisawidelyusedmodeltypethatcansolvedecisionproblemswithmanythousandsofvariables Generally thefeasiblevaluesofthedecisionsaredelimitedbyasetofconstraintsthataredescribedbymathematicalfunctionsofthedecisionvariables Thefeasibledecisionsarecomparedusinganobjectivefunctionofthedecisionvariables Foralinearprogramtheconstraintsandobjectivefunctionsarerequiredtobelinearlyrelatedtothevariablesoftheproblem 3 1PrototypeExample Thecirclesshowtherawmaterialsused andtherectanglesindicatetheoperationsthattheproductsmustpassthroughinthemanufacturingprocess Eachrectangledesignatesamachineusedfortheoperationandthetimerequired Example ThefigurerepresentsamanufacturingsystemproducingtwoproductslabeledPandQ Theroundedrectanglesatthetopofthefigureindicatetherevenueperunitandthemaximumsalesperweek Forinstancewecansellasmanyas100unitsofPfor 90perunit ForexampleproductPconsistsoftwosubassemblies Tomanufacturethefirstsubassembly oneunitofRM1passesthroughmachineAfor15minutes TheoutputofmachineAismovedtomachineCwhereitisprocessedfor10minutes ThesecondsubassemblystartswithRM2processedinmachineBfor15minutes TheoutputistakentomachineCfor5minutesofprocessing ThetwosubassembliesarejoinedwithapurchasedpartinmachineD TheresultisafinishedunitofP ProductQismanufacturedbyasimilarprocessasindicatedinthefigure Therectangleattheupperleftindicatesthatonemachineofeachtypeisavailable Eachmachineoperatesfor2400minutesperweek OEstandsforoperatingexpenses Forthiscasetheoperatingexpenses notincludingtherawmaterialcostis 6000 ThisamountisexpendedregardlessofamountsofPandQproduced Z 45P 60Q Theoptimumsolutionistoproduce100unitsofPand30unitsofQ Thenetprofitofthissolutionis 300 Results Findtheoptimumproductmix Fromthevaluecolumnfortheconstraints weseetheamountsoftimerequiredbytheoptimumproductionquantities Clearly thetimeonmachineBisabottleneckforthissituation ThemarketforPisalsoabottleneckbecausetheoptimumvalueistheupperboundforP IfeitherthetimeonmachineBorthemarketforproductPareincreased theprofitwillincrease Findthebottlenecks 康托洛维奇和丹捷格 1939年著名数理经济学者康托洛维奇发表了 生产组织和计划中的数学方法 这一运筹学的先驱性名著 其中已提到类似线性规划的模型和 解乘数求解法 但是他的工作直到1960年的 最佳资源利用的经济计算 一书出版后 才得到重视 1975年 康托洛维奇与T C Koopmans一起获得了诺贝尔经济学奖 1947年G B Dantzig在研究美国空军军事规划时提出了线性规划的模型和单纯形解法 并很快引起美国著名经济学家Koopmans的注意 Koopmans为此呼吁当时年轻的经济学家要关注线性规划 今天 单纯形法及其理论已成为了线性规划的一个重要的部分 Case1 TheWYNDORGLASSCO produceshigh qualityglassproducts includingwindowsandglassdoors Ithasthreeplants AluminumframesandhardwarearemadeinPlant1 woodframesaremadeinPlant2 andPlant3producestheglassandassemblestheproducts Therearetwoproducts Product1 an8 footglassdoorwithaluminumframing Product2 a4 6footdouble hungwood framedwindow Thetablesummarizesthedatagathered Formulationasalinearprogrammingproblem Toformulatethemathematicalmodelforthisproblem let x1 numberofbatchesofproduct1producedperweekx2 numberofbatchesofproduct2producedperweekZ totalprofitperweek inthousandsofdollars fromproducingthesetwoproducts Formulationasalinearprogrammingproblem Thus x1andx2arethedecisionvariablesforthemodel Usingthebottomrowofthetableabove weobtainZ 3x1 5x2Theobjectiveistochoosethevaluesofx1andx2soastomaximizeZ 3x1 5x2 subjecttotherestrictionsimposedontheirvaluesbythelimitedproductioncapacitiesavailableinthethreeplants MaximizeZ 3x1 5x2SubjecttotherestrictionsX1 0 X2 0 Briefly themostcommontypeofapplicationofLPinvolvesthegeneralproblemofallocatinglimitedresourcesamongcompetingactivitiesinabestpossible i e optimal way Moreprecisely thisprobleminvolvesselectingthelevelofcertainactivitiesthatcompeteforscarceresourcesthatarenecessarytoperformthoseactivities Thechoiceofactivitylevelsthendictateshowmuchofeachresourcewillbeconsumedbyeachactivity 3 2LinearProgrammingConcepts DecisionVariablesDecisionvariablesdescribethequantitiesthatthedecisionmakerswouldliketodetermine Theyaretheunknownsofamathematicalprogrammingmodel Typicallywewilldeterminetheiroptimumvalueswithanoptimizationmethod Inageneralmodel decisionvariablesaregivenalgebraicdesignationssuchasx1 x2 xn Thenumberofdecisionvariablesisn andxjisthenameofthejthvariable Inaspecificsituation itisoftenconvenienttouseothernamessuchasxijorykorz I j Anassignmentofvaluestoallvariablesinaproblemiscalledasolution BasisConceptsaboutLP ObjectiveFunctionTheobjectivefunctionevaluatessomequantitativecriterionofimmediateimportancesuchascost profit utility oryield ThegenerallinearobjectivefunctioncanbewrittenasHereCjisthecoefficientofthejthdecisionvariable Thecriterionselectedcanbeeithermaximizedorminimized Aconstraintisaninequalityorequalitydefininglimitationsondecisions Constraintsarisefromavarietyofsourcessuchaslimitedresources contractualobligations orphysicallaws Ingeneral anLPissaidtohavemlinearconstraintsthatcanbestatedasOneofthethreerelationsshowninthelargebracketsmustbechosenforeachconstraint Thenumberaijiscalleda technologicalcoefficient andthenumberbiiscalledthe right handside valueoftheIthconstraint Strictinequalities arenotpermitted Constraints NonnegativeRestrictionsInmostpracticalproblemsthevariablesarerequiredtobenonnegative Thisspecialkindofconstraintiscalledanonnegativerestriction Sometimesvariablesarerequiredtobenonpositiveor infact maybeunrestricted allowinganyrealvalue CompleteLinearProgrammingModelCombiningtheaforementionedcomponentsintoasinglestatementgives Theconstraints includingnonnegativeandsimpleupperbounds definethefeasibleregionofaproblem 3 3TheLinearProgrammingModel Asdescribedintheintroductiontothischapter themostcommontypeofapplicationoflinearprogramminginvolvesallocatingresourcestoactivities Theamountavailableofeachresourceislimited soacarefulallocationofresourcestoactivitiesmustbemade Determiningthisallocationinvolveschoosingthelevelsoftheactivitiesthatachievethebestpossiblevalueoftheoverallmeasureofperformance Thekeytermsareresourcesandactivities wheremdenotesthenumberofdifferentkindsofresourcesthatcanbeusedandndenotesthenumberofactivitiesbeingconsidered Sometypicalresourcesaremoneyandparticularkindsofmachines equipment vehicles andpersonnel Examplesofactivitiesincludeinvestinginparticularprojects advertisinginparticularmedia andshippinggoodsfromaparticularsourcetoaparticulardestination TheLinearProgrammingModel 三个基本要素 Note 1 善于抓住关键因素 忽略对系统影响不大的因素 2 可以把一个大系统合理地分解成n个子系统处理 1 决策变量xj 0 2 约束条件 一组决策变量的线性等式或不等式 3 目标函数 决策变量的线性函数 AStandard maximization LinearProgrammingProblem Theobjectivefunctionistobemaximized Allthevariablesinvolvedintheproblemarenonnegative Eachconstraintmaybewrittensothattheexpressionwiththevariablesislessthanorequaltoanonnegativeconstant MaximizeP 4x 5y Subjectto Ex Astandardmaximizationproblem Introducenonnegativeslackvariablestomakeequationsoutoftheinequalities max min z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn 或 b1a21x1 a22x2 a2nxn 或 b2 am1x1 am2x2 amnxn 或 bmxj 0 j 1 2 n 其中aij bi cj i 1 2 m j 1 2 n 为已知常数 线性规划问题的标准形式 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0 j 1 2 n bi 0 i 1 2 m 特点 1 目标函数为极大化 2 除决策变量的非负约束外 所有的约束条件都是等式 且右端常数均为非负 3 所有决策变量均非负 如何转化为标准形式 1 目标函数为求极小值 即为 因为求minz等价于求max z 令z z 即化为 2 约束条件为不等式 xn 1 0松弛变量 如何处理 右端项bi 0时 只需将等式两端同乘 1 则右端项必大于零 4 决策变量无非负约束 设xj没有非负约束 若xj 0 可令xj xj 则xj 0 又若xj为自由变量 即xj可为任意实数 可令xj xj xj 且xj xj 0 例题 试将LP问题 minz x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0化为标准形式 解 令x3 x4 x5其中x4 x5 0 对第一个约束条件加上松弛变量x6 对第二个约束条件减去松弛变量x7 对第三个约束条件两边乘以 1 令z z把求minz改为求maxz maxz x1 2x2 3x4 3x5s t x1 x2 x4 x5 x6 7x1 x2 x4 x5 x7 23x1 x2 2x4 2x5 5x1 x2 x4 x5 x6 x7 0 LP的几种表示形式 TerminologyforSolutionsoftheModel Afeasiblesolution 可行解 isasolutionforwhichalltheconstraintsaresatisfied Aninfeasiblesolution 非可行解 isasolutionforwhichatleastoneconstraintisviolated Thefeasibleregion 可行域 isthecollectionofallfeasiblesolutions Anoptimalsolution 最优解 isafeasiblesolutionthathasthemostfavorablevalueoftheobj