目标规划培训课件2

《目标规划培训课件2》由会员分享，可在线阅读，更多相关《目标规划培训课件2（41页珍藏版）》请在金锄头文库上搜索。

1、目 标 规 划 (Goal programming),目标规划的数学模型,目标规划的图解法,目标规划的单纯形法,目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。,例一、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。,一、目标规划模型,设：甲产品 x1 ，乙产品 x2,一般有：,maxZ=70 x1 + 120 x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x

2、2 3000 x1 ， x2 0,同时：,maxZ1=70 x1 + 120x2 minZ2= x1 maxZ3= x2 9 x1 +4 x2 3600 4 x1 +5 x2 2000 3 x1 +10 x2 3000 x1 ， x2 0,显然，这是一个多目标规划问题。,如何将多目标转化为单目标 如何表示不同目标的主次 如何求解,若在上例中提出下列要求： 1、完成或超额完成利润指标 50000元； 2、产品甲不超过 200件，产品乙不低于 250件； 3、现有钢材 3600吨必须用完。,2、产品甲不超过 200件，产品乙不低于 250件；,3、3600吨钢材必须用完,目标值：预先给定的某个目标

3、的一个期望值e。 实现值或决策值：当决策变量xj 被求出以后，目标函数的对应值。 偏差变量（事先无法确定的未知数）：实现值和目标值之间的差异,记为 d。 正偏差变量：实现值超过目标值的部分，记为d。 负偏差变量：实现值未达到目标值的部分，记为 d。,1、目标值和偏差变量,通过引入目标值和偏差变量，使上述三个要求变成相应的约束条件，即目标约束。 目标约束是目标规划中特有的，是软约束。,当完成或超额完成规定的指标则表示：d0, d0 当未完成规定的指标则表示： d0, d0 当恰好完成指标时则表示： d0, d0 d d 0 成立。,引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，即目标

4、约束。,在一次决策中，实现值不可能既超过目标值又未达到目标值，故有 d d 0,并规定d0, d0,2、目标约束和绝对约束,绝对约束：必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，有一个不满足就无可行解。所以，绝对约束是硬约束。,目标约束 （软约束）,绝对约束 （硬约束）,目标函数是一个使总偏差量为最小的目标函数，记为 minZ = f（d、d）。 一般说来，有以下三种情况，但只能出现其中之一：,3、目标函数, 要求恰好达到规定的目标值，即正、负偏差变量 要尽可能小，则minZ = f（d d）。, 要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则m

5、inZ = f（d）。, 要求不低于目标值，即超过量不限，也就是负偏差变量尽可能小，则minZ = f（d）。,对于由绝对约束转化而来的目标函数，也照上述处理即可。,优先因子Pk 是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1PK ，k=1.2K。 权系数k 区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。,对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,4、优先因子（优先等级）与优先权系数,5、满意解（具有层次意义的解）,对于上例中的目标： 1、完成或超额完成利润指标 50000元； 2、产品甲不超

6、过 200件，产品乙不低于 250件； 3、现有钢材 3600吨必须用完。 若实现值没有达到目标，则存在偏差，希望按目标先后尽可能使偏差最小。,偏差,目标2有两个要求，且具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即 70 :120，化简为7:12。,目标规划模型为：,例：某厂生产、两种产品，有关数据如表所示。试求获利最大的生产方案。,要求考虑： 1、产品的产量不低于产品的产量； 2、充分利用设备有效台时，不加班； 3、利润不小于 56 元。,设：I、II产品产量 分别为x1 ，x2,目标规划模型：,目标规划模型的一般形式,目标规划建模步骤,2、根据要研究的问题所提出的

7、各目标与条件，确定目标值，列出目标约束与绝对约束；,5、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数 。,4、给各目标赋予相应的优先因子 Pk（k=1.2K）。,3、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。,1、假设决策变量；,6、根据决策者的要求，按下列情况之一构造一个由 优先因子和权系数相对应的偏差变量组成的、要求实现极小化的目标函数，即达成函数。,.恰好达到目标值，取 。,.不希望低于目标值，取 。,.不希望超过目标值，取 。,图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目

8、了然。同时，也有助于理解一般目标规划的求解原理和过程。,图解法解题步骤如下： 1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来； 2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；,目标规划的图解法,3、求满足最高优先等级目标的解； 4、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解； 5、重复4，直到所有优先等级的目标都已审查完毕为止； 6、确定最优解或满意解。,例：用图解法求解目标规划问题,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,x2,x1,B (

9、0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上的所有点均是该问题的解（无穷多最优解）。,练习：用图解法求解下列目标规划问题,结论：有无穷多最优解。C（2，4）D（10/3，10/3）,例：已知一个生产计划的线性规划模型为,其中目标函数为总利润，x1,x2 为产品A、B产量。现有下列目标： 1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。 试建立目标规划模型，并用单纯形法求解。,P1,P3,P2,目标规划的单纯形法,= min2500/

10、30,140/2,60/1=60 ,故 为换出变量。,目标函数系数和检验数竖着排列, = 2.5P2-（0*P1+0*0-1*0+0*0）= 2.5P2 , 将2.5填P2行。,= min700/30,20/2, =10 ,故 为换出变量。, = 2.5P2-（30P1+2*0-1*0+0*0）= 2.5P2-30P1,= min400/15, =10 ,故 为换出变量。, = 0-（-15P1+2.5P2/2+1/2*0+0*0）= 15P1-2.5P2/2,= min,350/6,1250/6,100/1=75 ,故 为换出变量。,表中 P3 行有负检验数，说明P3 级目标没有实现，但已无

11、法改进，得到满意解 x1 60， x2 175/3， 115/3， 125/3。,结果分析：计算结果表明，工厂应生产A产品60件，B产品175/3件，2500元的利润目标刚好达到。 125/3，表明产品B比最高限额少125/3件，满足要求。 115/3 表明甲资源超过库存115/3公斤，该目标没有达到。 即甲资源多消耗115/3公斤，刚好实现2500元的利润目标。而按现有消耗水平和资源库存量，无法实现利润目标。 可考虑如下措施：降低A、B产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变P3级目标值，增加甲资源115/3公斤。 若很难实现上述措施，则需改变现有目标的优先等级，以取得可行

12、的满意解果。,1、要求总利润必须超过 2500 元； 2、考虑产品受市场影响，为避免积压，A、B的生产量不超过 60 件和 100 件； 3、由于甲资源供应比较紧张，不要超过现有量140。,1、建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部 。,2、检验是否为满意解。判别准则如下： .首先检查b列中的k (k=1.2K)是否全部为零？如果全部为零，则表示目标均已全部达到，获得满意解，停止计算转到第6步；否则转入。,（二）、单纯形法的计算步骤,.如果某一个k 0。说明第k个优先等级的目标

13、尚未达到,必须检查Pk行的检验数kj(j=1.2n+2m).若Pk这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改进，转到第3步；若Pk这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第6步。,3、确定进基变量。 在Pk行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量xs就是进基变量。若Pk行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的xs为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。,4、确定出基变量 其方

14、法同线性规划，即依据最小比值法则 故确定xr为出基变量，ers为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为xr 。,5、旋转变换（变量迭代）。 以主元素进行变换，得到新的单纯形表，获得一组新解，返回到第2步。,6、对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第1步。,练习：用单纯形法求解下列目标规划问题,= min,10/2,56/10,11/1= 5,故 为换出变量。,= min4/3,10,6/3,12/3= 2,故 为换出变量。,最优解为x12， x2 4。 但非基变量 的检验数为零，故此题

15、有无穷多最优解。 = min4 , 24 , 6= 4,故 为换出变量。,最优解为x110/3,，x2 =10/3。,例 某纺织厂生产尼龙布和棉布，平均生产能力是每小时1千米。工厂开工能力为每周80小时。根据市场预测，每周最大销售量尼龙布70千米，棉布45千米。尼龙布单位利润为每米2.5元，棉布每米1.5元。厂家确定四级管理目标： p1：保证正常生产，避免开工不足时间； p2：限制加班时间，不超过10小时； p3：尽量达到最大销售量，尼龙布70千米，棉布45千米。 p4：尽可能减少加班时间。 试建立这个问题的目标规划模型。,设x1, x2分别为尼龙布和棉布周生产量，,目标规划数学模型为：,p1：保证正常生产，避免开工不足时间； p2：限制加班时间，不超过10小时； p3：尽量达到最大销售量 p4：尽可能减少加班时间。,p1 、p4 p3 p3 p2,