运筹学第二单纯形法.ppt

《运筹学第二单纯形法.ppt》由会员分享，可在线阅读，更多相关《运筹学第二单纯形法.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学第二单纯形法1现在学习的是第1页，共73页2一、基础定理一、基础定理定理定理1 若线性规划问题存在最优解，则问题的可行域是凸集。若线性规划问题存在最优解，则问题的可行域是凸集。定理定理2 线性规划问题的基本可行解对应线性规划问题可行域线性规划问题的基本可行解对应线性规划问题可行域（凸集）的顶点。（凸集）的顶点。定理定理3 若线性规划问题最优解存在，则最优解一定在可行域顶若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。点处取得。由此可看出，最优解要在基本可行解（可行域顶点）中找。由此可看出，最优解要在基本可行解（可行域顶点）中找。现在学习的是第2页，共73页3v 若若LP问题

2、有最优解的话，定在可行域的问题有最优解的话，定在可行域的某顶点处达到，又，一个顶点对应一个基本某顶点处达到，又，一个顶点对应一个基本可行解，一个自然的想法是：找出所有的基可行解，一个自然的想法是：找出所有的基本可行解。本可行解。v因基本可行解的个数有限，通过因基本可行解的个数有限，通过“枚举法枚举法”，从理论上讲总能找出所有的基本可行解。而从理论上讲总能找出所有的基本可行解。而事实上随着事实上随着m，n的增大，解的个数迅速增大，的增大，解的个数迅速增大，致使此路行不通。致使此路行不通。现在学习的是第3页，共73页4v换一种思路：若从某一基本可行解（今后称换一种思路：若从某一基本可行解（今后称之

3、为初始基本可行解）出发，每次总是寻找之为初始基本可行解）出发，每次总是寻找比上一个更比上一个更“好好”的基本可行解，逐步改善，的基本可行解，逐步改善，直至最优。这需要解决以下三个问题：直至最优。这需要解决以下三个问题：v1.如何找到一个初始的基本可行解。如何找到一个初始的基本可行解。v2.如何判别当前的基本可行解是否已达到了如何判别当前的基本可行解是否已达到了最优解。最优解。v3.若当前解不是最优解，如何去寻找一个改若当前解不是最优解，如何去寻找一个改善了的基本可行解。善了的基本可行解。现在学习的是第4页，共73页5定义：如何从一个可行基找另一个可行基？称定义：如何从一个可行基找另一个可行基？

4、称基变换基变换。定义：两个基本可行解称为相邻的，如果它们之间仅变换定义：两个基本可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为一个基变量。对应的基称为相邻可行基相邻可行基。例例 LP问题问题 5,105242615552142132ixxxxxxxxxi543210002minxxxxxZ 二、思路解析二、思路解析212maxxxZ 0,524261552121212xxxxxxx现在学习的是第5页，共73页6当前可行基当前可行基 所对应的基本可行解所对应的基本可行解,3x,4x5xTX)5,24,15,0,0(0显然不是最优。显然不是最优。因为从经济意义上讲，因为从经济意义上讲

5、，,01x02x意味着该厂不安排生产，因此没有利润。意味着该厂不安排生产，因此没有利润。相应地，将相应地，将 代入目标函数得代入目标函数得0)(0XZ0X从数学角度看，若让非基变量从数学角度看，若让非基变量 取值从零增加，取值从零增加，,1x2x(对应可行域的对应可行域的 )0,0(o543210002minxxxxxZ 5,105242615552142132ixxxxxxxxxi现在学习的是第6页，共73页7相应的目标函数值相应的目标函数值Z也将随之减少。因此有可能找到一个也将随之减少。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变新的基本可行解，使其目标函数值有所改

6、善。即进行基变换，换一个与它相邻的基。再注意到换，换一个与它相邻的基。再注意到 前的系数前的系数2比比2x1x 前的系数前的系数1小，即小，即 每增加一个单位对每增加一个单位对Z的贡献比的贡献比 大。大。2x1x故应让故应让 从非基变量转为基变量，称为从非基变量转为基变量，称为进基进基。又因为基。又因为基1x变量只能有三个，因此必须从原有的基变量变量只能有三个，因此必须从原有的基变量,3x,4x5x中选一个离开基转为非基变量，称为中选一个离开基转为非基变量，称为出基出基。谁出基？。谁出基？543210002minxxxxxZ现在学习的是第7页，共73页8又因为又因为 仍留作非基变量，故仍有仍留

7、作非基变量，故仍有2x02x（2）式变为）式变为05062401515143xxxxx再让再让 从零增加，能取得的最大值为从零增加，能取得的最大值为1x6241x51x.45,624min1x此时，此时，已经从已经从24降到了降到了0，达到了非基的取值，变，达到了非基的取值，变成非基变量。从而得到新的可行基成非基变量。从而得到新的可行基 。4x,531xxx由此得到一个新的基本可行解：由此得到一个新的基本可行解：TX)1,0,15,0,4(1现在学习的是第8页，共73页9目标函数值：目标函数值：.0)(842)(01XZXZ从目标函数值明显看出，从目标函数值明显看出，比比 明显地得到了改善。明

8、显地得到了改善。0X1X(4,0)顶顶点点此基本可行解对应可行域的此基本可行解对应可行域的将（将（2）式）式5,105262451521521423ixxxxxxxxxi（2）可行基可行基,531xxx留在左边，非基变量留在左边，非基变量,2x4x移到右边移到右边现在学习的是第9页，共73页105,105224651525142123ixxxxxxxxxi（3）5,10613216131451542542123ixxxxxxxxxi用代入法得：用代入法得：（4）现在学习的是第10页，共73页11代入目标函数得：代入目标函数得：Zxx2411833 这一过程用增广矩阵的行初等变换表示为：这一过程

9、用增广矩阵的行初等变换表示为：00001251001124010261500150A2x4x3x5x1xb1/6000012510011406/103/111500150（-1）（2）按最小非负比值规则：按最小非负比值规则：415,624min543210002xxxxxZ主元素主元素 5,105242615552142132ixxxxxxxxxi现在学习的是第11页，共73页12803/103/10116/103/20406/103/1115001502x4x3x5x1xb目标函数系数行目标函数系数行4231318xxZ按最小非负比值规则：按最小非负比值规则：233/21,3/14,515m

10、in现在学习的是第12页，共73页13803/103/10116/103/20406/103/1115001502x4x3x5x1xb3/2803/103/102/32/34/1010406/103/111500150（-5）（-1/3）（1/3）现在学习的是第13页，共73页14 2/172/14/10002/32/34/10102/72/14/10012/152/154/5100所对应的所对应的 LP问题问题ixxxxxxxxxxi3451452455151542211742213342201,5 542141217minxxZ 现在学习的是第14页，共73页15 5,1023234127

11、214121521554542541543ixxxxxxxxxxi542141217minxxZ 可行基可行基,321xxxTX)0,0,215,23,27(3 令非基变量令非基变量 为为0，得到最优解，得到最优解,4x5x最优值：最优值：217max Z现在学习的是第15页，共73页16总结：总结：在迭代过程中要保持常数列向量非负，这能保证基在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值能做到这一点。可行解的非负性。最小比值能做到这一点。主元素不能为主元素不能为0 0。因为行的初等变换不能把。因为行的初等变换不能把0 0变成变成1 1。主元素不能为负数。因为用行的初等变

12、换把负数变成主元素不能为负数。因为用行的初等变换把负数变成1 1会会把常数列中对应的常数变成负数。把常数列中对应的常数变成负数。此基本可行解对应可行域的此基本可行解对应可行域的(7/2,3/2)顶顶点点其结果与图解法一致。其结果与图解法一致。现在学习的是第16页，共73页1754321002minxxxxxZ )5,4,3,2,1(06122.53214321ixxxxxxxxxtsi例例2 解解LP问题：问题：对单纯形矩阵作初等行变换，有：对单纯形矩阵作初等行变换，有：000121610111101221T按最小非负比值原则：按最小非负比值原则：116,11min 确定主元素。确定主元素。（

13、-1）（1）1、无穷多个解、无穷多个解三、其他解的情况三、其他解的情况现在学习的是第17页，共73页18101100511330101221至此，检验行已没有负数，至此，检验行已没有负数，当前解即为最优解。当前解即为最优解。此时对应的此时对应的LP问题为：问题为：1000min54321xxxxxS)5,4,3,2,1(05330122.543214321ixxxxxxxxxxt si0现在学习的是第18页，共73页19101100511330101221此时对应的此时对应的LP问题为：问题为：1000max54321xxxxxS)5,4,3,2,1(05330122.543214321ixx

14、xxxxxxxxt si0TX)5,0,0,0,1(11S现在学习的是第19页，共73页20101100511330101221此时对应的此时对应的LP问题为：问题为：1000max54321xxxxxS)5,4,3,2,1(05330122.543214321ixxxxxxxxxxt si01TX)2,0,0,1,3(21S现在学习的是第20页，共73页21当当0043xx时，不管时，不管 取何值，均有目标函数取何值，均有目标函数取得最大值取得最大值1。此时约束方程为：。此时约束方程为：53125221xxxx其中其中 为基变量。为基变量。,1x5x25213521xxxx用非基变量表示出基

15、变量：用非基变量表示出基变量：其中，其中，为自由变量。设为为自由变量。设为 有有:2x,2cx cxcx352151其中其中c是满足非负性的任意常数。是满足非负性的任意常数。2x1000max54321xxxxxS现在学习的是第21页，共73页22再由再由,1x5x的非负性，知：的非负性，知：0350021521cxcxcx解出解出350 c（其中（其中 ）350 cTccc)35,0,0,12(最优解为：最优解为：最优值为：最优值为：Smax1.现在学习的是第22页，共73页232、无最优解的两种情况：、无最优解的两种情况：无界解无界解例例3 解解LP问题：问题：212minxxs)4,3,

16、2,1(0105215.421321ixxxxxxxtsi解：解：对单纯形矩阵作初等行变换，有：对单纯形矩阵作初等行变换，有：现在学习的是第23页，共73页240001210105250111T1/200012521025150111（2）101060521025110211230注意到注意到6所在的列无正元所在的列无正元素，将基变量素，将基变量 及目及目标函数用非基变量标函数用非基变量 表表示为示为,1x3x,2x4x现在学习的是第24页，共73页25xxxxxxZxx1243242451522311022610 从目标函数看，若令非基变量从目标函数看，若令非基变量,04x2x无限增大，无限

17、增大，Z也无限也无限性，即该性，即该LP问题所追求的目标函数是无界的，即无最小问题所追求的目标函数是无界的，即无最小值，于是该值，于是该LP问题无最优解。问题无最优解。减小，且没有影响减小，且没有影响 的非负的非负,1x3x现在学习的是第25页，共73页26 无可行解无可行解例例4 4 求解求解LPLP问题问题212maxxxZ0,6222212121xxxxxx221 xx62221 xx1x2x解：可行域为空集，无可行解。解：可行域为空集，无可行解。现在学习的是第26页，共73页27下面先把此下面先把此LP问题化为标准型，然后用单纯形法求解。问题化为标准型，然后用单纯形法求解。432100

18、2minxxxxZ0622241421321xxxxxxx对单纯形矩阵作初等行变换，有：对单纯形矩阵作初等行变换，有：212maxxxZ0,6222212121xxxxxx现在学习的是第27页，共73页28000126102220111T100112111032110032 1/2从最后一个矩阵可看出，此从最后一个矩阵可看出，此LP问题无可行基，当然就无问题无可行基，当然就无可行解。可行解。（-1）1211102110321000 100112111032110032（-1）（1）现在学习的是第28页，共73页29LP当前解已是最优的四大特征：当前解已是最优的四大特征：存在一组存在一组(初始初

19、始)可行基（其系数矩阵为单位阵）。可行基（其系数矩阵为单位阵）。检验行的基变量系数检验行的基变量系数=0。检验行的非基变量系数检验行的非基变量系数 0。全部全部0唯一解。唯一解。存在存在=0无穷多个解。无穷多个解。常数列向量常数列向量0。下面的问题是：所给下面的问题是：所给LPLP的标准型中约束矩阵中没有现成的的标准型中约束矩阵中没有现成的可行基怎么办？可行基怎么办？现在学习的是第29页，共73页30人工变量法（也称大人工变量法（也称大M M法）法）针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。例例6 6 用单纯形法求解用单纯形法求解

20、LPLP问题问题313maxxxZ0,9312432132321321xxxxxxxxxxx 单纯形的进一步讨论单纯形的进一步讨论现在学习的是第30页，共73页31解：先将其化为标准形式解：先将其化为标准形式543210003minxxxxxZ093124513253214321xxxxxxxxxxx再强行加上再强行加上人工变量人工变量，使其出现单位矩阵：，使其出现单位矩阵：12341235623717421390 xxxxxxxxxxxxx 现在学习的是第31页，共73页32但这样处理后：但这样处理后：不易接受。因为不易接受。因为 是强行引进，称为是强行引进，称为 76,xx人工变量人工变量

21、。它们与。它们与 不一样。不一样。称为松弛变量和剩称为松弛变量和剩54,xx54,xx余变量，是为了将不等式改写为等式而引进的，而改写前后余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。两个约束是等价的。人工变量的引入一般来说是前后不等人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把

22、目标函数作如下处理：量。为此，发明者建议把目标函数作如下处理：现在学习的是第32页，共73页3376543210003minMxMxxxxxxZxxxxxxxxxxxxx12341235623715421390 其中其中M为任意大的实数，为任意大的实数，“M”称为称为“罚因子罚因子”。用意：只要人。用意：只要人工变量取值大于零，目标函数就不可能实现最优。工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：对此单纯形矩阵作初等行变换，有：现在学习的是第33页，共73页34000103910001301011011240001111MMTMMMM10000143291000

23、1301011011240001111MM（-1）（-3）（4M）MMMMM60430140366133040610110112301112031/6现在学习的是第34页，共73页3534/32/32/3030016/12/12/103/20133/10003/11002/12/12/11000MM34/32/32/303002/34/14/34/30102/333/10003/11002/12/12/11000MM3/2（-1/3）（3）2/34/14/34/30002/92/34/14/34/30102/32/54/14/14/10012/102/12/12/11000MM现在学习的是第3

24、5页，共73页36至此，检验行已没有负数，当前解即为最优解。至此，检验行已没有负数，当前解即为最优解。TX)0,0,23,25,0(0最优值为最优值为：.23maxZ去掉人工变量去掉人工变量 ，即得原，即得原LP问题的最优解：问题的最优解：76,xx2/34/14/34/30002/92/34/14/34/30102/32/54/14/14/10012/102/12/12/11000MM现在学习的是第36页，共73页37 最优解判别定理：所有检验数最优解判别定理：所有检验数0 0；人工变量为；人工变量为0 0 无穷多最优解判别定理：所有检验数无穷多最优解判别定理：所有检验数 0 0；人工变量为

25、；人工变量为0 0；存在某个；存在某个非基变量的检验数为非基变量的检验数为0 0 无可行解判别：无可行解判别：所有检验数所有检验数 0 0；人工变量；人工变量0 0(4)(4)无界解判别定理：有一个非基变量的检验数无界解判别定理：有一个非基变量的检验数0,0,但该数对应但该数对应的列中没有正元素；人工变量为的列中没有正元素；人工变量为0 0解的判别定理：解的判别定理：现在学习的是第37页，共73页38单纯形法步骤单纯形法步骤v一、构造初始可行基一、构造初始可行基v1、引入附加变量，化为标准型、引入附加变量，化为标准型v2、必要时引入人工变量、必要时引入人工变量v3、目标函数中，附加变量系数为、

26、目标函数中，附加变量系数为0，人工变量则为，人工变量则为Mv二、求基本可行解二、求基本可行解v1、用非基变量表示基变量和目标函数式、用非基变量表示基变量和目标函数式v2、求出一个基本可行解及相应、求出一个基本可行解及相应Z值值v三、最优性检验三、最优性检验v依据依据:检验数及判别定理检验数及判别定理v四、基变换四、基变换v1、换入基的确定：检验数负值中最小的、换入基的确定：检验数负值中最小的v2、换出基的确定：最小非负比值规则、换出基的确定：最小非负比值规则v返回步骤二返回步骤二现在学习的是第38页，共73页392.2 单纯形法的表格形式单纯形法的表格形式书例书例2.1 P18 5,1,052

27、2834min532431321ixxxxxxxxxxZi现在学习的是第39页，共73页40v作业vP79 1.3（2），1.7（1）现在学习的是第40页，共73页41大大M法目标是尽快把人工变量从基变量中全部法目标是尽快把人工变量从基变量中全部“赶赶”出去（如果出去（如果能全部能全部“赶赶”出去的话）。所用方法除了大出去的话）。所用方法除了大M法外，还有下面的两法外，还有下面的两阶段法。阶段法。两阶段法两阶段法用大用大M法处理人工变量时，若用计算机处理，必须对法处理人工变量时，若用计算机处理，必须对M给出给出一个较大的具体数据，并视具体情况对一个较大的具体数据，并视具体情况对M值作适当的调整

28、。值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问问题分两个阶段来计算：题分两个阶段来计算：2.3 大大M法和两阶段法法和两阶段法现在学习的是第41页，共73页42v两阶段法的第一阶段求解一个目标中只包含人工变量两阶段法的第一阶段求解一个目标中只包含人工变量的的LP问题，即令目标函数中其它变量的系数取零，人工问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取变量的系数取某个正的常数（一般取1），在保持原问题），在保持原问题约束不变的情况下求这个目标函数极小化的解。约束不变的情况下求这个目标函数极小化的解

29、。v显然在第一阶段中，当人工变量取值为显然在第一阶段中，当人工变量取值为0时，目标函数值时，目标函数值也为也为0。这时候的最优解就是原问题的一个基可行解。这时候的最优解就是原问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为如果第一阶段求解结果最优解的目标函数值不为0，也，也即最优解的基变量中含有非零的人工变量，表明原即最优解的基变量中含有非零的人工变量，表明原LP问问题无可行解。题无可行解。现在学习的是第42页，共73页43v第二阶段：求解原线性规划问题的最优解。第二阶段：求解原线性规划问题的最优解。v以第一阶段的最终单纯形表为基础，去掉人以第一阶段的最终单纯形表为基础，去掉人工

30、变量，目标函数换为原问题的目标函数，工变量，目标函数换为原问题的目标函数，得到第二阶段的初始表，继续迭代求解。得到第二阶段的初始表，继续迭代求解。现在学习的是第43页，共73页44miinx1min0,0112211222222121111212111mnmnmmnnmnmmnnnnnnxxxbxxaxaxabxxaxaxabxxaxaxa 若求得的单纯形矩阵中，所有人工变量都处在非基变量若求得的单纯形矩阵中，所有人工变量都处在非基变量的位置。即的位置。即 及及 。则从第。则从第1 1阶阶段去掉人工变量后，即为原问题的初始单纯形矩阵。并进入第段去掉人工变量后，即为原问题的初始单纯形矩阵。并进入

31、第2 2阶段阶段。n ixim0(1,2,)*0 第一阶段求解第一个线性规划：第一阶段求解第一个线性规划：现在学习的是第44页，共73页45 若第一阶段所求得的单纯形中仍含有（解）非零的人工若第一阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第变量，则说明原问题无可行解。不再进入第2 2阶段。阶段。因此两阶段法的第因此两阶段法的第1阶段求解有两个目的：一为判断原问题阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第对原问题进行第2阶段的计算。阶段的计算。现在学习

32、的是第45页，共73页46xxxxxxxxxxxxx12341235623715421390 76minxx 对单纯形矩阵作初等行变换，有：对单纯形矩阵作初等行变换，有：76543210003minMxMxxxxxxZ例：例：第第1阶段：阶段：现在学习的是第46页，共73页4701100000910001301011011240001111T11010112910001301011011240001111100010042910001301011011240001111（-1）（-1）现在学习的是第47页，共73页48100100429100130101011240011111x2x3x4x5

33、x7x6030406613040610101123011203（-3）（4）6304066304061101123112031/6（-1）现在学习的是第48页，共73页4963040612/103/201110112311203（-3）（6）200000012/103/2013003/11002/110001x2x3x5x4x转入第2阶段：543210003minxxxxxZ3-1（-3）现在学习的是第49页，共73页5032/3030012/103/2013003/11002/110003/232/303002/34/30102/33003/11002/11000（-1/3）（3）2/34/

34、30002/92/34/30102/32/54/10012/102/11000现在学习的是第50页，共73页51书例：表格形式书例：表格形式7,1,0522.834min7532643176321jxxxxxxxxxtsMxMxxxxZj大大M法法:P25 表表2.2.1 两阶段法两阶段法:P27 表表2.3.1；2.3.2现在学习的是第51页，共73页52v作业vP80 1.8（1）现在学习的是第52页，共73页532.4 退化问题退化问题v退化问题：按最小比值退化问题：按最小比值来确定换出基变量时，有时出现来确定换出基变量时，有时出现两个以上相同的最小比值，从而使下一个表的基可行解两个以上

35、相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。中出现一个或多个基变量等于零的退化解。v循环问题：退化解出现的原因是模型中存在多余的约循环问题：退化解出现的原因是模型中存在多余的约束，使多个基可行解对应同一个顶点。当存在退化解束，使多个基可行解对应同一个顶点。当存在退化解时，就有可能出现迭代计算的循环。即从一个可行基时，就有可能出现迭代计算的循环。即从一个可行基经有限次迭代后又回到原来的可行基。尽管可能性及经有限次迭代后又回到原来的可行基。尽管可能性及其微小（直到目前为止，还没有见到一个实际应用问其微小（直到目前为止，还没有见到一个实际应用问题产生循环的例子），但

36、在理论上讲是存在的。题产生循环的例子），但在理论上讲是存在的。现在学习的是第53页，共73页54vE.Beale曾给出一个循环的例子曾给出一个循环的例子v这个例子用单纯形法经过这个例子用单纯形法经过6次迭代后，又回到次迭代后，又回到了初始状态，得不到最优解。有兴趣的同学了初始状态，得不到最优解。有兴趣的同学可自行用单纯形法验证本题产生的循环现象。可自行用单纯形法验证本题产生的循环现象。而实际上本题有最优解。而实际上本题有最优解。v解决方法：摄动法；勃兰特法。解决方法：摄动法；勃兰特法。现在学习的是第54页，共73页552.5 改进单纯形法改进单纯形法v单纯形法计算的特点是每迭代一次，就要把整个

37、单纯单纯形法计算的特点是每迭代一次，就要把整个单纯形表重新计算一遍。从计算机的角度来讲，单纯形法形表重新计算一遍。从计算机的角度来讲，单纯形法并不是一种经济高效的方法。首先是要占用大量的存并不是一种经济高效的方法。首先是要占用大量的存贮空间，其次，由于每次计算都利用上一次的单纯形贮空间，其次，由于每次计算都利用上一次的单纯形表，当计算次数较多时，容易造成误差的积累，直接表，当计算次数较多时，容易造成误差的积累，直接影响计算精度和收敛速度。影响计算精度和收敛速度。v改进单纯形法的基本计算步骤和单纯形法基本相同，改进单纯形法的基本计算步骤和单纯形法基本相同，但在上述两方面有所改进。但在上述两方面有

38、所改进。现在学习的是第55页，共73页56v在单纯形法的迭代过程中，我们实际需要的在单纯形法的迭代过程中，我们实际需要的只有以下各项：只有以下各项：v1、检验数、检验数 ,以判断是否最优或确定以判断是否最优或确定换入基变量。换入基变量。v2、换入变量所在列的各元素、换入变量所在列的各元素 和基变量的和基变量的值值 ，根据，根据 决定换出基变量。决定换出基变量。jjjzc ijaibijiab现在学习的是第56页，共73页57 Min z =CX s.t.AX=b X 0),(),(),(NBNBXXXCCCNBA 单纯形法的矩阵形式单纯形法的矩阵形式0,0min NBNBNNBBXXbNXBX

39、XCXCz现在学习的是第57页，共73页580 zXCXCbNXBXNNBBNBBNB BXB NXB b111BNNNBEXB NXB bXzC B b111 BNBBNNXB NXB bC XC Xz110 得得代代入入NBNBCC B N XzC B b11()现在学习的是第58页，共73页59BNNNBEXB NXB bXzC B b111 NBCCbBCzbBXXBNNBBN111 ,0 得得令令.,0 !出出则则最最优优解解直直接接由由上上式式求求若若能能找找到到最最优优为为最最优优基基的的使使注注BBN bBCzbBXB11 0 目标函数目标函数基本可行解基本可行解现在学习的是第

40、59页，共73页60v在单纯形法的矩阵形式中我们可以发现，单纯形表中的其它数字可利用在单纯形法的矩阵形式中我们可以发现，单纯形表中的其它数字可利用 和原始系数进行运算直接得到：和原始系数进行运算直接得到：v这就是改进单纯形法的出发点。这就是改进单纯形法的出发点。v令向量令向量Y表示表示 ，即，即 称其为称其为单纯形乘子单纯形乘子。jjjBjjjjPBPbBbPBCczc111 1 BCB1 BCYB1 BbBCzB1 现在学习的是第60页，共73页61求解步骤求解步骤v1、第、第0次迭代：初始可行基次迭代：初始可行基 检验数检验数 如不是最优解，确定换入基，换出基。如不是最优解，确定换入基，换

41、出基。2、计算、计算 ：三种方法：三种方法 3、计算第、计算第i1次迭代的常数列和检验数次迭代的常数列和检验数 4、最优性检验：如最优，结束。否则下一步。、最优性检验：如最优，结束。否则下一步。5、计算第、计算第i1次迭代中的换入列次迭代中的换入列 6、确定第、确定第i1次迭代中换出基的下标，返回步次迭代中换出基的下标，返回步2。0B010000NBCCBNN 11 iBkP初等变换法初等变换法取主变换取主变换逆的乘积形式逆的乘积形式现在学习的是第61页，共73页62逆的乘积形式逆的乘积形式v 的计算方法的计算方法v已知：已知：；第；第i次迭代中的换入列；主元素。次迭代中的换入列；主元素。v公

42、式推导可得：公式推导可得：11 iB1 iB 21,mkrkkkkaaaaP rkaTrkmkrkrkkrkkimrriiiaaaaaaaBeeeeeBEB 2111121111,1,),(其其中中，01111EEEEBiii 现在学习的是第62页，共73页63jzxxxs txxxxxxxj123123123max436.3330223400(1,2,3)例：例：jzxxxs txxxxxxxxxj12312341235min436.3330223400(1,2,3)cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 现在

43、学习的是第63页，共73页64cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 Bpp045(,)1001 第第0次迭代：次迭代：NNBCC B N000100 c c cc cppp1234512310(,)(,)(,)0110313(4,3,6)(0,0)01223(4,3,6)B101001 换入换入p3，换出换出p4。基变量为基变量为x3，x5现在学习的是第64页，共73页65cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 第第1次迭代：次迭

44、代：B101001 换入换入p3，换出换出p4。pBpa13033,3 1313主主元元素素计算计算B1-1Taaa2313131,T1,13 BE BE111000 e2(,)10311 基变量为基变量为x3，x5现在学习的是第65页，共73页66cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 第第1次迭代：次迭代：计算当前解和检验数计算当前解和检验数B1110311 TbBb11101010 NNBCC B N111111 c c cc cppp1243512410(,)(,)(,)31113110(4,3,0)(6

45、,0)322011(2,1,2)换入换入p3，换出换出p4。基变量为基变量为x3，x5现在学习的是第66页，共73页67cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 第第1次迭代：次迭代：换入换入p2，换出换出p5，换基换基B1110311 TbBb11101010 N1(2,1,2)pBp12121110,332111 换入换入p3，换出换出p4。基变量为基变量为x3，x5基变量为基变量为x3，x2a2222主主元元素素现在学习的是第67页，共73页68cc c c c c12345(,)(4,3,6,0,0)App

46、ppp12345(,)3131022301 b03040 第第2次迭代：次迭代：换入换入p2，换出换出p5。计算计算B2-1Taaa2322221,T1,13 BE B11211 eB111(,)1121103333011111 基变量为基变量为x3，x2p21,31 B1110311 现在学习的是第68页，共73页69cc c c c c12345(,)(4,3,6,0,0)Appppp12345(,)3131022301 b03040 第第2次迭代：次迭代：计算当前解和检验数计算当前解和检验数B12213311 TbBb122020103 NNBCC B N222122 c c cc cp

47、pp1453214521(,)(,)(,)3311(1,1,1)换入换入p2，换出换出p5。基变量为基变量为x3，x2TX20(0,10,0,0)3 BzCBbc c2120322130(,)70334011 现在学习的是第69页，共73页70v作业v复习例题 P81 1.11现在学习的是第70页，共73页71543210002minxxxxxZixxxxxxxxxi324125121552462501,5 5,105242615552142132ixxxxxxxxxi(1)(2)现在学习的是第71页，共73页7276546212043minxxxxZ 7,1,010321122109841.637654276541 jxxxxxxxxxxxxxtsj现在学习的是第72页，共73页9/7/2022感谢大家观看感谢大家观看现在学习的是第73页，共73页