第9章目标规划.ppt

1、,Chapter 9 目标规划,运筹学 Operations Research,1 目标规划数学模型 2 目标规划的图解法 3 本章重点：目标规划模型的建立，图解法,线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。 而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。 1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开

2、创性的研究.,【例1.1】 ： 试求利润最大的生产方案。,1目标规划的数学模型,解：设x1,x2分别为生产甲、乙的数量 MaxZ=8x1+10 x2 2x1+ x211 x1+2x2 10 x1,x20,实际中，工厂作决策时，还会考虑市场等一系列的其他条件，如： (1)据市场信息，产品甲的销量有下降的趋势，故考虑产品甲的产量不大于产品乙； (2)超过计划供应的原材料时，需高价采购，就使成本增加； (3)应尽可能充分利用设备工时，但不希望加班； (4)应尽可能达到并超过计划利润指标56元 这样在考虑产品决策时，便为多目标决策。 目标规划就是解决此类多目标决策问题的方法之一。,(二)、概念 1.目

3、标值、决策值（实际值） 目标值：决策者为每个要考虑的目标确定一个指标 值。 决策值或实际值：是指当决策变量xi选定以后，目标函数的对应值。 如：x1*=4 x2*=3 目标函数：2x1+x2=24+3=11,2. 正负偏差量d+,d 正偏差量d+：决策值超过目标值的部分； 负偏差量d：决策值未达到目标值的部分；,11。0.2。,11。,目标值,11.2。,决策值,正负偏差量只能有一个存在， 正的存在，负的就为0,当完成或超额完成规定的指标则表示： d+ 0, d = 0 当未完成规定的指标则表示：d+=0, d0 当恰好完成指标则表示：d+=0, d=0,3、绝对约束和目标约束 绝对约束：指必

4、须严格满足的等式约束或不等式约束。 在线性规划中，“目标”与“约束”十分明确，要求完全满足约束条件，并在此条件下使目标函数到极大或极小，这种“目标”与“约束”具有“绝对”的意义，称为硬约束；,在目标规划中，常将约束条件右侧值看成“追求的目标”，即目标值。在达到目标值时允许发生正或负的偏差，这样“目标”与“约束”的差别就不那么明显了，约束条件得到了软化，则它们是软约束。 目标约束： 在绝对约束中加入正负偏差量就变为目标约束； 线性规划问题的目标函数，在给定目标值和加入正负偏差量后就变为目标约束。,如： 绝对约束： x1+2x210 x1+2x2+ d d+=10 目标函数： max Z=8x1+

5、10 x2 8x1+10 x2+ d d+56,给定的目标值,设备的限制,应尽可能达到并超过计划利润指标56元,4、优先级因子与权系数 不同目标的重要程度是有区别的； 第一个要达到的目标，为第一优先级，优先级因子为P1， 第二个要达到的目标，优先级因子P2, 规定：Pk Pk+1 即：首先保证P1级目标实现，这时可不考虑次级目标，而P2级目标是在实现P1级目标的基础上考虑的.,权系数： 如有相同优先级因子的两个目标，则赋予它们不同的权系数ij。 5、目标规划的目标函数 指按各目标约束的正负偏差量和赋予相应的优先因子而构造的。 当一个目标值确定后，决策者的要求是尽可能缩小偏离目标值 目标规划的目

6、标函数只能是minZ=f(d+,d ),分三种情况： (1)决策值要求恰好达到目标值。即正负偏差量都尽可能地小。 MinZ= f (d+, d ),d,d,d越来越小,d+越来越小,目标值,(2)决策值要求不超过目标值。即允许达不到目标值，就是说正偏差量尽量地小 MinZ= f ( d+ ),d,d,d越来越小,目标值,d+越来越小,d+如果0，则d-一定为0; d+尽量地小，才能使d-有可能0,例如：血压不超过130，吃药使正偏差量尽量地小,(3)决策值要求超过目标值。即允许超过目标值，就是说负偏差量尽量地小 MinZ= f ( d ),d,d,d越来越小,目标为60分,d+越来越小,d-如

7、果0，则d+一定为0; d-尽量地小，才能使d+有可能0,例如：及格万岁,【例1.2】 决策者在原材料供应严格限制的基础上考虑： (1)产品乙的产量不低于产品甲的产量； (2)充分利用设备有效台时，不加班； (3)利润不小于56元； 求决策方案。,x1x2,解,思考,解：设x1,x2分别为生产甲、乙的数量 分别赋予这三个目标P1,P2,P3优先级因子 原材料供应严格限制 2x1+x211 考虑级别： 第一级： (1)产品乙的产量不低于产品甲的产量, x1x2, x1 x2 0, x1x2+ d1 d1+=0,第二级：(2)充分利用设备有效台时，不加班 x1+2x2+ d2 d2+=10 第三级

8、： (3)利润不小于56元 8x1+10 x2+ d3 d3+=56 minZ=P1d1+ + P2 ( d2+ + d2) + P3d3,x1 x2 0 使x1x2不超过0，就要使d+尽可能地小,要求利润尽量超过56,充分利用设备不加班,题,数学模型： minZ=P1d1+ + P2 ( d2+ + d2) + P3d3 2x1+x211 x1x2+ d1 d1+=0 x1+2x2+ d2 d2+=10 8x1+10 x2+ d3 d3+=56 xi0,dj+ 0,dj 0, i=1,2, j=1,2,3,思考以下的写法对吗？ minZ=P1d3+ + P2 ( d1+ + d1) + P3

9、d2 2x1+x211 x1+2x2+ d1 d1+=10 8x1+10 x2+ d2 d2+=56 x1x2+ d3 d3+=0 xi0,dj+ 0,dj 0, i=1,2, j=1,2,3,题目,1.下标变化 2.约束条件位置变了,【例1.3】 ：某企业加工产品甲和乙，它们的加工工时及相关数据如下表：,解,经研究提出下目标： P1：在制品占用金4600元； P2：产品甲争取销售50件； P3：减少两车间的剩余工时； P4：加工车间加班时间20h； P5：产品乙销售至少80件。,模型,解：设甲乙两产品的产量分别是x1,x2。 P1： 50 x1+30 x24600 50 x1+30 x2 +

10、 d1 d1+=4600 P1d1+ P2： x150 x1+ d2 d2+=50 P2 d2 P3： 2x1+x2120 x1+3x2 150 2x1+x2+ d3 d3+=120 x1+3x2+ d4 d4+=150 P3 ( d3 + 2d4),题目,P4：d3+20 d3 + d5 d5+ =20 P4 d5+ P5：x280 x2+ d6 d6+=80 P5 d6,题,综上所述，数学模型为： minZ=P1d1+ + P2 d2 + P3 ( d3 + 2d4) + P4 d5+ + P5 d6 50 x1+30 x2 + d1 d1+=4600 x1+ d2 d2+=50 2x1+

11、x2+ d3 d3+=120 x1+3x2+ d4 d4+=150 d3 + d5 d5+ =20 x2+ d6 d6+=80 xi0,dj+ 0,dj 0, i=1,2, j=16,课堂练习,参考解答,minZ=P1（d1+ + d1 ) + P2 ( d2 + d3) + P3 ( 3d2+ + d3+) 15 x1+25x2+ d1 d1+=750 x1+3x2+ d2 d2+=60 x1+x2+ d3 d3+=40 xi0,dj+ 0,dj 0, i=1,2, j=1,2,3,2 目标规划的图解法,2目标规划的图解法,当目标规划模型中只含两个决策变量（不包含偏差变量）时，可以用图解法求

12、出满意解,【例2.1】企业计划生产I 、 II 两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表44所示,表21,【解】设x1、x2分别为产品甲和产品乙的产量，目标规划数学模型为：,企业怎样安排生产计划，尽可能满足下列目标： (1)力求使利润指标不低于80元 (2)考虑到市场需求,、II两种产品的生产量需保持1:1的比例 (3)设备A既要求充分利用，又尽可能不加班 (4) 设备B必要时可以加班，但加班时间尽可能少 (5)材料必须不能超用。,2目标规划的图解法,(2),(1),(3),(4 ),x2,x1,(6),(5),o,4,6,4,6,2,2,图21,A,B,C,满意

13、解C(3,3),满意解X(3,3),问题1：最后的利润是多少？,问题3：B设备的加班时间是多少？,问题2：A设备的加班时间是多少？,20 x1+40 x2+d1d1+=80,x1=3, x2=3 得到d1+=100 利润=180,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,B,C,满意解是线段 上任意点，端点的解是 B(100/3，80/3)，C(60，0) 决策者根据实际情形进行二次选择,A,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,B,C,满意解

14、是点 B，X=(100/3，80/3),A,(3),x1,x2,20,40,60,80,100,20,40,60,80,100,(2),(1),(4),图53,满意解是点 A，X=(20,40),A,D,【例2.2】某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元该厂确定的目标为： P1：充分利用装配线每周计划开动40小时； P2：允许装配线加班；但加班时间每周尽量不超过10小时； P3：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其

15、权系数为2。 试建立目标规划模型，并求出黑白和彩色电视机的产量。,解：设彩色和黑白电视机的产量分别是x1,x2 minZ=P1d1 + P2 d2+ + P3（2d3 d4 ） x1x2 + d1 d1+ =40 x1x2 + d2 d2+ =50 x1 + d3 d3+ =24 x2 + d4 d4+ =30 xi0,dj+ 0,dj 0, i=1,2, j=1,2,3,4,以上的模型这样写对吗？ minZ=P1d1 + P2 d2+ + P3（2d3 d4 ） x1x2 + d1 d1+ =40 d1 + d2 d2+ =10 x1 + d3 d3+ =24 x2 + d4 d4+ =30

16、 xi0,dj+ 0,dj 0, i=1,2, j=1,2,3,4,3 应用举例,3 应用举例,【例3.1】：某工厂生产甲、乙两种型号的微机，每种型号的微机均需经过两道相同的工序，每台微机所需的加工时间、销售利润及工厂每周最大加工能力如下表：,如果工厂经营目标的期望值和优先等级如下： p1:每周总利润不得低于10 000； p2:因合同要求，甲型机每周至少生产10台，乙型机每周至少生产15台； p3:希望工序A的每周生产时间恰好为150小时，工序B的生产时间最好用足，甚至可适当加班； 试建立这个问题的目标规划模型。,解：设x1,x2分别为生产甲、乙两微机的台数 300 x1+ 450 x2 +

17、 d1 d1+ =10 000 x1 + d2 d2+=10 x2 + d3 d3+=15 4x1+6x2 + d4 d4+ =150 3x1+2x2 + d5 d5+ =70 xi0,dj+ 0, dj 0, i=12, j=15 minZ=P1d1 + P2 ( d2 + d3) + P3(d4 + d4+ + d5 ),【例3.2】：某工厂生产甲、乙两种型号的微机，每种型号的微机均需经过两道相同的工序，每台微机所需的加工时间、销售利润及工厂每周最大加工能力如下表：,如果工厂经营目标的期望值和优先等级如下： p1:每周总利润不得低于10 000； p2:因合同要求，甲型机每周至少生产10台

18、，乙型机每周至少生产15台； p3:希望工序A的每周生产时间恰好为150小时，工序B的生产时间最好用足，甚至可适当加班； p4：工序B的最多加班时间每周不超过30小时。 如果在工序B加班时间内生产出的产品，每台甲型减少利润20元，每台乙型机减少利润25元。 试建立这个问题的目标规划模型。,加班生产,解：设x1,x2分别为为正常时间和加班时间生产的甲型机台数，设x3,x4分别为为正常时间和加班时间生产的乙型机台数 300 x1+ 280 x2 + 450 x3+ 425x2 + d1 d1+ =10 000 x1 + x2 + d2 d2+=10 x3 + x4 + d3 d3+=15 4x1+4x2 + 6x3+6x4 + d4 d4+ =150 3x1+3x2 + 2x3+2x4 + d5 d5+ =70 d5 + d6 d6+ =30 xi0,dj+ 0, dj 0, i=14, j=16 minZ=P1d1 + P2 ( d2 + d3) + P3(d4 + d4+ + d5 )+ P4d6 +,课堂练习：LB广告代理公司正在设法为奇瑞汽车公司确定电视广告时间表。奇瑞汽车公司有3个目标： 它的广告至少应当由40