运筹学-目标规划分析课件.ppt

1、运筹学运筹学第四章第四章 目标规划目标规划 第四章第四章 目标规划目标规划 目标规划的求解方法目标规划的求解方法本章内容本章内容目标规划的数学模型目标规划的数学模型目标规划的灵敏度分析及应用举例目标规划的灵敏度分析及应用举例目的：目的：掌握掌握目标规划的数学模型及求解目标规划的数学模型及求解 理解理解目标规划的灵敏度分析目标规划的灵敏度分析例例1、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大，已知资料如表所示。试制定生产计划，使获得的利润最大，试建立数学模型。试建立数学模型。引言：引言：1207

2、0单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大。已知资料如表所示。试制定生产计划，使获得的利润最大。试建立数学模型。试建立数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗要求：要求：1、完成或超额完成利润指标、完成或超额完成

3、利润指标 50000元；元；2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；3、现有钢材、现有钢材 3600吨用完。吨用完。第一节第一节 目标规划的数学模型目标规划的数学模型 目标规划是在线性规划的基础上，为适应实际问题中目标规划是在线性规划的基础上，为适应实际问题中多多目标决策目标决策的需要而逐步发展起来的一个分支。的需要而逐步发展起来的一个分支。2 2、线性规划要求问题的解必须严格满足全部约束条件，、线性规划要求问题的解必须严格满足全部约束条件，但实际问题中并非所有约束都需严格满足；目标规划无此要但实际问题中并非所有约束都需严格满足；目标规划无此要求。

4、求。1 1、线性规划只讨论一个线性目标函数在一组线性约束条、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。合实际的解。一、目标规划概述一、目标规划概述（一）目标规划与线性规划的比较（一）目标规划与线性规划的比较 5 5、线性规划的最优解是绝对意义下的最优，但需花去大、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。满意解，就能满足需要（或更能满

5、足需要）。4 4、线性规划中的约束条件是同等重要的，是、线性规划中的约束条件是同等重要的，是硬约束硬约束；而；而目标规划中有轻重缓急和主次之分，即有优先权。目标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。财务管理等方面得到了广泛的应用。3 3、线性规划求最优解；目标规划是找到一个满意解。、线性规划求最优解；目标规划是找到一个满意解。目标值目标值：是指预先给定的某个目标的一个期望值。：是指预先给定的某个目标的一个期望值。1 1、目标值和偏差变量、目标值和偏差变量（二

6、）目标规划的基本概念（二）目标规划的基本概念偏差变量偏差变量（事先无法确定的未知数）：是指实现值和（事先无法确定的未知数）：是指实现值和目标值之间的差异目标值之间的差异,记为记为 d d。正偏差变量正偏差变量：表示实现值超过目标值的部分，记为：表示实现值超过目标值的部分，记为 d d。负偏差变量负偏差变量：表示实现值未达到目标值的部分，记为：表示实现值未达到目标值的部分，记为 d d。当完成或超额完成规定的指标则表示：当完成或超额完成规定的指标则表示：当未完成规定的指标则表示：当未完成规定的指标则表示：当恰好完成指标时则表示：当恰好完成指标时则表示：在一次决策中，实现值不可能既超过目标值又未达

7、到目在一次决策中，实现值不可能既超过目标值又未达到目标值，故有标值，故有 d d d d 0,0,并规定并规定d d0,d d0注意注意：目标规划中，一般有多个目标值，每个目标值都：目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量相应有一对偏差变量 。d d0,d d0d d0,d d0d d0,d d02 2、绝对约束和目标约束、绝对约束和目标约束 绝对约束：绝对约束：是指必须严格满足的等式约束或不等式约束；是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是称为非

8、可行解，所以绝对约束是硬约束硬约束。目标约束：目标约束：是目标规划所特有的一种约束，它把要追求的是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求此目标值时允许发生正偏目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的变量和要追求的目标值组成的软约束软约束。优先因子优先因子Pk 是将决策目标按其重要程度排序并表示出是将决策目标按其重要程度排序并表示出来。来。P1P2PkPk+1，k=1.2N。3 3、优先因子（优先等级）与优先权系数、优先因子（优先等级

9、）与优先权系数 权系数权系数k 区别具有相同优先因子的两个目标的差别，区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。决策者可视具体情况而定。解释：解释：表示表示Pk比比Pk+1有更大的优先级。有更大的优先级。目标函数是按各目标约束的正、负偏差变量和赋予相应目标函数是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。的优先因子及权系数而构造的。4 4、目标函数、目标函数 要求恰好达到规定的目标值：要求恰好达到规定的目标值：要求不超过目标值：要求不超过目标值：弹性约束基本形式：弹性约束基本形式：要求超过目标值：要求超过目标值：则则min(d d)则则min(d)则则

10、min(d)对于这种解来说，前面的目标可以保证实现或部分对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。有些可能就不能实现。5 5、满意解（具有层次意义的解）、满意解（具有层次意义的解）（三）目标规划的数学模型（三）目标规划的数学模型)2.1(0.n)1.2(j 0)2.1().()2.1()(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk 例例2、某厂计划在下一个生产周期内生产甲、乙两种产品，、某厂计划在下一个生产周

11、期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？已知资料如表所示。试制定生产计划，使获得的利润最大？试建立数学模型。试建立数学模型。12070单件利润单件利润3000103设备台时设备台时200054煤炭煤炭360049钢材钢材资源限制资源限制乙乙甲甲 单位单位 产品产品资源资源 消耗消耗要求：要求：1、完成或超额完成利润指标、完成或超额完成利润指标 50000元；元；2、产品甲不超过、产品甲不超过 200件，产品乙不低于件，产品乙不低于 250件；件；3、现有钢材、现有钢材 3600吨用完。吨用完。11223344121112223312441212min()()

12、7012050000 200 250 9 43600 4 5 2000 3 10 ZPdP ddP ddxxddxddxddxxddxxxx1 2 30000,.0 (1.2.3.4)jjxddj目标规划模型为：目标规划模型为：分析：分析：例一分析：例一分析：题目有三个目标层次，包含四个目标值。题目有三个目标层次，包含四个目标值。第一目标：第一目标：第二目标：有两个要求即甲第二目标：有两个要求即甲 ，乙，乙 ，但两个具，但两个具有相同的优先因子。有相同的优先因子。本题可用单件利润比作为权系数即本题可用单件利润比作为权系数即 70:120，化简为，化简为7:12。11dP32 dd)127(32

13、2ddP第三目标：第三目标：)(443 ddP)4.3.2.1(0.,03000 10 3 2000 5 4 36004 9 250 200 5000012070)()127(min2121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目标规划模型为：目标规划模型为：例例3：某厂生产：某厂生产、两两种产品，有关数据如表所种产品，有关数据如表所示。试求获利最大的生产示。试求获利最大的生产方案？方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑：1、产品、产品的

14、产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。211112221233121 2 0 210810562 110,.0 (1.2.3)jjxxddxxddxxddxxxddj 目标：目标：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。第一目标：第一目标：即产品即产品的产量不大于的产量不大于的产量。的产量。第二目标：第二目标：11P d222()P dd第三目标：第三

15、目标：33dP 目标：目标：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利润不小于、利润不小于 56 元。元。目标函数：目标函数：)(min3322211dPddPdPZ1122233211112221233121 2min()0 210810562 110,.0 (1.2.3)jjZPdP ddP dxxddxxddxxddxxxddj目标规划模型为：目标规划模型为：课堂练习课堂练习 某厂生产某厂生产A、B、C三种产品，装配工作在同一生产线三种产品，装配工作在同一生产线上完成，三种产品的工时消耗分别为上完

16、成，三种产品的工时消耗分别为6 6、8 8、1010小时，生产小时，生产线每月正常工作时间为线每月正常工作时间为200200小时；三种产品销售后，每台可小时；三种产品销售后，每台可获利分别为获利分别为500500、650650和和800800元；每月销售量预计为元；每月销售量预计为1212、1010和和6 6台。台。该厂经营目标如下：该厂经营目标如下：1 1、利润指标为每月、利润指标为每月1600016000元，争取超额完成；元，争取超额完成；2 2、充分利用现有生产能力；、充分利用现有生产能力；3 3、可以适当加班，但加班时间不超过、可以适当加班，但加班时间不超过2424小时；小时；4 4、

17、产量以预计销售量为准。、产量以预计销售量为准。试建立目标规划模型。试建立目标规划模型。答案：答案：)6,2,1(0,0,6101224200108616000800650500 )(min ,.132166355244133222321113216655444332211321iddxxxddxddxddxdddddxxxddxxxddddddpdpdpdpZxxxii型型为为则则该该问问题题的的目目标标规规划划模模量量，分分别别表表示示三三种种产产品品的的产产设设（四（四）小结小结线性规划线性规划LPLP目标规划目标规划GPGP目标函数目标函数min ,max系数可正负系数可正负min ,偏

18、差变量偏差变量系数系数00变量变量决策变量决策变量 决策变量决策变量 d d约束条件约束条件绝对约束绝对约束目标约束目标约束绝对约束绝对约束解解最优最优最满意最满意第二节第二节 解目标规划的图解法解目标规划的图解法 引例：某厂生产引例：某厂生产、两两种产品，有关数据如表所种产品，有关数据如表所示。试求获利最大的生产示。试求获利最大的生产方案？方案？拥有量拥有量原材料原材料2111设备设备(台时台时)1210单件利润单件利润810 在此基础上考虑：在此基础上考虑：1、产品、产品的产量不低于产品的产量不低于产品的产量；的产量；2、充分利用设备有效台时，不加班；、充分利用设备有效台时，不加班；3、利

19、润不小于、利润不小于 56 元。元。11222331212111222123312m in()2 1 1 0 21 081 05 60,.0 (1,2,3)jjZP dPddP dxxxxddxxddxxddxddj目标规划模型为：目标规划模型为：图解法解题步骤如下：图解法解题步骤如下：步骤步骤1 1 建立直角坐标系，令各偏差变量为建立直角坐标系，令各偏差变量为0 0，作出所有的约，作出所有的约束直线束直线 。满足所有。满足所有绝对约束条件绝对约束条件的区域，用阴影标出。的区域，用阴影标出。3322211mindpddpdpz。，3,2,1,0,561081020112s.t.21332122

20、21112121iddxxddxxddxxddxxxxii步骤步骤2 2 作图表示偏差变量增减对约束直线的影响作图表示偏差变量增减对约束直线的影响 在所有目标约束直线旁在所有目标约束直线旁标上标上 d d+，d d-，3322211mindpddpdpz。，3,2,1,0,561081020112s.t.2133212221112121iddxxddxxddxxddxxxxii步骤步骤3 3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。3322211mindpddpdpz。，3,2,1,0,561081020112s.t.21332122211121

21、21iddxxddxxddxxddxxxxii步骤步骤3 3 根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，逐步分析求解。根据目标函数中的优先因子次序，首先考虑具有优先根据目标函数中的优先因子次序，首先考虑具有优先因子因子 p p1 1 的目标的实现。目标函数要求实现的目标的实现。目标函数要求实现 min min d d1 1+，从图从图中可见，可以满足中可见，可以满足d d1 1+=0=0，这时，只能在三角形这时，只能在三角形 OBCOBC的区的区域上取值；域上取值；考察具有优先因子考察具有优先因子 p p2 2的目的目标，此时可在线段标，此时可在线段ED ED

22、上取值；上取值；考察优先因子考察优先因子 p p3 3 的目标，的目标，这就使取值范围缩小到线段这就使取值范围缩小到线段 GD GD 上，该线段上所有点的坐上，该线段上所有点的坐标，都是问题的解，标，都是问题的解，G(2,4)G(2,4)D(10/3,10/3)D(10/3,10/3)。例例1、用图解法求解目标规划问题、用图解法求解目标规划问题)2.1(0,08 2 102 5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll01 2 3 4 5 6 7 8 1 2 3 4 5 6 x2 x11d1d2d2dBC B(0.6250,4.687

23、5)C(0,5.2083)，B、C 线段上的所线段上的所有点均是该问题的解（无穷多最优解）。有点均是该问题的解（无穷多最优解）。)2.1(0,08 2 102 5.621210)(min21212221112122111lddxxxddxxddxxdPddPZll例例2、已知一个生产计划的线性规划模型为、已知一个生产计划的线性规划模型为12121212ma x3 01 221 4 0 ()6 0 1 0 0 0Zxxxxxxx甲 资 源 其中目标函数为总利润，其中目标函数为总利润，x1，x2 为产品为产品A、B产量。现有下产量。现有下列目标：列目标：1、要求总利润必须超过、要求总利润必须超过

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

25、dPddPdPZll 0 x2 0 x11401201008060402020 40 60 80 1003作图：作图：)4.3.2.1(0,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll x2 x11401201008060402020 40 60 80 1000 02d2d1d1d3d3d4d4dABC 结论：结论：C(60,58.3)C(60,58.3)为所求的满意解。为所求的满意解。作图：作图：)4.3.2.1(0,010060140225001230)5.2(min2144233

26、1222111212343211lddxddxddxddxxddxxdPddPdPZll 第三节第三节 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型与线性规划的数学模型基本相目标规划的数学模型与线性规划的数学模型基本相同，因此利用单纯形法求解步骤也基本相同，但是需要同，因此利用单纯形法求解步骤也基本相同，但是需要尤其注意它们之间的区别。尤其注意它们之间的区别。线性规划的单纯形法求解过程线性规划的单纯形法求解过程(目标函数极大化情况下目标函数极大化情况下)：1.1.建立初始单纯形表，计算出所有变量的检验数；建立初始单纯形表，计算出所有变量的检验数；2.2.在非基变量检验数中找到最

27、大的正数在非基变量检验数中找到最大的正数j j，它所对应的它所对应的变量变量x xj j 作为换入基的变量；作为换入基的变量；3.3.对于所有对于所有a aijij0 0 计算计算b bi i/a aijij 其中最小的元素其中最小的元素所对应所对应的基变量的基变量x xi i 作为换出基的变量；作为换出基的变量；4.4.建立新单纯形表，重复上述步骤建立新单纯形表，重复上述步骤2 2、3 3，直到所有检验，直到所有检验数都小于等于零。数都小于等于零。由于目标规划的目标函数都是求由于目标规划的目标函数都是求极小化极小化问题，而线性问题，而线性规划问题的标准型中目标函数是求规划问题的标准型中目标函

28、数是求极大化极大化问题，因此在用问题，因此在用单纯形法求解时要注意一些重要的的差别。单纯形法求解时要注意一些重要的的差别。112231111222123312min 1024032100,0 (1,2,3)iizP ddPdxddxxddxxddx x ddi例例1 1 用单纯形法求解下述目标规划问题：用单纯形法求解下述目标规划问题：第一步：第一步：列出初始单纯形表，并计算检验数。列出初始单纯形表，并计算检验数。将表格中最后一行检验数按优先级改写为：将表格中最后一行检验数按优先级改写为：（这是与线性规划单纯形法的（这是与线性规划单纯形法的第一个差别第一个差别）第二步：第二步：确定换入基的变量。

29、确定换入基的变量。在负检验数中，选择最小的一个在负检验数中，选择最小的一个j j 所对应的变量所对应的变量x xj j作为作为换入基的变量换入基的变量(第二个差别第二个差别)。第三步：第三步：确定换出基的变量（这与线性规划相同）。确定换出基的变量（这与线性规划相同）。第四步：第四步：用换入变量替换换出变量，进行单纯形法迭代运算，用换入变量替换换出变量，进行单纯形法迭代运算，直至优先级直至优先级 P P1 1 所对应的检验数全为非负。所对应的检验数全为非负。本例中，第本例中，第一优先级计一优先级计算后得：算后得：由于优先级由于优先级 P P2 2 的检验数仍然的检验数仍然有负值，因此有负值，因此

30、可以继续优化，可以继续优化，重复上述步骤重复上述步骤 2-4 2-4。确定换入、换出变量：确定换入、换出变量：第一点说明：第一点说明：目标函数按优先级顺序进行优化，当目标函数按优先级顺序进行优化，当P P1 1 行所有检验数非负行所有检验数非负时，说明第一级已经优化，可以转入下一级，考察时，说明第一级已经优化，可以转入下一级，考察 P P2 2 行检验行检验数，依此类推。数，依此类推。第二点说明：第二点说明：从考察从考察P P2 2行检验数开始，注意应把更高级别的优先因子行检验数开始，注意应把更高级别的优先因子考虑在内。如上述问题的进一步单纯形表如下：考虑在内。如上述问题的进一步单纯形表如下：

31、对应的检验数为对应的检验数为P P1 1+(+(3/2)3/2)P P2 200对应的检验数为对应的检验数为P P1 1 P P2 2 00对应的检验数为对应的检验数为P P1 12 2P P2 200 因此上述三种情况都不能因此上述三种情况都不能选为换入基的变量，这其实选为换入基的变量，这其实与线性规划相同。与线性规划相同。判别迭代计算停止的准则：判别迭代计算停止的准则：(1)(1)检验数检验数P P1 1,P P2 2,P Pk k行的所有值均为非负；行的所有值均为非负；(2)(2)若若P P1 1,P P2 2,P Pi i行的所有检验数为非负而行的所有检验数为非负而 P Pi i+1+

32、1行存在负检验数，但在负检验数所在列的上面行行存在负检验数，但在负检验数所在列的上面行中有正检验数（不一定是相邻行，只要在其上方中有正检验数（不一定是相邻行，只要在其上方即可）。即可）。例例2 2：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题：112233123121112221233123Min 510602 0s.t.4 4 3668 48,0,0,(1,2,3)iiZPdPdPdxxxxxddxxddxxddx x xddi cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0

33、1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 11d1d2d3d2d3d1d2d3djjjzc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0

34、1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 11d1d2d3d2d3d1d2d3djjjzc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 5 10 1 0 0 0 0 0 0 P1 0 1-2 0 1-1 0 0 0 0 0 36 4 4 0 0 0 1-1 0 0 P3 48 6 8 0 0 0 0 0 1-1 P1-1 2 0 0 1 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3-6-8 0 0 0 0 0 0 1 0 x3 60 0 20 1-5 5 0 0 0

35、 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020 0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 11d1d2d3d2d3d1d2d3djjjzc 2d3djjjzc cj 0 0 0 P1 0 0 P2 P3 0 CB XB b x1 x2 x3 0 x3 60 0 20 1-5 5 0 0 0 0 0 x1 0 1-2 0 1-1 0 0 0 0 0 36 0 12 0-4 4 1-1 0 0 P3 48 020

36、0-6 6 0 0 1-1 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0-20 0 6-6 0 0 0 1 0 x312 0 0 1 1 -1 0 0 -1 1 0 x124/5 1 0 0 2/5-2/5 0 01/10-1/10 036/5 0 0 0-2/5 2/5 1-1-3/5 3/5 0 x212/5 0 1 0-3/10 3/10 0 01/20-1/20 P1 0 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 1 0 0 P3 0 0 0 0 0 0 0 1 01d1d2d3d2d3d2d3djjjzc 2djjj

37、zc)4.3.2.1(0,0100 60 140 2 250012305.2min214423312221112123423211lddxddxddxddxxddxxdPdPdPdPZll例例3 3：用单纯形法求解下列目标规划问题：用单纯形法求解下列目标规划问题Cj00P100002.5P20P2CBXBbx1x2P1250030121100000001402100110000060100000110001000100000011kjP1 301201000000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d3d4d=min2500/30,14

38、0/2,60/1=60,故故 为换出变量。为换出变量。3dCj 00P100P302.5P20P2CBXBbx1x2P1700012110030300002001001122000 x160100000110001000100000011kjP1 0120100303000P2 00000002.501P3 00000100001d1d2d2d3d3d4d4d1d2d4d=min700/30,20/2,=10,故故 为换出变量。为换出变量。2dCj 00P100P302.5P20P2CBXBbx1x2P14000-31-1-151500002.5P21001/2001/2-1/2-11000

39、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-1100002.5P270/302/51/30-1/3000-11000 x1250/312/51/30-1/3000000001000100000011kjP1 0010000000P2 0-1-1/121/1

40、2002/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 x160100000-11000125/300-1/121/12005/2-5/211kjP1 0010000000P2 00000005/201P3 00-1/121/12101/2-1/2001d1d2d2d3d3d4

41、d4d4d2d满意解满意解x x1 1*=60=60，x x2 2*=175/3=175/3。目标规划的灵敏度分析所讨论内容包括：目标规划的灵敏度分析所讨论内容包括：1 1、约束条件（目标约束和硬约束）右端常数的变化；、约束条件（目标约束和硬约束）右端常数的变化；2 2、约束条件中各变量系数的变化；、约束条件中各变量系数的变化；3 3、加入新的变量（决策变量和偏差变量）；、加入新的变量（决策变量和偏差变量）；4 4、加入新的约束条件；、加入新的约束条件；5 5、目标函数中偏差变量的优先等级及权系数的变化；、目标函数中偏差变量的优先等级及权系数的变化；第四节第四节 灵敏度分析灵敏度分析已知目标规

42、划问题：已知目标规划问题：4,3,2,1,0,125635410)32(min214421332122111214332211iddxxddxxddxxddxddxxdPdPddPzii满足约束条件：目标函数：XBCjP31P3 1-22-33P2 32P1 kj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P11d1d2d2d3d3d3d4d4d4d表表1:1:目标函数的优先等级变化为：目标函数的优先等级变化为：(1)(1)min z=Pmin z=P1 1(2d(2d1 1+3d+3d2 2+)+P)+P2 2d d4 4+P+P3

43、 3d d3 3-(2)min z=P(2)min z=P1 1d d3 3-+P+P2 2(2d(2d1 1+3d+3d2 2+)+P)+P3 3d d4 4+试分析原解有什么变化。试分析原解有什么变化。XBCjP31P3 1-22-33P2 32P1 kj-1111-112P2-112-23-318-11141-1-1116x1x2x1bx2CBP23P12P11d1d2d2d3d3d3d4d4d4d原：min z=P1(2d1+3d2+)+P2d3-+P3d4+分析分析(1):(1):XBCjP21-22-33P3 1P2 32P1 kj-1111-112P3-112-23-318-11

44、141-1-1116x1x2x1bx2CBP33P12P11d1d2d2d3d3d3d4d4d4d新1:min z=P1(2d1+3d2+)+P2d4+P3 d3-将原目标函数中将原目标函数中d d4 4+，d d3 3-的优先因子对换了一下。只的优先因子对换了一下。只需对表需对表1 1的检验数中的的检验数中的P P2 2、P P3 3行和行和c cj j行的行的P P2 2、P P3 3对换即可。对换即可。表表1 1:XBCjP31P3 32P2 1-22-33P1 kj-1111-12P1-112-23-318-11141-1-1116x1x2x1bx2CBP13P22P21d1d2d2d

45、3d3d3d4d4d4d表表2:2:然后继续进行迭代然后继续进行迭代新2:min z=P1 d3-+P2(2d1+3d2+)+P3 d4+分析分析(2):(2):XBCjP31/3-1/3-2/32/3P3 32P2 1P1 kj-1/31/32/3-2/31-16P31-1-1/31/32/3-2/34-1114-1/31/35/3-5/3112x1x2x1bx2CBP13P22P21d1d2d2d3d3d4d4d表表3:3:1d4d从表从表3 3中得到新的满意解中得到新的满意解x x1 1*=4=4，x x2 2*=12=12。P111 4.2(2)P111 4.2(2)P112 4.4(

46、1)P112 4.4(1)、(2)(2)某公司生产某公司生产A A、B B两种药品，这两种药品每小时的产量均为两种药品，这两种药品每小时的产量均为10001000盒，该公司每天采用两班制生产，每周最大工作时间为盒，该公司每天采用两班制生产，每周最大工作时间为8080小时，按预测每周市场最大销量分别为小时，按预测每周市场最大销量分别为7000070000盒和盒和4500045000盒盒A A种药每盒的利润为种药每盒的利润为2.52.5元，元，B B种为种为1.51.5元试确定公司每周元试确定公司每周A A、B B两种药品生产量两种药品生产量x x1 1和和x x2 2（单位：千盒），使公司的下列

47、目标得单位：千盒），使公司的下列目标得以实现：以实现：避免每周避免每周8080小时生产能力的过少使用小时生产能力的过少使用 加班的时间尽量限制在加班的时间尽量限制在1010小时以内小时以内 A A、B B两种药品的每周产量尽量分别达到两种药品的每周产量尽量分别达到7000070000盒和盒和4500045000盒，盒，但不得超出，其权系数依它们每盒的利润为准但不得超出，其权系数依它们每盒的利润为准 尽量减少加班时间尽量减少加班时间 应用举例应用举例先建立这个问题的线性规划模型，依题意分别建立各先建立这个问题的线性规划模型，依题意分别建立各项目标约束项目标约束),(,iddxxdxdxddddd

48、xxii权系数是指它们在目标函数中的重要程度，由权系数是指它们在目标函数中的重要程度，由 2.51.5=532.51.5=53，故：目标函数为：，故：目标函数为：1121132341Min 53ZPdP dPddP d建立单纯形表建立单纯形表运算运算如下：如下：cj 0 0 P1 5P3 3P3 0 P4 P2 CB XB b x1 x2 P1 80 1 1 1 0 0 0-1 0 5P3 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1-1-1 0 0 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3

49、-5-3 0 0 0 0 0 0 P4 0 0 0 0 0 0 1 0 P1 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1 0-1 0 1 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3 0-3 0 5 0 0 0 0 P4 0 0 0 0 0 0 1 01d1d2d3d11d1d2d3djjjzc 3d11djjjzc 11d11d1d cj 0 0 P1 5P3 3P3 0 P4 P2 CB XB b x1 x2 P1 10 0 1 1-1 0

50、0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 45 0 1 0 0 1 0 0 0 0 10 0 0 0 0 0 1 1-1 P1 0-1 0 1 0 0 1 0 P2 0 0 0 0 0 0 0 1 P3 0-3 0 5 0 0 0 0 P4 0 0 0 0 0 0 1 0 0 x2 10 0 1 1-1 0 0-1 0 0 x1 70 1 0 0 1 0 0 0 0 3P3 35 0 0-1 1 1 0 1 0 0 10 0 0 0 0 0 1 1-1 P1 0 0 1 0 0 0 0 0 P2 0 0 0 0 0 0 0 1 P3 0 0 3 2 0 0-3 0 P