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

运筹学王莉莉四川农业大学数学系2012年10月学习目标正确理解目标规划的定义；掌握目标规划的建模技巧；掌握目标规划的图解解法；掌握目标规划的单纯形求解模型.第五章—目标规划目标规划

GoalProgramming

目标规划方法是Charnes和Cooper于1961年提出的，目前已成为一种简单、实用的处理多目标决策问题的方法，是多目标决策中应用最为广泛的一种方法。为了学习和初步掌握目标规划与线性规划在处理问题的方法上的区别，我们分析如下案例——家具制造问题——王老板遇到的新问题背景材料：王老板一直从事专业家具制造，主要生产桌子、椅子两种家具，王老板的经营环境主要受到两种资源——木工和油漆工每天的有效工作时间的限制。王老板过去的经营环境条件如下：1、每天木工和油漆工的总有效工作时间分别为11小时和10小时.2、每生产一把椅子需要2小时的木工、1小时的油漆工.3、每生产一张桌子需要1小时的木工、2小时的油漆工.4、每生产一把椅子和一张桌子分别可获利润8元、10元.

求解此线性规划问题可以得到王老板的最优方案：每天生产椅子4把，桌子3张，获最大利润62元.家具制造问题——王老板遇到的新问题王老板过去一直以如何计划两种家具的生产量才能获得最大总利润为其生产、经营的唯一目标。然而，市场经济环境下新的问题出现了，它迫使王老板不得不考虑…...（1）首先，根据市场信息，椅子的销售量已有下降的趋势，故应果断决策减少椅子的产量，其产量最好不大于桌子的产量.（2）其次，市场上找不到符合生产质量要求的木工了，因此决不可能考虑增加木工这种资源来增加产量，并且由于某种原因木工决不可能加班.（3）再其次，应尽可能充分利用油漆工的有效工作时间，但油漆工希望最好不加班.（4）最后，王老板考虑最好达到并超过预计利润指标56元.家具制造问题——王老板遇到的新问题讨论——1、王老板现在的生产、经营问题——多个目标的生产问题2、决策变量——椅子、桌子的生产量x1，x2

引入一种新的变量——正、负偏差变量d+、d-，d+、d-≥03、约束条件——

绝对约束、目标约束——硬约束、软约束4、目标函数——

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

d-）

其基本形式有三种：家具制造问题——王老板遇到的新问题（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小

minZ=f（d++d-

）（2）要求不超过目标值，即允许达不到目标值，即正偏差变量要尽可能地小

minZ=f（d+）（3）要求超过目标值，即超过量不限，但必须是即负偏差变量要尽可能地小

minZ=f（d-）家具制造问题——王老板遇到的新问题归纳上面的分析——王老板应在木工每天的有效工作时间受到严格限制的基础上按顺序考虑其他目标的实现.目标优先等级：（1）P1——椅子的产量最好不大于桌子的产量.（2）P2——充分利用油漆工的有效工作时间，但希望不加班.（3）P3——总利润不小于

56元.家具制造问题——王老板遇到的新问题决策变量：（1）x1——椅子的产量，x2——桌子的产量（2）

P1等级正、负偏差变量——d1+、d1-

P2等级正、负偏差变量——d2+、d2-

P3等级正、负偏差变量——d3+、d3-

x1

、x2

、d1+、d1-、d2+、d2-

、d3+、d3-≥0目标函数：

minZ=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+10x2+d3--d3+=56（P3

）家具制造问题——王老板遇到的新问题王老板的多目标线性规划问题——目标规划问题minZ=P1d1++P2（d2-+d2+）+P3

d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥0目标规划的一般形式目标规划VS线性规划线性规划只有一个目标.而目标规划具有多个目标，并有不同的优先级，低优先级目标必须服从高优先级目标的实现.线性规划寻求单一目标的最优值.而目标规划寻求所有目标与预计成果的最小差距，差距越小，目标实现的可能性越大.线性规划只接受最优解，而目标规划接受满意解，即如果某些低优先级的约束得不到满足，将目标规划的解称为满意解.目标规划的图解法如何求解多目标线性规划问题，其方法与求解线性规划问题的方法相似——目标线性规划单纯形法.但是，对于只有两个决策变量的目标线性规划问题同样可以采用图解的方法来揭示问题的解的某种特征.在用图解法解目标规划时，首先必须满足所有绝对约束条件.在此基础上，再按照目标优先级别从高到低的顺序，逐个地考虑各个目标约束条件.minZ=P1d1++P2（d2-+d2+）+P3d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥08x1+10x2=56

x1-x2=0

x1+2x2=102x1+x2=11

绝对约束域d2+

d3+

d3-d2-

d1-

d1+

（10/3，10/3）（2，4）目标规划的图解法王老板的目标规划新问题图解目标规划的单纯形解法

目标规划的模型实际上是求min型的线性规划，因此，也可以用单纯形法求解.在采用单纯形法求解目标规划时，目标函数是各优先因子的线性组合.因此，在判别各系数的正负及大小时，关键是要注意到优先因子的级别.当系数按优先级别从高到低已满足最优性条件时，且无法进一步优化时，从单纯形表上就可以得到目标规划的最优解或满意解.minZ=P1d1++P2（d2-+d2+）+P3d3-s.t.2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-≥02x1+x2+xs=11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1

、x2

、xs、d1+、d1-、d2+、d2-、d3+、d3-≥0

minZ=P1d1++P2(d2-+d2+)+P3d3-s.t.引入松弛变量列出初始单纯形表x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P3-102110000001101-10100-100001200100-10100810000100-156为了找到基变量xs、d1-、d2-、d3-，需将其目标函数中所在列的系数化为0.改写初始单纯形表x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156按优先级的级别由高到低依次检验，方法和单纯形法一样.11---55.6x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P212-2P3810-1xs021100000011d1-01-10100-1000d2-01200100-1010d3-0810000100-156从第一级优先P1行开始，由于第一行上系数都非正，故第一级优先P1已得到满足。x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P33-55-1xs03/2010-1/2001/206d1-03/20011/20-1-1/205x201/21001/200-1/205d3-03000-5105-16由于第二行上系数都非正，故第二级优先P2已得到满足。12/310/3102x1x2xsd1-d2-d3-d1+d2+d3+RHSP1-1P2-1-1P3-1xs000102-1/20-21/23d1-000013-1/2-1-31/22x2001004/3-1/6-4/3-1/21/64x101000-5/31/305/3-1/32由于第三行上系数都非正，故第三级优先P3也已得到满足。从而此题得满意解x1=2，x2=4.案例——

电视机厂装配彩色和黑白两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时.预计市场每周彩色电视机的销量是24台，每台可获利80元；每周黑白电视机的销量是30台，每台可获利40元.决策者的目标为：

第一优先级目标：充分利用装配线每周计划开动的40小时；

第二优先级目标：允许装配线加班，但加班时间每周尽量不超过10小时；第三优先级目标：装配电视机的数量尽量满足市场需求.因为彩色电视机的利润更高（是黑白电视机利润的2倍），取其市场需求满足权系数为2.目标规划模型

x1

——彩色电视机的生产量

x2

——黑白电视机的生产量x1+x2+d1--d1+=40x1+x2+d2--d2+=50x1+d3--d3+=24

x2+d4--d4+=30x1

、x2

、d1+、d1-、d2+、d2-、d3+、d3-、d4+、d4-≥0

minZ=P1d1-+P2

d2++P3（2d3-+1d4-）s.t.列出初始单纯形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-2-1d1-0111000-100040d2-01101000-10050d3-010001000-1024d4-0010001000-130为了找到基变量d1-、d2-、d3-、d4-，需将其目标函数中所在列的系数化为0.改写初始单纯形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP111-1P2-1P321-2-1d1-0111000-100040d2-01101000-10050d3-010001000-1024d4-0010001000-130按优先级的级别由高到低依次检验，方法和单纯形法一样.405024---x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP11-1-11P2-1P31-2-1d1-00110-10-101016d2-00101-100-11026x1010001000-1024d4-0010001000-1301626---30至此第一级优先P1、第二级优先P2已得到满足，但因为第三级优先P3还有数大于0，所以继续迭代.x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-1-11-1-1x200110-10-101016d2-000-11001-10010x1010001000-1024d4-000-101110-1-114---10---14虽然第三级优先级P3中仍有数大于零，但并不意味着解不是最优的。对于一个最优决策，如果优先级的系数中存在正数，就要看一看在同一列的更高等级水平是否有任何负数。若有，则最优解已达到；若没有，则继续求解.x1x2d1-d2-d3-d4-d1+d2+d3+d4+RHSP1-1P2-1P3-1-11-1-1x200101-100-11026d1+000-11001-10010x1010001000-1024d4-00-1-1-12101-2-14故此题得满意解x1=24，x2=26.目标规划的灵敏度分析目标规划的灵敏度分析主要针对优先级别进行，其原因是目标优先级别和权系数的确定往往带有一定的主观性.分析的方法主要是通过改变优先级别的顺序来观察解的变化情况.目标规划的应用某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1)不超过年工资总额60000元；(2)每级的人数不超过定编规定的人数；(3)Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工有10%要退休.有关资料汇总见下表，问如何拟定满意的方案？等级ⅠⅡⅢ工资额(元/年)现有人数编制人数200015001000101215121515解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数.对各级目标确定优先因子为：P1——不超过年工资总额60000元；P2——每级的人数不超过定编规定的人数；P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%建立目标约束2000(10-0.1×10+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1--d1+=6000010-0.1×10+x1+d2--d2+=12目标约束12-x1+x2+d3--d3+=1515-x2+x3+d4--d4+=15x1+d5--d5+=12×0.2X2+d6--d6+=15×0.2目标函数Minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)目标规划的应用某工厂生产甲、乙两种型号的微型计算机，他们均需经过两道工序加工。每台微机所需的加工时间、销售利润及该厂每周最大加工能力如下表工序1工序2利润甲乙最大加工能力433006245075150工厂经营目标的各级优先级如下：1、每周总利润不低于10000元；2、合同要求甲型机每周至少生产10台，乙型机每周至少生产15台；3、工序1每周生产时间最好为150，工序2生产时间可适当超过其能力.试建立这个问题的数学模型.解：设x1、x2分别表示甲、乙机器的生产台数目标规划的应用某市准备在下一年度预算中购置一批救护车，已知每辆救护车购置价为20万元。救护车用于所属的两个郊区县，各分配xA和xB台。A县