《目标规划》课件.ppt

《《目标规划》课件.ppt》由会员分享，可在线阅读，更多相关《《目标规划》课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、第4章 目标规划(Goal programming),4.1 目标规划模型,4.2 目标规划的求解算法,4.3 目标规划模型的实例,4.1 目标规划模型(The Model for Goal programming),目标规划与线性规划的比较,4.1.2 目标规划的基本概念,4.1.3 目标规划的一般模型,目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。它与线性规划的区别在于：,2、线性规划求最优解；目标规划是找到一个满意解。,1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。,4.1.1

2、目标规划与线性规划的比较,4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。,3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。,目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。,例4.1 某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。,4.1.2 目标规划的基本概念,设

3、：甲产品 x1，乙产品 x2,一般有：,maxZ=70 x1+120 x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,同时：,max Z1=70 x1+120 x2 min Z2=x1 max Z3=x2 9 x1+4 x2 3600 4 x1+5 x2 2000 3 x1+10 x2 3000 x1，x2 0,显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。,目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj 选定以后，目标

4、函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为 d。正偏差变量：表示实现值超过目标值的部分，记为 d。负偏差变量：表示实现值未达到目标值的部分，记为 d。,1、目标值和偏差变量,当完成或超额完成规定的指标则表示：d0,d0 当未完成规定的指标则表示：d0,d0 当恰好完成指标时则表示：d0,d0 d d 0 成立。,引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有 d d 0,并规定d0,

5、d0,2、目标约束和绝对约束,绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。,例如在例4.1中，规定Z1 的目标值为 50000,正、负偏差为d、d,则目标函数可以转换为目标约束，即70 x1+120 x2 d 1-d1+50000，同样，若规定 Z2200，Z3250 则有,若规定3600的钢材必须用完，原式 9 x1+4 x2 3600则变为,达成函数是一个使总偏差量为最小的目标函数，记为 min f（d,d）。一般说来，有以下三种情况，但只能出现其中之一：.要求恰好达到规定的目标值，即正、负偏差变量要

6、尽可能小，则 min f（d+d）。.要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则min f（d）。.要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则min f（d）。对于由绝对约束转化而来的目标函数，也照上述处理即可。,3、达成函数（即目标规划中的目标函数）,优先因子Pk 是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1PK，k=1.2K。权系数k 区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,4、优先

7、因子（优先等级）与优先权系数,5、满意解（具有层次意义的解）,例4.2 若在例4.1中提出下列要求：(1)完成或超额完成利润指标 50000元；(2)产品甲不超过 200件，产品乙不低于 250件；(3)现有钢材 3600吨尽可能用完。试建立目标规划模型。,分析：题目有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即对甲有，对乙有，但两个具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即 70:120，化简为7:12。因此，第二目标可以写成,第三目标：,综上，该问题的目标规划模型为：,例：某厂生产、两种产品，有关数据如表所示。试求获利最大的生产方案？,在此基础

8、上考虑：1、产品的产量不低于产品的产量；2、充分利用设备有效台时，不加班；3、利润不小于 56 元。,解:第一目标：即产品的产量不大于的产量。,第二目标：,第三目标：,规划模型：,（一）模型的一般形式,4.1.3 目标规划的一般模型,4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。,（二）建模的步骤,1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,3、给各目标赋予相应的优先因子 Pk（k=1.2K）。,2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。,5、根据决策

9、者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。,.恰好达到目标值，取。,.允许超过目标值，取。,.不允许超过目标值，取。,4.2 目标规划的求解方法(Methods for Solving Goal programming),4.2.1 求解目标规划的图解法,4.2.2 求解目标规划的单纯形算法,*4.2.3 求解目标规划的序贯式算法,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤如下：1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和

10、绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,4.2.1 求解目标规划的图解法,3、求满足最高优先等级目标的解；4、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5、重复4，直到所有优先等级的目标都已审查完毕为止；6、确定最优解和满意解。,例4.3 用图解法求解目标规划问题,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,A,x2,x1,B,C,B(0.6250,4.6875)、C(0,5.2083)，B、C 线段上的所有点均是该问题的解（无穷多最优解）。,课堂

11、练习：已知一个生产计划的线性规划模型为,其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标：1、要求总利润必须超过 2500 元；2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件；3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。,解：以产品 A、B 的单件利润比 2.5:1 为权系数，模型如下：,0,x2,0,x1,14012010080604020,20 40 60 80 100,A,B,C,D,结论：C(60,58.3)为所求的满意解。,作图：,4.2.2 求解目标规划的单纯形算法,（一）一般形式：,1、建

12、立初始单纯形表 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表下半部的K行中，置 k=1。,2、检验是否为满意解,（二）单纯形法的计算步骤,若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,3、确定进基变量在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比

13、较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量，转第4步。否则，转第6步。,4、确定出基变量其方法同线性规划，即依据最小比值法则故确定xr为出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr。,5、旋转变换（变量迭代）以ers为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2步。,6、对求得的解进行分析当k=K时，计算结束，停止运算；表中的解即为最终解。若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。否则置k=k+1，返回第2步。

14、,例4.4 用单纯形法求解下列目标规划问题,=min2500/30,140/2,60/1=60,故 为换出变量。,=min700/30,20/2,=10,故 为换出变量。,=min400/15,=10,故 为换出变量。,=min,350/6,1250/6,100/1=75,故 为换出变量。,表中P3行仍有负数，说明P3 优先等级目标没有实现，但已无法改进，得到满意解 x1 60，x2 175/3，115/3，125/3。,课堂练习：用单纯形法求解下列目标规划问题,=min,10/2,56/10,11/1=5,故 为换出变量。,=min10/3,10,6/3,12/3=2,故 为换出变量。,最优

15、解为x12，x2 4。但非基变量 的检验数为零，故此题有无穷多最优解。=min4,24,6=4,故 为换出变量。,最优解为x110/3,，x2=10/3。,*4.2.3 求解目标规划的序贯式算法,序贯式算法其核心是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。对于l=1,2,L，求解单目标问题,（4-1）,（4-2）,（4-3）,其最优目标值为，当时 l=1 时约束(4-3)为空约束当时 l=L 时，所对应的解为目标规划的最优解,例4.5 用序贯式算法求解例4.4。解：例4.4一共有三级目标，每个单目标问题的目标函数分别为,（1）求第一级目标 min=dmi

16、nus1;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;end,计算结果如下：Global optimal solution found.Objective value:0.000000 Total solver iterations:0,目标函数的最优值为0，即第一级偏差为0。（2）求第二级目标，列出LINGO程序如下。,min=2.5*dplus3+dplus4;30*x1+12*x2+dminus1-dplus1=2500;2*x1

17、+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0;end计算结果如下：Global optimal solution found.Objective value:0.000000 Total solver iterations:3 Variable Value Reduced Cost DPLUS3 0.000000 2.500000,目标函数的最优值仍为0，即第二级的偏差仍为0。（3）求第三级目标。列出LINGO程序如下。,min=dplus2;30*x1+12*x2+dminus1-dpl

18、us1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0;2.5*dplus3+dplus4=0;end,计算结果如下：,Global optimal solution found.Objective value:38.33333 Total solver iterations:1 Variable Value Reduced Cost DPLUS2 38.33333 0.000000 X1 60.00000 0.000000 X2 58.33333 0.000000 DMI

19、NUS1 0.000000 0.000000 DPLUS1 0.000000 0.8333333E-01 DMINUS2 0.000000 1.000000 DMINUS3 0.000000 0.5000000 DPLUS3 0.000000 0.000000 DMINUS4 41.66667 0.000000 DPLUS4 0.000000 0.2000000,计算结果与用单纯形法求解结果相同,上述过程虽然给出了目标规划问题的最优解，但需要连续编几个程序，使用时很不方便。下面，我们给出用LINGO软件求解目标规划的通用程序，在程序中用到数据段未知数据的编程方法。在以下的通用程序中，II为目标

20、规划的优先级的个数，JJ为决策变量的个数，KK为硬约束方程的个数（在通用程序中要求将所有的硬约束均转化为等式约束），LL为软约束方程的个数。在通用程序中，Level说明的是目标规划的优先级，有三个变量P,Z和Goal，其中P表示优先级,Goal表示相应优先级时的最优目标值程序的12行和13行表示将根据计算过程输入它们相应的值 求解目标规划的通用LINGO程序如下。,1MODEL:2SETS:3 LEVEL/1.II/:P,Z,GOAL;!目标个数,P优先因子,Z各级目标值,GOAL目标;4 VARIABLE/1.JJ/:X;!决策变量;5 H_CON_NUM/1.KK/:B;!硬约束方程的个数

21、，B为硬约束的右端项;6 S_CON_NUM/1.LL/:G,DPLUS,DMINUS;!软约束个数,G为软约束的右端项,DPLUS和DMINUS为d+和d-;7 H_CONS(H_CON_NUM,VARIABLE):A;!硬约束的系数矩阵;8 S_CONS(S_CON_NUM,VARIABLE):C;!软约束的系数矩阵;9 OBJ(LEVEL,S_CON_NUM):WPLUS,WMINUS;!目标函数中d+和d-的系数矩阵;10ENDSETS,11 DATA:12P=?,?,?;!共II个”？”;!优先因子。在具体计算是，若计算第一级目标，则P为1,0,0,0，即输入的第一个P值为1，其余的

22、均为0，计算二级目标P则为0,1,0,0，依此类推;13GOAL=?,?.,?,0;!共II-1个”?”;!人为输入的目标值,计算一级目标时输入II-1个较大的数,计算二级目标时,输入已计算的一级目标值、II-2个较大数,计算其余目标时依此类推;14 B=;!在此列出硬约束右端项;15 G=;!在此列出软约束的右端项;16 A=;!在此列出硬约束的系数矩阵;17 C=;!在此列出软约束的系数矩阵;18 WPLUS=;!目标函数中各优先级中d+的系数;19 WMINUS=;!目标函数中各优先级中d-的系数;20 ENDDATA,22 MIN=SUM(LEVEL:P*Z);!目标函数;23!各级目

23、标;24FOR(LEVEL(I):Z(I)=SUM(S_CON_NUM(J):WPLUS(I,J)*DPLUS(J)+SUM(S_CON_NUM(J):WMINUS(I,J)*DMINUS(J);25!各个硬约束方程;26FOR(H_CON_NUM(I):SUM(VARIABLE(J):A(I,J)*X(J)=B(I);27!软约束方程;28FOR(S_CON_NUM(I):SUM(VARIABLE(J):C(I,J)*X(J)+DMINUS(I)-DPLUS(I)=G(I);29!Z(I)的变化范围;30 FOR(LEVEL(I)|I#LT#SIZE(LEVEL):BND(0,Z(I),GO

24、AL(I);31END,例1 某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；每月销售量预计为12、10和6台。该厂经营目标如下：1、利润指标为每月16000元，争取超额完成；2、充分利用现有生产能力；3、可以适当加班，但加班时间不得超过24小时；4、产量以预计销售量为准。试建立目标规划模型。,4.3 目标规划模型的实例,例2 已知条件如表所示,如果工厂经营目标的期望值和优先等级如下：p1:每周总利润不得低于10000元；p2:因合同要求，A型机每周

25、至少生产10台，B型机每周至少 生产15台；p3:希望工序的每周生产时间正好为150小时，工序的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。,例3 在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润20元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。,解：设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4 分别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：,例4.7 已知三个工厂生产的产品供应给四个用户，各工厂生产量、用户需求量及从各工厂到用户的单位产品的运输费用如

26、表4-7所示。,由于总生产量小于总需求量，上级部门经研究后，制定了调配方案的8项指标，并规定了重要性的次序。,第一目标：用户4为重要部门，需求量必须全部满足；第二目标：供应用户1的产品中，工厂3的产品不少于100个单位；第三目标：每个用户的满足率不低于80；第四目标：应尽量满足各用户的需求；第五目标：新方案的总运费不超过原运输问题的调度方案的10；第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务；第七目标：用户1和用户3的满足率应尽量保持平衡；第八目标：力求减少总运费。请列出相应的目标规划模型。,解：求解原运输问题。设xij 为工厂i调配给用户j的运量，由于总生产量小于总需求量，所

27、以原运输问题的数学模型如下：,求解此运输问题，得到总运费是2950元，运输方案如表4-8所示。,从表4-8可以看出，上述方案中，第一个目标就不满足，用户4的需求量得不到满足。下面按照目标的重要性的等级列出目标规划的约束和目标函数。,(1)供应约束应严格满足，即,(2)供应用户1的产品中，工厂3的产品不少于100个单位，即,(3)需求约束。各用户的满足率不低于80，即,(4)应尽量满足各用户的需求，即,(5)新方案的总运费不超过原方案的10（原运输方案的运费为2950元），即,(6)工厂2到用户4的路线应尽量避免运输任务，即,(7)用户1和用户3的满足率应尽量保持平衡，即,(8)力求总运费最少，即,目标函数为,计算此问题的LINGO程序及求解过程请参照教材。经以上8次计算，得到最终的计算结果如下表所示。计算得到总运费为3360元，比原运费高410元，超过原方案10的上限115元。,