线性规划的扩展

1、 应用运筹学应用运筹学 v 目标规划目标规划 v 动态规划动态规划 v目标规划目标规划 解决需要考虑多个目标的决策问题解决需要考虑多个目标的决策问题 目标规划与线性规划比较：目标规划与线性规划比较： 线性规划线性规划 目标规划目标规划 问题：问题： 单目标单目标 多目标多目标 约束：约束： 硬约束、矛盾硬约束、矛盾 划分等级划分等级 求解：求解： 绝对最优绝对最优 实际满意实际满意 目标规划是在满足现有的一组约束条件下，求出尽目标规划是在满足现有的一组约束条件下，求出尽 可能接近理想值的解。可能接近理想值的解。 v目标规划引例目标规划引例 某厂生产某厂生产i, ,ii两种产品：两种产品： 求获

2、利最大的生产方案？求获利最大的生产方案？ iii 拥有量拥有量 原材料原材料 设设 备备 2 1 1 2 11 10 利润利润810 这是一个单目标规划这是一个单目标规划 线性规划模型：线性规划模型： max z 8x1+10x2 s.t. 2x1+ x211 x1+2x210 x1,x20 最优方案为：最优方案为： x1=4 x2=3 z=62 实际上工厂作决策时要考虑市场等一系列其他条实际上工厂作决策时要考虑市场等一系列其他条 件或目标，如：件或目标，如： 根据市场信息，产品根据市场信息，产品i的销售有下降，因此考的销售有下降，因此考 虑产品虑产品ii的产量不低于产品的产量不低于产品i；

3、尽可能利用设备，但不希望加班；尽可能利用设备，但不希望加班； 应尽可能达到计划利润指标应尽可能达到计划利润指标56元。元。 这样在考虑产品决策时，成为多目标决策问题。这样在考虑产品决策时，成为多目标决策问题。 需要通过目标规划方法来解决。结果是满意解需要通过目标规划方法来解决。结果是满意解 （可以是不到一点，也可以超出一点，但要尽可（可以是不到一点，也可以超出一点，但要尽可 能提接近目标值能提接近目标值 ）。）。 设决策变量为设决策变量为 x1,x2 , 实际决策值与目标值之间的差异实际决策值与目标值之间的差异 决策值超过目标值的部分决策值超过目标值的部分 决策值低于目标值的部分决策值低于目标

4、值的部分 严格满足的等式或不等式约束严格满足的等式或不等式约束 把约束右端项看成是要追求的目标值，在达到此目标时把约束右端项看成是要追求的目标值，在达到此目标时 允许有正负偏差，线性规划问题的目标函数，在给定目标值和加允许有正负偏差，线性规划问题的目标函数，在给定目标值和加 入正、负偏差后可变换为目标约束，也可将绝对约束变换为目标入正、负偏差后可变换为目标约束，也可将绝对约束变换为目标 约束。约束。 引例中：引例中： z 8x1+10x2 可变换为可变换为: 8x1+10x2d1d1 = 56 2x1+ x211 可变换为可变换为: 2x1+ x2d2d2 = 11 要达到的多个目标之间有主次

5、、轻重要达到的多个目标之间有主次、轻重 缓急之分，因此各目标之间有优先等级。凡第一位要达到的目缓急之分，因此各目标之间有优先等级。凡第一位要达到的目 标赋予等级系数标赋予等级系数p1,次位的赋予等级系数次位的赋予等级系数p2，以此类推；并规，以此类推；并规 定定pkpk+1, pk比比pk+1更大的优先权。相同等级的以不同的权更大的优先权。相同等级的以不同的权 系数系数加以区别。加以区别。 目标规划的目标函数是按各目标目标规划的目标函数是按各目标 约束的正、负偏差变量和赋予相应的优先因子而构造的。当每约束的正、负偏差变量和赋予相应的优先因子而构造的。当每 一目标值确定后，决策者的要求是尽可能缩

6、小偏离目标值，因一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因 此目标规划的目标函数只能是此目标规划的目标函数只能是 min z = f f（d+,d- ) )。 要求恰好达到目标值（正负偏差都要尽可能地小），这时要求恰好达到目标值（正负偏差都要尽可能地小），这时 min z = f f（d+ d- ) ) 要求不超过目标值（允许达不到，正偏差要尽可能地小）要求不超过目标值（允许达不到，正偏差要尽可能地小） min z = f f（d+ ) ) 要求不低于要求不低于( (至少达到）目标值：至少达到）目标值： min z = f f（d- ) ) 例49 ：引例问题的目标规划模型引例问题

7、的目标规划模型 在原材料供应严格限制的条件下，考虑：在原材料供应严格限制的条件下，考虑： 产品产品 i 的产量不超过产品的产量不超过产品 ii ； 优先因子优先因子 p1 尽可能利用设备，但不希望加班；尽可能利用设备，但不希望加班； 优先因子优先因子 p2 应尽可能达到应尽可能达到（超过）利润指标超过）利润指标56元。元。 优先因子优先因子 p3 目标函数：目标函数： min z = p1d1+p2(d2- + d2+)+p3d3- s.t. 2x1 + x2 11 x1 - x2 + d1- - d1+ = 0 （0） x1 + 2x2 + d2- - d2+ = 10 （10） 8x1 +

8、 10x2 + d3- - d3+ = 56 （ 56） x1 ,x2 ,d1- ,d1+ ,d2-, d2+ , d3- ,d3+ 0 v目标规划的求解目标规划的求解 与线性规划问题求解相同，与线性规划问题求解相同， 采用单纯型方法，只是变量采用单纯型方法，只是变量 增加。增加。 （不作要求）（不作要求） 两个决策变量也可用图解法两个决策变量也可用图解法 求解，但比线性规划问题求求解，但比线性规划问题求 解要复杂得多。解要复杂得多。 例例49的图解的图解 2x1+x2=11 x1-x2 = 0 d2- -d3- - x1+2x2 =10 8x1+10x2 = 56 步骤：步骤： 1 先作绝对

9、约束先作绝对约束 2 再作再作d=0时的时的 目标约束目标约束 3 标出标出d+， d- - 的方向 的方向 4 按优先的次序按优先的次序 逐个使目标函逐个使目标函 数中的极小偏数中的极小偏 差变量尽可能差变量尽可能 取零，缩小可取零，缩小可 行域，找出问行域，找出问 题解。题解。 第一级：第一级： d1+ 取最小为取最小为0，可，可 行域为行域为ocb。 第二级：第二级： (d2+ d2- -)取最小取最小 值值0，只能在，只能在egd直线上直线上 第三级：第三级：d3- - 取最小取最小0，在直，在直 线线fgh上方上方 g(2,4) d(10/3,10/3) gd线段上的任线段上的任 一

10、点都是解。一点都是解。 d3+ + d2 d1+ + d1- - 例例410 ：建立目标规划模型并求解建立目标规划模型并求解 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配 线线1小时，装配线每周计划开动小时，装配线每周计划开动40小时。预计市场每周彩电的销量是小时。预计市场每周彩电的销量是 24台；黑白电视机的销量是台；黑白电视机的销量是30台。该厂确定的目标为：台。该厂确定的目标为： 第一优先级：充分利用装配线，每周计划开动不低于第一优先级：充分利用装配线，每周计划开动不低于40小时；小时； 第二优先级：允许装配

11、线加班，但加班时间每周尽量不超过第二优先级：允许装配线加班，但加班时间每周尽量不超过10小时。小时。 第三优先级：装配电视机的数量尽量满足市场需要，因彩电利润高于第三优先级：装配电视机的数量尽量满足市场需要，因彩电利润高于 黑白电视机，取其权系数为黑白电视机，取其权系数为2。 设：设：x1 ，x2分别为彩色和黑白电视机的产量：分别为彩色和黑白电视机的产量： 目标函数：目标函数： min z = p1d1 p2 d2 p3（2d3 d4 ） ） s.t. x1 x2 d1 d1 = 40 （ （ 40） x1 x2 d2 d2 = 50 （ （ 50） x1 d3 d3 = 24 （ （24）

12、x2 d4 d4 = 30 （ （ 30） x1 ,x2 ,d1- ,d1+ ,d2-, d2+ , d3- ,d3+ , d4- ,d4+ 0 例例410的图解的图解 x1+x2=40 x1 = 24 d2- - d3- - x1+ x2 =50 x2 = 30 步骤：步骤： 1 先作绝对约束先作绝对约束 2 再作再作d=0时的时的 目标约束目标约束 3 标出标出d+， d- - 的方向 的方向 4 按优先的次序按优先的次序 逐个使目标函逐个使目标函 数中的极小偏数中的极小偏 差变量取零，差变量取零， 缩小可行域，缩小可行域， 找出问题解。找出问题解。 第一级：第一级： d1 取最小为 取最

13、小为0 第二级：第二级： d2+ 取最小为取最小为0， 只能在只能在abcd范围范围 第三级：第三级：d3- - 的权数大，先取的权数大，先取 取取d3- 最小最小0，范围为，范围为abef 再取再取d4-最小，只能是最小，只能是e点点 e(24,26) 是满意解是满意解 彩色彩色24台台 黑白黑白26台台 d3+ + d2 d1+ + d1- - d4+ + d4- - v练习：建立目标规划模型练习：建立目标规划模型 某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下 规定：规定： 1.不超过年工资总额不超过年工资总额60000元

14、；元； 2.每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数； 3.ii，iii级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20； 4.iii级不足编制的人数可录用新职工，又级不足编制的人数可录用新职工，又i级的职工中有级的职工中有10 要退休。要退休。 有关资料汇总于下表中，问该领导应如何拟定一个满意的方案。有关资料汇总于下表中，问该领导应如何拟定一个满意的方案。 等级等级 工资额工资额 （元（元/年）年） 现有人数现有人数编制人数编制人数 i ii iii 2000 1500 1000 10 12 15 12 15 15 合计合计3742 v 决策决策1决策决

15、策2决策决策3决策决策n 1 状态状态1 23n 状态状态n 状态状态4状态状态3状态状态2 阶段阶段1阶段阶段2阶段阶段3阶段阶段n 表示决策顺序的离散量，阶段可按时间或空间划分。表示决策顺序的离散量，阶段可按时间或空间划分。 能确定地表示决策过程当前特征的量。状态可以是数能确定地表示决策过程当前特征的量。状态可以是数 量也可以是字符，数量状态可以是连续的也可以是离散的。量也可以是字符，数量状态可以是连续的也可以是离散的。 表示每一状态可以取不同值的变量。表示每一状态可以取不同值的变量。 ：从某一状态向下一状态过渡时所做的选择。决策是所：从某一状态向下一状态过渡时所做的选择。决策是所 在状态

16、变量的函数，记为在状态变量的函数，记为d (x )。 在状态在状态x 下，允许采取决策的全体。下，允许采取决策的全体。 某一状态以及该状态下的决策，某一状态以及该状态下的决策， 与下一状态之间的函数关系。与下一状态之间的函数关系。 下图表示从起点下图表示从起点a到终点到终点e之间各点间的距离。求之间各点间的距离。求a 到到e的最短路径。的最短路径。 c1 c3 d1 a b1 b3 b2 d2 ec2 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 阶段阶段1阶段阶段2阶段阶段3阶段阶段4 每一个阶段都至少有一个起始点初始状态（如每一个阶段都至少

17、有一个起始点初始状态（如bi) ) 每一个阶段都需要作一个选择决策本阶段由初始每一个阶段都需要作一个选择决策本阶段由初始 状态应演变到下一个阶段的哪一个起始点（本阶段状态应演变到下一个阶段的哪一个起始点（本阶段 终点）；终点）； 每一个阶段的决策不仅影响到本阶段的效果，还影响每一个阶段的决策不仅影响到本阶段的效果，还影响 到下一阶段的初始状态，从而也影响到此后的演变到下一阶段的初始状态，从而也影响到此后的演变 过程；过程； 每一个阶段的决策不能只从这一阶段本身考虑，要考每一个阶段的决策不能只从这一阶段本身考虑，要考 虑整个过程的最优效果。虑整个过程的最优效果。 v求从求从a到到e的最短路径问题

18、，可以转化为三个性质完的最短路径问题，可以转化为三个性质完 全相同，但规模较小的子问题，即分别从全相同，但规模较小的子问题，即分别从b1、b2、 b3到到e的最短路径问题。的最短路径问题。 记从记从bi (i=1, 2, 3) 到到e的最短路径为的最短路径为s(bi)，则从，则从a到到 e的最短距离的最短距离s(a)可以表示为：可以表示为： 状态转移函数在本例中为距离和最小状态转移函数在本例中为距离和最小 )b(s1 )b(s5 )b(s2 min )b(sab )b(sab )b(sab min)a(s 3 2 1 33 22 11 v同样，计算同样，计算s(b1)又可以归结为性质完全相同，

19、又可以归结为性质完全相同， 但规模更小的问题，即分别求但规模更小的问题，即分别求c1，c2，c3到到e的的 最短路径问题最短路径问题s(ci) (i=1, 2, 3)，而求，而求s(ci)又可以又可以 归结为求归结为求s(d1)和和s(d2)这两个子问题。从图中可这两个子问题。从图中可 以看出，在这个问题中，以看出，在这个问题中，s(d1)和和s(d2)是以知的，是以知的， 它们分别是：它们分别是： s(d1)=5，s(d2)=2 因而，可以从这两个值开始，逆向递归计算因而，可以从这两个值开始，逆向递归计算s(a) 的值。的值。 最优化原理最优化原理 最佳路径中任一状态（中间某点）到最终状态（

20、最最佳路径中任一状态（中间某点）到最终状态（最 终点）的路径也是该状态到最终状态一切可能中的终点）的路径也是该状态到最终状态一切可能中的 最短路径。最短路径。 c j abicjdte 阶段1阶段2阶段3阶段4 dt 例例410 教材教材p92 实例实例4.13 6 7 8 9 5 4 3 2 1 格拉斯哥格拉斯哥伦敦伦敦 起点起点终点终点 行进方向行进方向 寻优方向寻优方向 阶段阶段3阶段阶段4阶段阶段2阶段阶段1 130 110 120 105 110 130 125 130 140 105 110 95 110 140 95 125 125 0 420 310 305 235 200 2

21、05 110 140 95 v例例411 教材教材p95 实例实例4.14（资源分配）（资源分配） 一家医院有一家医院有5位护士要分派到位护士要分派到3个病房，不同数量的护个病房，不同数量的护 士在每个病房的作用如表，如何分配使总作用最大？士在每个病房的作用如表，如何分配使总作用最大？ 护士护士 人数人数 在病房中的作用在病房中的作用 xyz 0 1 2 3 4 5 0 4 6 10 14 16 0 4 8 13 15 16 0 6 9 13 16 17 请思考：请思考： 能否用线性规划来做能否用线性规划来做？ 动态规划思路动态规划思路： 护士分到护士分到x后就不能再分到后就不能再分到y与与z

22、， 因此可考虑先分配给因此可考虑先分配给x,再分配给再分配给y， 最后分配给最后分配给z。 每一阶段可分配数是前一阶段做每一阶段可分配数是前一阶段做 决策时的可分配数减去实际分配数。决策时的可分配数减去实际分配数。 5 1 2 3 4 5 0 1 2 3 4 5 0 0 x z y 剩余剩余 剩余剩余 0 4 6 10 14 16 0 0 4 0 6 9 13 16 17 分分5个个 结果：结果： x: 分分 1个个 y: 分分 3 个个 z: 分分 1 个个 总作用：总作用： 23 分分0个个 分分1个个 4 13 8 0 0 4 8 分分5个个 分分0个个 求求s到到f的最长距离？的最长距

23、离？ sf 22 23 19 14 10 6 0 17 16 13 9 6 0 15 16 作业作业 v某科研项目由三个小组用不同的方法独立进行研某科研项目由三个小组用不同的方法独立进行研 究，他们失败的概率分别为究，他们失败的概率分别为0.4、0.6和和0.8。为减。为减 少三个组失败的可能性，现决定派两名高级科学少三个组失败的可能性，现决定派两名高级科学 家参加这一科研项目，把这两人分配到各组后，家参加这一科研项目，把这两人分配到各组后， 各小组仍失败的概率如下表。应如何分派这两名各小组仍失败的概率如下表。应如何分派这两名 科学家以使三个小组都失败的概率最小。科学家以使三个小组都失败的概率

24、最小。 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 求从求从a到到e的最短路径的最短路径 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 e c2 f5(e)=0 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d1)=5 f5(e)=0 505)e(f)ed(d)d(f 5114 2 5

25、1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f4(d1)=5 202)e(f)ed(d)d(f 5224 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c1)=8 f4(d1)=5 11 2421 1411 13 dc8 11 8 min 29 53 min )d(f)d,c( )d(f)d,c( min)c(f 最优决策

26、 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0f3(c2)=7 f4(d1)=5 f3(c1)=8 22 2422 1412 23 7 7 11 min 25 56 min )(),( )(),( min)( dc dfdc dfdc cf 最优决策最优决策 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c3)=12

27、 f4(d1)=5 f3(c1)=8 f3(c2)=7 23 2423 1413 33 dc12 12 13 min 210 58 min )d(f)d,c( )d(f)d,c( min)c(f 最优决策 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c3)=12 f4(d1)=5 f2(b1)=20 f3(c2)=7 f3(c1)=8 11 3331 2321 1311 12 cb 20 22 21 20 min 1210 714 812 min )

28、c(f)c,b( )c(f)c,b( )c(f)c,b( min)b(f 最优决策 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c3)=12 f4(d1)=5 f2(b2)=14f3(c2)=7 f3(c1)=8f2(b1)=20 12 3332 2322 1312 22 cb 14 16 17 14 min 124 710 86 min )c(f)c,b( )c(f)c,b( )c(f)c,b( min)b(f 最优决策 2 5 1 12 14 1

29、0 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c3)=12 f4(d1)=5 f2(b3)=19 f3(c2)=7 f3(c1)=8f2(b1)=20 f2(b2)=14 23 3333 2323 1313 32 cb 19 23 19 21 min 1211 712 813 min )c(f)c,b( )c(f)c,b( )c(f)c,b( min)b(f 最优决策 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1 b3 b2 d2 ec2 f4(d2)=2 f5(e)=0 f3(c3)=12 f4(d1)=5 f2(b3)=19 f3(c2)=7 f3(c1)=8 f1(a)=19f2(b2)=14 f2(b1)=20 2 323 222 121 1 ba 19 20 19 23 min 191 145 212 min )b(f)b,a( )b(f)b,a( )b(f)b,a( min)a(f 最优决策 2 5 1 12 14 10 6 10 4 13 11 12 3 9 6 5 8 10 5 2 c1 c3 d1 a b1