运筹学课件 ppt 复习资料 目标规划(运筹学)

1、 运 筹 学王 莉 莉四川农业大学数学系四川农业大学数学系2012年10月学习目标正确理解目标规划的定义；掌握目标规划的建模技巧；掌握目标规划的图解解法；掌握目标规划的单纯形求解模型.第五章目标规划 Goal Programming 目标规划方法是Charnes和Cooper于1961年提出的，目前已成为一种简单、实用的处理多目标决策问题的 方法，是多目标决策中应用最为广泛的一种方法。 为了学习和初步掌握目标规划与线性规划在处理问题的方法上的区别，我们分析如下案例家具制造问题王老板遇到的新问题背景材料： 王老板一直从事专业家具制造，主要生产桌子、椅子两种家具，王老板的经营环境主要受到两种资源木

2、工和油漆工每天的有效工作时间的限制。王老板过去的经营环境条件如下：1、每天木工和油漆工的总有效工作时间分别为 11小时和10小时.2、每生产一把椅子需要2小时的木工、 1小时的油漆工.3、每生产一张桌子需要1小时的木工、 2小时的油漆工.4、每生产一把椅子和一张桌子分别可获利润 8元、 10元. 求解此线性规划问题可以得到王老板的最优方案：每天生产椅子 4 把，桌子 3 张，获最大利润 62 元.家具制造问题王老板遇到的新问题王老板过去一直以如何计划两种家具的生产量才能获得最大总利润为其生产、经营的唯一目标。然而，市场经济环境下新的问题出现了，它迫使王老板不得不考虑.（1）首先，根据市场信息，

3、椅子的销售量已有下降的趋势，故应果断决策减少椅子的产量，其产量最好不大于桌子的产量.（2）其次，市场上找不到符合生产质量要求的木工了，因此决不可能考虑增加木工这种资源来增加产量，并且由于某种原因木工决不可能加班.（3）再其次，应尽可能充分利用油漆工的有效工作时间，但油漆工希望最好不加班.（4）最后，王老板考虑最好达到并超过预计利润指标 56元.家具制造问题王老板遇到的新问题讨论1、王老板现在的生产、经营问题多个目标的生产问题2、决策变量椅子、桌子的生产量x1，x2 引入一种新的变量正、负偏差变量d+、d-， d+、d- 03、约束条件 绝对约束、目标约束硬约束、软约束4、目标函数 优先因子（优

4、先等级）P1，P2，规定 Pk Pk+1，k=1,2,表示Pk比Pk+1有更大的优先权. 这意味着当目标与目标之间发生冲突时应按其优先等级来实现.家具制造问题王老板遇到的新问题 目标规划独特的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋予相应的优先因子而构造的. 当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值. 因此，目标规划的目标函数只能是 min Z = f（d +, d -） 其基本形式有三种：家具制造问题王老板遇到的新问题 （1） 要求恰好达到目标值，即正、负偏差变量都要尽可能地小 min Z = f（ d + d - ） （2） 要求不超过目标值，即允许达不到目标值

5、，即正偏差变量 要尽可能地小 min Z = f（ d +） （3） 要求超过目标值，即超过量不限，但必须是即负偏差变量要尽可能地小 min Z = f（ d -）家具制造问题王老板遇到的新问题归纳上面的分析王老板应在木工每天的有效工作时间受到严格限制的基础上按顺序考虑其他目标的实现.目标优先等级：（1）P1椅子的产量最好不大于桌子的产量.（2）P2充分利用油漆工的有效工作时间，但希望不加班.（3）P3总利润不小于 56元.家具制造问题王老板遇到的新问题决策变量：（1） x1椅子的产量，x2桌子的产量（2） P1等级正、负偏差变量d1+、d1- P2等级正、负偏差变量d2+、d2- P3等级正

6、、负偏差变量d3+、d3- x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 0目标函数： min Z = P1 d1+ P2（ d2-+ d2+）+ P3 d3-家具制造问题王老板遇到的新问题约束条件：（1）绝对约束 2x1+ x2 11（2）目标约束 x1 - x2 + d1- - d1+ = 0 （ P1 ） x1 + 2x2 + d2- - d2+ = 10 （ P2 ） 8x1 +10 x2 + d3- - d3+ = 56 （ P3 ）家具制造问题王老板遇到的新问题王老板的多目标线性规划问题目标规划问题min Z = P1 d1+ P2（ d2-+ d2+）+ P3

7、 d3- s.t. 2x1+ x2 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 10 8x1 +10 x2 + d3- - d3+= 56 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 0目标规划的一般形式1111min(), (1,2,.,)( , ) , (1,2,.,). .0,(1,2,., ),0,(1,2,.,)LKllkklkklknkjjkkkjnijjijjkkzPw dw dc xddgkKa xbimstxknddkK 目标规划 VS 线性规划线性规划只有一个目标. 而目标规划具有多个目标，并有不同的

8、优先级，低优先级目标必须服从高优先级目标的实现.线性规划寻求单一目标的最优值. 而目标规划寻求所有目标与预计成果的最小差距，差距越小，目标实现的可能性越大.线性规划只接受最优解，而目标规划接受满意解，即如果某些低优先级的约束得不到满足，将目标规划的解称为满意解.目标规划的图解法 如何求解多目标线性规划问题，其方法与求解线性规划问题的方法相似目标线性规划单纯形法.但是，对于只有两个决策变量的目标线性规划问题同样可以采用图解的方法来揭示问题的解的某种特征. 在用图解法解目标规划时，首先必须满足所有绝对约束条件. 在此基础上，再按照目标优先级别从高到低的顺序，逐个地考虑各个目标约束条件. min Z

9、 = P1 d1+ P2（ d2-+ d2+）+ P3 d3- s.t. 2x1+ x2 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 10 8x1 +10 x2 + d3- - d3+= 56 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 08x1 +10 x2 = 56 x1 - x2 = 0 x1 + 2x2 = 102x1+ x2 =11 绝对约束域绝对约束域d2+ d3+ d3- d2- d1- d1+ （10/3，10/3）（2，4）目标规划的图解法王老板的目标规划新问题图解目标规划的单纯形解法 min Z =

10、P1 d1+ P2（ d2-+ d2+）+ P3 d3- s.t. 2x1+ x2 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 10 8x1 +10 x2 + d3- - d3+= 56 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 02x1 + x2 + xs = 11 x1 - x2 + d1- - d1+= 0 x1 + 2x2 + d2- - d2+= 108x1+10 x2 +d3- -d3+= 56x1 、x2 、 xs、 d1+、d1-、d2+、d2- 、d3+、d3- 0 min Z = P1 d1+ P2

11、 (d2-+d2+)+P3d3- s.t.引入松弛变量列出初始单纯形表为了找到基变量xs、123改写初始单纯形表xsd1-d2-d3-按优先级的级别由高到低依次检验，方法和单纯形法一样.11- 55.6xsd1-d2-d3- 从第一级优先P1行开始，由于第一行上系数都非正，故第一级优先P1已得到满足。xsd1-x2d3- 由于第二行上系数都非正，故第二级优先P2已得到满足。12/310/3 102xsd1-x2x1 由于第三行上系数都非正，故第三级优先P3也已得到满足。从而此题得满意解x1=2，x2=4.目标规划模型 x1 彩色电视机的生产量 x2 黑白电视机的生产量x1 + x2 + d1-

12、 - d1+= 40 x1 + x2 + d2- - d2+= 50 x1 + d3- - d3+= 24 x2 + d4- - d4+= 30 x1 、x2 、d1+、d1-、d2+、d2- 、d3+、d3- 、d4+、d4- 0 min Z = P1 d1-+ P2 d2+ P3（2d3- +1d4-）s.t.列出初始单纯形表1234为了找到基变量1234改写初始单纯形表-按优先级的级别由高到低依次检验，方法和单纯形法一样.405024-1626-30至此第一级优先P1、第二级优先P2已得到满足，但因为第三级优先P3还有数大于0，所以继续迭代.-10-14 虽然第三级优先级P3中仍有数大于

13、零，但并不意味着解不是最优的。对于一个最优决策，如果优先级的系数中对于一个最优决策，如果优先级的系数中存在正数，就要看一看在同一列的更高等级水平是否有任存在正数，就要看一看在同一列的更高等级水平是否有任何负数。何负数。若有，则最优解已达到；若没有，则继续求解.+-故此题得满意解x1=24，x2=26.目标规划的灵敏度分析目标规划的应用某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1)不超过年工资总额60000元；(2)每级的人数不超过定编规定的人数；(3) 、级的升级面尽可能达到现有人数的20%，且无越级提升；(4) 级不足编制的人数可录用新职工，又级的职工有10%要退休.有

14、关资料汇总见下表，问如何拟定满意的方案？等级工资额(元/年)现有人数编制人数200015001000101215121515解：设x1、x2、x3分别表示提升到、级和录用到级的新职工人数. 对各级目标确定优先因子为：P1不超过年工资总额60000元；P2每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有人数的20%建立目标约束2000(10-0.110+x1)+1500(12-x1+x2)+1000(15- x2+x3)+d1- -d1+=6000010-0.110+x1+d2- -d2+=12目标约束12-x1+x2+d3- -d3+=1515-x2+x3+d4- -d4+=15

15、x1+d5- -d5+=120.2X2+d6- -d6+=150.2目标函数Min z=P1d1+P2(d2+ +d3+d4+) +P3 (d5- +d6-)目标规划的应用某工厂生产甲、乙两种型号的微型计算机，他们均需经过两道工序加工。每台微机所需的加工时间、销售利润及该厂每周最大加工能力如下表工序1工序2利润甲 乙最大加工能力 4 3 300 6 245075150工厂经营目标的各级优先级如下：1、每周总利润不低于10000元；2、合同要求甲型机每周至少生产10台，乙型机每周至少生产15台；3、工序1每周生产时间最好为150，工序2生产时间可适当超过其能力.试建立这个问题的数学模型.解：设x

16、1、x2分别表示甲、乙机器的生产台数112233445121112223312441255min()()300450100001015. .461503275,0iiizPdP ddP dddxxddxddxddstxxddxxddx dd 目标规划的应用某市准备在下一年度预算中购置一批救护车，已知每辆救护车购置价为20万元。救护车用于所属的两个郊区县，各分配xA和xB台。A县救护站从接到电话到救护车出动的响应时间为(40-3xA)分钟，B县响应时间为(50-4xB)分钟。该市确定如下优先级目标：1、用于救护车购置费用不超过400万元2、A县的响应时间不超过5分钟3、B县的响应时间不超过5分钟试建立该问题的目标规划模型。解：设x1、x2分别表示分配给A、B县的救护车数1122331211122233min20204004035. .5045,0iiizPdPdPdxxddxddstxddx dd目标规划的应用彩虹集团准备为他在甲、乙两市设立的分公司招聘从事三个专业的职员170名，其中甲市需要生产专业20人、营销专业30人、财务专业40人，乙市需要生产专业25人、营销专业20人、财务专业35人。集团将应聘审查合格人员共180人按适合从事专业、本人希望从