目标规划ppt课件

1、机 型 工 时 （小时/台） 销量预测 （台）利 润 （元）黑白电视机115200彩色电视机130400例 1. 某厂消费黑白和彩色二种电视机。工况如下：第三章 目的规划假设该厂每周的正常消费才干是40小时，应如何安排消费可使得每周所获得的利润最大?解：设每周消费彩色电视机 x1台，黑白电视机 x2台。 最优方案：x* =(30,10)T,获利 14000 元。问题的提出：假设按上述方案安排消费，获利的目的得到了优化，其他的目的忽略了：对于消费车间来说，生产的种类越少、批量越大，越容易安排消费；对于销售部门来说，种类越多越容易满足不同的消费群体，从而适销对路。对于仓储部门来说，希望销售周期较长

2、的商品消费的越少越好，这样可以节约仓储空间。Max f = 400 x1 + 200 x2s.t.x1 30 x2 15x1 + x2 40 x1 0, x2 0在 例 1 中，假设该厂经理从实践出发思索以下目的，并按 其重要性陈列如下： 必需坚持正常开工； 希望多销售一些电视机，最好多销售些彩电； 希望加班时间尽能够地少。这时，该厂又应如何安排消费呢?在处置实践决策问题时，除了要思索可用资源量的限制以外，还要思索多个决策要求。换句话说，实践决策问题往往有多个“目的，而不是像 (LP) 一样目的独一。普通说来，对于目的的表达通常有三种方式：1. fi(x)bi, 希望第 i 个目的不超越某值；

3、2. fi(x)bi, 希望第 i 个目的不低于某值；3. fi(x) = bi, 希望第 i 个目的等于某值。不论哪种表达方式，我们都可以在目的表达式一侧加上一个缺乏偏向 di, 或减去一个多余偏向 di+, 使它们转换成某种规范方式，继而可以经过控制偏向的变化来达到实现目的的愿望。这就是目的规划的根本思想。在规范方式中，对第 i 个目的而言，缺乏偏向 di 和多余偏向 di+ 必需同时出现，且满足： di di+ = 0, di 0, di+ 0.fi(x) bifi(x) + di di+ = biMin di+ fi(x) bifi(x) + di di+ = biMin di fi(

4、x) = bifi(x) + di di+ = biMin (di +di+)目 标 相 应 约 束优化要求 消费才干约束 设 d1 表示任务时间缺乏 40 小时的 偏向，d1+ 表示任务时间超越 40 小时的偏向。得解：引入缺乏偏向和剩余偏向： 销售约束 设 d2 表示彩电销售缺乏 30 台的偏向； d2+ 表示彩电销售超越30台的偏向； d3 表示黑白电视销售缺乏15台的偏向； d3+表示黑白电视销售超越15 台的偏向。x1 + d2 d2+ = 30 x2 + d3 d3+ = 15优化要求：Min d1 .x1 + x2 + d1 d1+ = 40优化性态分别为 Min d2 和 Mi

5、n d3. 欲表达“最好多销售些彩电的要求，那么 Min ( 2d2 + d3 ). 假设 Pi 表示优化第 i 级的目的偏向，那么本例的目的规划模型为: 加班约束 加班越少越好应表达为 Min d1+. s.t.Min f = P1d1 + P2 (2d2 + d3 ) + P3d1+x1 + x2 + d1 d1+ = 40 x1 + d2 d2+ = 30 x2 + d3 d3+ = 15xi 0, i = 1,2; di, di+ 0, i = 1,2,3经理目的是：例 2. 某唱片商店有 5 位全职售货员，4 位兼职售货员。 唱片销售利润为1.5元/张。详细工况如下：售货员 工作时间

6、（小时/月） 销 售（张/小时） 工 资（元/小时） 加班工资（元/小时）全职160534.5兼职80222(1) 下月的唱片销售量达5500张；(2) 限制全职售货员的加班时间不超越100小时；(3) 坚持全体售货员充分就业，优先思索全职售货员； 尽量减少加班时间，但对二种售货员区别对待，优 先权因子视其对利润的奉献而定。试建立目的规划模型。解：设全体全职售货员下月任务时间为 x1小时，全体兼 职售货员下月任务时间为 x2小时。 销售量约束 设 d1 和 d1+ 分别表示销售量缺乏和超 过5500张的偏向，那么 5x1 + 2x2 + d1d1+ = 5500 优化要求： Min d1.(2

7、) 任务时间约束 设 d2, d2+和 d3, d3+分别表示全体全 职售货员、兼职售货员任务时间缺乏和超越额定时 间的偏向，那么 x1 + d2 d2+ = 5160 x2 + d3 d3+ = 480 优化要求分别为 Min d2 和 Min d3. 欲表达“优先思索全职售货员的要求，必需 Min (2d2 + d3)(3) 全职售货员加班时间约束 设 d21 和 d21+分别表示全 职售货员加班缺乏或超越100小时的偏向，那么 d2+ + d21 d21+ = 100 优化要求： Min d21+.(4) 总加班时间约束 由 (2) 知，d2+ 和 d3+ 分别表示全职 售货员、兼职售货

8、员的加班时间。 全职售货员的实践奉献是 51.5 4.5 = 3元； 兼职售货员的实践奉献是 21.5 2 = 1元。 相应的权因子为 3:1. 优化要求： Min (d2+ +3d3+). “全职售货员的加班时间 约束也可用另一种方式表达：设 d4 和 d4+ 分别表示全体全职售货员任务时间缺乏和超越 900 小时的偏向，那么 x1 + d4 d4+ = 900优化要求： Min d4+.所求的目的规划模型为：Min f = P1d1+P2 d21+P3 (2d2+d3)+P4 (d2+3d3+) s.t.5x1 + 2x2 + d1 d1+ = 5500 x1 + d2 d2+ = 800

9、 x2 + d3 d3+ = 320d2+ + d21d21+ = 100 xi 0, i = 1,2; dj, dj+ 0, j = 1,2,3,21目的规划模型的普通方式11min,llkkLKlkklkfddPs.t.1,nijjkkkjc xddb1( , ),nijjija xb 0,jx 1,2,., ;jn1,2,.,;kK1,2,.,;im,0,kkdd1,2,.,.kK(1)(2)Pl 称为优先因子； lk , lk+ 是是 Pl 对应各目的的权系数；对应各目的的权系数；约束 (1) 称为目的约束；约束 (2) 称为绝对约束。如何建立目的规划模型？建立目的规划模型需求确定 预

10、期目的值，优先级 和 权系数。预期目的值、优先级和权系数确实定要根据现有信息，综合运用各种决策技术以保证其合理性。例 3. 某公司有 3 个煤矿，4 个工厂。 每天的煤炭产量 和需求量以及运价如下表所示： 工厂煤矿B1B2B3B4产量A1365512A2244110A3436310需求量68610公司在做调运方案是依次思索以下要素：产地 A1 因库存限制，应尽量全部调出；因煤质要求，B4 的需求最好由 A3 供应；满足各销地需求；调运总费用尽能够小。试建立该问题的目的规划模型。解：设 xij 为从 Ai 调运到 Bj 的煤炭数量， ai 为 Ai 的产量，bj 为 Bj 的需求量，cij 为从

11、 Ai 调运到 Bj 的单位运价。由于调运总费用的预期值不知道， 我们首先要确定调运总费用的合理预期值。 工厂煤矿B1B2B3B4B5产量A13655012A22441010A34363010需求量686102 工厂煤矿B1B2B3B4B5产量A112A210A310需求量686102用最小元素法求出一初始调运方案24601082 对应初始调运方案的运价为： 36+54+02+20+110+38+62 = 84.取 80 作为调运总费用的预期值，那么可建立如下的目的规划模型：1231227144minjjfdddPPPP d s.t.14,ijijxa 1,.,4i 111114,jjxdda

12、 2213,ijjjjixddb 1,.,4j 35771180ijijijc xdd34224,xddb0,ijx 1,2,3,i1,.,4,j,0,kkdd1,.,7.k 目的规划的图解法适用范围：两个决策变量、多个目的的目的规划问题算法思想：在可行域内，首先找到一个使 P1 级目的满足的区域 R1. 然后，再在区域 R1 中寻觅一个使 P2级目的满足的区域 R2. 如此进展，直至找到满足最后一级目的的区域 Rs. 区域 Rs 称为此目的规划的解。对于 R1 R2 Rs, 假设某一 Ri (1is) 已减少到一点，那么计算在第 i 步终止，该点即为问题的可接受解。它阐明，只能满足 P1,P

13、i 级目的，无法进一步改善以满足后续的 Pi+1,Ps 级目的。例 1. 用图解法求解目的规划问题Min f = P1d1 + P2d2+ +P3d3s.t.5x1 + 10 x2 60 x1 2x2 + d1 d1+ = 04x1 +4x2 + d2 d2+ = 366x1 + 8x2 + d3 d3+ = 48xi 0, i = 1,2; dj , dj+0, j = 1,2,3解:x1x204812693. 依次遴选最优解区域。d1+d1d2d2+d3d3+P1d1 + P2d2+ +P3d3蓝色凸四边形区域中的点完全满足三个目的，即一切目的都得到了满足。1. 先不思索偏向变量，画出问题

14、的约束直线。2. 在约束直线上标上偏向变量。例 2. 用图解法求解目的规划问题Min f = P1(d1+ d2+) + P2d3 +P3d4+ + P4d5+s.t.4x1 + 5x2 + d1 d1+ = 804x1 + 2x2 + d2 d2+ = 4880 x1 +100 x2 + d3 d3+ = 800 x1 + d4 d4+ = 6x1 + x2 + d5 d5+ = 7xi0, i =1,2; dj, dj+ 0, j = 1,5 解:x1x204812162048123. 依次遴选最优解区域。d1d1+d2d2+d3d3+d4d4+d5d5+P1(d1+ d2+) + P2d

15、3 +P3d4+ + P4d5+解 x* = (0,8)T 完全满足前三个目的，第四个目的未能实现。暂不思索偏向变量， 画出问题的约束直线。2. 在约束直线上标上偏向变量。目的规划解的情况不意味着其后的低级目的也一定不能被满足。例 3. 某厂消费A, B 两种布料，平均消费才干是 1千米/ 小时。假设该厂每周的任务时间是80小时；市场预 测下周最大销量为 A 布料7万米，B 布料4.5万米； A 布料获利2.5元/米，B 布料获利1.5元/米。经理的目的是：(1) 防止开工缺乏；(2) 加班不超越10小时；(3) 力争到达最大销量；(4) 尽能够减少加班。建立问题的目的规划模型并解之。解: 设

16、消费 A 布料 x1 小时，B 布料 x2 小时。那么 正常任务约束 设 d1 和 d1+ 分别表示开工缺乏或超越80小时的偏向，那么 x1 + x2 + d1 d1+ = 80优化要求：Min d1. (2) 加班约束设 d2, d2+分别表示加班缺乏或超越额定时间的偏向，那么 x1 + x2 + d2 d2+ = 90优化要求：Min d2+. (3) 最大销量约束设 d3, d3+ 和 d4, d4+分别表示 A, B 两种布料销量缺乏或超越市场最大预丈量的偏向，那么 x1 + d3 d3+ = 70 x2 + d4 d4+ = 45优化要求：Min (5d3 + 3d4) .(4) 尽

17、能够减少加班由 (1), 尽能够减少加班就是要求开工超越 80小时的偏向d1+ 尽能够的小，故有优化要求：Min d1+. 由以上分析我们可以建立如下的规划模型：Min f = P1d1 + P2d2+ + P3 (5d3 + 3d4) + P4d1+s.t.x1 + x2 + d1 d1+ = 80 x1 + x2 + d2 d2+ = 90 x1 + d3 d3+ = 70 x2 + d4 d4+ = 45xi0, i = 1,2 ; dj, dj+ 0, j = 1,4x1x2020406080100204060801. 不思索偏向变量，画出问题的约束直线。2. 在约束直线上标上偏向变量

18、。d1d1+d2d2+d3d3+d4d4+P1d1+ P2d2+ P3 (5d3+3d4) + P4d1+3. 依次遴选最优 解区域。解x*= (70,20) 完全满足前二个目的，第三四两个目的未能实现，分别比预定值多了25和10个单位。目的规划的序贯算法按目的优先顺序，从高级到低级将目的规划的依次分解为一系列单目的规划问题分别求解。例 1. 用序贯算法求解目的规划问题Min f = P1( d3+ d3+) +P2d4+ +P3(2d1+ 3d2+)s.t.2x1 + x2 + d1 d1+ = 242x1 +3x2+ d2 d2+ = 48x1 + x2+ d3 d3+ = 203x1+4

19、x2+ d4 d4+ = 100 xi 0, i = 1,2; dj, dj+0, j = 1,4解:1. 思索第一级目的能否得到满足： 解之得： d3= d3+= 0, f1*=0, 第一级目的得到满足。2. 在第一级目的得到满足的根底上，思索第二级目的是 否得到满足：将 d3= d3+= 0 代入 Min f1 = d3+ d3+s.t.x1 + x2+ d3 d3+ = 20 xi 0, i =1,2; d3, d3+ 0.Min f2 = d4+s.t.x1 + x2+ d3 d3+ = 203x1+ 4x2+ d4 d4+ = 100 xi 0, i =1,2; dj, dj+ 0,

20、 j =3,4.可得 解之得： d4+= 0, f2*= 0, 即在第一级目的得到满足的基础上，第二级目的得到满足。3. 在第一级和第二级目的都得到满足的根底上，思索 第三级目的能否得到满足：将 d4+= 0 代入 到以下目 标规划模型中Min f2 = d4+s.t.x1 + x2= 203x1+ 4x2+ d4 d4+ = 100 xi 0, i =1,2; d4, d4+0. 可得Min f3 = 2d1+ 3d2+s.t.x1 + x2 = 203x1+ 4x2+ d4 d4+ = 1002x1 + x2 + d1 d1+ = 242x1 + 3x2+ d2 d2+ = 48xi 0,

21、 i = 1,2; dj, dj+ 0, j = 1,2,4Min f3 = 2d1+ 3d2+ s.t.x1 + x2= 203x1+ 4x2+ d4 = 1002x1 + x2 + d1 d1+ = 242x1 +3x2+ d2 d2+ = 48xi 0, i = 1,2; d4, dj, dj+ 0, j = 1,2.解之得： d1= d2= 0, d1+=8, d2+= 0, d4=32, f3*=16, 即第三级目的未能得到满足。x1x2010203040102030d1+d2+d4+d3-d3+目的规划的单纯形法算法思想11minllkkkllLKkkfddP将目的规划的目的函数中

22、的一切 Pi, i =1,L, 看成正常数，并以为 P1P2 PL,同时将一切的 + 看成普通意义下的加法，那么可将线性目的规划问题作为线性规划问题求解。例 1. 用单纯形法求解下面的目的规划 解：将一切 xi, dj, dj+ 视作一致的决策变量，建立单纯形表x1x2d1-d2-d3-d4-d1+d2+d3+d4+d1-111000100080d2-110100010090d3-100010001070d4-010001000145c00P105P33P3P4P2000Min f = P1d1 + P2d2+ + P3 (5d3 + 3d4) + P4d1+s.t.x1 + x2 + d1

23、d1+ = 80 x1 + x2 + d2 d2+ = 90 x1 + d3 d3+ = 70 x2 + d4 d4+ = 45xi 0, i = 1,2 ; dj , dj+ 0, j = 1,4x1x2d1-d2-d3-d4-d1+d2+d3+d4+d1-111000100080d2-110100010090d3-100010001070d4-010001000145P15P3P13P30000P1+P4P25P33P3fx1x2d1-d2-d3-d4-d1+d2+d3+d4+x2011110011020 x1100010001070d4-001011011125单纯形初表单纯形终表x1x

24、2d1-d2-d3-d4-d1+d2+d3+d4+x2011110011020 x1100010001070d4-001011011125d1+00010011001000P1+3P33P3P42P3 00P23P3+P43P33P3f最优解为: (x1, x2, d1-, d2-, d3-, d4-, d1+, d2+, d3+, d4+)T = (70, 20, 0, 0, 0, 25, 10, 0, 0, 0) .显然，前二个目的得到满足，第三四两个目的未能实现，分别比预定值多了25和10个单位。Min f = P1d1 + P2d2+ + P3 (5d3 + 3d4) + P4d1+x

25、1x2d1-d2-d3-d4-d1+d2+d3+d4+d1-111000100080d2-110100010090d3-100010001070d4-010001000145P15P3P13P30000P1+P4P25P33P3fP11100001000P20000000100P35300000053为了防止上机运算时给 Pi (i=1,L) 赋值的困难，可将初始单纯形表改成以下方式：根据 P1P2PL 比较检验数的大小，做一次换基迭代得下表：x1x2d1-d2-d3-d4-d1+d2+d3+d4+d1-011010101010d2-010110011020 x1100010001070d4-

26、010001000145P15P3P13P30000P1+P4P25P33P3fP11(0)100101010P20000000100如此经过假设干步之后的单纯形终表：x1x2d1-d2-d3-d4-d1+d2+d3+d4+x2011110011020 x1100010001070d4-001011011125d1+00010011001000P1+3P33P3P42P3 00P23P3+P43P33P3fP10010000000P20000000100P30033200333P40001000100由于设定 P1P2PL , 判别检验数 j 的正负大小时，以高级别的 Pi 的系数为准。假设同

27、级别的 Pi 的系数一样，那么比较下一级别 Pi+1 的系数 (字典序)。目的规划的练习题 练习 1. 用图解法求解下面的目的规划3. 依次遴选最优解区域。1. 暂不思索偏向变量，画出问题的约束直线；2. 在约束直线上标上偏向变量；解：记住图解法的三个步骤：Min f = P1(d3+d4+) +P2d1+ P3d2 + P4(d3+1.5d4)s.t.x1 + x2 + d1 d1+ = 40 x1 + x2 + d2 d2+ = 100 x1 + d3 d3+ = 30 x2 + d4 d4+ = 15xi 0, i = 1,2; dj , dj+0, j = 1,4x1x20204060

28、80100204060d1+d2-d3-d3+d4-d4+解 x* = (25,15)T 完全满足前二个目的，第三、四两个目的未能实现，分别比预定值多了60 和 5 个单位。80100P1(d3+d4+) +P2d1+ P3d2 +P4(d3+1.5d4)练习 2. 某公司方案用 1000 万元基金开发 A, B, C 三种新产品。估计开发 A, B, C 三中新产品的投资利润率为 5%,7%, 10%. 由于新产品开发有一定风险，为了躲避风险，公司确定了如下优先顺序目的：产品 A 至少投资 300 万元；为了分散风险，任一产品的投资额不超越开发基金 总额的 35%;3. 至少留10%的开发基

29、金，以备急用；4. 使总投资利润最大。试建立投资分配方案的目的规划模型。解：设产品 A, B, C 的投资额分别为 x1, x2, x3 万元，那么总投资利润为 Z = (5x1+7x2+10 x3) %. 思索如下的 (LP) 问题：设上述 (LP) 问题的最优解为 Z0.如今，以 Z0 作为总投资利润的预期值并设 dZ,dZ+ 分别表示总投资利润缺乏或超越 Z0 的偏向变量；Max Z = (5x1+7x2+10 x3) %.s.t.x1 300 x1 350 x2 350 x3 350 x1 + x2 + x3 900 xi 0, i = 1,2,3. 令 d1,d1+ 分别表示产品 A

30、 的投资额缺乏或超越 300 万元的偏向变量；di, di+ (i =2,3,4) 分别表示产品 A, B, C的投资额缺乏或超越开发基金总额 35% 的偏向变量；d5, d5+分别表示开发基金预留额缺乏或超越10%的偏差变量。那么所求模型为：Min f = P1d1 + P2(10d2+7d3+5d4+) + P3d5+ + P4dZs.t.x1 + d1 d1+ = 300 x1 + d2 d2+ = 350 x2 + d3 d3+ = 350 x3 + d4 d4+ = 350 x1 + x2 + x3 + d5 d5+ = 900(5x1+7x2+10 x3) %+dZ dZ+= Z0 xi 0, i = 1,2,3 ; dZ, dZ+,dj, dj+0, j = 1,5.练习 3.某单位职工情况如下：单位指点在思索本单位职工的调资方案时，拟依次遵照以下原那么：(1) 不超越年工资总额60万元；(2) 调资后每级人数不超越定编人数；(3) II, III 级职工的晋级面尽能够各自到达现有人数的20% 晋级时不思索跳级。等级年工资额 (元/人)现有人数编制人数I200001012II15