运筹学第五章_目标规划

1、第五章第五章目标规划目标规划学习目的了解了解目标规划在多目标决策中的作用掌握掌握目标规划的建模方法和线性目标规划基本求解方法 了解了解目标规划在经济和管理中的基本应用方法 线性规划只有一个目标函数，但实际问题中往往要考虑多个目标，如设计一个新产品的工艺过程，不仅希望利润大而且希望产量高、消耗低、质量好、投入少等，由于同时考虑多个目标，使这类多目标问题要比单目标问题复杂得多 另一方面，这一系列目标之间，不仅有主次之分，而且有时会互相矛盾，这就给用传统方法来解决目标问题带来了一定的困难第一节目标规划实例与模型目标规划实例与模型 目标规划正是为了解决这类多目标问题而产生的一种方法。它要求决策者预先给

2、每个目标定出一个理想值(期望值) 目标规划就是在满足现有的一组约束条件下，求出尽可能接近理想值的解，这个解称为满意解(不称为最优解，因为一般情况不，它不是使每个目标都达到最优值的解)第一节目标规划实例与模型目标规划实例与模型与线性规划的区别与线性规划的区别n在线性规划中，要求单个目标的优化，而目标规划则强调使多个目标得到满意的解答 n线性规划中，为得到一个可行解，必须满足所有的约束条件。n在目标规划中，并不认为所有约束都是绝对的，因此对于非绝对的约束，目标规划并不要求绝对满足，而是设法使各目标离原先设定的意向指标值的偏差尽可能的小。 第一节目标规划实例与模型目标规划实例与模型例1：某工厂生产甲

3、乙两种产品，生产单位产品所需要的原材料及占用设备台时如下表所示，该工厂每天拥有设备台时为10，原材料最大供应量为11kg/天，已知生产 每单位甲产品可获利800元，乙产品为1000元，工厂在安排生产计划时，有如下一系列考虑：(1)由于市场信息反馈，产品甲销售量有下降趋势，故决定产品甲的生产量不超过产品乙的生产量(2)尽可能不超过计划使用原材料，因为超过计划后，需高价采购原材料，使成本增加(3)尽可能充分利用设备，但不希望加班(4)尽可能达到并超过计划利润5600元一、实一、实 例例甲乙拥有量原材料2111(kg)设备1210(台时)利润/元8001000第一节目标规划实例与模型目标规划实例与模

4、型显然这是一个多目标问题，若设x1,x2分别为该厂每日生产甲，乙两种产品的产量，则工厂决策者的考虑则可表示成：x1-x202x1+x2 11X1+2x2 108x1+10 x256第一节目标规划实例与模型目标规划实例与模型2、目标规划的基本概念与特点(1)理想值(期望值) 是指决策者事先对每个目标都有个期望值 如上例的右端值：0,11,10,56(2)正负偏差变量d+,d- 目标规划不是对每个目标求最优值，而是寻找使每个目标与各自的理想值之差尽可能小的解，为此对每个原始目标表达式(等式或不等式)的左端都加上负偏差变量d-及减去正偏差变量d+后，都将变成等式.第一节目标规划实例与模型目标规划实例

5、与模型如 8x1+10 x2568x1+10 x2+d-d+=56d-表示：当决策变量x1,x2取定一组值后，由原始目标式左端计算出来的值与理想值之偏差不足理想值的偏差d+表示超过理想值之偏差计算值与理想值关系：不足：d+=0超过：d-=0等于：d-=d+=0因此将总有：d+*d-=0必成立第一节目标规划实例与模型目标规划实例与模型(3)绝对约束与目标约束 绝对约束(硬约束)是指必须严格满足的等式或不等式约束，如线性规划问题中的所有约束条件都是绝对约束。 如上例2x1+x2 11 目标约束是目标规划特有的约束，它是把要追求的目标的理想值作为右端常数项，在目标表达式左端加减正负偏差变量构成的等式

6、约束，目标约束是由决策变量、正负偏差变量及理想值构成的软约束 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-+d3+=56第一节目标规划实例与模型目标规划实例与模型绝对约束与目标约束从形式上可以转化的如上例的绝对约束可以转化为2x1+x2+d4-d4+=11 和附加约束d4+=0一般地 fi(x)+di-di+=bi附加约束 di-=0 相当于绝对约束fi(x) bi附加约束di+=0 相当于约束约束fi(x) bi附加约束di-=di+=0 相当于fi(x)=bi第一节目标规划实例与模型目标规划实例与模型(4)优先级与权因子 多个目标之间有主次缓急

7、之分，凡要求首先达到的目标，赋于优先级p1,要求第2位达到的目标赋于优先级p2,设共有k0个优先级则规定 p1p2p3Pk00 P1优先级远远高于p2,p3，只有当p1级完成优化后，再考虑p2,p3。反之p2在优化时不能破坏p1级的优先值，p3级在优化时不能破坏p1,p2已达到的优值 由于绝对约束是必须满足的约束，因此与绝对约束相应的目标函数总是放在p1级第一节目标规划实例与模型目标规划实例与模型 有时在同一优先级中有几个不同的偏差变量要求极小，而这几个偏差变量之间重要性又有区别，这时可以用权因子来区别同一优先级中不同偏差变量的重要性，重要性大的在偏差变量前赋予大的系数如P3(2d3-+d3+

8、)表示偏差变量d3-,d3+处于同一优先级，但d3-的重要性比d3+的大，前者重要程度约为后者的2倍第一节目标规划实例与模型目标规划实例与模型(5)目标函数准则函数目标函数是由各目标约束的正负偏差变量及其相应的优先级、权因子构成的函数，且对这个函数求极小值，其中不包含决策变量xi.因为决策者的愿望总是希望尽可能缩小偏差，使目标尽可能达到理想值，因此目标函数总是极小化。有三种基本形式：第一节目标规划实例与模型目标规划实例与模型对fi(x)+di-di+=gi，要求选取一组x使：(1)若希望fi(x) gi，即fi(x)超过gi可以接受，不足则不能接受，则其对应目标函数为mindi-(2)若希望f

9、i(x) gi，即fi(x)不能超过gi值，不足可以接受，超过则不能接受，则其目标函数为：mindi+(3)若希望fi(x)=gi，即fi(x)既不能超过也不能不足gi，只能恰好等于gi，则其目标函数为：min(di-+di+)第一节目标规划实例与模型目标规划实例与模型对于上例目标约束为：x1-x2+d1-d1+=0 x1+2x2+d2-d2+=108x1+10 x2+d3-d3+=56考虑甲的生产量不能超过乙的生产量第1优先级目标函数为：minp1d1+考虑尽可能地充分利用设备，但不希望加班第2级的目标函数为：minp2(d2-+d2+)工厂希望达到并超过计划利润5600 第3级的目标函数为

10、:minp3(d3-)第一节目标规划实例与模型目标规划实例与模型因此其目标规划的数学模型：minz=p1d1+p2(d2-+d2+)+p3d3-s.t 2x1+x211 x1-x2+d1-d1+=0 x1+2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1,x20,di-,di+0，i=1,2,3第一节目标规划实例与模型目标规划实例与模型看起来有点繁有点烦例2：设某公司生产两种型号的电扇，一种为普通型，装配一个需要1小时，另一种为豪华型，装配一个需要2小时。正常的装配时间每周限定为40小时。市场调查表明每周销售普通型不超过30件，豪华型不超过15件。普通型每件的净利润为8

11、元，豪华型为每件12元。p公司经理提出如下优先次序的要求： n1总利润最大n2装配线尽可能少加班n3销售尽可能多的电扇（这同尽可能获取最大利润一致）。 n4根据市场调研要求每周生产的产品数不能多于销售的数量，即普通型电扇为30件，豪华型电扇为15件。第一节目标规划实例与模型目标规划实例与模型该问题的决策目标是：该问题的决策目标是：（1）总利润最大；（2）尽可能少加工；（3）尽可能多销售电扇；（4）生产数量不能超过预销售数量。（5）绝对目标约束。所谓绝对目标约束绝对目标约束就是必须要严格满足的约束。绝对目标约束是最高优先级，在考虑较低优先级的目标之前它们必须首先得到满足。第一节目标规划实例与模型

12、目标规划实例与模型 0, 15 30 4021000128 . .)5 . 1(),(),(),(min21222111442133212144332211),(21ddxxddxddxddxxddxxtsddPdPdPddPxx第一优先级决策目标 正偏差：决策正偏差：决策值超过目标值的值超过目标值的偏差部分偏差部分 负偏差：决策值小于目标值的偏差部分 指标偏离函数 约束条件约束条件决决策策变变量量第一节目标规划实例与模型目标规划实例与模型二、建立目标规划模型的步骤二、建立目标规划模型的步骤 p第一步：定义决策变量和有关的常量第一步：定义决策变量和有关的常量定义决策变量和决策目标约束等式右边的

13、常数。等定义决策变量和决策目标约束等式右边的常数。等式右边的常数是可利用的资源或是决策者特定的目标值。式右边的常数是可利用的资源或是决策者特定的目标值。p第二步：建立决策目标约束第二步：建立决策目标约束 通过分析决策变量之间的关系以及决策变量与目标值通过分析决策变量之间的关系以及决策变量与目标值之间的关系，建立一组目标约束。并从所有的决策目标中，之间的关系，建立一组目标约束。并从所有的决策目标中，找出绝对决策目标（即，如果不满足将导致最终结果无法找出绝对决策目标（即，如果不满足将导致最终结果无法实现的目标），将这些目标作为第一优先级。而后再确定实现的目标），将这些目标作为第一优先级。而后再确定

14、其余目标的优先级。其余目标的优先级。p第三步：建立指标偏差函数第三步：建立指标偏差函数第一节目标规划实例与模型目标规划实例与模型目标规划的一般模型为：目标规划的一般模型为： ), 2 , 1( 0 , ), 2 , 1( 0 ), 2 , 1( ),( . .)(min1n111LlddnjxLleddxcbxatsdwdwPalljlllnjjljjjjijKkLllkllklk第一节目标规划实例与模型目标规划实例与模型其中其中x xj j（j=1,2,j=1,2,n n）为决策变量；）为决策变量；P Pk k（ k=1,2k=1,2.K.K）为第）为第k k级优先因子；级优先因子；WWkl

15、 kl+ +,w,wkl kl- - 分别为第分别为第l l个目标约束的正负偏差变量的权个目标约束的正负偏差变量的权系数，在同一等级的目标中，根据对各因子考虑的先系数，在同一等级的目标中，根据对各因子考虑的先后次序的不同，赋予不同权系数。后次序的不同，赋予不同权系数。 e el l（ l=1,2,l=1,2,.L .L）为目标的预期目标值；）为目标的预期目标值；b bj j 为系统的资源量。为系统的资源量。 第一节目标规划实例与模型目标规划实例与模型用图解法求目标规划的数学模型：minz=p1d1+p2(d2-+d2+)+p3d3-s.t 2x1+x211 x1-x2+d1-d1+=0 x1+

16、2x2+d2-d2+=10 8x1+10 x2+d3-d3+=56 x1,x20,di-,di+0，i=1,2,3第二节目标规划的求解方法目标规划的求解方法一、图解法第二节目标规划的求解方法目标规划的求解方法(1)先作硬约束与决策变量的非负约束，同一般线性规划作图法 即先作：2x1+x2=11 及 x10,x20(2)作目标约束，此时，先让di-=di+=0。然后标出di- 及di+的增加方向(实际上是目标值减少与增加的方向)对例1 x1-x2=0 x1+2x2=10 8x1+10 x2=56(3)按优先级的次序，逐级让目标规划的目标函数中极小化偏差变量取0，从而逐步缩小可行域，最后找到问题的

17、解一、图解法2x1+x2=11x1-x2=0d1-d1+x1+2x2=10d2+d2-CD8x1+10 x2=56FEGd3+d3-OABP1:mind1+P2:min(d2-+d2+)P3:min(d3-) 满意解为线段DG上所有点(无穷多个解)第二节目标规划的求解方法目标规划的求解方法x1x2x1-x2=0 x1+2x2=108x1+10 x2=56p由上图知G点坐标方程组x1+2x2=108x1+10 x2=56 解得x1=2,x2=4D点坐标方程组为：x1+2x2=10 x1-x2=0 解得x1=x2=10/3 此时d1+=0,d2-+d2+=0,d3-=0都已满足第二节目标规划的求解

18、方法目标规划的求解方法 再满足P4 ,使 , 极小化，由于 是 的1.5倍，先考虑先满足P1 =0, =04d4d3d4d再满足P2使 =01d3d再满足P3使 极小化3d2d第二节目标规划的求解方法目标规划的求解方法单纯形方法单纯形方法问题问题 第二节目标规划的求解方法目标规划的求解方法i ii ic cz z ciP15P33P3P4P2ziVBx1x2d1-d2-d3-d11-d1+d11+P1d1-80111-15P3d2-701 113P3d3-4511d11-1011-1P40-1P348553P20-1P18011-1 在选择最优列时，先从检验数栏中最优等级 行开始寻找最大正检验数。如 行内有最大正检验数，就确定它为最优列，进行迭代。直到 行内检验数没有正值为止，再转入 行寻找最大检验数。如此继续下去，直到所有检验数全部检查完毕。1P1P1P2P检验数的计算：以 列为例，此时， ， 所以， 。故在检验数栏中的 行和 行与 列的交叉点处的数分别为1和5。 1x315PPzi0ic315PPczii1P3P1x第二节目标规划的求解方法目标规划的求解方