运筹学(四).

第四章目标规划（GoalProgramming)主要内容：第一节目标规划问题及其数学模型第二节目标规划的图解法第三节目标规划的单纯形法第四节目标规划的灵敏度分析第五节目标规划的应用举例第一节目标规划问题及其数学模型一、引例例1：某企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为35元和60元；生产单位甲、乙两种产品需要消耗的原材料分别为2个单位和3个单位，需要占用的设备分别为1台时和2台时；原材料拥有量为16个单位；可利用的设备总台时为10台时。试问：若使得总产值最大，如何确定其生产方案？0,1021632212121xxxxxx216035maxxxZ元310Z4,2**2*1xx在实际决策时，企业领导者必须考虑市场等一系列其它条件，如：（1）根据市场信息，乙种产品的需求量有下降的趋势，因此乙种产品的产量不应大于甲种产品的产量；（2）超过计划供应的原材料，需用高价采购，这就会使生产成本增加,须注意避免超标；（3）应尽可能地充分利用设备的有效台时，但不希望加班；（4）应尽可能达到并超过260元的计划产值指标。012xx163221xx10221xx260603521xx这些目标可以表示为如下不等式（等式）：这是一个多目标决策问题，可以通过建立目标规划模型来解决。二、目标规划问题的数学模型（一）目标规划问题数学模型的相关概念1．优先因子和权系数优先因子是将决策目标按其重要程度排序并表示出来。P1P2……。权系数区别具有相同优先因子的目标的重要程度的差别，决策者可视具体情况而定。lPlP1lPLPlklP对于引例中的四个目标，决策人员经讨论得出各个目标主次轻重的意见：原材料的使用不得突破限额；甲种产品的产量必须优先考虑(P1)；设备台时问题其次考虑(P2)；最后考虑产值指标(P3)。163221xx012xxP1：10221xxP2：260603521xxP3：2.目标值和偏差变量目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。规定d＋≥0,d－≥0当超额完成规定的指标则表示：d＋0,d－＝0当未完成规定的指标则表示：d＋＝0,d－0当恰好完成指标时则表示：d＋＝0,d－＝0因此有d＋×d－＝0。163221xx)3,2,1(00,2606035102021332122211112kddxxddxxddxxddxxkk，，对于引例，有：3.绝对约束和目标约束绝对约束：在约束条件中，必须绝对满足的约束条件称为绝对约束。目标约束：对于某些条件，我们提出其目标值，希望它们尽量满足这些目标值，但允许他们能够偏离这个目标值，这样的约束称为目标约束。163221xx)3,2,1(00,2606035102021332122211112kddxxddxxddxxddxxkk，，绝对约束目标约束4.达成函数目标规划的目标函数称为达成函数，由各目标约束的偏差变量及相应的优先因子和权系数构成。因为目标规划追求的是各目标尽量达到其目标值，也就是期望有关偏差变量尽量小。具体而言，通常有三种形式：min{f(d+)}:表示希望某个目标不超过其期望值；min{f(d-)}:表示希望某个目标不少于其期望值；min{f(d++d-)}:表示希望某个目标刚好达到其期望值。对于引例，我们首先希望x2要尽量小于x1，即希望d1+尽量小；又希望设备台时尽量用完且不加班，即希望d2++d2-尽量小；还希望产值尽量超过目标值，即希望d3-尽量小。再结合它们目标对应的优先因子，列出达成函数，为：3322211)(mindPddPdPZ3322211)(mindPddPdPZ)3,2,1(00,2606035102016322133212221111221kddxxddxxddxxddxxxxkk，，由此，我们可以得到引例的目标规划模型如下：（二）目标规划问题数学模型的一般形式)2.1(0,n)1,2(j0)2.1(),()2.1()(min1111LlddxmibxaKkgddxcddPZlljnjijijnjkkkjkjLlKkklkklkl三、目标规划与线性规划的比较1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。2、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。3、线性规划求最优解；目标规划是找到一个满意解。第二节目标规划的图解法图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤如下：第1步：作出绝对约束及决策变量的约束（与一般线性规划作图法相同）。第2步：令目标约束中的，作目标约束直线，标出达成函数中涉及的偏差变量增大时对应的目标约束直线的移动方向。第3步：按照优先因子从高到低的顺序，逐级考虑各个目标约束。对级的各目标，确定最优解空间，对下一个优先级别级各目标，确定它的最优解空间，但必须是（=1，2，3，…，L-1）。在此过程中，若遇到不为空，而为空，则该目标规划的满意解在内，它（它们）能满足P1，P2，…，级目标，不能但尽量满足级目标；若能够求得最低优先级对应的解空间不为空，则中的所有点均为该目标规划的满意解，且能够满足所有目标要求。0kkddlPlR1lP1lR1lRlRllRmR1mRmRmP1mPLPLR)3.2.1(0,,0112561081020min2121332122211121332211jddxxxddxxddxxddxxdPdPdPZjj例2：用图解法确定以下目标规划的满意解区域OAB区域OAC区域ACDE区域EFGox2x1ABCDEFGl1l2l3d1d2d3++-(0,5)(0,5.6)(2,4)5544332211mindPdPdPdPdPZ)5,4,3,2,1(00,43649561081020112215521442133212221112121kddxxddxxddxxddxxddxxddxxxxkk，，EoFl3DCBl2+d1l1x1x2Ad2-d3+--d4d5Gl4l5例3：用图解法确定以下目标规划的满意解区域OAB区域OAC区域ACDE区域EFG点G（满足前3级目标，不满足第4级目标，但满足第5级目标）第三节目标规划的单纯形法单纯形法的计算步骤：1、建立初始单纯形表；2、检验是否为满意解；3、确定换入基变量；4、确定换出基变量；5、迭代，返回到第2步；6、确定满意解并对解进行分析。例4：用单纯形法求解例2。)3,2,1(00,,561081020112321332122211121321kddxxxddxxddxxddxxxxxkk，，解：引入松弛变量x3,将它们化为标准型：θ=min｛11/1,10/2,56/10｝=5,故为换出变量。Cj0000P1P200P3CBXBbx1x2x30x311211000000001-101-10000P210120001-100056810000001-1σkjP1000010000P2-1-20000100P30000000011d1d2d2d3d3d1d2d3d2d表1：Cj0000P1P200P3CBXBbx1x2x30x363/20100-1/21/200053/2001-11/2-1/2000x251/210001/2-1/2000630000-551-1σkjP1000010000P2000001000P30000000011d1d2d2d3d3ddd得到满意解x1=0,x2=5，满足所有约束。表2：Cj0000P1P200P3CBXBbx1x2x30x354/106/5010000-1/101/10056/109/5001-1001/10-1/100x256/104/51000001/10-1/1006/53/50000-111/5-1/5σkjP1000010000P2000001000P30000000011d1d2d2d3d3dd2d的检验数为0，把它作为换入变量。把作为换出变量。3d2d得到另外一个满意解x1=0,x2=5.6，满足所有约束。表2中，表2中，x1的检验数为0，把它作为换入变量。把作为换出变量。3dCj0000P1P200P3CBXBbx1x2x30x33001002-2-1/21/2020001-13-3-1/21/20x24010004/3-4/3-1/61/60x1210000-5/35/31/3-1/3σkjP1000010000P2000001000P30000000011d1d2d2d3d3dd得到又一个满意解x1=2,x2=4，满足所有约束。所以，该问题有无穷多满意解，表示为：)4,2()6.5,0()5,0(321*aaaX10,,321321aaaaaa且其中，)46.55,2(3213aaaa例5：5544332211mindPdPdPdPdPZ)5,4,3,2,1(00,,4364956108102011232155214421332122211121321kddxxxddxxddxxddxxddxxddxxxxxkk，，用单纯形法求解例3。解：引入松弛变量x3，化为标准形式如下：cj0000P1P200P3P40P50CBXBbx1x2x30x3112110000000000001-101-100000000P210120001-1000000056810000001-10000P4369400000001-100P54110000000001-1cj-zjP10000100000000P2-1-200001000000P30000000010000P4-9-400000000100P5-1-100000000001d2d3d5d4d1d1d2d2d3d3d4d5d4d5dcj0000P1P200P3P40P50CBXBbx1x2x30x3300100-331/2-1/20000020001-13-3-1/21/200000200000-1/31/31/6-1/600-110x1210000-5/35/31/3-1/30000P420000029/3-29/3-7/37/31-1000x24010008/6-8/6-1/61/60000cj-zjP10000100000000P20000010000000P30000000010000P400000-29/329/37/3-7/30100P50000000000010d5d4d1d1d2d2d3d3d4d5d4d5d经过若干步迭代，得到最终单纯形表：得到唯一满意解：X=(2,4