4目标规划.ppt

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

1、第4章 目标规划(Goal programming),第1节 目标规划的数学模型,第2节 目标规划的图解法,第3节 目标规划的单纯形法,目前，目标规划的方法和原理已经在经济管理、生产计划、经营管理、市场分析、财务管理等方面得到了广泛的应用。,目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。线性规划只研究在满足一定条件下，单一目标函数取得最优解，在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。,第1节 目标规划的数学模型,一、目

2、标规划概述,1)线性规划只讨论一个目标函数在约束条件下的极值问题；而目标规划是多个目标决策，可得到更切合实际的解。2)线性规划求最优解；目标规划求满意解。,（一）、目标规划与线性规划的比较,4)线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只求得满意解，就能满足需要（或更能满足需要）。,3)线性规划中的约束条件是同等重要的，是硬约束；而目标规划按优先权大小层次，有轻重缓急和主次之分，是软约束。,（二）、目标规划的基本概念,例1.某工厂生产I、II两种产品，已知有关数据如表。试求获利最大的生产方案。,实际上，工厂在作决策时，要考虑一系列因素：(1)产品I

3、的产量不大于产品II；(2)原材料超过时，采购成本增加；(3)设备台时尽量用完；(4)尽可能达到并超过计划利润指标56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,目标规划通过引入目标值g和偏差变量d，可以将目标函数转化为目标约束。目标值gk：是指预先给定的某个目标的一个期望值。实现值或决策值fk(xj)：是指当决策变量xj 选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异，记为d。单词deviation的首字母。正偏差变量，记为d+：表示实现值超过目标值的部分。负偏差变量，记为d-：表示实现值未

4、达到目标值的部分。,1、决策变量xj和正、负偏差变量d+，d-,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有 dd0，并规定d0，d0,偏差变量：实现值f(xj)超过目标值g的部分记d+实现值f(xj)不足目标值g的部分记d-d+0,d-0 且 f(xj)=g+d+-d-,若决策目标中规定 f(xj)g，则目标中d+=0；若决策目标中规定 f(xj)g，则目标中d-=0；若决策目标中规定 f(xj)=g，则目标中d+=d-=0，目标才算达到。,绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。,引

5、入目标值g、正偏差变量d+、负偏差变量d-后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。,2、目标约束和绝对约束,为了将不同级别的目标的重要性用数量表示，引进P1,P2,.，用它表示一级目标，二级目标，.的重要程度，规定P1P2 P3，称P1，P2，.,为级别系数。优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1，k=1,2,K。例如，四个决策目标用四个优先因子排序的准则函数：权系数k 区别具有同一个优先因子的两个目标的差别的情况。例如，目标i和目标j具有相同的优先因子Pk准则函数：,

6、3、优先因子(优先等级)Pk与优先权系数k,准则函数是一个使总偏差量为最小的目标函数，记为 min z=y(d,d-)。对应一个目标约束，有以下三种情况，但只能出现其中之一：.恰好达到规定的目标值，即f(xj)=g，正、负偏差变量d、d-都要尽可能小，则min z=y(dd-)。.不超过目标值，即f(xj)g，正偏差变量d尽可能小，则min z=y(d)。.超过目标值，即f(xj)g，负偏差变量d-尽可能小，则min z=y(d-)。,4、准则函数（即目标规划中的目标函数）,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,5、满

7、意解（具有层次意义的解）,例1.,(1)产品I的产量不大于产品II；(2)原材料超过时，采购成本增加；(3)设备台时尽量用完；(4)尽可能达到并超过计划利润指标56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,引入优先因子P1：x1-x20；P2：2x1+x211；P3：x1+2x2=10；P4：8x1+10 x256；,目标约束：x1-x2=0+d1+-d1-；2x1+x2=11+d2+-d2-；x1+2x2=10+d3+-d3-；8x1+10 x2=56+d4+-d4-；,例1.,(1)产品I的产量不大于产品II；(2)原材料超过时，

8、采购成本增加；(3)设备台时尽量用完；(4)尽可能达到并超过计划利润指标56元。,x1x2，即x1-x20；,2x1+x211；,x1+2x2=10；,8x1+10 x256；,目标函数min P1d1+；min P2d2+；min P3(d3+d3-)；min P4d4-；,min z=P1d1+P2d2+P3(d3+d3-)+P4d4-,目标约束：x1-x2=0+d1+-d1-；2x1+x2=11+d2+-d2-；x1+2x2=10+d3+-d3-；8x1+10 x2=56+d4+-d4-；,例a.某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润

9、最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的目标规划模型。,若在例a中提出下列要求：(1)完成或超额完成利润指标 5000元；(2)产品甲不超过 200件，产品乙不低于 250件；(3)现有钢材 3600吨必须用完。,若在例a中提出下列要求：(1)完成或超额完成利润指标 5000元；(2)产品甲不超过 200件，产品乙不低于 250件；(3)现有钢材 3600吨必须用完。试建立目标规划模型。分析：本例引入3个优先因子P1,P2,P3；,分析：题目有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即甲，乙，但两个具有相同的优先

10、因子P2，因此需要确定权系数。本题可用单件利润比作为权系数即 70:120，化简为7:12。,第三目标：,目标规划模型为：,某厂生产、两种产品，有关数据如表所示。试求获利最大的生产方案？,在此基础上考虑：(1)产品的产量不低于产品的产量；(2)充分利用设备有效台时，不加班；(3)利润不小于 56 元。,解:分析 第一目标：min z1=,第二目标：min z2=,例2：,第三目标：min z3=,x1x2，即x1-x20；,x1+2x2=10；,8x1+10 x256；,规划模型：,（一）、模型的一般形式,二、目标规划的数学模型,其中，gk为目标约束的目标值；bi为绝对约束的资源值。,约束,目

11、标函数,目标约束,资源约束,（二）、建模的步骤,1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；,4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。,3、给各目标赋予相应的优先因子 Pk(k=1,2,K)。,2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。,5、根据决策者的要求，按下列情况之一构造一个由 优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即准则函数。,.恰好达到目标值，取。,.允许超过目标值，取。,.不允许超过目标值，取。,（三）、小结

12、,建立目标规划的数学模型时，需要确定目标值gk、优先因子Pk、权系数j等，它都具有一定的主观性和模糊性，可以用专家评定法给以量化。,图解法同样适用两个变量的目标规划问题。,图解法解题步骤如下：(1)确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；(2)在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；(3)求满足最高优先等级目标的解；(4)转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；(5)重复(4)，直到所有优先等级的目标都已审查完毕为止；(6)确定最优解和满意解。,第2节

13、 目标规划的图解法,G,D,结论：有无穷多最优解，G(2,4)D(10/3,10/3),x2,x1,用图解法求解例2的目标规划,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 线段上的所有点均是该问题的解（无穷多最优解）。,例b.用图解法求解目标规划问题,在例2的图解法求解时，把绝对约束作最高级考虑，在此例中能依先后次序都能满足d1+=0、d2+d2-=0、d3-=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，仅仅得到满意解。,例3.,该厂目标为：P1：充分利用装配线每周

14、开动超过40小时；P2：加班时间每周尽量不超过10小时；P3：彩色、黑白电视销量尽量超过24、30台。同优先因子下两个目标的权系数可用单件利润比作为权系数即 80:40，化简为2:1。设x1，x2分别表示彩色和黑白电视机的产量。,以上问题的目标规划模型,10,20,30,40,50,10,20,30,40,50,x2,x1,(1),(2),(3),(4),E,F,B,A,ABEF区域中无法满足d4-=0，只能取一点使d4-尽可能小，即E点。E点为满意解，其坐标(24,26)。,例c、已知一个生产计划的线性规划模型为,其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标：1、要求总利

15、润必须超过 2500 元；2、由于甲资源供应比较紧张，不要超过现有量140；3、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件。试建立目标规划模型，并用图解法求解。,解：以产品 A、B 的单件利润比 2.5：1 为权系数，模型如下：,0,x2,0,x1,14012010080604020,20 40 60 80 100,A,B,C,D,结论：C(60,58.3)为所求的满意解。,作图：,检验：将上述结果带入模型，因 0；0；0，存在；0，存在。所以，有：min z=,将 x160，x2 58.3 带入约束条件，得,30601258.32499.62500；260+

16、58.3=178.3 140；16060158.358.3 100,由上可知：若A、B的计划产量为60件和58.3件时，所需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须采取措施降低A、B产品对甲资源的消耗量，由原来的100降至78.5（140178.30.785），才能使生产方案(60,58.3)成为可行方案。,第3节 目标规划的单纯形法,（一）、一般形式：,（二）、单纯形法的计算准则,1)min z，所有cj-zj0为最优准则。2)检验是否为满意解。非基变量的检验数含Pk，即cj-zj=kjPk，(k=1,2,k；j=1,2,n)首先检查kj 是否全部为零？如果kj

17、 全部为零，则表示目标均已全部达到，获得满意解，停止计算转到第(5)步；否则转入(2)。,(1)建立初始单纯形表。一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部。,（三）、单纯形法的计算步骤,在Pk行，从负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。,(2)检验是否为满意解。首先检查检验数kj(k=1,2,k)是否全部为

18、零？如果全部为零，则表示目标均已全部达到，获得满意解，停止计算转到第(5)步；某一个kj 0，并且Pk这一行的检验数kj0(j=1,2,n+2m)，应继续改进，转到第(3)步。,(3)确定出基变量 其方法同线性规划，即依据最小比值法则故确定xr为出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr。,(4)旋转变换（变量迭代）。以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第(2)步。,(5)对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第(2)步。,例4：用单纯形法求解例2

19、的目标规划问题,例4：用单纯形法求解例2的目标规划问题解：将例2化为标准型,=min,10/2,56/10,11/1=5，故 为换出变量。,表4-1,=min10/3,10,6/3,12/3=2,故 为换出变量。,表4-2,最优解为x12，x2 4。图4-1的G(2,4)点，但非基变量 的检验数为零，故此题有无穷多最优解。=min4,24,6=4,故 为换出变量。,表4-3,G,D,结论：有无穷多最优解，G(2,4)D(10/3,10/3),x2,x1,最优解为x110/3,，x2=10/3。图4-1的D(10/3,10/3)点。,表4-4,例d、用单纯形法求解下列目标规划问题,=min250

20、0/30,140/2,60/1=60,故 为换出变量。,=min700/30,20/2,=10,故 为换出变量。,=min400/15,=10,故 为换出变量。,=min,350/6,1250/6,100/1=75,故 为换出变量。,表中3115/30，说明P3 优先等级目标没有实现，但已无法改进，得到满意解 x1 60，x2 175/3，115/3，125/3。,结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。125/3，表明产品比最高限额少125/3件，满足要求。115/3 表明甲资源超过库存115/3公斤，该目标没有达到。从表中还可以看到

21、，P3 的检验数还有负数，但其高等级的检验数却是正数，要保证 P1目标实现，P3等级目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现2500元的利润目标。可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3等级目标的指标值，增加甲资源115/3公斤。若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。,1、某厂生产A、B、C三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为200小时；三种产品销售后，每台可获利分别为500、650和800元；三种产品每月销售量预计为12、10

22、和6台。该厂经营目标如下：(1)利润指标为每月16000元，争取超额完成；(2)充分利用现有生产能力；(3)可以适当加班，但加班时间不得超过24小时；(4)产量以预计销售量为准。试建立目标规划模型。,课堂作业：,答案：,2、用图解法求解下列目标规划问题：,满意解为由x1=（3，3）,x2=（3.5，1.5）所连线段。,3、用图解法解下列目标规划模型。,x1=400,x2=0,Z=80p3,0,100 200 300 400 500,100 200 300 400,x2,x1,4,4、用单纯形法求解下列目标规划问题：,x=（10，20，10）,5、用目标规划的单纯形方法解以下目标规划模型。,5、

23、x1=12,x2=10,=14,Z=14p4,习 题1.已知条件如表所示,如果工厂经营目标的期望值和优先等级如下：P1:每周总利润不得低于10000元；P2:因合同要求，A型机每周至少生产10台，B型机每周至少 生产15台；P3:希望工序的每周生产时间正好为150小时，工序的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。,2.在上题中，如果工序在加班时间内生产出来的产品，每台A型机减少利润10元，每台B型机减少利润25元，并且工序的加班时间每周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。,设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4分

24、别为在正常时间和加班时间生产B型机台数，目标规划数学模型为：,3.某纺织厂生产两种布料，一种用来做服装，另一种用来做窗帘。该厂实行两班生产，每周生产时间定为80小时。这两种布料每小时都生产1000米。假定每周窗帘布可销售70000米，每米的利润为2.5元；衣料布可销售45000米，每米的利润为1.5元。该厂在制定生产计划时有以下各级目标：p1：每周必须用足80小时的生产时间；p2：每周加班时数不超过10小时；p3：每周销售窗帘布70000米，衣料布45000米；p4：加班时间尽可能减少。试建立这个问题的目标规划模型。,设x1,x2分别为每周生产窗帘布和医疗布的小时数，目标规划数学模型为：,例：某企业计划用1000万元为下属5家工厂进行技术改造，各工厂的单位投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素。技术改造完成后预测单位投资收益率(单位投资获得利润/单位投资额)100%)。(熊伟书),某企业制定的目标：(1)(2)(3)(4),