运筹学-目标规划.pptx
本章内容目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例第1页/共22页目标规划问题的导出例4-1 某工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知上网条件下，要求制订一个获利最大的生产计划。具体数据如下：产品限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68解得，最优解x1=8，x2=2，max z=64（元）第2页/共22页目标规划问题的导出|一般来说，一个计划问题可能要满足多方面得要求。|线性规划有最优解的必要条件是其可行解集非空，即各约束条件彼此相容。但实际问题有时不能满足这样的要求。|线性规划解得可行性和最优性具有十分明确的意义，但那都是针对特定数学模型而言的。实际中，决策者需要计划人员提供的不是严格的数学上的最优解，而是可以帮助作出最优决策的参考性计划，或是提供多种计划方案，供最终决策时选择。第3页/共22页例4-2 假设计划人员被要求考虑如下意见：(1)由于产品销售疲软，故希望产品的产量不超过产品的一半；(2)原材料严重短缺，生产中应避免过量消耗；(3)最好能节约4h设备工时；(4)计划利润不少于48元。计划人员需要会同有关各方作进一步的协调，最后达成了一致意见：原材料使用限额不得突破；产品产量要求必须优先考虑；设备工时问题其次考虑；最后考虑计划利润的要求。类似这样的多目标决策问题是典型的目标规划问题。目标规划问题的导出第4页/共22页目标规划的数学模型基本概念（1）偏差变量 d+0，d-0，d+d-=0（2）绝对约束和目标约束（3）优先因子和权系数（4）目标规划的目标函数 三种基本表达式：要求恰好达到目标值minf(d+d-)要求不超过目标值，但允许不足目标值minf(d+)要求不低于目标值，但允许超过目标值minf(d-)第5页/共22页目标规划的数学模型例4-1的目标规划表达式为：minP1d1-,P2d2+,P3d3-绝对约束目标约束P1为两种产品产量要求的优先因子；P2为节约工时要求的优先因子；P3为计划利润要求的优先因子，它们应满足P1P2P3第6页/共22页目标规划的数学模型目标规划数学模型的一般形式：gk为第k个目标约束的预期目标值，Wlk-和Wlk+为Pl优先因子对应各目标的权系数。第7页/共22页目标规划目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例第8页/共22页目标规划的图解法对于只有两个决策变量的目标规划问题，可以用图解方法来求解。在用图解法解目标规划时，首先必须满足所有绝对约束。在此基础上，再按照优先级从高到低的顺序，逐个地考虑各个目标约束。一般地，若优先因子Pj对应的解空间为Rj，则优先因子Pj+1对应的解空间只能在Rj中考虑，即Rj+1属于Rj。若Rj不空，而Rj+1为空集，则Rj中的解为目标规划的满意解，它只能保证满足P1,P2,Pj级目标，而不保证满足其后的各级目标。第9页/共22页目标规划的图解法例4-3 用图解法解例4-2。第10页/共22页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,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目标规划的图解法第11页/共22页 例4-3最后一级目标的解空间非空。这时得到的解能满足所有目标的要求。当解不惟一时(如例4-3，R3为四边形EDCF区域)，决策者在作实际决策时究竟选择哪一个解，完全取决于决策者自身的考虑。目标规划的图解法第12页/共22页例4-4 用图解法解下面的目标规划minP1d1-,P2d2+,P3(5d3-+3d4-),P4d1+目标规划的图解法第13页/共22页所以满意解为：x1=6.5，x2=1.25目标规划的图解法 例4-4得到的解不能满足所有目标。这时，我们要做的是寻找满意解，使它尽可能满足高级别的目标，同时又使它对那些不能满足的较低级别目标的偏离程度尽可能的小。必须注意的是，在考虑低级别目标时，不能破坏已经满足的高级别目标，这是目标规划的基本原则。但是，也不能因此而以为，当高级别目标不能满足时，其后的低级别目标也一定不能被满足。事实上，在有些目标规划中，当某一优先级的目标不能满足时，其后的某些低级别目标仍有可能被满足。第14页/共22页目标规划目标规划问题及其数学模型目标规划的图解法解目标规划的单纯形法目标规划的灵敏度分析目标规划应用举例第15页/共22页解目标规划的单纯形法目标规划的数学模型实际上是最小化形的线性规划，可以用单纯形法求解。在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意P1P2P3。当所有检验数都已满足最优性条件(cj-zj0)时，从最终单纯形表上就可以得到目标规划的解。第16页/共22页解目标规划的单纯形法例4-5 用单纯形法解例4-4。引入松弛变量x3，min P1d1-,P2d2+,P3d3-第17页/共22页cj000P100P2P30CBxBbx1x2x3d1-d1+d2-d2+d3-d3+0 x3605101000000P1d1-01-201-100000d2-36440001-100P3d3-4868000001-1zj-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解目标规划的单纯形法第18页/共22页在单纯形表中，由于非基变量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解目标规划的单纯形法第19页/共22页以d3+为换入变量继续迭代，可得如下单纯形表cj000P100P2P30CBCBbx1x2x3d1-d1+d2-d2+d3-d3+0d3+120011-100-11P1x16101/101/2-1/200000d2-000-3/5-111-100P3x23011/20-1/41/40000cj-zjP1000100000P2000000100P3000000010解目标规划的单纯形法第20页/共22页解目标规划的单纯形法结论：例4-5的解为以上四个满意解(即C，D，E，F四点)的凸组合。而且，从单纯形表，中可知，各非基变量检验数中三个优先因子的系数全部非负，这表示任何一个满意解都能满足所有目标的要求。单纯形法和图解法的解题结果完全一致。第21页/共22页感谢您的观看！第22页/共22页
