运筹学第三版第四章目标规划课件.ppt

《运筹学第三版第四章目标规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第三版第四章目标规划课件.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 目标规划Operational Research(OR)本章内容|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例目标规划问题的导出例4-1 某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知上网条件下，要求制订一个获利最大的生产计划。具体数据如下：产品限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68解得，最优解x1=8，x2=2，max z=64（元）目标规划问题的导出|一般来说，一个计划问题可能要满足多方面得要求。|线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼

2、此相容。但实际问题有时不能满足这样的要求。|线性规划解得可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。实际中，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助作出最优决策的参考性计划，或是提供多种计划方案，供最终决策时选择。例4-2 假设计划人员被要求考虑如下意见：(1)由于产品销售疲软，故希望产品的产量不超过产品的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4h设备工时；(4)计划利润不少于48元。计划人员需要会同有关各方作进一步的协调，最后达成了一致意见：原材料使用限额不得突破；产品产量要求必须优先考虑；设备工时问题其次考虑；最后考虑

3、计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。目标规划问题的导出目标规划的数学模型|基本概念（1）偏差变量 正偏差变量d+表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分；d+0，d-0，d+d-=0（2）绝对约束和目标约束 绝对约束就是必须要满足的约束条件，如线性规划中的约束条件。绝对约束是硬约束，对它的满足与否决定了解的可行性。目标约束是目标规划特有的概念，是一种软约束，目标约束中决策值之间的差异用偏差变量表示。目标规划的数学模型|基本概念（3）优先因子和权系数 一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是主次或轻重缓急的不同。要求第一

4、位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定 Pk Pk+1，k=1，2，K。表示Pk比 Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。这是绝对差别。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予他们不同的权系数wj，这种差别是相对的。目标规划的数学模型|基本概念（4）目标规划的目标函数 目标规划的目标函数由各目标约束的偏差变量及相应的优先因子和权系数构成。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是极小化minz=f(d+，d-)。三种基本

5、表达式：要求恰好达到目标值，即正、负偏差变量都要尽可能地小 minf(d+d-)或者 minz=f(d+d-)要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小 minf(d+)或者 minz=f(d+)要求不低于目标值，但允许超过目标值，即超过量不限，但是必须是负偏差变量要尽可能地小 minf(d-)或者 minz=f(d-)目标规划的数学模型例4-1的目标规划表达式为：minP1d1-,P2d2+,P3d3-绝对约束目标约束P1为两种产品产量要求的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们应满足P1P2P3目标规划的数学模型目标规划数学模型的一

6、般形式：gk为第k个目标约束的预期目标值，Wlk-和Wlk+为Pl优先因子对应各目标的权系数。目标规划的案例|例1：某工厂生产，两种产品，已知有关数据见下表。试求获利最大的生产方案。产品限量原材料（kg/件）2111设备（hr/件）1210利润（元/件）810解得，最优解x1=4，x2=3，max z=62（元）但实际上工厂在做决策时，要考虑市场等一系列其他条件：(1)根据市场信息，产品的销售量有下降趋势，故考虑产品 的产量不大于产品；(2)超过计划供应的原材料时，需用高价采购，会使成本大幅度增加；(3)应尽可能充分利用设备台时，但不希望加班；(4)应尽可能达到并超过计划利润指标56元。在单目

7、标规划问题的基础上，决策者在原材料受严格限制的条件下考虑：首先是产品 的产量不低于产品的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求决策方案。目标规划的案例目标规划|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例目标规划的图解法|对于只有两个决策变量的目标规划问题，可以用图解方法来求解。|在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即Rj+1属于Rj。若

8、Rj不空，而Rj+1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1,P2,Pj级目标，而不保证满足其后的各级目标。目标规划的图解法例4-3 用图解法解例4-2。|OAB区域是满足绝对约束和非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向，见图所示。|首先考虑P1，此时要求min d-1，因而解空间R1为OAC区域；再考虑P2，此时要求min d2+，因而解空间R2为ODC区域；最后考虑P3，此时要求min d3-，因而解空间R3为四边形EDCF区域。容易求得E，D，C，F四点的坐标分别为(8,0)、(9,0)、(6,3)、(4.8,

9、2.4)，故问题的解可表示为：1(8,0)+2(9,0)+3(6,3)+4(4.8,2.4)=(81+92+63+4.84,33+2.44)其中，1，2，3，40，1+2+3+4=1目标规划的图解法 例4-3最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时(如例4-3，R3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。目标规划的图解法例4-4 用图解法解下面的目标规划minP1d1-,P2d2+,P3(5d3-+3d4-),P4d1+目标规划的图解法所以满意解为：x1=6.5，x2=1.25目标规划的图解法 例4-4得到的解不

10、能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能的小。必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。事实上，在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍有可能被满足。目标规划|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例解目标规划的单纯形法|目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。|

11、在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1P2P3。当所有检验数都已满足最优性条件(cj-zj0)时，从最终单纯形表上就可以得到目标规划的解。解目标规划的单纯形法例4-5 用单纯形法解例4-4。引入松弛变量x3，min P1d1-,P2d2+,P3d3-cj000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1zj-cjP1-120010000P2000000100P3-6-

12、800000010 x3600201-5500000 x101-201-100000d2-360120-441-100P3d3-480200-66001-1zj-cjP1000100000P2000000100P30-2006-600010 x3120011-100-110 x124/51002/5-2/5001/10-1/100d2-36/5000-2/52/51-1-3/53/5P3x212/5010-3/103/10001/20-1/20zj-cjP1000100000P2000000100P3000000010解目标规划的单纯形法在单纯形表中，由于非基变量d1+和d3+的检验数都是零，

13、故知例4-4有多重最优解(满意解)。以d1+为换入变量继续迭代，可得如下单纯形表cj000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0 x320010/310000-5/65/6P1x1814/3000001/6-1/60d2-40-4/30001-1-2/32/3P3d1+8010/30-11001/6-1/6cj-zjP1000100000P2000000100P3000000010解目标规划的单纯形法以d3+为换入变量继续迭代，可得如下单纯形表cj000P100P2P30CBCBbx1x2x3d1-d1+d2-d2+d3-d3+0d3+120011-10

14、0-11P1x16101/101/2-1/200000d2-000-3/5-111-100P3x23011/20-1/41/40000cj-zjP1000100000P2000000100P3000000010解目标规划的单纯形法解目标规划的单纯形法结论：例4-5的解为以上四个满意解(即C，D，E，F四点)的凸组合。而且，从单纯形表，中可知，各非基变量检验数中三个优先因子的系数全部非负，这表示任何一个满意解都能满足所有目标的要求。单纯形法和图解法的解题结果完全一致。目标规划|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例目标规划的灵敏度

15、分析|在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同。例4-6 对例4-4的目标规划问题，已求得满意解为x1=13/2,x2=5/4。现决策者想知道，目标函数中各目标的优先因子和权系数对最终解的影响。为此，提出了下面两个灵敏度分析问题，即目标函数分别变为：(1)minP1d1-,P2d2+,P3d1+,P4(5d3-+3d4-)(2)minP1d1-,P2d2+,P3(W1d3-+W2d4-),P4d1+(W1,W20)目标规划的灵敏度分析解 目标函数的变化仅

16、影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。1.当目标函数变为（1），就是要了解交换第三和第四优先级目标对原解的影响。此时，单纯形表变为下表：cj00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0 x113/210001/2-1/21/2-1/200P3d1+300-111-100003P4d4-3/40000-1/41/41/4-1/41-10 x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000000000P30010-110000P400003/4-3

17、/417/43/403目标规划的灵敏度分析可见，原解最优性已被破坏(d2-的检验数-P3+3/4P40，即W1/W21/4时，原解不变，仍为x1=13/2,x2=5/4|当W1/W21/4时，原解改变。用单纯形法继续求解，可得新的满意解x1=5,x2=2(此时，d3-=3,d4-=0)|当W1/W2=1/4时，两个解均为满意解。目标规划的灵敏度分析第三优先级两目标权系数的改变有可能会影响所得的满意解。解的变化取决于两目标权系数的比值W1/W2，其临界点为1/4。事实上，在前两优先级目标均已被满足的条件下，如满足d3-=0，则使d4-=3/4；如满足d4-=0，则使d3-=3。d4-/d3-=1

18、/4。如将W1/W2看作同一优先级下两目标重要程度的比较，而将d4-/d3-看作因此而引起的不满足程度的比较，则两者的一致恰好说明了目标规划中权系数的作用和意义。目标规划|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例目标规划应用举例例8 有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量ai、销地Bj(j=1,2,3,4)的需要量bj、各产销地之间的单位物资运费cij见表。表中，ai和bj的单位为t，cij的单位为元t。编制调运方案时要求按照相应的优先级依次考虑下列7项目标：P1:B4是重点保证单位，其需要量应尽可能全部

19、满足；P2:A3向B1提供的物资不少于100t；P3:每个销地得到的物资数量不少于其需要量的80%；P4:实际的总运费不超过当不考虑P1至P6各目标时的最小总运费的110%；P5:因路况原因，尽量避免安排A2的物资运往B4；P6:对B1和B3的供应率要尽可能相同；P7:力求使总运费最省。试求满意的调运方案。目标规划应用举例B1B2B3B4aiA15267300A23546200A34523400bj200100450250解 用表上作业法可以求得不考虑P1至P6各目标时的最小运费调运方案，相应的最小运费为2 950元。现在建立问题的目标规划模型。设Ai运往Bj的物资为xijt(i=1,2,3;

20、j=1,2,3,4)，问题的目标规划模型为：minP1d4-,P2d5-,P3(d6-+d7-+d8-+d9-),P4d10+,P5d11+,P6(d12-+d12+),P7d13+目标规划应用举例设Ai运往Bj的物资为xijt(i=1,2,3;j=1,2,3,4)，问题的目标规划模型为：minP1d4-,P2d5-,P3(d6-+d7-+d8-+d9-),P4d10+,P5d11+,P6(d12-+d12+),P7d13+需求量约束供应量约束。考虑到各销地的需要量可以有20%的向下浮动，故作为绝对约束条件，且皆取“”号A3向B1的供应量目标约束向各销地的最低供应量目标约束实际运费的上限目标约束A2尽量不向B4调运物资的目标约束给B1和B3的供应率尽量相同的目标约束总运费尽量小的目标约束 解该目标规划，目标规划，可得使各方面尽可能满意的调运方案。相应的总运费为3 360元。目标规划应用举例B1B2B3B4A1100200300A290110200A310025050400190100360250该调运方案满足P1,P2,P3,P5各优先级目标，但在总运费和对B1及B3的供应率这两方面未能满足目标要求。总运费3360元超出运费目标上限3245元约3.5%。对B1和B3的供应率分别为95%和80%，差别较大，但这是较低级的目标，对调运方案的满意程度影响不大。