建模目标规划

1、目目 标标 规规 划划(Goal programming)2.目标规划的图解法目标规划的图解法3.目标规划的单纯形法目标规划的单纯形法1.目标规划概述目标规划概述5. Lingo求解求解4. 应用问题举例应用问题举例11运筹学运筹学 第四章第四章 目标规划目标规划 引引例例1 1 某工厂生产某工厂生产，两种产品，已知有关两种产品，已知有关数据见下表。试求获利最大的生产方案。数据见下表。试求获利最大的生产方案。 解：这是求获利最大的单目标的规划问题，用解：这是求获利最大的单目标的规划问题，用x1，x2分别表示分别表示，产品的产量，其线性规划模型产品的产量，其线性规划模型表述为：表述为：0,102

2、112108max21212121xxxxxxxxz满足约束条件：目标函数：21运筹学运筹学 第四章第四章 目标规划目标规划 用图解法求得最优决策方案为：用图解法求得最优决策方案为：x1*=4, x2*=3, z*=62(元元)。(4,3)0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：31运筹学运筹学 第四章第四章 目标规划目标规划 ( (IVIV) )应尽可能达到并超过计划利润指标：应尽可能达到并超过计划利润指标：5656元。元。这样的产品决策问题便构成了一个多目标决策问题，目标规划方法正是解这类决策问题的方法之一。实际上，工厂在作决策时，需要考虑包括

3、市场因素在内等一系列实际上，工厂在作决策时，需要考虑包括市场因素在内等一系列条件。例如条件。例如:(I)根据市场信息，产品根据市场信息，产品的销售量有下降的趋势，因而的销售量有下降的趋势，因而希望产品希望产品的产量的产量不应大于不应大于产品产品。(II)当超过计划供应原材料时，需用高价采购，会使成本当超过计划供应原材料时，需用高价采购，会使成本大幅度增加。大幅度增加。(III)应尽可能充分利用设备台时，但不希望加班。应尽可能充分利用设备台时，但不希望加班。41运筹学运筹学 第四章第四章 目标规划目标规划 目标规划是在线性规划的基础上，为适应经济管理目标规划是在线性规划的基础上，为适应经济管理中

4、多目标决策的需要而逐步发展起来的一个分支。中多目标决策的需要而逐步发展起来的一个分支。 1 1、线性规划只讨论一个线性目标函数在一组线性约、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。求得更切合实际的解。1 目标规划概述目标规划概述（一）目标规划与线性规划的比较（一）目标规划与线性规划的比较线性规划建模的局限性：线性规划建模的局限性： 线性规划要求所有求解的问题必须满足全部的约束，而实线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；际问题中并

5、非所有约束都需要严格的满足；51运筹学运筹学 第四章第四章 目标规划目标规划 2 2、线性规划求最优解；目标规划是找到一个、线性规划求最优解；目标规划是找到一个满意解满意解。 线性规划只能处理单目标的优化问题，而对一些次目标只线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；相互转化的，处理时不一定要严格区分； 线性规划在处理问题时，将各个约束线性规划在处理问题时，将各个约束(也可看作目标也可看作目标)的地的地位看成同等重要，而在实际问题中，各个目标的重要

6、性即位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别有层次上的差别，也有在同一层次上不同权重的差别61运筹学运筹学 第四章第四章 目标规划目标规划 4 4、线性规划的最优解是绝对意义下的最优，但需花、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。要求得满意解，就能满足需要（或更能满足需要）。 3 3、线性规划中的约束条件是同等重要的，是硬约束；、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急

7、和主次之分，即有优先权。而目标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。分析、财务管理等方面得到了广泛的应用。71运筹学运筹学 第四章第四章 目标规划目标规划 目标值和偏差变量目标值和偏差变量 目标约束和绝对约束目标约束和绝对约束 达成函数（即目标规划中的目标函数）达成函数（即目标规划中的目标函数） 优先因子（优先等级）与优先权系数优先因子（优先等级）与优先权系数 满意解（具有层次意义的解）满意解（具有层次意义的解）（二）目标规划的基本概念（二）目标规划的基本概念81

8、运筹学运筹学 第四章第四章 目标规划目标规划 目标规划通过引入目标值和偏差变量，可以将目标目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。函数转化为目标约束。 目标值：是指预先给定的某个目标的一个期望值。目标值：是指预先给定的某个目标的一个期望值。 实现值或决策值：是指当决策变量实现值或决策值：是指当决策变量xj 选定以后，目选定以后，目标函数的对应值。标函数的对应值。 偏差变量（事先无法确定的未知数）：是指实现值偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异和目标值之间的差异, ,记为记为 d d 。 正偏差变量：表示实现值超过目标值的部分，记为正偏差变量：表

9、示实现值超过目标值的部分，记为 d d。 负偏差变量：表示实现值未达到目标值的部分，记负偏差变量：表示实现值未达到目标值的部分，记为为 d d。1 1、目标值和偏差变量、目标值和偏差变量91运筹学运筹学 第四章第四章 目标规划目标规划 当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：d d0, d d0 当未完成规定的指标则表示：当未完成规定的指标则表示： d d0, d d0 当恰好完成指标时则表示：当恰好完成指标时则表示： d d0, d d0 d d d d 0 0 成立。成立。 引入了目标值和正、负偏差变量后，就对某一问引入了目标值和正、负偏差变量后，就对某一问题有

10、了新的限制，既目标约束。题有了新的限制，既目标约束。 目标约束即可对原目标函数起作用，也可对原约束目标约束即可对原目标函数起作用，也可对原约束起作用。起作用。目标约束是目标规划中特有的，是软约束。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达在一次决策中，实现值不可能既超过目标值又未达到目标值，故有到目标值，故有 d d d d 0,0,并规定并规定d d0, d d02 2、目标约束和绝对约束、目标约束和绝对约束101运筹学运筹学 第四章第四章 目标规划目标规划 绝对约束（系统约束）是指绝对约束（系统约束）是指必须严格满足的等式或不等式必须严格满足的等式或

11、不等式约束。如线性规划中的所有约约束。如线性规划中的所有约束条件都是绝对约束，否则无束条件都是绝对约束，否则无可行解。所以，绝对约束是硬可行解。所以，绝对约束是硬约束。约束。线性规划问题的目标函数，在给定目标值和加入正、线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束，例如：在要将绝对约束变换为目标约束，例如：在引例引例1中，目中，目标值目标函数可以转换为标值目标函数可以转换为目标约束目标约束，既，既0,102112108max21212121xxxxxxxxz满足约束条件：目标

12、函数：目标函数目标函数 z=8x1+10 x2变换为目标约束变换为目标约束 8x1+10 x2+d1d1+=56约束条件约束条件 2x1+x211变换为目标约束变换为目标约束 2x1+x2+d 2 d2+=11111运筹学运筹学 第四章第四章 目标规划目标规划 达成函数是一个使总偏差量为最小的目标函数，记为达成函数是一个使总偏差量为最小的目标函数，记为 minZ = f（d、d）。）。 一般说来，有以下三种情况，但只能出现其中之一：一般说来，有以下三种情况，但只能出现其中之一： .要求恰好达到规定的目标值，即正、负偏差变量要要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则尽可能小，则m

13、inZ = f（d d）。）。 .要求不超过目标值，即允许达不到目标值，也就是要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则正偏差变量尽可能小，则minZ = f（d）。）。 .要求超过目标值，即超过量不限，但不低于目标值，要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则也就是负偏差变量尽可能小，则minZ = f（d）。）。 对于由绝对约束转化而来的目标函数，也照上述处理即对于由绝对约束转化而来的目标函数，也照上述处理即可。可。3 3、达成函数（即目标规划中的目标函数）、达成函数（即目标规划中的目标函数）121运筹学运筹学 第四章第四章 目标规划

14、目标规划 优先因子优先因子Pk 是将决策目标按其重要程度排序并表是将决策目标按其重要程度排序并表示出来。示出来。P1P2PkPk+1PK ，k=1.2K。 权系数权系数k 区别具有相同优先因子的两个目标的差区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。别，决策者可视具体情况而定。 对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。有些可能就不能实现。4 4、优先因子（优先等级）与优先权系数、优先因子（优先等级）与优先权系数 5

15、 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）131运筹学运筹学 第四章第四章 目标规划目标规划 某厂生产某厂生产、两两种产品，有关数据如表种产品，有关数据如表所示。所示。拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 经研究提出下列要求：经研究提出下列要求： 1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量； 2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班； 3、利润不小于、利润不小于 56 元。元。例例2：（三）目标规划的数学模型（三）目标规划的数学模型解：设解：设x1， x2分别表示分别表示产品产品和和产品产

16、品的产量。的产量。 di+, di- 分别为第分别为第i个目标的正、负偏差变量个目标的正、负偏差变量建立目标约束：建立目标约束：产品产品的产量不低于产品的产量不低于产品的产量的产量:0 1121ddxx21 xx 141运筹学运筹学 第四章第四章 目标规划目标规划 102 2221ddxx561083321ddxx11 221xx充分利用设备有效台时充分利用设备有效台时:利润不小于利润不小于 56 元元:原材料约束原材料约束:102 21xx5610821xx优先等级优先等级: : 第一目标：第一目标： 即产品即产品的产量不大于的产量不大于的产量。的产量。 11dP第二目标：第二目标：即充分利

17、用设备有效台时，不加班即充分利用设备有效台时，不加班)(222ddP第三目标：第三目标：即利润不小于即利润不小于 56 元元33dP151运筹学运筹学 第四章第四章 目标规划目标规划 达成函数：达成函数：)3,2, 1( 0 ,0,11 256108102 0 )(min21213321222111213322211iddxxxxddxxddxxddxxdPddPdPZii目标规划模型：目标规划模型：3322211)(mindPddPdPZ161运筹学运筹学 第四章第四章 目标规划目标规划 )2 .1( 0 .n)1.2(j 0)2 .1( ).()2 .1( )(min1111Llddxmi

18、bxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk目标规划模型一般形式目标规划模型一般形式171运筹学运筹学 第四章第四章 目标规划目标规划 建模的建模的步骤步骤 1 1、根据要研究的问题所提出的各目标与条件，确定、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；目标值，列出目标约束与绝对约束； klkl和和 4 4、对同一优先等级中的各偏差变量，若需要可按其对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数重要程度的不同，赋予相应的权系数 。 3 3、给各目标赋予相应的优先因子、给各目标赋予相应的优先因子 P

19、 Pk k（k=1.2K）。）。 2 2、可根据决策者的需要，将某些或全部绝对约束、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。变量和减去正偏差变量即可。181运筹学运筹学 第四章第四章 目标规划目标规划 5 5、根据决策者的要求，按下列情况之一、根据决策者的要求，按下列情况之一llddldld. .恰好达到目标值，取恰好达到目标值，取 。. .允许超过目标值，取允许超过目标值，取 。. .不允许超过目标值，取不允许超过目标值，取 。构造一个由优先因子和权系数相对应的偏差变量组成的

20、，要构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。求实现极小化的目标函数，即达成函数。191运筹学运筹学 第四章第四章 目标规划目标规划 小结小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min , max系数可正负系数可正负min , 偏差变量偏差变量系数系数0 0变量变量xi, xs xa xi xs xa d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意201运筹学运筹学 第四章第四章 目标规划目标规划 图解法同样适用两个变量的目标规划问题，但其操图解法同样适

21、用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。标规划的求解原理和过程。 图解法解题步骤如下：图解法解题步骤如下： 1、确定各约束条件的可行域，即将所有约束条件、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；在坐标平面上表示出来；2 目标规划的图解法目标规划的图解法 2、在目标约束所代表的边界线上，用箭头标出正、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；负偏差变

22、量值增大的方向；211运筹学运筹学 第四章第四章 目标规划目标规划 5、重复、重复4，直到所有优先等级的目标都已审查完毕为，直到所有优先等级的目标都已审查完毕为止；止；3、求满足最高优先等级目标的解；、求满足最高优先等级目标的解；4、转到下一个优先等级的目标，再不破坏所有较高、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；优先等级目标的前提下，求出该优先等级目标的解； 6、确定最优解和满意解。、确定最优解和满意解。221运筹学运筹学 第四章第四章 目标规划目标规划 某电视机厂装配黑白和彩色电视机，每装配一台某电视机厂装配黑白和彩色电视机，每装配一台电视

23、机需占用装配线电视机需占用装配线1 1小时，装配线每周计划开动小时，装配线每周计划开动4040小时。预计市场每周彩色电视机的销量是小时。预计市场每周彩色电视机的销量是2424台，台，每台可获利每台可获利8080元；黑白电视机的销量是元；黑白电视机的销量是3030台，每台台，每台可获利可获利4040元。该企业决策者确定的目标为：元。该企业决策者确定的目标为： 第一优先级：充分利用装配线每周计划开动第一优先级：充分利用装配线每周计划开动40小时；小时； 第二优先级：允许装配线加班；但加班时间每周尽第二优先级：允许装配线加班；但加班时间每周尽量不超过量不超过10小时；小时； 第三优先级：装配电视机的

24、数量尽量满足市场需要。第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权数为因彩色电视机的利润高，取其权数为2。 试建立该问题的目标规划模型，并求解试建立该问题的目标规划模型，并求解黑白和彩色黑白和彩色电视机的产量。电视机的产量。例例3231运筹学运筹学 第四章第四章 目标规划目标规划 A010 20 30 40 50 60 70 80 10 20 30 40 50 60 x2 x1B1d1d2d2dC 3d 3d 4d 4dDEFHGE(24 ,26)E(24 ,26)为所求的满意解。为所求的满意解。)41(0, 0,302450 40)2(min2144233122

25、2111214332211iddxxddxddxddxxddxxddPdPdPZii解：设解：设x1， x2分别表示彩色和黑白电视机的产量。分别表示彩色和黑白电视机的产量。241运筹学运筹学 第四章第四章 目标规划目标规划 01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上线段上的所有点均是该问题的解（无穷多最优解）。的所有点均是该问题的解（无穷多最优解）。 )2 . 1(0, 0,8 2 102 5 .621210)(min21212221112122111ldd

26、xxxxddxxddxxdPddPZll例例4、用图解法求解目标规划问题、用图解法求解目标规划问题251运筹学运筹学 第四章第四章 目标规划目标规划 例例5、已知一个生产计划的线性规划模型为、已知一个生产计划的线性规划模型为 01006014021230max21212121xxxxxxxZ)( )( )( 丙丙资资源源乙乙资资源源甲甲资资源源 其中目标函数为总利润，其中目标函数为总利润，x1,x2 为产品为产品A、B产量。现产量。现有下列目标：有下列目标： 1、要求总利润必须超过、要求总利润必须超过 2500 元；元； 2、考虑产品受市场影响，为避免积压，、考虑产品受市场影响，为避免积压，A

27、、B的生产生产量不超过量不超过 60 件和件和 100 件；件； 3、由于甲资源供应比较紧张，不要超过现有量、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。261运筹学运筹学 第四章第四章 目标规划目标规划 解：以产品解：以产品 A A、B B 的单件利润比的单件利润比 2.5 2.5 ：1 1 为权系数，为权系数，模型模型如下：如下： )4 .3 .2 .1(0,010060140225001230)5 .2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 2

28、71运筹学运筹学 第四章第四章 目标规划目标规划 0 x2 0 x11401201008060402020 40 60 80 1002d2d1d1d3d3d4d4dABCD 结论：结论：C(60 ,58.3)C(60 ,58.3)为所求的满意解。为所求的满意解。作图：作图： ) 4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 281运筹学运筹学 第四章第四章 目标规划目标规划 检验：将上述结果带入模型，因检验：将上述结果带入模型，因 0； 0； 0，

29、 存在；存在； 0， 存在。所以，存在。所以，有下式：有下式： min Z=P3 2d2d1d1d3d3d4d4d 将将 x160， x2 58.3 带入约束条件，得带入约束条件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 0。说明第说明第k k个优先等级的目标尚个优先等级的目标尚未达到未达到, ,必须检查必须检查Pk这一的检验数这一的检验数kj(j=1.2n+2m).(j=1.2n+2m).若若Pk这这一行某些负检验数的同列上面（较高优先等级）一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得到满意解，应继续改

30、进，转没有正检验数，说明未得到满意解，应继续改进，转到第到第3 3步；若步；若Pk这一行全部负检验数的同列上面（较高这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第不能改进，故得满意解，转到第6 6步。步。 3 3、确定进基变量。、确定进基变量。 在在Pk行行，从那些上面没有正检验数的负检验数中，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量选绝对值最大者，对应的变量xs就是进基变量。若就是进基变量。若Pk行行中有几个相同的绝对值最大者，则依次比较它们各列中有几个相同的绝对

31、值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列下部的检验数，取其绝对值最大的负检验数的所在列的的xs为进基变量。假如仍无法确定，则选最左边的变量为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。（变量下标小者）为进基变量。331运筹学运筹学 第四章第四章 目标规划目标规划 4 4、确定出基变量、确定出基变量 其方法同线性规划，即依据最小比值法则其方法同线性规划，即依据最小比值法则故确定故确定xr为出基变量，为出基变量，arsrs为主元素。若有几个相同的为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为行可供选择时，选最上面那一行

32、所对应得变量为xr 。rsorisissiabaab 0/min 5 5、旋转变换（变量迭代）。、旋转变换（变量迭代）。 以为主元素进行变换，得到新的单纯形表，获得一组以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第新解，返回到第2 2步。步。 6 6、对求得的解进行分析、对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，型，即调整目标优先等级和权系数，或者改变目标值，重新进行第重新进行第1 1步。步。341运筹学运筹学 第四章第四章 目标规划目标规划 )4 . 3 . 2 .

33、 1( 0, 0100 60 140 2 250012305 . 2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例例6、用单纯形法求解下列目标规划问题、用单纯形法求解下列目标规划问题351运筹学运筹学 第四章第四章 目标规划目标规划 CjCBXBbx1x21d1d2d2d3d3d4d4d= min2500/30,140/2,60/1=60 ,故故 为换出变量。为换出变量。3di00P100P302.5P20P230121-100000021001-100001000001-100010000001-1)4.3.2.1( 0,0

34、100 60 140 2 250012305.2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll2500140601001d2d3d4dP1000P1P2P332111111003030)1000102030(0PPPPPacciB -3000-120000000000000010000102.50010-2500002500/30140/260/1/361运筹学运筹学 第四章第四章 目标规划目标规划 Cj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x16

35、0100000110001000100000011kjP1 7000120100303000P2 000000002.501P3 000000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20/2, =10 ,故故 为换出变量。为换出变量。2d371运筹学运筹学 第四章第四章 目标规划目标规划 Cj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 -400030115-150000P2

36、 -250-5/400-5/45/45/2001P3 000000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10 ,故故 为换出变量。为换出变量。3d1d381运筹学运筹学 第四章第四章 目标规划目标规划 Cj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 00010000000P2 -175/30-1-1/121/12002/5001P3 -80/

37、301/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 为换出变量。为换出变量。2d3d3d391运筹学运筹学 第四章第四章 目标规划目标规划 Cj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x160100000-11000125/300-1/121/12005/2-5/211kjP1 00010000000P2 000000005/201P3 -115/300-1/121/1

38、2101/2-1/2001d1d2d2d3d3d4d4d4d2d表中表中3115/30，说明说明P3 优先等级目标没有实现，但已无法改进，优先等级目标没有实现，但已无法改进，得到满意解得到满意解 x1 60， x2 175/3， 115/3， 125/3。4d2d401运筹学运筹学 第四章第四章 目标规划目标规划 结果分析：计算结果表明，工厂应生产结果分析：计算结果表明，工厂应生产A产品产品60件，件，B产品产品175/3件，件，2500元的利润目标刚好达到。元的利润目标刚好达到。 125/3，表明产品比最高限额少，表明产品比最高限额少125/3件，满足要求。件，满足要求。 115/3 表明甲

39、资源超过库存表明甲资源超过库存115/3公斤，该目标没有达公斤，该目标没有达到。到。 从表中还可以看到，从表中还可以看到，P3 的检验数还有负数，但其高的检验数还有负数，但其高等级的检验数却是正数，要保证等级的检验数却是正数，要保证 P1目标实现，目标实现，P3等级等级目标则无法实现。所以，按现有消耗水平和资源库存目标则无法实现。所以，按现有消耗水平和资源库存量，无法实现量，无法实现25002500元的利润目标。元的利润目标。 可考虑如下措施：降低可考虑如下措施：降低A、B产品对甲资源的消耗产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变量，以满足现有甲资源库存量的目标；或改变P3等

40、级目等级目标的指标值，增加甲资源标的指标值，增加甲资源115/3115/3公斤。公斤。 若很难实现上述措施，则需改变现有目标的优先等若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意结果。级，以取得可行的满意结果。4d2d411运筹学运筹学 第四章第四章 目标规划目标规划 4 应用举例应用举例例例7（人事问题）（人事问题）某单位领导在考虑本单位职工的升某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：级调资方案时，依次遵守以下规定：1、不超过年工资总额、不超过年工资总额60000元；元；2、每级的人数不超过定编规定的人数；、每级的人数不超过定编规定的人数；3、II，I

41、II级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%，且无越级提升；，且无越级提升；4、III级级不足编制的人数可录用新职工，又不足编制的人数可录用新职工，又I级级职工中有职工中有10%要退休要退休。有关资料汇总于下表，问该领导应如何拟订一个满意的方案。有关资料汇总于下表，问该领导应如何拟订一个满意的方案。等级等级工资额（元工资额（元/年）年） 现有人数现有人数编制人数编制人数IIIIII200015001000101215121515合计合计3742421运筹学运筹学 第四章第四章 目标规划目标规划 解：设解：设x1， x2 ， x3分别表示提升分别表示提升I，II级和录用

42、到级和录用到III级的级的新职工人数。新职工人数。 di+, di-分别为第分别为第i个目标的负、正偏差变量个目标的负、正偏差变量第一优先级第一优先级P1：不超过年工资总额不超过年工资总额60000元；元；第二优先级第二优先级P2 ：每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数；第三优先级第三优先级P3 ： II，III级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%。确定优先因子：确定优先因子：60000)15(1000)12(1500)1 . 01010(20001132211 ddxxxxx建立目标约束：建立目标约束：年工资总额不超过年工资总额不超过6

43、0000元元每级的人数不超过定编规定的人数：每级的人数不超过定编规定的人数：对对I级级有：有：12)1 . 01010(221 ddx对对II级有：级有：15123321 ddxx对对III级有：级有：15154432 ddxx431运筹学运筹学 第四章第四章 目标规划目标规划 II，III级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%：达成函数：达成函数：对对II级有：级有：2.012551 ddx对对III级有：级有：2 . 015662 ddx)()(min653432211 ddPdddPdPZ目标规划模型：目标规划模型： )61(0,0,34.2033475.05

44、.0)()(min3216625514432332122111321653432211iddxxxddxddxddxxddxxddxddxxxddPdddPdPZii第一优先级第一优先级P1：不超过年工资总额不超过年工资总额60000元；元；第二优先级第二优先级P2 ：每级的人数不超过定编规定的人数；每级的人数不超过定编规定的人数；第三优先级第三优先级P3 ： II，III级的升级面尽可能达到现有人数的级的升级面尽可能达到现有人数的20%。441运筹学运筹学 第四章第四章 目标规划目标规划 用用单纯形法求解得多重解，如下表单纯形法求解得多重解，如下表变量变量含义含义解解1解解2解解3解解4x1

45、x2x3d1-d2-d3-d4-d5+d6+晋升到晋升到I的人数的人数晋升到晋升到II的人数的人数新招收新招收III的人数的人数工资总额的结余额工资总额的结余额I级缺编人数级缺编人数II级缺编人数级缺编人数III级缺编人数级缺编人数II级超编人数级超编人数III级超编人数级超编人数2.43063000.62.43002.43333000.62.40003333000030.60035500100.62451运筹学运筹学 第四章第四章 目标规划目标规划 目标约束中偏差变量的选择目标约束中偏差变量的选择 目前的有关目标规划的文献往往给人们这目前的有关目标规划的文献往往给人们这样一种印象，似乎模型中

46、目标约束中的正样一种印象，似乎模型中目标约束中的正负偏差变量要成对出现。而实际上决策者负偏差变量要成对出现。而实际上决策者在解决实际多目标决策问题时，模型中目在解决实际多目标决策问题时，模型中目标约束中的正负偏差变量可能只出现一个标约束中的正负偏差变量可能只出现一个（正偏变量或负偏差变量）或成对出现。（正偏变量或负偏差变量）或成对出现。目标约束中偏差变量的正确选择对于多目目标约束中偏差变量的正确选择对于多目标决策问题的求解结果有很大的影响，决标决策问题的求解结果有很大的影响，决策者应该根据实际决策情况选择目标约束策者应该根据实际决策情况选择目标约束中的偏差变量中的偏差变量. .461运筹学运筹

47、学 第四章第四章 目标规划目标规划 例例8 某企业在计划期内生产两种产品。每生产一某企业在计划期内生产两种产品。每生产一件产品件产品1 1可以获利可以获利1212元，每生产一件产品元，每生产一件产品2 2可以获可以获利利1414元，生产一件产品元，生产一件产品1 1所需设备所需设备A A和设备和设备B B的台时的台时分别分别为为8 8台时和台时和1010台时，生产一件产品台时，生产一件产品2 2所需设备所需设备A A和设备和设备B B的台时分别为的台时分别为1010台时和台时和6 6台时。设备台时。设备A A和设和设备备B B的有效台时分别为的有效台时分别为15001500台时和台时和1000

48、1000台时，该企台时，该企业决策者确定的目标优先级为：业决策者确定的目标优先级为： 第一优先级：实现利润不低于第一优先级：实现利润不低于50005000元；元； 第二优先级：充分利用设备第二优先级：充分利用设备A A和设备和设备B B的有效台时的有效台时 问问: :如何安排产品如何安排产品1 1和产品和产品2 2的生产的生产. .471运筹学运筹学 第四章第四章 目标规划目标规划 设产品设产品1 1的产量为的产量为x1，产品产品2 2的产量为的产量为x2 ，短期规划决策目标规划模型为：短期规划决策目标规划模型为：)(min32211ddPdPz0,1000610150010850001412

49、321213212211121dddxxdxxdxxddxx第一优先级：实现利润不低于第一优先级：实现利润不低于5000元；元；第二优先级：充分利用设备第二优先级：充分利用设备A和设备和设备B的有效台时的有效台时481运筹学运筹学 第四章第四章 目标规划目标规划 利用解目标规划的单纯形法，模型的满意解为，利用解目标规划的单纯形法，模型的满意解为， 其余变量为零，即产品其余变量为零，即产品1的产量的产量为为19.23单位单位,产品产品2的产量为的产量为134.62单位。可以验证，实际利润为单位。可以验证，实际利润为2115.38元元,第一优先级的目标没有完成，设备第一优先级的目标没有完成，设备A

50、和和设备设备B的有效台时得到充分的利用的有效台时得到充分的利用,第二优先级的第二优先级的目标完成。这说明了在短期内，即使现有设备的目标完成。这说明了在短期内，即使现有设备的生产能力得到充分的利用，仍然不能实现决策者生产能力得到充分的利用，仍然不能实现决策者所提出的利润目标。所提出的利润目标。 62.2884,62.134,23.191*2*1dxx491运筹学运筹学 第四章第四章 目标规划目标规划 与短期规划决策目标模型不同，因为设备的生产与短期规划决策目标模型不同，因为设备的生产能力在长期可以改变，长期规划决策目标规划模能力在长期可以改变，长期规划决策目标规划模型在设备生产能力目标约束中同时

51、考虑了正负偏型在设备生产能力目标约束中同时考虑了正负偏差变量，其模型为：差变量，其模型为： )(min32211ddPdPz0,100061015001085000141232132121332122211121ddddddxxddxxddxxddxx501运筹学运筹学 第四章第四章 目标规划目标规划 可以求出模型的满意解为，可以求出模型的满意解为， 其余变量为零，即产品其余变量为零，即产品1 1的产量为的产量为416.67416.67单位，不单位，不生产产品生产产品2 2，两个优先级的目标都得到完成。由两，两个优先级的目标都得到完成。由两个正偏差变量的值可以看出：从长期来看，要实个正偏差变量

52、的值可以看出：从长期来看，要实现决策者既定的利润目标，现有设备现决策者既定的利润目标，现有设备A A的生产能力的生产能力应该应该由由15001500台时增加台时增加到到3333.333333.33台时台时, ,设备设备B B的生产的生产能力应该由能力应该由10001000台时增加到台时增加到4166.674166.67台时。比较两台时。比较两模型可以看出：目标约束中偏差变量是单个出现模型可以看出：目标约束中偏差变量是单个出现还是成对出现，对于模型的求解结果和求解结果还是成对出现，对于模型的求解结果和求解结果的分析有很大的影响。的分析有很大的影响。67.3166,33.1833,67.41632

53、*1ddx511运筹学运筹学 第四章第四章 目标规划目标规划 5 Lingo求解目标规划求解目标规划 求解目标规划的序贯式算法求解目标规划的序贯式算法其算法是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规其算法是根据优先级的先后次序，将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。划问题，然后再依次求解。算法算法5.1 对于对于k=1,2,q,求解单目标问题求解单目标问题; )(min1ljjkjjkjdwdwz,2, 1,),(.1mibxatsijnjij,2,1,0,2,1,0,1,2,1,)(,2,1,*11liddnjxkszdwdwligddxciijljj

54、sjjsjiiijnjij521运筹学运筹学 第四章第四章 目标规划目标规划 例例5.1 用Lingo求解： )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 531运筹学运筹学 第四章第四章 目标规划目标规划 解：用“序贯式”算法求求第一级目标。写出Lingo程序(程序名exam1.lg4)min=dminus1;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus

55、3-dplus3=60;x2+dminus4-dplus4=100;计算结果(只列出相关部分)为Global optimal solution found. Objective value: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost DMINUS1 0.000000 1.000000 X2 208.3333 0.000000目标函数的最优值为0，即第一级偏差为0。541运筹学运筹学 第四章第四章 目标规划目标规划 求第二级目标。写出Lingo程序(程序名exam2.lg4)min=2.5*dplus3+dpl

56、us4;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0;计算结果(只列出相关部分)为目标函数的最优值为0，即第二级偏差仍为0。Global optimal solution found. Objective value: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost X2 58.33333 0.000000551运筹学运筹学 第四章第四章

57、目标规划目标规划 求第三级目标。写出Lingo程序(程序名exam3.lg4)min=dplus2;30*x1+12*x2+dminus1-dplus1=2500;2*x1+x2+dminus2-dplus2=140;x1+dminus3-dplus3=60;x2+dminus4-dplus4=100;dminus1=0; 2.5*dplus3+dplus4=0;计算结果(只列出相关部分)为目标函数的最优值为最优值为38.333338.3333，第三级偏差为38.3333。得到满意解：x1=60, x2=58.3333。Global optimal solution found. Object

58、ive 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.000000561运筹学运筹学 第四章第四章 目标规划目标规划 例例5.25.2 某计算机公司生产三种型号的笔记本电脑某计算机公司生产三种型号的笔记本电脑A A、B B、C C。这三。这三种笔记本电脑需要在复杂的装配线上生产，生产种笔记本电脑需要在复杂的装配线上生产，生产1 1台台A A、B B和和C C型型号的笔记本电脑分别需

59、要号的笔记本电脑分别需要5 5小时、小时、8 8小时和小时和1212小时。公司装配线小时。公司装配线正常的生产时间是每月正常的生产时间是每月17001700小时。公司营业部门估计小时。公司营业部门估计A A、B B和和C C三三种笔记本电脑的利润分别是每台种笔记本电脑的利润分别是每台10001000元、元、14401440元和元和25202520元，而元，而公司预测这个月生产的笔记本电脑能够全部售出。公司经理考公司预测这个月生产的笔记本电脑能够全部售出。公司经理考虑：虑：P1:充分利用正常的生产能力，避免开工不足；充分利用正常的生产能力，避免开工不足；P2:优先满足老客户的需求，优先满足老客户

60、的需求，A、B和和C三种型号的电脑三种型号的电脑50、50和和80台，同台，同时根据三种电脑的纯利润分配不同的权因子；时根据三种电脑的纯利润分配不同的权因子；P3:限制装配线的加班时间，尽量不超过限制装配线的加班时间，尽量不超过200小时；小时；P4:满足各种型号电脑的销售目标，满足各种型号电脑的销售目标， A、B和和C型号的电脑分别为型号的电脑分别为100、120和和100台，再根据三种电脑的纯利润分配不同的权因子；台，再根据三种电脑的纯利润分配不同的权因子；P5:装配线的加班时间尽可能少。装配线的加班时间尽可能少。列出相应的目标规划模型，并用列出相应的目标规划模型，并用Lingo程序求解。