课件运筹学四

1、第四章目 标 规 划（Goal Programming)主要内容：第一节 目标规划问题及其数学模型第二节 目标规划的图解法第三节 目标规划的单纯形法第四节 目标规划的灵敏度分析第五节 目标规划的应用举例第一节目标规划问题及其数学模型一、引例 例1：某企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为35元和60元；生产单位甲、乙两种产品需要消耗的原材料分别为2个单位和3个单位，需要占用的设备分别为1台时和2台时；原材料拥有量为16个单位；可利用的设备总台时为10台时。试问：若使得总产值最大，如何确定其生产方案？ 在实际决策时，企业领导者必须考虑市场等一系列其它条

2、件，如：（1）根据市场信息，乙种产品的需求量有下降的趋势，因此乙种产品的产量不应大于甲种产品的产量；（2）超过计划供应的原材料，需用高价采购，这就会使生产成本增加,须注意避免超标；（3）应尽可能地充分利用设备的有效台时，但不希望加班；（4）应尽可能达到并超过260元的计划产值指标。这些目标可以表示为如下不等式（等式）： 这是一个多目标决策问题，可以通过建立目标规划模型来解决。 二、目标规划问题的数学模型（一）目标规划问题数学模型的相关概念 1优先因子和权系数 优先因子 是将决策目标按其重要程度排序并表示出来。P1P2 。 权系数 区别具有相同优先因子 的目标的重要程度的差别，决策者可视具体情况

3、而定。对于引例中的四个目标，决策人员经讨论得出各个目标主次轻重的意见：原材料的使用不得突破限额；甲种产品的产量必须优先考虑(P1)；设备台时问题其次考虑(P2) ；最后考虑产值指标(P3) 。 P1： P2： P3： 2.目标值和偏差变量目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj 选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为 d 。 正偏差变量：表示实现值超过目标值的部分，记为 d。 负偏差变量：表示实现值未达到目标值的部分，记为 d。 规定d0, d0 当超额完成规定的指标则表示：d0, d0 当未完成规

4、定的指标则表示： d0, d0 当恰好完成指标时则表示： d0, d0 因此有 d d 0。对于引例，有：3.绝对约束和目标约束绝对约束：在约束条件中，必须绝对满足的约束条件称为绝对约束。目标约束：对于某些条件，我们提出其目标值，希望它们尽量满足这些目标值，但允许他们能够偏离这个目标值，这样的约束称为目标约束 。绝对约束目标约束4.达成函数目标规划的目标函数称为达成函数，由各目标约束的偏差变量及相应的优先因子和权系数构成。 因为目标规划追求的是各目标尽量达到其目标值，也就是期望有关偏差变量尽量小。具体而言，通常有三种形式： minf(d+):表示希望某个目标不超过其期望值；minf(d-):表

5、示希望某个目标不少于其期望值；minf(d+ d-):表示希望某个目标刚好达到其期望值。对于引例，我们首先希望x2要尽量小于x1，即希望d1+尽量小；又希望设备台时尽量用完且不加班，即希望d2+ d2-尽量小；还希望产值尽量超过目标值，即希望d3-尽量小。再结合它们目标对应的优先因子，列出达成函数，为： 由此，我们可以得到引例的目标规划模型如下： （二）目标规划问题数学模型的一般形式 三、目标规划与线性规划的比较 1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。 2、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重

6、缓急和主次之分，即有优先权。3、线性规划求最优解；目标规划是找到一个满意解。第二节目标规划的图解法 图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤如下：第1步：作出绝对约束及决策变量的约束（与一般线性规划作图法相同）。第2步：令目标约束中的 ，作目标约束直线，标出达成函数中涉及的偏差变量增大时对应的目标约束直线的移动方向。第3步：按照优先因子从高到低的顺序，逐级考虑各个目标约束。对 级的各目标，确定最优解空间 ，对下一个优先级别 级各目标，确定它的最优解空间 ，但必须是 （ =1，2，3，L-1）。 在此过程中，

7、若遇到 不为空，而 为空，则该目标规划的满意解在 内，它（它们）能满足P1，P2， 级目标，不能但尽量满足 级目标；若能够求得最低优先级 对应的解空间不为空，则 中的所有点均为该目标规划的满意解，且能够满足所有目标要求。 例2：用图解法确定以下目标规划的满意解区域OAB区域OAC区域ACDE区域EFG(0,5)(0,5.6)(2,4)例3：用图解法确定以下目标规划的满意解区域OAB区域OAC区域ACDE区域EFG点G（满足前3级目标，不满足第4级目标，但满足第5级目标）第三节目标规划的单纯形法单纯形法的计算步骤： 1、建立初始单纯形表； 2、检验是否为满意解； 3、确定换入基变量； 4、确定换

8、出基变量； 5、迭代，返回到第2步； 6、确定满意解并对解进行分析。例4：用单纯形法求解例2。 解：引入松弛变量x3,将它们化为标准型： = min11/1,10/2,56/10=5 ,故 为换出变量。Cj0000P1P200P3CBXBbx1x2x30 x311211000000001-101-10000P210120001-100056810000001-1kjP1 000010000P2 -1-20000100P3 000000001表1：Cj0000P1P200P3CBXBbx1x2x30 x363/20100-1/21/200053/2001-11/2-1/2000 x251/210

9、001/2-1/2000630000-551-1kjP1 000010000P2 000001000P3 000000001得到满意解x1=0,x2=5，满足所有约束。表2：Cj0000P1P200P3CBXBbx1x2x30 x354/106/5010000-1/101/10056/109/5001-1001/10-1/100 x256/104/51000001/10-1/1006/53/50000-111/5-1/5kjP1 000010000P2 000001000P3 000000001的检验数为0，把它作为换入变量。把 作为换出变量。得到另外一个满意解x1=0,x2=5.6，满足所有

10、约束。表2中，表2中，x1的检验数为0，把它作为换入变量。把 作为换出变量。 Cj0000P1P200P3CBXBbx1x2x30 x33001002-2-1/21/2020001-13-3-1/21/20 x24010004/3-4/3-1/61/60 x1210000-5/35/31/3-1/3kjP1 000010000P2 000001000P3 000000001得到又一个满意解x1=2,x2=4，满足所有约束。所以，该问题有无穷多满意解，表示为：例5：用单纯形法求解例3。解：引入松弛变量x3，化为标准形式如下：cj0000P1P200P3P40P50CBXBbx1x2x30 x31

11、12110000000000001-101-100000000P210120001-1000000056810000001-10000P4369400000001-100P54110000000001-1cj-zjP10000100000000P2-1-200001000000P30000000010000P4-9-400000000100P5-1-100000000001cj0000P1P200P3P40P50CBXBbx1x2x30 x3300100-331/2-1/20000020001-13-3-1/21/200000200000-1/31/31/6-1/600-110 x121000

12、0-5/35/31/3-1/30000P420000029/3-29/3-7/37/31-1000 x24010008/6-8/6-1/61/60000cj-zjP10000100000000P20000010000000P30000000010000P400000-29/329/37/3-7/30100P50000000000010经过若干步迭代，得到最终单纯形表：得到唯一满意解：X=(2,4)第四节灵敏度分析例：求解如下目标规划问题当上述问题的目标函数变为 时，最优解是否改变？考虑前两级目标，得到解空间ABCD;考虑第三级目标，首先考虑min ,得到解空间ABEF; 然后考虑min ,在E

13、点得到满意解;解：（1）用图解法求解Cj00P1P40P25P303P30CBXBbx1x2P16121-10000000912001-100005P341-200001-1003P32010000001-1kjP1 -1-201000000P2 0000010000P3-5700000503P40001000000（2）用单纯形法求解Cj00P1P40P25P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4300-111-100003P33/40000-1/41/41/4-1/41-10 x25/401001/4-1/4-1/41/400kjP1 0

14、010000000P2 0000010000P300003/4-3/417/43/403P40010-110000X=(13/2,5/4)E点（3）用图解法求解新问题考虑前两级目标，得到解空间ABCD;考虑第三级目标，首先考虑min ,得到解空间CDGH; 然后考虑min ,在G点得到满意解;（4）用灵敏度分析考察新问题的最优解Cj00P1P40P2P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4300-111-100003P33/40000-1/41/41/4-1/41-10 x25/401001/4-1/4-1/41/400kjP1 001000

15、0000P2 0000010000P300003/4-3/41/43/403P40010-110000X=(13/2,5/4)E点与图解法矛盾！注意：图解法在处理有权系数的问题时可能会出现错误第五节目标规划的应用举例一、物资调运 某公司下属三个小型煤矿A1，A2，A3，每天煤炭的生产量分别为12t，10t，10t，供应B1，B2，B3，B4四个工厂，需求量分别为6t，8t，6t，10t。公司调运时依次考虑的目标优先级为： P1 ：A1产地因库存限制，应尽量全部调出； P2：因煤质要求，B4需求最好由A3供应； P3：满足各需求地需求； P4：调运总费用尽可能不超过82元； P5：A2至B2的道

16、路较差，运量尽量减少到最低点。 从煤矿到各工厂调运的运价见下表，试建立该问题的目标规划模型。 工厂 运价煤矿B1B2B3B4供应量（t）A1365212A2244110A3436310需求量（t）68610二、工作时间安排 某商店由经理、主任、销售员甲和乙以及1名兼职售货员。根据以往经验，各类人员每小时工作带来的销售额的分别是：经理：120元；主任：80元；销售员甲：45元；销售员乙：25元；兼职销售员：12元。该单位每投入100元的广告费带来240元的销售额。各类人员工作时间规定如下：经理、主任每月各200小时；销售员甲172小时；销售员乙160小时；兼职销售员100小时。主任和两位售货员可得相当于其销售额约5.5%的工资收入，根据以往经验，主任每月可得收入1050元；售货员430元；销售员乙为260元。加班限制：经理、主任每月不超过24小时；售货员甲不超过52小时；售货员乙不超过42小时；兼职售货员不超过32小时。 试确定该商店各类人员每月的工作时间及