[理学]第4章：目标规划ppt课件

1、第四章第四章 目标规划目标规划(Goal programming)目标规划问题及其数学模型目标规划问题及其数学模型 目标规划的图解法目标规划的图解法目标规划的单纯形法目标规划的单纯形法目标规划的灵敏度分析目标规划的灵敏度分析 WinQSBWinQSB软件应用软件应用 目标规划是在线性规划的基础上，为适应经济管理中多目标目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。目标规划是决策的需要而逐步发展起来的一个分支。目标规划是60年代初年代初由美国科学家由美国科学家A.charnes和和W.cooper在在管理模型和线性规划的管理模型和线性规划的工业应用工业应

2、用中一书提出的。中一书提出的。 线性规划立足于求满足所有约束条件的最优可行解，而目线性规划立足于求满足所有约束条件的最优可行解，而目标规划可以在相互矛盾的约束条件下找到满意解，得出决策问标规划可以在相互矛盾的约束条件下找到满意解，得出决策问题的满意方案。题的满意方案。 线性规划只能处理一个目标的问题，而目标规划则能够统线性规划只能处理一个目标的问题，而目标规划则能够统筹兼顾多个目标的关系，更能适用于经营管理中的多目标决策筹兼顾多个目标的关系，更能适用于经营管理中的多目标决策问题。问题。目标规划与线性规划的比较目标规划与线性规划的比较: : 目标规划找到的最优解是指尽可能达到或接近一个或多个目标

3、规划找到的最优解是指尽可能达到或接近一个或多个已给定目标值的满意解。已给定目标值的满意解。 线性规划对约束条件是不分主次地同等对待，而目标规划线性规划对约束条件是不分主次地同等对待，而目标规划可以根据实际需要灵活地给予轻重缓急的考虑。可以根据实际需要灵活地给予轻重缓急的考虑。第一节第一节 目标规划问题及其数学模型目标规划问题及其数学模型一、目标规划问题的提出一、目标规划问题的提出 【例例4-14-1】产品生产问题。某企业计划生产产品生产问题。某企业计划生产I I、IIII两种型号的两种型号的产品，具体相关数据如下表所示：产品，具体相关数据如下表所示：108利润1021设备工时1112原材料拥有

4、量 产品 消耗 资源 解：解：若用若用x xi i（i i1,21,2）分别表示）分别表示I I、IIII两种产品的生产量，两种产品的生产量，则问题可以归结为如下的线性规划问题数学模型：则问题可以归结为如下的线性规划问题数学模型： 21108maxxxZ0,102112212121xxxxxx 这是一个单目标的线性规划模型，可求出最优解为这是一个单目标的线性规划模型，可求出最优解为x14件，件，x23件，件，Max z=62元。元。企业生产中可能有下列情况出现：企业生产中可能有下列情况出现： 根据市场对该产品销售预测得知，产品根据市场对该产品销售预测得知，产品I I的利润有下降的的利润有下降的

5、趋势，故应考虑产品趋势，故应考虑产品I I的产量不应大于产品的产量不应大于产品IIII的产量。的产量。 尽可能不超过计划使用原材料，因为超过计划后，需要尽可能不超过计划使用原材料，因为超过计划后，需要高价采购原材料，导致成本增加。高价采购原材料，导致成本增加。 应尽量充分利用原有的设备工时，而不希望加班生产。应尽量充分利用原有的设备工时，而不希望加班生产。 应尽可能达到或超过原计划利润指标应尽可能达到或超过原计划利润指标5656。 此时，企业决策者的考虑用数学表达式表述为：此时，企业决策者的考虑用数学表达式表述为： 56108102112021212121xxxxxxxx二、目标规划的一般概念

6、二、目标规划的一般概念 1 1目标值和偏差变量目标值和偏差变量 目标值：是指预先给定的某个目标的一个期望值。目标值：是指预先给定的某个目标的一个期望值。 实现值或决策值：是指当决策变量实现值或决策值：是指当决策变量x xj j 选定以后，目标函数选定以后，目标函数的对应值。的对应值。 偏差变量（事先无法确定的未知数）：是指实现值和目标值偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异之间的差异, ,记为记为 d d 。 正偏差变量：表示实现值超过目标值的部分，记为正偏差变量：表示实现值超过目标值的部分，记为 d d。 负偏差变量：表示实现值未达到目标值的部分，记为负偏差变量：表示

7、实现值未达到目标值的部分，记为 d d。 在一次决策中，实现值不可能既超过目标值又未达到目标值，在一次决策中，实现值不可能既超过目标值又未达到目标值，故有故有 d d d d 0,0,并规定并规定d d0, d d0 当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：d d0，d d0 当未完成规定的指标则表示：当未完成规定的指标则表示： d d0，d d0 当恰好完成指标时则表示：当恰好完成指标时则表示： d d0，d d0 d d d d 0 0 成立。成立。 引入了目标值和正、负偏差变量后，就对某一问题有了新的引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，即

8、目标约束。限制，即目标约束。 目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。目标约束是目标规划中特有的，是软约束。2 2、目标约束和绝对约束、目标约束和绝对约束 绝对约束（系统约束）是指必须严格满足的等式或不等式约绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。解。所以，绝对约束是硬约束。3 3、优先因子与权系数、优先因子与权系数 优先因子优先因子Pk 是将决策

9、目标按其重要程度排序并表示出来。是将决策目标按其重要程度排序并表示出来。P1P2PkPk+1PK ，k=1.2K。 权系数权系数k 区别具有相同优先因子的两个目标的差别，决策者区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。可视具体情况而定。4 4、目标规划的目标函数、目标规划的目标函数 目标函数是一个使总偏差量为最小的目标函数，记为：目标函数是一个使总偏差量为最小的目标函数，记为：ddfZ,min 一般说来，有以下三种情况，但只能出现其中之一：一般说来，有以下三种情况，但只能出现其中之一： 要求恰好达到规定的目标值，即正、负偏差变量要尽可能要求恰好达到规定的目标值，即正、负偏差

10、变量要尽可能小，则：小，则： 要求不超过目标值，即允许达不到目标值，也就是正偏差要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则：变量尽可能小，则：ddfZmin 要求超过目标值，即对目标的正偏差要求不限，而负偏差要求超过目标值，即对目标的正偏差要求不限，而负偏差越小越好，这时的目标函数为：越小越好，这时的目标函数为：dfZmin对于由绝对约束转化而来的目标函数，也照上述处理即可。对于由绝对约束转化而来的目标函数，也照上述处理即可。dfZmin 对于这种解来说，前面的目标可以保证实现或部分实现，而对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现

11、或部分实现，有些可能就不能后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。实现。 5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解） 目标规划问题的求解是在不破坏上一级目标的前提下，实现目标规划问题的求解是在不破坏上一级目标的前提下，实现下一级目标的最优化。因此，这样最后求出的解就不是通常意下一级目标的最优化。因此，这样最后求出的解就不是通常意义下的最优解，我们称为它为义下的最优解，我们称为它为满意解满意解。 三、目标规划的一般模型三、目标规划的一般模型 如例如例4-14-1，产品，产品I I的产量不应大于产品的产量不应大于产品IIII的产量，其目标优先的产量，其目标优

12、先级为级为p p1 1，则第一优先级的目标函数为：，则第一优先级的目标函数为：11min p d 第二个目标要求是应尽量充分利用原有的设备工时，而不希第二个目标要求是应尽量充分利用原有的设备工时，而不希望加班生产，其目标优先级为望加班生产，其目标优先级为p p2 2，则其目标函数应为：，则其目标函数应为：222min()p dd 第三个目标要求是企业希望达到并超过计划利润第三个目标要求是企业希望达到并超过计划利润5656，其目标优，其目标优先级为先级为p p3 3，则其相应的目标函数为：，则其相应的目标函数为：33min p d则例则例1 1对应的目标规划数学模型为对应的目标规划数学模型为 ：

13、3322211mindpddpdpZ3 , 2 , 10,5610810201122133212221112121iddxxddxxddxxddxxxxii 对于任何一个多目标决策问题，不妨设问题有对于任何一个多目标决策问题，不妨设问题有n n个决策变量、个决策变量、m m个绝对约束、个绝对约束、L L（1 1）个目标约束、）个目标约束、K K（KLKL）个优先等级。）个优先等级。可以给出多目标决策问题的一般目标规划模型：可以给出多目标决策问题的一般目标规划模型： KkLlllllkddpZ11minLlddnjxmibxaLlgddxclljinjjijlllnjjlj, 2 , 10, 2

14、 , 10, 2 , 1,2 , 111四、建模步骤四、建模步骤 1 1、根据要研究的问题所提出的各目标与条件，确定目标值，、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；列出目标约束与绝对约束； 3 3、给各目标赋予相应的优先因子、给各目标赋予相应的优先因子 P Pk k（k=1.2Kk=1.2K）。）。 2 2、可根据决策者的需要，将某些或全部绝对约束转化为目、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。变量即可。 5 5、根据决策者的要求，

15、按下列情况之一构造一个由、根据决策者的要求，按下列情况之一构造一个由 lldd恰好达到目标值，取恰好达到目标值，取 。ld允许超过目标值，取允许超过目标值，取 。ld不允许超过目标值，取不允许超过目标值，取 。 优先因子和权系数相对应的偏差变量组成的，要求实现极小优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。化的目标函数，即达成函数。klkl和和 4 4、对同一优先等级中的各偏差变量，若需要可按其重要程度、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数的不同，赋予相应的权系数 。第二节第二节 目标规划的图解法目标规划的图解法 图解法同

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

17、增大的方向；变量值增大的方向； 3、求满足最高优先等级目标的解；、求满足最高优先等级目标的解； 4、转到下一个优先等级的目标，再不破坏所有较高优先等、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；级目标的前提下，求出该优先等级目标的解； 5、重复、重复4，直到所有优先等级的目标都已审查完毕为止；，直到所有优先等级的目标都已审查完毕为止； 6、确定最优解和满意解。、确定最优解和满意解。【例例】用图解法求解例用图解法求解例4-1目标规划问题目标规划问题【例例】用图解法求解目标规划问题用图解法求解目标规划问题0,82122201232124164214421

18、33212221112121iiddxxddxxddxxddxxddxxxx4333322211)(3)(mindpddpddpdpz0 x2 x11d1d2d2dA AB BC C3d3d4d4dE EK KML LJ J0,8212220123212416421442133212221112121iiddxxddxxddxxddxxddxxxx4333322211)(3)(mindpddpddpdpz01 2 3 4 5 6 7 8 1 2 3 4 5 6 Ax2 x1B1d1d2d2dC B(0.6250,4.6875) B(0.6250,4.6875)、C(0,5.2083)C(0,5

19、.2083)，B B、C C 线段上的所有点线段上的所有点均是该问题的解（无穷多最优解）。均是该问题的解（无穷多最优解）。)2 . 1(0, 08 2 102 5 .621210)(min21212221112122111lddxxxddxxddxxdPddPZll第三节第三节 目标规划的单纯形法目标规划的单纯形法mn+2mm2 m1K PK 2n+2m22212P2 1n+2m12111P1 kjemn+2mem2em1bomxjm cjme2n+2me22e21bo2xj2cj2e1n+2me12e11 bo1xj1cj1 xn+2m x2 x1bXBCBcn+2mc2c1Cj 一、目标规

20、划单纯形法的一般形式一、目标规划单纯形法的一般形式目标规划求解时，其单纯形表的一般结构如下表：目标规划求解时，其单纯形表的一般结构如下表： 2 2、建立初始单纯形表。、建立初始单纯形表。 一般假定初始解在原点，即以约束条件中的所有负偏差变一般假定初始解在原点，即以约束条件中的所有负偏差变量或松弛变量为初始基变量，按目标优先等级从左至右分别计量或松弛变量为初始基变量，按目标优先等级从左至右分别计算出各列的检验数，填入表的下半部算出各列的检验数，填入表的下半部 。 3 3、检验是否为满意解。判别准则如下：、检验是否为满意解。判别准则如下： 首先检查首先检查k k ( (k k=1.2=1.2K K

21、) )是否全部大于零？如果全部大于是否全部大于零？如果全部大于零，则表示目标均已全部达到，获得最优解，停止计算转到第零，则表示目标均已全部达到，获得最优解，停止计算转到第7 7步；否则转入。步；否则转入。 二、单纯形法的计算步骤二、单纯形法的计算步骤 如果某一个如果某一个 k k 00。说明第。说明第k k个优先等级的目标尚未达到个优先等级的目标尚未达到, ,必须检查必须检查P Pk k这一的检验数这一的检验数kjkj(j=1.2n+2m).(j=1.2n+2m).若若P Pk k这一行某些负这一行某些负检验数的同列上面（较高优先等级）没有正检验数，说明未得检验数的同列上面（较高优先等级）没有

22、正检验数，说明未得到满意解，应继续改进，转到第到满意解，应继续改进，转到第3 3步；若步；若P Pk k这一行全部负检验数这一行全部负检验数的同列上面（较高优先等级）都有正检验数，说明目标虽没达的同列上面（较高优先等级）都有正检验数，说明目标虽没达到，但已不能改进，故得满意解，转到第到，但已不能改进，故得满意解，转到第7 7步。步。 1 1、将目标规划问题的数学模型化为标准形。、将目标规划问题的数学模型化为标准形。 4 4、确定进基变量。、确定进基变量。 在在P Pk k行，从那些上面没有正检验数的负检验数中，选绝对值行，从那些上面没有正检验数的负检验数中，选绝对值最大者，对应的变量最大者，对

23、应的变量x xs s就是进基变量。若就是进基变量。若P Pk k行中有几个相同的绝行中有几个相同的绝对值最大者，则依次比较它们各列下部的检验数，取其绝对值对值最大者，则依次比较它们各列下部的检验数，取其绝对值最大的负检验数的所在列的最大的负检验数的所在列的x xs s为进基变量。假如仍无法确定，为进基变量。假如仍无法确定，则选最左边的变量（变量下标小者）为进基变量。则选最左边的变量（变量下标小者）为进基变量。 5 5、确定出基变量、确定出基变量 其方法同线性规划，即依据最小比值法则：其方法同线性规划，即依据最小比值法则：rsorisissiebeeb0/min故确定故确定xr为出基变量，为出基

24、变量，ers为主元素。若有几个相同的行可供为主元素。若有几个相同的行可供选择时，选最上面那一行所对应得变量为选择时，选最上面那一行所对应得变量为xr 。 6 6、旋转变换（变量迭代）、旋转变换（变量迭代） 以主元素为中心进行变换，得到新的单纯形表，获得一组新以主元素为中心进行变换，得到新的单纯形表，获得一组新解，返回到第解，返回到第3 3步。步。 7 7、对求得的解进行分析、对求得的解进行分析 若计算结果满意，停止运算；若不满意，需修改模型，即调若计算结果满意，停止运算；若不满意，需修改模型，即调整目标优先等级和权系数，或者改变目标值，重新进行第整目标优先等级和权系数，或者改变目标值，重新进行

25、第2 2步。步。【例例4-2 】用单纯形法求解下列目标规划问题用单纯形法求解下列目标规划问题3322211mindpddpdpz3 , 2 , 10,561081020112321332122211121321iddxxxddxxddxxddxxxxxii3213,dddx 解：解：本例中由于各目标约束中均存在负偏差变量，取本例中由于各目标约束中均存在负偏差变量，取 为初始基变量，计算检验数，并将有关数据填入单为初始基变量，计算检验数，并将有关数据填入单纯形表中，如下表：纯形表中，如下表：3232188110200ppppk-1110856-112110-11-1100112110000001

26、p1pjc1xBX2p2p2p3pbBC3p3pij2p1d3x3x3d2x3d1d2d2d2d1d3d-8-1-2-10121表中第一列检验数计算方法为：表中第一列检验数计算方法为：20|max2222jj即即x x2 2进基变量进基变量1155.652101056,210,111min2d即即 离基变量离基变量331332102302300ppk-115-536-1/21/211/250-1/21/2-113/2501/2-1/213/260000001p1pjc1xBX2p2p2p3pbBC3p3pij1d3x3x3d2x3d1d2d2d2x1d3d表中第一列检验数计算方法为：表中第一列

27、检验数计算方法为：即即x x1 1进基变量进基变量1-323626,215,235,236min3d即即 离基变量离基变量151-51410/31024212,614,212,213min1d即即 为离基变量为离基变量11114*2x因表中全部检验数均大于因表中全部检验数均大于0，所以得到满意解：，所以得到满意解：2*1x3d又因表中又因表中 列的检验数等于列的检验数等于0，则该问题存在多重解。，则该问题存在多重解。则则 为进基变量为进基变量3d-1/31/3-5-5/3121/6-1/6-4/34/31401/2-1/2-33-11201/2-1/2-22130000001p1p1xBX2p2p2p3pbBC3p3pij1d3x3x3d2x3d1d2d2d2x1d1xjc310*2x因表中全部检验数均大于因表中全部检验数均大于0，所以得到另一个满意解：，所以得到另一个满意解：310*1x1-1/31/3-2/32/3110/3-1/31/31