大学精品课件：第五章目标规划（第4-5节）.ppt

1、第第1页页目标规划的数学模型结构与线性规划的数学模型结目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质区别，所以可用单纯形法求解。构形式上没有本质区别，所以可用单纯形法求解。第第2页页考虑目标规划的数学模型一些特点，做如下规定：考虑目标规划的数学模型一些特点，做如下规定：1.目标规划问题的目标函数为极小化，所以检验数目标规划问题的目标函数为极小化，所以检验数检验数检验数 0 的非基变量应该作为换入变量，所有检的非基变量应该作为换入变量，所有检验数均验数均 0时，问题达到最优。时，问题达到最优。第第3页页2.因非基变量的检验数中含有不同等级的优先因子，因非基变量的检验数中含有不同等级

2、的优先因子，所以检验数的正、负首先决定于优先因子。所以检验数的正、负首先决定于优先因子。第第4页页1.建立初始单纯形表。建立初始单纯形表。2.在表中将检验数行按优先因子个数分别列成在表中将检验数行按优先因子个数分别列成 K 行行（K 为优先因子数）。为优先因子数）。3.计算检验数，并按优先因子顺序排成计算检验数，并按优先因子顺序排成 K 行：行：第第5页页将检验数为负数的非基变量作为换入变量；将检验数为负数的非基变量作为换入变量；如果存在多个检验数为负数的非基变量，则选择如果存在多个检验数为负数的非基变量，则选择检验数最小的非基变量作为换入变量；检验数最小的非基变量作为换入变量；判断检验数正负

3、和大小时，必须注意：判断检验数正负和大小时，必须注意：KPPP .21第第6页页所有检验数都满足非负要求时，停止：所有检验数都满足非负要求时，停止：u如果检验数的各优先因子行均为非负，则最终如果检验数的各优先因子行均为非负，则最终解也为最优解。解也为最优解。u如果检验数的各优先因子行有负、有正，则最如果检验数的各优先因子行有负、有正，则最终解为满意解。终解为满意解。第第7页页4.按最小比值规则确定换出变量，若有两个或两个按最小比值规则确定换出变量，若有两个或两个以上最小比值时，选取有较高优先因子的变量为换以上最小比值时，选取有较高优先因子的变量为换出变量；出变量；5.按单纯形法进行旋转运算，建

4、立新单纯形表，返按单纯形法进行旋转运算，建立新单纯形表，返回步骤回步骤 3；第第8页页 3,2,1,0,561081020112 .)(min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPzii例例 1：用单纯形法求解下列目标规划问题。用单纯形法求解下列目标规划问题。第第9页页解：解：将目标规划问题的模型化为标准形。将目标规划问题的模型化为标准形。3,2,1,0,56 10810 2 0 11 2 .)(min3213321222111213213322211iddxxxddxxddxxddxxxxxtsdPddPdPzii第第10页页（

5、1）取）取 为基变量，并列出初始单为基变量，并列出初始单纯形表。纯形表。3213,dddxcj0000P1P2P2P30CBXBbx1x2x30 x31121100000011/1001-101-10000-P2101 2 0001-10010/2P356810000001-156/10c j z jP1000010000P2-1-20000200P3-8-100000001 1d 1d 2d 2d 3d 3d 1d 2d 3d第第11页页（2）x2 换入，换入，换出，得到新的单纯形表换出，得到新的单纯形表 2dcj0000P1P2P2P30CBXBbx1x2x30 x363/20100-1/

6、21/2004053/2001-11/2-1/20010/30 x251/210001/2-1/20010P36 3 0000-551-16/3c j z jP1000010000P2000001100P3-300005-501 1d 1d 2d 2d 3d 3d 1d 3d为正数为正数第第12页页（3）x1 换入，换入，换出，得到新的单纯形表换出，得到新的单纯形表 3dcj0000P1P2P2P30CBXBbx1x2x30 x33001002-2-1/21/2020001-13-3-1/21/20 x24010004/3-4/3-1/61/60 x1210000-5/35/31/3-1/3c

7、 j z jP1000010000P2000001100P3000000010 1d 1d 2d 2d 3d 3d 1d第第13页页所有检验数均为正，达到最终解，又因为检验数的所有检验数均为正，达到最终解，又因为检验数的各优先因子行均为非负，所以最终解为最优解：各优先因子行均为非负，所以最终解为最优解：)4 ,2(),(*2*1*xxX下面来分析该最终解为最优解。下面来分析该最终解为最优解。第第14页页分分 析：析：1.从最终单纯形表中可以看到：从最终单纯形表中可以看到：所有非基变量的检验数都已非负。所有非基变量的检验数都已非负。该解是问题的最优解，因为所有目标均已满足该解是问题的最优解，因为

8、所有目标均已满足（从检验数行可以看出）。（从检验数行可以看出）。第第15页页2.从检验数行可以看出：从检验数行可以看出：优先因子优先因子 P1、P2、P3 的系数均为非负数：表明的系数均为非负数：表明优先因子优先因子 P1、P2、P3的各目标均已满足；的各目标均已满足；第第16页页 11mindPz优先因子优先因子 P1 的各目标：的各目标：01 d的目标已实现的目标已实现01 d第第17页页优先因子优先因子 P2 的各目标：的各目标：02 d02 d)(min222 ddPz的目标已实现的目标已实现02 d02 d的目标已实现的目标已实现第第18页页 33mindPz优先因子优先因子 P3

9、的各目标：的各目标：03 d03 d的目标已实现的目标已实现第第19页页该最终解能满足所有目标，所以该解为最优解：该最终解能满足所有目标，所以该解为最优解：)4 ,2(),(*2*1*xxX 3d又因为非基变量又因为非基变量 的检验数为的检验数为 0，表示问题有，表示问题有多重解。多重解。第第20页页cj0000P1P2P2P30CBXBbx1x2x30 x33001002-2-1/21/26020001-13-3-1/21/240 x24010004/3-4/3-1/61/6240 x1210000-5/35/31/3-1/3-c j z jP1000010000P2000001100P30

10、00000010 1d 1d 2d 2d 3d 3d 1d第第21页页 换入，换入，换出，得到新的单纯形表换出，得到新的单纯形表 1dcj0000P1P2P2P30CBXBbx1x2x30 x31001-11-1100040002-26-6-110 x210/3010-1/31/31/3-1/3000 x110/31002/32/31/3-1/300c j z jP1000010000P2000001100P3000000010 1d 1d 2d 2d 3d 3d 3d 3d第第22页页所有检验数均为正，达到满意解，满意解为：所有检验数均为正，达到满意解，满意解为：)310 ,310(),(*

11、2*1*xxX第第23页页 4,3,2,1,0,2 429262 .)35(min21442332122211121144332211iddxxddxddxxddxxddxxtsdPddPdPdPzii例例 2：用单纯形法求解下列目标规划问题。用单纯形法求解下列目标规划问题。第第24页页解：（解：（1）取）取 为基变量，并列出初为基变量，并列出初始单纯形表。始单纯形表。4321,ddddcj00P1P40P25P303P30CBXBbx1x2P16121-10000000912001-100005P341-200001-1003P320 1 0000001-1c j z jP1-1-20100

12、0000P20000010000P3-5700000503P40001000000 1d 1d 2d 2d 3d 3d 4d 4d 3d 4d 1d 2d第第25页页（2）经多次跌代得到最终单纯形表）经多次跌代得到最终单纯形表cj00P1P40P25P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4310-111-100003P33/41000-1/41/41/4-1/41-10 x25/401 001/4-1/4-1/41/400c j z jP10010000000P20000010000P300003/4-3/417/43/403P40010-1

13、10000 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第26页页所有检验数均为正，达到最终解，又因为检验数的所有检验数均为正，达到最终解，又因为检验数的各优先因子行有正有负，所以最终解为满意解：各优先因子行有正有负，所以最终解为满意解：)45 ,213(),(*2*1*xxX下面来分析该最终解为满意解，而不是最优解。下面来分析该最终解为满意解，而不是最优解。第第27页页分分 析：析：1.从最终单纯形表中可以看到：从最终单纯形表中可以看到：所有非基变量的检验数都已非负。所有非基变量的检验数都已非负。该解只是问题的满意解，它没有满足所有目标要该解只是问题的满意解，它没有满足所有目

14、标要求（从检验数行可以看出）。求（从检验数行可以看出）。第第28页页2.从检验数行可以看出：从检验数行可以看出：优先因子优先因子 P1 和和 P2 的系数均为正数：表明优先因子的系数均为正数：表明优先因子 P1 和和 P2 的各目标均已满足；的各目标均已满足；优先因子优先因子 P3 和和 P4 的系数还有负数：表明优先因子的系数还有负数：表明优先因子 P3 和和 P4 的各目标并未全部满足的各目标并未全部满足；第第29页页)35(min433 ddPz434 d优先因子优先因子 P3 的各目标：的各目标：03 d04 d03 d的目标已实现的目标已实现的目标未实现的目标未实现第第30页页优先因

15、子优先因子 P4 的各目标：的各目标：31 d01 d 14mindPz的目标未实现的目标未实现第第31页页目标规划的灵敏度分析方法与线性规划相似，除了目标规划的灵敏度分析方法与线性规划相似，除了分析各项系数的变化之外，还有优先因子和权系数分析各项系数的变化之外，还有优先因子和权系数的变化问题。的变化问题。第第32页页例：已知目标规划问题例：已知目标规划问题 4,3,2,1,0,10 45 70 80 .)53()35(min2144133222111213234334211iddxxdddddxddxddxxtsddPddPdPdPzii第第33页页最终单纯形表为最终单纯形表为cj00P10

16、5P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-1000003500-111-11-100010000000001-1c j z jP10010000000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第34页页若第一个目标约束的右端项变为若第一个目标约束的右端项变为 120，原满意解发生，原满意解发生什么样的变化？什么样的变化？第第35页页解：解：10000111001001001B 00040b 040001bB第第36页页 bBb1 10570450400010357

17、045将其反映到最终单纯形表中：将其反映到最终单纯形表中：第第37页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP10010000000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d即出现了第三种情况（原问题不可行，对偶问题可行），利即出现了第三种情况（原问题不可行，对偶问题可行），利用对偶单纯形法求解：用对偶单纯形法求解：第第38页页cj00P105P33P33P35P3

18、0P2CBXBbx1x20 x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP10010000000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d333133135,3,min15,13,1minPPPPPPP 第第39页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP100100000

19、00P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第40页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x175101-100-11003P35001-1-11-1100010000000001-1c j z jP10010100000P20000000001P300-33806200 1d 1d 2d 2d 3d 3d 4d 4d 4d 2d第第41页页得到问题的满意解为：得到问题的满意解为：)45,75(),(*2*1*xxX第第42页页例：已知目标规划问题例：已知目标规

20、划问题 4,3,2,1,0,2 429262 .)35(min21442332122211121144332211iddxxddxddxxddxxddxxtsdPddPdPdPzii第第43页页最终单纯形表为最终单纯形表为cj00P1P40P25P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4310-111-100003P33/41000-1/41/41/4-1/41-10 x25/401 001/4-1/4-1/41/400c j z jP10010000000P20000010000P300003/4-3/417/43/403P40010-110

21、000 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第44页页求：目标函数变为求：目标函数变为)35(min434132211 ddPdPdPdPz后问题的满意解。后问题的满意解。解：解：144332211)35(mindPddPdPdPz)35(min434132211 ddPdPdPdPz第第45页页目标函数的变化仅影响各变量的检验数。因此，只需目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。考察检验数的变化即可。分析：分析：变化后的目标函数只是将原目标函数的变化后的目标函数只是将原目标函数的 P3 和和 P4 优先优先因子顺序改变了一下。因子顺序改变了

22、一下。处理方法：将原目标规划的最终单纯形表的目标函数处理方法：将原目标规划的最终单纯形表的目标函数行（行（cj 行）做出相应调整，并重新计算检验数。行）做出相应调整，并重新计算检验数。第第46页页最终单纯形表转变为最终单纯形表转变为cj00P1P30P25P403P40CBXBbx1x20 x113/210001/2-1/21/2-1/200P3310-11 1-100003P43/41000-1/41/41/4-1/41-10 x25/401 001/4-1/4-1/41/400c j z jP10010000000P20000010000P30010-110000P400003/4-3/4

23、17/43/403 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第47页页 换入，换入，换出，得到新的单纯形表：换出，得到新的单纯形表：cj00P1P30P25P403P40CBXBbx1x20 x15101/2-1/2001/2-1/2000300-111-100003P43/200-1/41/4001/4-1/41-10 x21/201 1/4-1/400-1/41/400c j z jP10010000000P20000010000P30001000000P4003/4-3/40017/43/403 1d 1d 2d 2d 3d 3d 4d 4d 4d 2d 1d 2d第

24、第48页页得到问题的满意解为：得到问题的满意解为：)21,5(),(*2*1*xxX第第49页页例：已知目标规划问题例：已知目标规划问题 4,3,2,1,0,2 429262 .)35(min21442332122211121144332211iddxxddxddxxddxxddxxtsdPddPdPdPzii第第50页页最终单纯形表为最终单纯形表为cj00P1P40P25P303P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4310-111-100003P33/41000-1/41/41/4-1/41-10 x25/401 001/4-1/4-1/41/4

25、00c j z jP10010000000P20000010000P300003/4-3/417/43/403P40010-110000 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d第第51页页求：目标函数变为求：目标函数变为 14423132211)(mindPdWdWPdPdPz后问题的满意解。后问题的满意解。解：解：144332211)35(mindPddPdPdPz 14423132211)(mindPdWdWPdPdPz0,21 WW第第52页页目标函数的变化仅影响各变量的检验数。因此，只需目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。考察检验数的

26、变化即可。分析：分析：变化后的目标函数只是将原目标函数的变化后的目标函数只是将原目标函数的 P3 优先因子优先因子中两目标的权系数改变了一下。中两目标的权系数改变了一下。处理方法：将原目标规划的最终单纯形表的目标函数处理方法：将原目标规划的最终单纯形表的目标函数行（行（cj 行）做出相应调整，并重新计算检验数。行）做出相应调整，并重新计算检验数。第第53页页最终单纯形表为最终单纯形表为cj00P1P40P2W1P30W2P30CBXBbx1x20 x113/210001/2-1/21/2-1/200P4310-111-10000W2P33/41000-1/41/41/4-1/41-10 x25/401 001/4-1/4-1/41/400c j z jP10010000000P20000010000P30000W2/4-W2/4W2/40W2P40010-110000 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d421WW 第第54页页分析：分析：0421 WW：原解不变。：原解不变。0421 WW：利用单纯形法继续求解。：利用单纯形法继续求解。