第04章目标规划.

第四章目标规划OperationalResearch(OR)本章内容目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例目标规划问题的导出例4-1某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知上网条件下，要求制订一个获利最大的生产计划。具体数据如下：产品ⅠⅡ限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）6812121212max6851060..4440,0zxxxxstxxxx解得，最优解x1=8，x2=2，maxz=64（元）目标规划问题的导出一般来说，一个计划问题可能要满足多方面得要求。线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但实际问题有时不能满足这样的要求。线性规划解得可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。实际中，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助作出最优决策的参考性计划，或是提供多种计划方案，供最终决策时选择。例4-2假设计划人员被要求考虑如下意见：(1)由于产品Ⅱ销售疲软，故希望产品Ⅱ的产量不超过产品Ⅰ的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4h设备工时；(4)计划利润不少于48元。计划人员需要会同有关各方作进一步的协调，最后达成了一致意见：原材料使用限额不得突破；产品Ⅱ产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。目标规划问题的导出目标规划的数学模型基本概念（1）偏差变量d+≥0，d-≥0，d+·d-=0（2）绝对约束和目标约束（3）优先因子和权系数（4）目标规划的目标函数三种基本表达式：①要求恰好达到目标值min{f(d++d-)}②要求不超过目标值，但允许不足目标值min{f(d+)}③要求不低于目标值，但允许超过目标值min{f(d-)}目标规划的数学模型例4-1的目标规划表达式为：min{P1d1-,P2d2+,P3d3-}绝对约束目标约束P1为两种产品产量要求的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们应满足P1》P2》P3目标规划的数学模型目标规划数学模型的一般形式：gk为第k个目标约束的预期目标值，Wlk-和Wlk+为Pl优先因子对应各目标的权系数。目标规划目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例目标规划的图解法对于只有两个决策变量的目标规划问题，可以用图解方法来求解。在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即Rj+1属于Rj。若Rj不空，而Rj+1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1,P2,…,Pj级目标，而不保证满足其后的各级目标。目标规划的图解法例4-3用图解法解例4-2。△OAB区域是满足绝对约束和非负条件的解空间。对于所有目标约束，去掉偏差变量，画出相应直线，然后标出偏差变量变化时直线平移方向，见图所示。首先考虑P1，此时要求mind-1，因而解空间R1为△OAC区域；再考虑P2，此时要求mind2+，因而解空间R2为△ODC区域；最后考虑P3，此时要求mind3-，因而解空间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)=(8α1+9α2+6α3+4.8α4,3α3+2.4α4)其中，α1，α2，α3，α4≥0，α1+α2+α3+α4=1目标规划的图解法例4-3最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时(如例4-3，R3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。目标规划的图解法例4-4用图解法解下面的目标规划min{P1d1-,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得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能的小。必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。事实上，在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍有可能被满足。目标规划目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例解目标规划的单纯形法目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1»P2»P3»…。当所有检验数都已满足最优性条件(cj-zj≥0)时，从最终单纯形表上就可以得到目标规划的解。解目标规划的单纯形法例4-5用单纯形法解例4-4。3123-+1211-+1222-+123-+123ii5x+10x+x=60x-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-}cj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x3605101000000P1d1-0[1]-201-100000d2-36440001-100P3d3-4868000001-1zj-cjP1-120010000P2000000100P3-6-800000010x3600201-5500000x101-201-100000d2-360120-441-100P3d3-480[20]0-66001-1zj-cjP1000100000P2000000100P30-2006-600010x3120011-100-110x124/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+的检验数都是零，故知例4-4有多重最优解(满意解)。以d1+为换入变量继续迭代，可得如下单纯形表Ⅳcj→000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0x320010/310000-5/65/6P1x1814/3000001/6-1/60d2-40-4/30001-1-2/32/3P3d1+8010/30-11001/6-1/6cj-zjP1000100000P2000000100P3000000010Ⅳ解目标规划的单纯形法以d3+为换入变量继续迭代，可得如下单纯形表Ⅴcj→000P100P2P30CBCBbx1x2x3d1-d1+d2-d2+d3-d3+0d3+120011-100-11P1x16101/101/2-1/200000d2-000-3/5-111-100P3x23011/20-1/41/40000cj-zjP1000100000P2000000100P3000000010解目标规划的单纯形法解目标规划的单纯形法结论：例4-5的解为以上四个满意解(即C，D，E，F四点)的凸组合。而且，从单纯形表Ⅲ，Ⅳ，Ⅴ，Ⅵ中可知，各非基变量检验数中三个优先因子的系数全部非负，这表示任何一个满意解都能满足所有目标的要求。单纯形法和图解法的解题结果完全一致。目标规划目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例目标规划的灵敏度分析在目标规划建模时，目标优先级和权系数的确定往往带有一定的主观性，因此，对它们的灵敏度分析是目标规划灵敏度分析的主要内容。目标规划灵敏度分析的方法、原理同线性规划的灵敏度分析本质上相同。例4-6对例4-4的目标规划问题，已求得满意解为x1=13/2,x2=5/4。现决策者想知道，目标函数中各目标的优先因子和权系数对最终解的影响。为此，提出了下面两个灵敏度分析问题，即目标函数分别变为：(1)min{P1d1-,P2d2+,P3d1+,P4(5d3-+3d4-)}(2)min{P1d1-,P2d2+,P3(W1d3-+W2d4-),P4d1+}(W1,W20)目标规划的灵敏度分析解目标函数的变化仅影响原解的最优性，即各变量的检验数。因此，应当先考察检验数的变化，然后再作适当的处理。1.当目标函数变为（1），就是要了解交换第三和第四优先级目标对原解的影响。此时，单纯形表变为下表：cj→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P3d1+300-111-100003P4d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000000000P30010-110000P400003/4-3/417/43/403目标规划的灵敏度分析可见，原解最优性已被破坏(d2-的检验数-P3+3/4P40)，故应用单纯形法继续求解。目标规划的灵敏度分析cj→00P1P30P25P403P40CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x15101/2-1/2001/2-1/2000d2-300-111-100003P4d4-3/200-1/41/4001/4-1/41-10x21/2011/4-1/400-1/41/400cj-zjP10010000000P20000000000P30001010000P4003/4-3/40017/43/403可知，第三和第四优先级目标交换后，原满意解已失去了最优性。新的满意解为x1=5,x2=1/2当目标函数变为(2)，就是要了解第三优先级中两目标权系数取值对原解的影响。此时，单纯形表变为:目标规划的灵敏度分析cj→00P1P40P2W1P30W2P30CBxBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x113/210001/2-1/21/2-1/200P4d1+300-111-10000W2P3d4-3/40000-1/41/41/4-1/41-10x25/401001/4-1/4-1/41/400cj-zjP10010000000P20000010000P30000W2/4-W2/4-W2/4W2/40W2P40010-1117/43/403可知，原解是否改变取决于d3-的检验数W1-W2/4。因此：当W1-W2/40，即W1/W21/4时，原解不变，仍为x1=13/2,x2=5/4当W1/W21/4时，原解改变。用单纯形法继续求解，可得新的满意解x1=5,x2=2(此时，d3-=3,d4-=0)当W1/W2=1/4时，两个解均为满意解。目标规划的灵敏度分析第三优先级两目标权系数的改变有可能会影响所得的满意解。解的变化