运筹学--第四章--目标规划演示教学

1、运筹学-第四章-目标规划 运筹学运筹学 第四章第四章 目标规划目标规划Slide 2线性规划的局限性：线性规划的局限性：只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题。实际决策中，衡量方案优劣考虑多个目标。这些目标中，有主要的，也有次要的；有最大的，也有最小的；有定量的，也有定性的；有互相补充的，也有互相对立的，LP则无能为力。约束条件不能矛盾。在实际决策中，一旦出现矛盾，人们总是力图设法解决，或增加资源，或减少消耗，从而得到比较可行的方案。目标规划（Goal Programming）是在LP的基础上发展起来的解决多目标规划问题的最有效的方法之一。美国经济学家查恩斯

2、和库柏在1961年出版的管理模型及线性规划的工业应用一书中首先提出的。 运筹学运筹学 第四章第四章 目标规划目标规划Slide 3一、目标规划模型的基本思想一、目标规划模型的基本思想P110 例例3.1目标规划的基本思想：对每一个目标函数引进一个期望值期望值（理想值），但由于种种条件的限制，这些期望值往往并不都能达到，从而我们对每个目标引进正、负偏差变量正、负偏差变量，然后将所有的目标函数并入原来的约束条件并入原来的约束条件，组成新的约束条件。在这组新的约束条件下，寻找使各种目标偏差达到最小的方案各种目标偏差达到最小的方案。二、目标规划模型的建立二、目标规划模型的建立1、目标函数的期望值、目标

3、函数的期望值首先要对每一个目标确定一个希望达到的期望值ei(i=1,2, ,n)。根据历史资料、市场需求或上级部门的布置等来确定。第一节第一节 目标规划模型目标规划模型 运筹学运筹学 第四章第四章 目标规划目标规划Slide 42、正负偏差变量、正负偏差变量每个目标函数的期望值确定之后，目标的实际值和它的期望值之间就有正的或负的偏差。正偏差变量di+ 表示第i个目标超过期望值的数值；负偏差变量di- 表示第i个目标未达到期望值的数值。同一目标，它的取值不可能在超过期望值的同时，又没有达到期望值，所以在di+ 和di- 中至少有一个必须为零。di+ di-=0引入正、负偏差变量后，对各个目标建立

4、的目标函数方程。原来的目标函数变成了约束条件的一部分，即目标约束(软约束) ，原来的约束条件称为系统约束(硬约束硬约束)。njkkjkjEddxc1* 运筹学运筹学 第四章第四章 目标规划目标规划Slide 5对约束方程引入偏差变量，使矛盾着的方程不再矛盾。当不易发现矛盾时，我们甚至可以在所有的约束方程中都加入偏差变量。3、达成函数、达成函数如何使各目标的实际值最接近于各自的期望值，构造一个新的目标函数以求得有关偏差变量的最小值。这个新的目标函数反映了各目标函数的期望值达到或实现的情况，故把这个新的目标函数称为目标达成函数。（1）若要求尽可能达到规定的目标值，则正、负偏差变量di+、di- 都

5、尽可能最小，即minSi=di+di- ；最好等于最好等于（2）若希望尽可能不低于期望值(允许超过)，则负偏差变量di 尽可能的小，而不关心超出量di+ ，故只需将di- 列入目标函数，minSi= di- ；最好不小于最好不小于 运筹学运筹学 第四章第四章 目标规划目标规划Slide 6（3）若允许某个目标低于期望值，但希望不得超过期望值，则正偏差变量dk+ 尽可能地小，而不关心低于量dk- ，故只需将dk+列入目标函数，minSk= dk+ 。最好不大于最好不大于4、优先等级和目标的权系数优先等级和目标的权系数目标的重要程度不同，用优先等级因子Pk 来表示第k等级目标。优先等级因子Pk 是

6、正的常数，Pk Pk+1 。“ ”的含义是远远大于的意思。仅仅是个优先等级的记号，在具体计算时，它并不表示任何具体的数。在求较低级别目标的最优值时，不容许破坏已得到的较高级别的目标。一般来说，必须严格实现的目标和不能超过的资源约束必须严格实现的目标和不能超过的资源约束等均须列入等均须列入 P1级目标。级目标。同一优先等级下的目标的相对重要性，赋以不同的加权加权 系数系数w。 运筹学运筹学 第四章第四章 目标规划目标规划Slide 75、建立目标规划模型的基本步骤：、建立目标规划模型的基本步骤：1）按生产和工作要求确定各个目标及其优先等级和期望值；2）设立决策变量，建立各个约束条件方程；3）对每

7、个目标引进正、负偏差变量，建立目标约束条件，并入已有的约束条件；4）如果各约束条件之间有矛盾，也可适当引入偏差变量；5）根据各目标的优先等级和权系数写出达成函数。P110-113 例例3.1 ,P117 例例3.4【课堂作业课堂作业】：某工厂计划生产甲、乙两种产品，现有的设备资源、每种产品的技术消耗定额及单位产品的利润如下表所示。 运筹学运筹学 第四章第四章 目标规划目标规划Slide 8产品产品资源资源甲甲乙乙现有资源现有资源 设备设备4324单位产品利润单位产品利润 54管理部门提出新要求：第一个目标是实现利润最大，计划部门规定利润目标是20；第二个目标是充分利用设备台时，但尽量少加班；第

8、三个目标做如下规定，甲产品产量希望不少于3单位，乙产品产量比甲产品至少多2单位。假设：甲产品产量希望不少于3单位的权数为3，乙产品产量比甲产品多2单位的权数为5。 minf= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- ) s.t. 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0三、目标规划模型的标准形式三、目标规划模型的标准形式middniximiEddxclibxadwdwPfiii

9、njiijijinjjijjijmjjijKii,.,.,.,.,)(min*2102102121),(1111非负性约束目标约束绝对约束 运筹学运筹学 第四章第四章 目标规划目标规划Slide 10只含有两个决策变量的目标规划模型。线性规划是在可行域中寻找一点，使单个目标极大或极小；目标规划则是寻找一个区域，这个区域提供了相互矛盾的目标集的折衷方案。目标规划的图解法的思路：目标规划的图解法的思路：首先在可行域内寻找一个使P1级各目标均满足的区域R1；然后再在R1中寻找一个使P2级各目标均满足的区域R2(R2R1)；接着再在R2中寻找一个满足P3级各目标的区域R3(R3 R2 R1)；如此继续

10、，直到寻找到一个区域RK(RK RK-1 R3 R2 R1)，满足PK级各目标，这时RK即为这个目标规划的最优解 空间，其中的任一点均为这个目标规划的满意解。第二节第二节 目标规划的图解法目标规划的图解法 目标规划的图解法的步骤：目标规划的图解法的步骤：p首先，按照绝对约束画出可行域；p其次，不考虑正负偏差变量，画出目标约束的边界线,标出正负偏差的方向；p最后，按优先级别和权重依次分析各级目标。P118例例3.5【作业】:minf= P1 d1- + P2(d2- + d2+ ) + P3(3d3- +5 d4- )s.t. 5x1+4x2 +d1-d1+ = 20 4x1+3x2 +d2-

11、d2+ = 24 x1 +d3- d3+ = 3 -x1 + x2 +d4- d4+ = 2 x1 , x2 ,dk- , dk+ 0 x1x2d1+d1-d2+d2-d3+d3-d4-d4+ABCD满意解：满意解：x1=18/7, x2=32/7由图可知P1、P2都满足。满意解代入约束方程 后可得minf=9/7P3 运筹学运筹学 第四章第四章 目标规划目标规划Slide 12目标规划与线性规划的数学模型的结构相似。可用前述单纯形算法求解目标规划模型：v将优先等级Pk视为不同数量级很大的正常数；v正负偏差变量dk+、dk-视为松弛变量，以负偏差变量dk-为初始基变量，建立初始单纯形表；v在表

12、中按优先级别分别列出目标函数行；v最优性判别准则类似于LP的单纯形算法：检验数一般是判断各优先等级因子系数的正负和大小；v迭代时，先从最高级优先等级系数P1行中挑选调入变量。如果P1行的系数已全部非正，则从下一个优先等级系数P2行中挑选调入变量。以此类推。第三节第三节 目标规划的单纯形法目标规划的单纯形法 P120 例例3.6 序贯法，序贯法， P122 例例3.7 【课堂作业课堂作业】： minZ=P1 d1-+P2(d2-+d2+)+P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+= 24 x1 +d3- - d3+ = 3 -

13、x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0 划为标准型划为标准型 maxZ=-P1 d1-P2(d2-+d2+)-P3(3d3-+5d4-) 5x1+4x2 +d1- d1+ = 20 4x1+3x2 +d2- - d2+ = 24 x1 +d3- - d3+ = 3 - x1 + x2 +d4- - d4+ = 2 x1 , x2 ,dk- , dk+ 0cj 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数检验数 j00-P10- P2- P2-3P30-5P302054-1000000244300-100003100

14、000-1002-11000000 -1d1-d2-d3-d4- P1- P2- 3P3- 5P3+5 P1 +4 P2 -2 P3+4 P1 +3 P2 +5 P30-P10-2P20-3P30-5P3463-检验数检验数 j jd1-d2-x1d4- P1- P20- 5P33000001-100504-100-5500120300-1-440050100001-1-10+4 P1 +3 P2 +5 P30-P10-2P2-5 P1 -4 P2 +2 P3+5 P1 +4 P2 -5 P30-5P313-cj00- P10- P2- P2- 3P30- 5P30 值值CBXBbx1x2d1

15、-d1+d2-d2+d3-d3+d4-d4+检验数检验数 j jd3+d2-x1d4-0- P20- 5P3104/5 1/5 -1/500-10080-1/5 -4/5 4/5-1000044/5 1/5 -1/5000000609/5 1/5 -1/50000-1 0- P1000-1/5P2-4/5P2+4/5P2-2P2+9P3+P3-P3-3P3-5P3-10-检验数检验数 j jd3+d1+x1d4-000- 5P3100-1/4 -15/4 -5/40000303/4001/4 -1/4 -10063/4001/4 -1/40000807/4001/4 -1/400-10- P1

16、000-P2-P235/4P3+5/4P3-5/4P3-3P3-5P34-832/7c cj j00- P10- P2- P2- 3P30- 5P30 值值CBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+检验数检验数 j jx2d1+x1d4-000- 5P340001/3 -1/3 -4/3 4/3001100-14/3 -4/3 -1/3 1/300300000-110010000-1/3 1/3 7/3 -7/3 -100- P10 0-P2-P2-5/3P3+5/3P326/3P3-35/3P3-5P3-3检验数检验数 j jx2d1+x1d3-000- 3P33/7

17、0000-1/7 1/7-13/7 -3/732/70001/7 -1/7004/7 -4/778/700-19/7 -9/7001/7 -1/718/7 0001/7 -1/700-3/7 3/700- P100 0-P2-P2-3/7P3+3/7P3-3P3-26/7P3-9/7P3P3行中d2+的系数是3/7，但它在P2行中的系数为-1，故不能调入。所有检验数均小于等于零，已得最优解：X1=18/7,X2=32/7，d1-=d2+=d2-=d3+=d4+=d4-=0,d1+=78/7，d3-=3/7,minf=9/7P3。这说明最优解能完全实现P1、P2级目标，而P3级目标不能完全实现，

18、还相差9/7。第四节第四节 目标规划的应用目标规划的应用P124 例例3.8，P125 例例3.9在目标管理中的应用在目标管理中的应用 产品产品资源资源甲甲乙乙现有资源现有资源设备设备2010140售价售价108成本成本56最大需求量最大需求量610经营目标经营目标P1：总利润不低于40，P2：充分利用设备能力，且尽量不超过140如何安排生产？如何安排生产？minf= P1 d1- + P2 (d2-+d2+ ) x1 6 x2 10 5x1 + 2 x2 +d1- -d1+ =40 20 x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-, d

19、2+ 0 x1x2x1 =6x2 =10d1+d1-d2+d2-CBD(6,5)满意解：x1 =6, x2 = 5设备能力：需求：206+10 5=170，实际：140实现目标P1和P2，降低甲乙产品的设备消耗:降低率(170-140)/170=18%， 甲产品的设备消耗降为20 (1-18%)=16.4, 乙产品的设备消耗降为10 (1-18%)=8.2。总利润：总利润：40单位甲：单位甲：5单位乙：单位乙：2生产部目标生产部目标甲产品的产量：甲产品的产量：6，成本：，成本：5乙产品的产量：乙产品的产量：5，成本：，成本：6技术部目标技术部目标甲产品的设备单耗：甲产品的设备单耗：16.4乙产

20、品的设备单耗：乙产品的设备单耗： 8.2销售部目标销售部目标甲产品的销量：甲产品的销量：6，单价：，单价：10乙产品的销量：乙产品的销量：5，单价：，单价： 8minf= P2 d1- + P1 (d2-+d2+ ) x1 6 x2 10 5x1 + 2 x2 +d1- -d1+ =40 20 x1 +10 x2 +d2- -d2+ = 140 x1 , x2, d1-, d1+ , d2-, d2+ 0 x1x2x1 =6x2 =10A(6,2)d1+d1-d2+d2-E产品产品资源资源甲甲乙乙现有资源现有资源设备设备2010140售价售价108成本成本56最大需求量最大需求量610 降低设

21、备消耗很困难，则调整经营目标的次序降低设备消耗很困难，则调整经营目标的次序P1：充分利用设备能力，且尽量不超过140，P2：总利润不低于40如何安排生产？满意解：满意解：x1 =6, x2 = 2利润指标：利润指标：实际：56+2 2=34，期望： 40实现实现目标目标P1和和P2，增加甲乙产品的单位利润，增加甲乙产品的单位利润:增长率(40-34)/34=18%产品售价由市场决定，为提高利润，应从降低成本入手：产品售价由市场决定，为提高利润，应从降低成本入手： 甲产品的成本由5降为10 -5 (1+18%)=4.12, 乙产品的成本由6降为 8 -2 (1+18%)=5.63。总利润：总利润

22、：40单位甲：单位甲：5.88单位乙：单位乙：2.26生产部目标生产部目标甲产品的产量：6，成本：4.12乙产品的产量：2，成本：5.63技术部目标技术部目标甲产品的设备单耗：20乙产品的设备单耗：10销售部目标销售部目标甲产品的销量：6，单价：10乙产品的销量：2，单价： 8 运筹学运筹学 第四章第四章 目标规划目标规划Slide 22某副食品批发店预测某商品今后4月的购进与售出价格如表： 在库存管理中的应用在库存管理中的应用 月份月份1234成本成本(购价购价+库存库存)2.62.52.72.8售价售价2.92.73.13.3假设假设：该商品供不应求，最大销量受仓库容量限制； 正常库容3吨

23、，机动库容2吨； 月初批发销货，月中采购进货，进货所需资金完全来自销售收入； 1月初库存量2吨，成本2.5千元/吨，该月初无现金。 经营目标：经营目标：(1) 每月都使用正常库容，尽量不超容； (2) 每月下旬都应储备1千元以备急用； (3) 4个月总盈利最大。决策变量：决策变量：xj 第j 月的采购量， yj 第j 月的销售量绝对约束条件绝对约束条件各月销量约束各月销量约束:月初售货，各月销量不能多于其期初库存量。 1月 y1 2 2月 y2 2 y1 + x1 y1 + y2 x1 2 3月 y3 2 y1 + x1 y2 + x2 y1 + y2 + y3 x1 x2 2 4月 y42

24、y1 + x1 y2 + x2 y3 + x3 y1 + y2 + y3 + y4 x1 x2 x3 2各月采购量约束各月采购量约束：每月采购量依赖月初的售货收入。 1月 2.6x1 2.9y1 2.9y1 + 2.6x1 0 2月 2.9y1 2.7y2 + 2.6x1 +2.5x2 0 3月 2.9y1 2.7y2 3.1y3 + 2.6x1+2.5x2+2.7x3 0 4月 2.9y1 2.7y2 3.1y3 3.3y4 + 2.6x1 +2.5x2+2.7x3+2.8x40目标约束条件目标约束条件正常库容约束正常库容约束 1月 2 y1 + x1 3y1 + x1 + d1- d1+

25、=1 2月 y1 y2 + x1+ x2 + d2- d2+ = 1 3月 y1 y2 y3 + x1+ x2+ x3 + d3- d3+ = 1 4月 y1 y2 y3 y4 + x1+ x2+ x3 + x4 + d4- d4+ = 1各月储备金约束各月储备金约束 1月 2.9y1 -2.6x1 + d5- d5+ = 1 2月 2.9y1 +2.7y2 - 2.6x1 -2.5x2 + d6- d6+ = 1 3月 2.9y1 +2.7y2 +3.1y3 - 2.6x1-2.5x2-2.7x3 + d7- d7+ = 1 4月 2.9y1 +2.7y2 +3.1y3 +3.3y4- 2.

26、6x1 -2.5x2-2.7x3-2.8x4 + d8- d8+ = 1总盈利约束：总盈利约束：期望利润期望利润 (3.3-2.5)(3+2) 4=16 销售收入销售收入: 2.9y1 +2.7y2 +3.1y3 +3.3y4 销售成本销售成本: 2.52+2.6x1 +2.5x2+2.7x3+2.8x4 2.9y1 +2.7y2 +3.1y3 +3.3y4 -2.6x1 -2.5x2-2.7x3 - 2.8x4+ d9- d9+ = 21目标达成函数目标达成函数:minf=P1 (d1+ + d2+ + d3+ + d4+ ) + P2 ( d5- + d6- + d7- + d8- ) +

27、 P3 d9- 运筹学运筹学 第四章第四章 目标规划目标规划Slide 25目前的有关目标规划的文献往往给人们这样一种印象，似乎模型中目标约束中的正负偏差变量要成对出现。而实际上决策者在解决实际多目标决策问题时，模型中目标约束中的正负偏差变量可能只出现一个(正偏变量或负偏差变量)或成对出现。目标约束中偏差变量的正确选择对于多目标决策问题的求解结果有很大的影响，决策者应该根据实际决策情况选择目标约束中的偏差变量。【例子例子】：某企业在计划期内生产两种产品。每生产一件产品1可以获利12元，每生产一件产品2可以获利14元，生产一件产品1所需设备A和设备B的台时分别为8台时和10台时，生产一件产品2所

28、需设备A和设备B的台时分别为10台时和6台时。设备A和设备B的有效台时分别为1500台时和1000台时，该企业决策者确定的目标优先级为：【补充补充】：目标约束中偏差变量的选择：目标约束中偏差变量的选择第一优先级：实现利润不低于第一优先级：实现利润不低于5000元；元；第二优先级：充分利用设备第二优先级：充分利用设备A和设备和设备B的有效台时的有效台时 。问问:如何安排产品如何安排产品1和产品和产品2的生产。的生产。建立目标规划模型时，企业决策者需要从两个方面进行考虑：首先要考虑现有的设备资源在短期内能否满足所提出的目标，短期内设备的生产能力难以改变，所以这属于短期规划决策问题。其次是如果现有设备的生产能力不能满足既定的目标，那么要实现上述目标，在长期内又应该如何决策，因为设备的生产能力在长期可以改变，所以这属于长期规划决策问题。 设产品设产品1的产量为的产量为X1，产品，产品2的产量为的产量为X2，短期规划决策目，短期规划决策目标规划