线性目标规划

1、一、目标规划概述一、目标规划概述二、目标规划的数学模型二、目标规划的数学模型三、目标规划的图解法三、目标规划的图解法四、目标规划的单纯形法四、目标规划的单纯形法第第5章章 线性目标规划线性目标规划(Goal Programming)一、目标规划概述一、目标规划概述线性规划在实践中得到广泛应用，但有两个方线性规划在实践中得到广泛应用，但有两个方面不足：一是不能处理多目标的优化问题；二是面不足：一是不能处理多目标的优化问题；二是其约束条件过于刚性化，不允许约束资源有丝毫其约束条件过于刚性化，不允许约束资源有丝毫超差超差。目标规划是为了解决这一不足而创建的一类数目标规划是为了解决这一不足而创建的一类

2、数学模型。学模型。 线性规划是在线性规划是在一组线性约束条件一组线性约束条件下，寻求下，寻求某一项某一项目标目标的最优值，而实际问题往往要考虑多个目标的的最优值，而实际问题往往要考虑多个目标的决策问题。决策问题。 如核电站的设计问题，传统的单目标规划只允许如核电站的设计问题，传统的单目标规划只允许设定一个目标，那么单一目标选择什么？设定一个目标，那么单一目标选择什么？电站建设电站建设费用最低，安全运行的可靠性最高，电能输出最大费用最低，安全运行的可靠性最高，电能输出最大，对周围环境的影响最小，对周围环境的影响最小。显然，上述目标都很重。显然，上述目标都很重要，且又互相矛盾。这是一个多目标决策问

3、题，普要，且又互相矛盾。这是一个多目标决策问题，普通的线性规划是无能为力的。通的线性规划是无能为力的。1 1、问题的提出、问题的提出例例1：工厂生产两种产品，受到原材料供应和设：工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划，具体数据下，要求制订一个获利最大的生产计划，具体数据见下表。见下表。产品产品限量限量原材料原材料(kg/件件)51060设备工时设备工时(h/件件)4440利润利润(元元/件件)68目标规划问题实例目标规划问题实例 设产品设产品、的产量分别为的产量分别为 ，建立

4、线性，建立线性规划模型：规划模型：解得最优生产计划为解得最优生产计划为 件，件， 件，件，利润为利润为 元。元。81x22x64maxz21,xx0,404460105. .86max21212121xxxxxxtsxxZ 如果工厂作决策时可能还需根据市场和工厂实际如果工厂作决策时可能还需根据市场和工厂实际情况，考虑其它问题，如：情况，考虑其它问题，如：（1）由于产品）由于产品销售疲软，故希望产品销售疲软，故希望产品的产量不的产量不超过产品超过产品的一半；的一半；（2）原材料严重短缺，原料数量只有）原材料严重短缺，原料数量只有60；（3）最好能节约）最好能节约4小时设备工时；小时设备工时；（4

5、）计划利润不少于）计划利润不少于48元。元。2 2、目标规划的基本概念、目标规划的基本概念（1）目标值和正、负偏差变量）目标值和正、负偏差变量 目标规划通过引入目标规划通过引入目标值目标值和和正、负偏差变量正、负偏差变量。所谓所谓目标值目标值是预先给定的某个目标的一个期望值。是预先给定的某个目标的一个期望值。实际值实际值（或决策值）是当决策变量（或决策值）是当决策变量x1、x2、xn选定选定以后目标函数的对应值。显然，以后目标函数的对应值。显然，实际值实际值和和目标值目标值之间之间会有一定的差异，这种差异称为会有一定的差异，这种差异称为偏差变量偏差变量(事先无法确事先无法确定的未知量定的未知量

6、)，用，用d和和d表示。表示。 d超出目标值的差值，称正偏差变量；超出目标值的差值，称正偏差变量；d未达到目标值的差值，称负偏差变未达到目标值的差值，称负偏差变量；量；当当实际值实际值超出超出目标值目标值时，有时，有d0， d0；当当实际值实际值未达到未达到目标值目标值时，有时，有d0，d0 ；当当实际值实际值同同目标值目标值恰好一致时，恰好一致时， d d 0 。即至少有一个为零中注意0,:dddd（2）绝对约束与目标约束）绝对约束与目标约束又称系统约束，是指必须严格满足的等又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝式和不等式约束，如线性规划问题的所有约

7、束都是绝对约束，不满足这些约束条件的解称为非可行解，所对约束，不满足这些约束条件的解称为非可行解，所以它们是以它们是硬约束硬约束。目标约束目标约束是目标规划特有的，可把约束右端看做是目标规划特有的，可把约束右端看做要追求的目标。在达到此目标值时允许发生正偏差或要追求的目标。在达到此目标值时允许发生正偏差或负偏差，因此在这些约束中加入正、负偏差变量，是负偏差，因此在这些约束中加入正、负偏差变量，是软约束。软约束。6010521xx原材料严重短缺，原料数量只有原材料严重短缺，原料数量只有60；目标函数变为目标约束目标函数变为目标约束线性规划问题的目标函数，在给定目标值和偏差线性规划问题的目标函数，

8、在给定目标值和偏差变量后可变换为目标约束。变量后可变换为目标约束。这样就将这样就将目标函数目标函数则转化为则转化为目标约束。目标约束。比如：计划利润不少于比如：计划利润不少于48元。元。2186xx 488621ddxx绝对约束变为目标约束绝对约束变为目标约束该约束的右端项看作目标值，再引入正、负偏差该约束的右端项看作目标值，再引入正、负偏差变量即可。变量即可。1221xx 或或0221 xx此为系统约束此为系统约束在达到此目标值时允许发生正或负偏差，因此在在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，这些约束中加入正、负偏差变量，它们是软约束，在给定目

9、标值和加入正、负偏差变量之后，可以将在给定目标值和加入正、负偏差变量之后，可以将绝对绝对转化为转化为目标约束目标约束。0221ddxx（3 3）优先因子（优先等级）与权系数）优先因子（优先等级）与权系数 在一个规划问题中，决策者在要求达到这些目标时，在一个规划问题中，决策者在要求达到这些目标时，是有轻重缓急的，称这些目标是属于是有轻重缓急的，称这些目标是属于不同层次的优先等不同层次的优先等级级。优先等级层次的高低可分别通过。优先等级层次的高低可分别通过优先因子优先因子P1，P2，表示，并规定表示，并规定Pk Pk1，符号，符号“”表示表示“远大于远大于”，表示，表示Pk与与Pk1，不是同一各级

10、别的量，即，不是同一各级别的量，即Pk与与Pk1有更大的优先权。有更大的优先权。 对属于对属于同一层次优先等级同一层次优先等级的不同目标，按其重要程的不同目标，按其重要程度可分别乘上不同的度可分别乘上不同的权系数权系数。权系数是一个个具体数字，。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。乘上的权系数越大，表明该目标越重要。（4 4）目标规划的目标函数准则函数）目标规划的目标函数准则函数 从从决策者的要求决策者的要求分析：总希望得到的结果与规分析：总希望得到的结果与规定的目标值间的偏差愈小愈好，由此决策者可根据定的目标值间的偏差愈小愈好，由此决策者可根据自己的要求构造一个使自己

11、的要求构造一个使总偏差量为最小的目标函数总偏差量为最小的目标函数，这就是目标规划的目标函数称为这就是目标规划的目标函数称为准则函数准则函数，记为，记为即目标函数是正、负偏变量的函数。即目标函数是正、负偏变量的函数。 ddfZ,min一般来说，可能提出的要求只能是以下三种情一般来说，可能提出的要求只能是以下三种情况之一，对应每种要求，可分别构造目标函数：况之一，对应每种要求，可分别构造目标函数： 构造目标函数的方法构造目标函数的方法如希望产品如希望产品 产量恰好等于产品产量恰好等于产品的产量的产量 ，即正、，即正、负偏变量都要尽可能地小，这时目标函数是：负偏变量都要尽可能地小，这时目标函数是：如

12、希望产品如希望产品 产量低于产品产量低于产品的产量的产量 ，即允许达不，即允许达不到目标值，正偏差变量要尽可能地小到目标值，正偏差变量要尽可能地小, , 这时目标函数是：这时目标函数是：如希望产品如希望产品 产量不低于产品产量不低于产品的产量的产量 ，即要求超，即要求超过目标值，不得低于目标值，负偏差变量尽可能地小，这过目标值，不得低于目标值，负偏差变量尽可能地小，这时目标函数是：时目标函数是：021ddxx)(minddfz)(mindfz)(mindfz例例1中目标函数的构成中目标函数的构成希望产品希望产品 产量不超过产品产量不超过产品产量的一半，即正偏差产量的一半，即正偏差变量要尽可能地

13、小，不希望上式中的变量要尽可能地小，不希望上式中的0，这时目标函，这时目标函数是：数是：0221ddxx dmin364421ddxx希望能节约希望能节约4小时设备工时，即正偏差变量要尽可能小时设备工时，即正偏差变量要尽可能小，小，不希望上式中的不希望上式中的0，这时目标函数是：，这时目标函数是： dmin488621ddxx希望计划利润不少于希望计划利润不少于48元，即负偏差变量尽可能小，元，即负偏差变量尽可能小，不希望上式中的不希望上式中的0，这时目标函数是：，这时目标函数是： dmin（5）满意解）满意解目标规划问题的求解是分级进行的，首先要求满足目标规划问题的求解是分级进行的，首先要求

14、满足P1级目标的解；然后再保证级目标的解；然后再保证 P1级目标不被破坏的前提下，级目标不被破坏的前提下，再要求满足再要求满足P2级目标的解；级目标的解；依次类推。总之，是在不破依次类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它这样最后求出的解就不是通常意义下的最优解，我们称它为为满意解满意解。之所以叫满意解，是因为前面的目标是可以保。之所以叫满意解，是因为前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现。证实现或部分实现的，后面的目标就不一定能保证实现

15、。满意解这一概念的提出是对最优化概念的一种突破，满意解这一概念的提出是对最优化概念的一种突破，显然它更切合实际，更便于运用，因而受到广大实际工作显然它更切合实际，更便于运用，因而受到广大实际工作者的欢迎而被广泛采用。者的欢迎而被广泛采用。 3 3、目标规划的数学模型、目标规划的数学模型 在例在例1中若工厂提出的管理目标按优先级排列如下：中若工厂提出的管理目标按优先级排列如下： 级目标：希望产品级目标：希望产品的产量不超过产品的产量不超过产品的一半；的一半； 级目标：最好能节约级目标：最好能节约4小时设备工时；小时设备工时； 级目标：希望计划利润不小于级目标：希望计划利润不小于48元；元； 由于

16、原材料严重短缺，故原材料约束作为绝对约束。由于原材料严重短缺，故原材料约束作为绝对约束。试建立目标规划模型。试建立目标规划模型。1P2P3P021121ddxx36442221ddxx48863321ddxx)3 , 2 , 1(,iddii 解：解：引入偏差变量引入偏差变量 目标约束：目标约束： 按优先级确定目标函数，按优先级确定目标函数， 级目标要求级目标要求 ； 级级目标要求目标要求 ； 级目标要求级目标要求 该问题的目标规划模型为：该问题的目标规划模型为：1P1mind2P2mind3P3mind其中为绝对约束，、为目标约束。其中为绝对约束，、为目标约束。332211mindPdPdP

17、z6010521xx021121ddxx36442221ddxx48863321ddxx3 , 2 , 10,21iddxxiis.t.而把而把 级目标要求级目标要求 设为，其余依次后退优先级，设为，其余依次后退优先级，得：得：1P0mind该问题也可以这样处理，把绝对约束化为目标约束。该问题也可以这样处理，把绝对约束化为目标约束。601050021ddxx34231201mindPdPdPdPz601050021ddxx021121ddxx36442221ddxx48863321ddxx3 , 2 , 1 , 00,21iddxxiis.t.1 1、模型的一般形式、模型的一般形式),2, 1

18、( 0,n),1,2,(j 0)2, 1( ),()2, 1( )(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk二、目标规划的数学模型二、目标规划的数学模型（4）对）对同一优先等级中同一优先等级中的各偏差变量，若需要可按的各偏差变量，若需要可按其其重要程度的不同，赋予相应的权系数重要程度的不同，赋予相应的权系数2 2、目标规划问题的建模步骤、目标规划问题的建模步骤（1）根据要研究的问题所提出的各目标与条件，）根据要研究的问题所提出的各目标与条件，确定确定目标值，列出目标约束与绝对约束目标值，列出目标约束与绝对约束； klkl和

19、和（3）给）给各目标赋予相应的优先因子各目标赋予相应的优先因子 Pk(k=1,2,K)；（2）可根据决策者的需要，将）可根据决策者的需要，将某些或全部绝对约束某些或全部绝对约束转化为目标约束转化为目标约束。这时只需要给绝对约束加上负偏差。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可；变量和减去正偏差变量即可；（5 5）根据决策者的要求，按下列情况之一构造一个由）根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。现极小化的目标函数。llddldld恰好达到目标值，取恰好达到目标值，取

20、 。允许超过目标值，取允许超过目标值，取 。不允许超过目标值，取不允许超过目标值，取 。例例3：某厂计划在下一个生产周期内生产甲、乙两种：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。试建立此问题的数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢

21、材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗 若提出下列要求：若提出下列要求：（1）完成或超额完成利润指标）完成或超额完成利润指标 50000元；元；（2）产品甲不超过）产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；（3）现有钢材）现有钢材 3600吨正好用完。吨正好用完。 试建立目标规划模型。试建立目标规划模型。 分析：题目有三个目标层次，包含四个目标值。分析：题目有三个目标层次，包含四个目标值。11dP)127( 322ddP第三目标：第三目标：)(443 ddP32 dd 第二目标：有两个要求即甲第二目标：有两个要求即甲 ，乙，乙 ，但两个具，但

22、两个具有相同的优先因子，因此需要确定权系数。本题可有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即用单件利润比作为权系数即 70 :120，化简为，化简为7:12。第一目标：第一目标：规定利润的目标值为规定利润的目标值为 50000，正、负偏差为，正、负偏差为d、d ，则目标函数可以转换为目标约束，既则目标函数可以转换为目标约束，既70 x1 + 120 x2 50000，同样，规定同样，规定 x2200， x3250 则有则有 11dd200221ddx250332ddx)3 . 2 . 1( 0,jddjj 规定规定3600的钢材正好用完，原式的钢材正好用完，原式9 x

23、1 +4 x2 3600则变为则变为0, 360049444421ddddxx)4 , 3 , 2 , 1( 0, 03000 10 3 2000 5 4 36004 9 250 200 5000012070)()127(min2, 121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目标规划模型为：目标规划模型为：例例4：某工艺品厂手工生产两种工艺品：某工艺品厂手工生产两种工艺品A、B，已知生产，已知生产一件产品一件产品A需要耗费人力需要耗费人力2工时，生产一件产品工时，生产一件产品B需要需要耗费人力耗费人力3工时。工时。A

24、、B产品单位利润分别为产品单位利润分别为250元和元和125元。为了最大效率利用人力资源，确定生产首要元。为了最大效率利用人力资源，确定生产首要任务是保证人员高负荷生产，要求每周总耗费人力资任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于源不能低于600工时，但也不能超过工时，但也不能超过680工时的极限；工时的极限；次要任务是要求每周的利润超过次要任务是要求每周的利润超过70000元；在前两个元；在前两个任务的前提下，为了保证库存需要，要求每周产品任务的前提下，为了保证库存需要，要求每周产品A和和B的产量分别不低于的产量分别不低于200和和120件，因为件，因为B产品比产品比A产产品

25、更重要，不妨假设品更重要，不妨假设B完成最低产量完成最低产量120件的重要性件的重要性是是A完成完成200件的重要性的件的重要性的1倍。试求如何安排生产？倍。试求如何安排生产？解：解： 本问题中有本问题中有3个不同优先权的目标，不妨用个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。表示从高至低的优先权。 P1有两个目标：每周总耗费人力资源不能低于有两个目标：每周总耗费人力资源不能低于600工时，也不能超过工时，也不能超过680工时；工时； P2有一个目标：每周利润超过有一个目标：每周利润超过70000元；元； P3有两个目标：每周产品有两个目标：每周产品A和和B的产量分别不低于

26、的产量分别不低于200和和120件。件。采用简化模式，最终得到目标线性规划如下：采用简化模式，最终得到目标线性规划如下：)5 , 4 , 3 , 2 , 1( 0, 0120 d- 200700001252506803 2 6003 2 . .)2(min2, 15524413321222111215343322111jddxdxddxddxxddxxddxxtsdPdPdPdPdPZjj 某厂生产某厂生产、两两种产品，有关数据如表种产品，有关数据如表所示。试求获利最大的所示。试求获利最大的生产方案？生产方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810

27、在此基础上考虑：在此基础上考虑：（1）产品）产品的产量不低于产品的产量不低于产品的产量；的产量；（2）充分利用设备有效台时，不加班；）充分利用设备有效台时，不加班；（3）利润不小于）利润不小于 56 元。元。解解: : 第一目标：第一目标： 即产品即产品的产量不大于的产量不大于的产量。的产量。 第二目标：第二目标：11dP)(222ddP练习练习第三目标：第三目标：33dP规划模型：规划模型：)3 , 2 , 1( 0, 011 256108102 0 )(min2, 1213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj小结：目标规划模型与线性规

28、划模型的异同小结：目标规划模型与线性规划模型的异同线性规划线性规划LP目标规划目标规划GP目标函数目标函数min , max系数可正负系数可正负min , 偏差变量偏差变量系数系数0变量变量xixi d约束条件约束条件系统约束系统约束（绝对约束）（绝对约束）目标约束目标约束系统约束系统约束解解最优最优最满意最满意三、目标规划的图解法三、目标规划的图解法和线性规划问题一样，图解法虽然只适用于两和线性规划问题一样，图解法虽然只适用于两个决策变量的目标规划问题，但其操作简便，原理个决策变量的目标规划问题，但其操作简便，原理一目了然，并且有助于理解一般目标规划问题的求一目了然，并且有助于理解一般目标规

29、划问题的求解原理和过程。解原理和过程。 例例：用图解法求解目标规划问题用图解法求解目标规划问题解：确定各个约束条件的可行域。在解：确定各个约束条件的可行域。在x1Ox2坐标平面上，坐标平面上，暂暂不考虑每个约束方程中的正、负偏差变量不考虑每个约束方程中的正、负偏差变量，将上述每，将上述每一个约束方程用一条直线表示出来，再用两个箭头分别一个约束方程用一条直线表示出来，再用两个箭头分别表示上述目标约束方程中的正、负偏差变量。表示上述目标约束方程中的正、负偏差变量。0,821222012321241643min214421332122211121214333312221iiddxxddxxddxxd

30、dxxddxxxxdPddPdPddPZ0,821222012321241643min214421332122211121214333312221iiddxxddxxddxxddxxddxxxxdPddPdPddPZ1x1x243215623456d1+d1-d2-d2+d3-d3+d4+d4-022dd01d04d0, 033dd例：用图解法求解例：用图解法求解44332211mindPdPdPdPz601051121ddxx022221ddxx36443321ddxx48864421ddxx4 , 3 , 2 , 10,21iddxxiis.t.2d3d4dx2x10L1L2L3L4BCD

31、EF结论：结论：CDEF内内均为满意解均为满意解（最优解），（最优解），无穷多最优解无穷多最优解0*z44332211mindPdPdPdPz601051121ddxx022221ddxx36443321ddxx48864421ddxx4 , 3 , 2 , 10,21iddxxiis.t.1dA01d02d03d04d例：用图解法求解目标规划问题例：用图解法求解目标规划问题)2 , 1(0, 08 2 102 5 .621210)(min2, 1212221112122111lddxxxddxxddxxdPddPZll01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1

32、d1d2dC B (0.6250 , 4.6875) C (0 , 5.2083) ， B、C 线段上线段上的所有点均是该问题的解（无穷多最优解）。的所有点均是该问题的解（无穷多最优解）。)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll0*z011dd02d 例：已知一个生产计划的线性规划模型为例：已知一个生产计划的线性规划模型为 01006014021230max21212121xxxxxxxZ)( )( )( 丙丙资资源源乙乙资资源源甲甲资资源源 其中目标函数为总利润，其中目标函数为总利润，x1

33、，x2 为产品为产品A、B产量。产量。现有下列目标：现有下列目标： 1.要求总利润必须超过要求总利润必须超过 2500 元；元； 2.考虑产品受市场影响，为避免积压，考虑产品受市场影响，为避免积压，A、B的生产生产量不超过量不超过 60 件和件和 100 件；件； 3.由于甲资源供应比较紧张，不要超过现有量由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。试建立目标规划模型，并用图解法求解。 解：以产品解：以产品 A、B 的单件利润比的单件利润比 2.5 ：1 为权系数，为权系数，模型如下：模型如下： )4 . 3 . 2 . 1(0, 010060140225

34、001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 0 x2 0 x11401201008060402020 40 60 80 1002d1d3d4dABCD 结论：结论：C(60 ，58.3)为所求的满意解。为所求的满意解。 )4 . 3 . 2 . 1(0, 010060140225001230)5 . 2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll 011dd033dd0, 044dd0, 022dd 检验：将上述结果带入模型，因检验：将上

35、述结果带入模型，因 0； 0； 0， 存在；存在； 0， 存在。所以，存在。所以，有下式：有下式： minZ=P3 2d2d1d1d3d3d4d4d2d 将将 x160， x2 58.3 带入约束条件，得带入约束条件，得30601258.32499.62500；260+58.3=178.3 140；16060158.358.3 100 由上可知：若由上可知：若A、B的计划产量为的计划产量为60件和件和58.3件时，所件时，所需甲资源数量将超过现有库存。在现有条件下，此解需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须采取措施降低为非可行解。为此，企业必须采取措施降低A、

36、B产品产品对甲资源的消耗量，由原来的对甲资源的消耗量，由原来的100降至降至78.5（140/178.30.785），才能使生产方案（），才能使生产方案（60，58.3）成为可行方案。成为可行方案。 )3 . 2 . 1(0., 0112561081020)(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj 练习：用图解法求解下列目标规划问题练习：用图解法求解下列目标规划问题CD2d2d1d3d结论：有无穷多最优解。结论：有无穷多最优解。C（2，4）D（10/3，10/3） )3 . 2 . 1(0., 0112561081020)(

37、min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj 1、建立初始单纯形表。、建立初始单纯形表。 由于目标规划中的目标函数一定是求最小，检验准由于目标规划中的目标函数一定是求最小，检验准则发生改变。以约束条件中的所有负偏差变量或松弛则发生改变。以约束条件中的所有负偏差变量或松弛变量为初始基变量，即构成一个基。检验数按优先因变量为初始基变量，即构成一个基。检验数按优先因子分成子分成K行，分别计算出各列的检验数。行，分别计算出各列的检验数。 2、检验是否为满意解。判别准则如下：、检验是否为满意解。判别准则如下： （1）对目标函数的优化是按优先

38、级顺序逐级进行的，）对目标函数的优化是按优先级顺序逐级进行的，当当P1行的所有检验数均为非负，说明第一级已得到优行的所有检验数均为非负，说明第一级已得到优化，可转入下一级，再考查化，可转入下一级，再考查P2行的检验数是否存在负行的检验数是否存在负值。值。单纯形法的计算步骤单纯形法的计算步骤四、目标规划的单纯形法四、目标规划的单纯形法 3 3、确定进基换入变量。、确定进基换入变量。 在在Pk行，从那些上面没有正检验数的负检验数中，行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量选绝对值最大者，对应的变量xs就是换入变量。若就是换入变量。若Pk行行中有几个相同的绝对值最大者，则依

39、次比较它们各列中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列下部的检验数，取其绝对值最大的负检验数的所在列的的xs为换入变量。假如仍无法确定，则选最左边的变量为换入变量。假如仍无法确定，则选最左边的变量（变量下标小者）为换入变量。（变量下标小者）为换入变量。 （2）计算停止的准则：）计算停止的准则： 检验数检验数P1，P2，PK行的所有值均为非负。行的所有值均为非负。 如如P1，P2，Pi行的所有检验数为非负，第行的所有检验数为非负，第Pi+1行存在负检验数，但在负检验数所在列的上面行中有行存在负检验数，但在负检验数所在列的上面行中有正检验数。正检

40、验数。 4、确定出基换出变量。、确定出基换出变量。 其方法同线性规划，即依据最小比值法则其方法同线性规划，即依据最小比值法则 故确定故确定xr为出基变量，为出基变量，ers为主元素。若有几个相同为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为的行可供选择时，选最上面那一行所对应得变量为xr 。rsorisissiebeeb0/min 5、变量迭代。、变量迭代。 以为主元素进行变换，得到新的单纯形表，获得一以为主元素进行变换，得到新的单纯形表，获得一组新解，返回到第组新解，返回到第2步。步。 6、对求得的解进行分析。、对求得的解进行分析。 若计算结果满意，停止运算；若不满意，需

41、修改模若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标型，即调整目标优先等级和权系数，或者改变目标值，重新进行第值，重新进行第1步。步。)4 , 3 , 2 , 1( 0, 0100 60 140 2 250012305 . 2min2, 14423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例：用单纯形法求解下列目标规划问题例：用单纯形法求解下列目标规划问题Cj00P100P302.5P20P2CBXBbx1x2P125003012110000000140210011000006010000011000

42、1000100000011kjP1 301201000000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d3d4d= min2500/30,140/2,60/1, =60,故故 为换出变量。为换出变量。3dCj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 0120100303000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d4d= min700/30,20

43、/2, =10 ,故故 为换出变量。为换出变量。2dCj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000 x17011/2001/2-1/200000100010000001-1kjP1 030115-150000P2 0-5/400-5/45/45/2001P3 00000100001d1d2d2d3d3d4d4d1d4d= min400/15, =10,故故 为换出变量。为换出变量。3d1dCj 00P100P302.5P20P2CBXBbx1x2P380/30-1/51/15-1/15-11

44、00002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 0010000000P2 0-1-1/121/12002/5001P3 01/5-1/151/151000001d1d2d2d3d3d4d4d4d= min,350/6,1250/6,100/1=75 ,故故 为换出变量。为换出变量。2d3d3dCj 00P100P302.5P20P2CBXBbx1x2P3115/3001/12-1/12-11-1/21/2000 x2175/3011/12-1/1200-5/25/2000 x1601

45、00000-11000125/300-1/121/12005/2-5/211kjP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/2001d1d2d2d3d3d4d4d4d2dP3行的检验数中有负数，但上面行有正检验数，说明行的检验数中有负数，但上面行有正检验数，说明P3 优先等级目标没有实现，但已无法改进，得到满意解优先等级目标没有实现，但已无法改进，得到满意解 x1 60，x2 175/3， 115/3， 125/3。4d2d结果分析：计算结果表明，应生产结果分析：计算结果表明，应生产A产品产品60件，件，B产品产品175/3件，件，250

46、0元的利润目标刚好达到。元的利润目标刚好达到。 125/3，表明，表明产品比最高限额少产品比最高限额少125/3件，满足要求。件，满足要求。 115/3 表明表明甲资源超过库存甲资源超过库存115/3公斤，该目标没有达到。公斤，该目标没有达到。 从表中还可以看到，从表中还可以看到，P3 的检验数还有负数，但其高的检验数还有负数，但其高等级的检验数却是正数，要保证等级的检验数却是正数，要保证 P1目标实现，目标实现，P3等级目等级目标则无法实现。所以，按现有消耗水平和资源库存量，标则无法实现。所以，按现有消耗水平和资源库存量，无法实现无法实现2500元的利润目标。元的利润目标。 可考虑如下措施：

47、降低可考虑如下措施：降低A、B产品对甲资源的消耗产品对甲资源的消耗量，以满足现有甲资源库存量的目标；或改变量，以满足现有甲资源库存量的目标；或改变P3等级目等级目标的指标值，增加甲资源标的指标值，增加甲资源115/3公斤。公斤。 若很难实现上述措施，则需改变现有目标的优先等若很难实现上述措施，则需改变现有目标的优先等级，以取得可行的满意解果。级，以取得可行的满意解果。4d2d)3 , 2 , 1( 0, 011 256108102 0 )(min2, 1213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj练习：练习：用单纯形法求解下列目标规划问题用

48、单纯形法求解下列目标规划问题Cj 000P1 P2 P2P3 00CBXBbx1x2 x3 00111100000P210120011000 P3 5681000001100 x3 11210000001kjP1 000100000P2 120002000P3 81000000101d1d2d2d3d3d1d2d3d= min,10/2,56/10,11/1= 5,故故 为换出变量。为换出变量。2dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 023/20111/2-1/20000 x251/21001/2-1/2000 P3 63000-551100 x3 63/2000-

49、1/21/2001kjP1 000100000P2 000011000P3 30005-50101d1d2d2d3d3d1d3d= min10/3,10,6/3,12/3= 2,故故 为换出变量。为换出变量。3dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 0200113-3-1/21/200 x2401004/3-4/3-1/61/600 x121000-5/35/31/3-1/300 x3 300002-2-1/21/21kjP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d1d 最优解为最优解为x12，x2 4。但非基变量。

50、但非基变量 的检验数为的检验数为零，故此题有无穷多最优解。零，故此题有无穷多最优解。= min4 , 24 , 6= 4,故故 为换出变量。为换出变量。1d3dCj 000P1 P2 P2P3 00CBXBbx1x2 x3 04002-26-6-1100 x210/301-1/31/31/3-1/30000 x110/3102/3-2/31/3-1/30000 x3 100-11-11001kjP1 000100000P2 000011000P3 0000001001d1d2d2d3d3d3d 最优解为最优解为x110/3，x2 =10/3。作业：作业： 1、某厂生产、某厂生产A、B、C三种产

51、品，装配工作在同一三种产品，装配工作在同一生产线上完成，三种产品时的工时消耗分别为生产线上完成，三种产品时的工时消耗分别为6、8、10小时，生产线每月正常工作时间为小时，生产线每月正常工作时间为200小时；三种产小时；三种产品销售后，每台可获利分别为品销售后，每台可获利分别为500、650和和800元；每月元；每月销售量预计为销售量预计为12、10和和6台。台。 该厂经营目标如下：该厂经营目标如下：（1）利润指标为每月）利润指标为每月16000元，争取超额完成；元，争取超额完成；（2）充分利用现有生产能力；）充分利用现有生产能力；（3）可以适当加班，但加班时间不得超过）可以适当加班，但加班时间

52、不得超过24小时；小时；（4）产量以预计销售量为准。试建立目标规划模型。）产量以预计销售量为准。试建立目标规划模型。 答案：答案：)6 , 2 , 1(0, 0,6101224200108616000800650500 )( min 32166355244133222321113216655444332211iddxxxddxddxddxdddddxxxddxxxddddddpdpdpdpZii1、设、设x1, x2, x3分别表示三种产品的产量，分别表示三种产品的产量，则该问题的目标规划模型为则该问题的目标规划模型为2 2、用图解法求解下列目标规划问题：、用图解法求解下列目标规划问题：)3

53、,2, 1(0,0,15552426)(min21332222111211132231lddxxddxddxxddxxddPdPdPZll满意解为由满意解为由x1 =（3， 3）, x2 =（3.5，1.5）所连线段。）所连线段。3、用图解法解下列目标规划模型。、用图解法解下列目标规划模型。 4, 3 ,2, 1 0,2403 .04 .0300 5002400 . )(min 214421331222111214332211iddxxddxxddxddxxddxxtsdpdpddpfiix1=400, x2=0, Z=80p30 100 200 300 400 500 100 200 300 400 x2 x11d1d44、用单纯形法求解下列目标规划问题：、用单纯形法求解下列目标规划问题：)3 ,2, 1(0,20102603)(min3213