运筹学胡运权第04章课件.ppt

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

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

3、策问题是典型的目标规划问题。|基本概念（1）偏差变量 d+0，d-0，d+d-=0（2）绝对约束和目标约束（3）优先因子和权系数（4）目标规划的目标函数 三种基本表达式：要求恰好达到目标值minf(d+d-)要求不超过目标值，但允许不足目标值minf(d+)要求不低于目标值，但允许超过目标值minf(d-)例4-1的目标规划表达式为：minP1d1-,P2d2+,P3d3-绝对约束目标约束P1为两种产品产量要求的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们应满足P1P2P3目标规划数学模型的一般形式：gk为第k个目标约束的预期目标值，Wlk-和Wlk+为Pl优先因

4、子对应各目标的权系数。|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例|对于只有两个决策变量的目标规划问题，可以用图解方法来求解。|在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即Rj+1属于Rj。若Rj不空，而Rj+1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1,P2,Pj级目标，而不保证满足其后的各级目标。例4-3 用图解法解例4-2。|OAB区域是满足绝对约束和

5、非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向，见图所示。|首先考虑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,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最后一级

6、目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时(如例4-3，R3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。例4-4 用图解法解下面的目标规划minP1d1-,P2d2+,P3(5d3-+3d4-),P4d1+-+1211-+1222-+1233-+244-+12iix+2x+d-d=6x+2x+d-d=9s.t.x-2x+d-d=4x+d-d=2x,x,d,d0(i=1,2,3,4)所以满意解为：x1=6.5，x2=1.25 例4-4得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对

7、那些不能满足的较低级别目标的偏离程度尽可能的小。必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。事实上，在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍有可能被满足。|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例|目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。|在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1P2P3。

8、当所有检验数都已满足最优性条件(cj-zj0)时，从最终单纯形表上就可以得到目标规划的解。例4-5 用单纯形法解例4-4。3123-+1211-+1222-+123-+123ii5x+10 x+x=60 x-2x+d-d=0s.t.4x+4x+d-d=366x+8x+d-d=48x,x,x,d,d0(i=1,2,3)引入松弛变量x3，min P1d1-,P2d2+,P3d3-cj000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1zj

9、-cjP1-120010000P2000000100P3-6-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在单纯形表中，

10、由于非基变量d1+和d3+的检验数都是零，故知例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+0d

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

12、定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同。例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)解 目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，

13、然后再作适当的处理。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/417/43/403可见，原解最优性已被破坏(d2-的检验数-P

14、3+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/4。如将W1/W2看作同一优先级下两目标重要程度的比较，而将d4-/d3-看作因此而引起的不满足程度的比

15、较，则两者的一致恰好说明了目标规划中权系数的作用和意义。|目标规划问题及其数学模型|目标规划的图解法|解目标规划的单纯形法|目标规划的灵敏度分析|目标规划应用举例例8 有三个产地向四个销地供应物资。产地Ai(i=1,2,3)的供应量ai、销地Bj(j=1,2,3,4)的需要量bj、各产销地之间的单位物资运费cij见表。表中，ai和bj的单位为t，cij的单位为元t。编制调运方案时要求按照相应的优先级依次考虑下列7项目标：P1:B4是重点保证单位，其需要量应尽可能全部满足；P2:A3向B1提供的物资不少于100t；P3:每个销地得到的物资数量不少于其需要量的80%；P4:实际的总运费不超过当不考

16、虑P1至P6各目标时的最小总运费的110%；P5:因路况原因，尽量避免安排A2的物资运往B4；P6:对B1和B3的供应率要尽可能相同；P7:力求使总运费最省。试求满意的调运方案。B1B2B3B4aiA15267300A23546200A34523400bj200100450250解 用表上作业法可以求得不考虑P1至P6各目标时的最小运费调运方案，相应的最小运费为2 950元。现在建立问题的目标规划模型。设Ai运往Bj的物资为xijt(i=1,2,3;j=1,2,3,4)，问题的目标规划模型为：minP1d4-,P2d5-,P3(d6-+d7-+d8-+d9-),P4d10+,P5d11+,P6

17、(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+111213142122232431323334-+11213111-+12223222-+13233333-+14243444-+3155-+112131661222x+x+x+x300 x+x+x+x200 x+x+x+x400 x+x+x+d-d=200 x+x+x+d-d=100 x+x+x+d-d=450 x+x+x+d-

18、d=250 x+d-d=100s.t.x+x+x+d-d=160 x+x+x-+3277-+13233388-+1424349934-+ijij1010i=1j=1-+241111-112131132333121234-+ijij1313i1j 1-+ijkk+d-d=80 x+x+x+d-d=360 x+x+x+d-d=200c x+d-d=3245x+d-d=0200(x+x+x)-(xxx)d-d0450c xd-d=2950 x,d,d0,i=1,2 ,3;j=1,2,3,4;k=1,2,.,13需求量约束供应量约束。考虑到各销地的需要量可以有20%的向下浮动，故作为绝对约束条件，且皆取“”号A3向B1的供应量目标约束向各销地的最低供应量目标约束实际运费的上限目标约束A2尽量不向B4调运物资的目标约束给B1和B3的供应率尽量相同的目标约束总运费尽量小的目标约束