运筹学-第一章-单纯形法进一步讨论ppt课件.ppt

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

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外单纯形法进一步讨论单纯形法进一步讨论窦志武窦志武云南财经大学云南财经大学 物流学院物流学院在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法人工变量法：人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位

2、确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为的变量称为人工变量人工变量，构成的可行基称为，构成的可行基称为人工基人工基，用，用大大MM法法或或两阶段法两阶段法求解，这种用人工变量作桥梁的求解方法称求解，这种用人工变量作桥梁的求解方法称为为人工变量法人工变量法。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 例：min z

3、=2x1+3x2 max z=-2x1-3x2+0 x3 s.t x1+x2 3 标准化 s s.t t x1+x2-x3=3 x1+2x2=4 x1+2x2=4 x10,x20 xj0,(j=1,2,3,4)max z=-2x1-3x2+0 x3-M x4-M x5 s s.t t x1+x2-x3+x4=3 x1+2x2 +x5=4 xj0,(j=1,2,3,4,5)引进人工变量，及引进人工变量，及M非常大正系数，模型转变为非常大正系数，模型转变为这种处理方法称为大这种处理方法称为大M法，以下则可完全按单纯形法法，以下则可完全按单纯形法求解。求解。1大大M法法单纯形法的进一步讨论人工变量法

4、单纯形法的进一步讨论人工变量法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法例例1.10 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量

5、，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7i-M

6、x64-431-101040 x5101-1201005-Mx712-21000113-2M2+M-1+2M-M-Mx63-650-1013/50 x58-3300108/3-1x312-210005-6M5M0-M002x23/56/5101/500 x531/53/5003/5131/3-1x311/52/5012/505 00002x213010123x131/310015/3-1x319/300102/3000-5-25/3在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变

7、量法例例1.11 用大用大M法解下列线性规划法解下列线性规划解：首先将数学模型化为标准形式解：首先将数学模型化为标准形式系数矩阵中不存在系数矩阵中不存在单位矩阵，无法建单位矩阵，无法建立初始单纯形表。立初始单纯形表。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：故人为添加两个单位向量，得到人工变量单纯形法数学模型：其其中中：M是是一一个个很很大大的的抽抽象象的的数数，不不需需要要给给出出具具体体的的数数值值，可可以以理理

8、解解为为它它能能大大于于给给定定的的任任何何一一个个确确定定数数值值；再再用用前前面面介介绍的单纯形法求解该模型，计算结果见下表。绍的单纯形法求解该模型，计算结果见下表。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4111-21100011-Mx63-4120-1103/2-Mx71-201000113-6M-1+M-1+3M0-M000 x4103-20100-1-Mx610100-11-21-1x3

9、1-20100011-1+M00-M0-3M+1在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法Cj3-1-100-M-MCBXBbx1x2x3x4x5x6x70 x4123001-22-54-1x210100-11-2-1x31-2010001Z-21000-1-M+1-M-13x141001/3-2/32/3-5/3-1x210100-11-2-1x390012/3-4/34/3-7/3Z2000-1/3-1/3-M+1/3-M+2/3在整堂课的教学中，刘教师总是让学生带

10、着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法 用计算机处理数据时，只能用很大的数代替用计算机处理数据时，只能用很大的数代替M,可能造可能造成计算机上的错误，故多采用成计算机上的错误，故多采用两阶段法两阶段法。第一阶段：第一阶段：在原线性规划问题中加入人工变量，构造如下模型：在原线性规划问题中加入人工变量，构造如下模型：对上述模型求解（单纯形法），若对上述模型求解（单纯形法），若=0,说明问题存在基说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停可行解，可以进行第二个阶段；否则，原问题无可行解，

11、停止运算。止运算。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法第一阶段的线性规划问题可写为：第一阶段的线性规划问题可写为：第一阶段单纯形法迭代的过程见下表第一阶段单纯形法迭代的过程见下表在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法Cj00000-1-1CBXBbx1x2x3x4x5x6x70 x4111-21100011-1x63-4120-1103/2-1

12、x71-2010001146130-1000 x4103-20100-1-1x610100-11-210 x31-201000110100-10-30 x4123001-22-50 x210100-11-20 x31-2010000000000-1-1在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法 第二阶段：第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始系数换成原问题

13、的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。表（用单纯形法计算）。例：例：在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论两阶段法单纯形法的进一步讨论两阶段法cj3-1-100cBxBbx1x2x3x4x50 x4123001-24-1x210100-1-1x31-20100Z-21000-13x141001/3-2/3-1x210100-1-1x390012/3-4/3Z2000-1/3-1/3第二阶段：第二阶段：最优解为（最优解为（4 1 9 0 0），目标函数），目标函数 Z=2在整堂课的教学

14、中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论单纯形法的进一步讨论 通过大法或两阶段法求初始的基本可行解。但是通过大法或两阶段法求初始的基本可行解。但是如果在大法的最优单纯形表的基变量中仍含有人工变如果在大法的最优单纯形表的基变量中仍含有人工变量，或者两阶段法的辅助线性规划的目标函数的极小值量，或者两阶段法的辅助线性规划的目标函数的极小值大于零，那么该线性规划就不存在可行解。大于零，那么该线性规划就不存在可行解。无可行解无可行解 在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问

15、题也很明确C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0-M-M x4x7x8 643 1 1 1 1 0 0 0 01 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 6/1-3/1 Z-7M-6-4M-15-M -3+M -2+M -1-2M 0 -M -M 0 0 0-M-2 x4x7x2 343 1 0 2 1 0 1 0 -11 0 -1 0 -1 0 1 00 1 -1 0 0 -1 0 1 3/14/1-Z Z -3+M 0 -3-M 0 -M -2 0 2-M-3-M-2 x1x7x2 313

16、1 0 2 1 0 1 0 -10 0 -3 -1 -1 -1 1 10 1 -1 0 0 -1 0 1 0 0 3-3M 3-M -M 1-M 0 -1 例例单纯形法的进一步讨论单纯形法的进一步讨论运算到检验数全负为止，仍含有人工变量，无可行解。运算到检验数全负为止，仍含有人工变量，无可行解。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论单纯形法的进一步讨论 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指无可行解是指原规划不存在可行解

17、，从几何的角度解释是指 线性规划问题的可行域为空集；线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目无最优解则是指线性规划问题存在可行解，但是可行解的目 标函数达不到最优值，即目标函数在可行域内可以趋于无穷大标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。（或者无穷小）。无最优解也称为有限最优解，或无界解。判别方法：无最优解判别定理判别方法：无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应

18、的非基变量行存在某个大于零的检验数，但是该检验数所对应的非基变量 的的系数列向量的全部系数都为负数或零，则该线性规划问题系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解无最优解 无最优解无最优解在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因因 但但 所以原问题无最优解所以原问题无最优解单纯形法的进一步讨论单纯形法的进一步讨论在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深

19、，所提出的问题也很明确 退化退化 即计算出的即计算出的（用于确定换出变量）存在有两个以上（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基相同的最小比值，会造成下一次迭代中由一个或几个基变量等于零，这就是变量等于零，这就是退化退化（会产生退化解）。（会产生退化解）。为避免出现计算的循环，勃兰特为避免出现计算的循环，勃兰特(Bland)提出一个简提出一个简便有效的规则（摄动法原理）：便有效的规则（摄动法原理）：当存在多个当存在多个 时，选下标最小的非基变量为换时，选下标最小的非基变量为换入变量；入变量；(2)当当值出现两个以上相同的最小值时，选下标最小的值出现两个

20、以上相同的最小值时，选下标最小的基变量为换出变量。基变量为换出变量。单纯形法的进一步讨论单纯形法的进一步讨论在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确 无穷多最优解无穷多最优解 若若线线性性规规划划问问题题某某个个基基本本可可行行解解所所有有的的非非基基变变量量检检验验数数都都小小于于等等于于零零，但但其其中中存存在在一一个个检检验验数数等等于于零零，那那么么该该线性规划问题有无穷多最优解。线性规划问题有无穷多最优解。例：最优表：例：最优表：非基变量检验非基变量检验数数，所以有无穷多所以有无穷多最优解。最优解。C 1 2 0 0

21、 0CBXBb x1 x2 x3 x4 x5021x3x2x12320 0 1 2 -10 1 0 1 01 0 0 -2 12/23/1-Z8 0 0 0 0 -1单纯形法的进一步讨论单纯形法的进一步讨论在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单纯形法的进一步讨论单纯形法的进一步讨论解的判别：解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零）唯一最优解判别：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解。则线性规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零）多重最优解判别：

22、最优表中存在非基变量的检验数为零,则线性规划具有多重最优解（或无穷多最优解）。则线性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个）无界解判别：某个 k0且且aik（i=1，2,m）则线性）则线性规划具有无界解。规划具有无界解。4）无无可可行行解解的的判判断断：当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且存在且存在Ri0时，则表明原线性规划无可行解。时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。）退化解的判别：存在某个基变量为零的基本可行解。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，

23、所提出的问题也很明确单纯形法的进一步讨论单纯形法的进一步讨论单纯性法小结单纯性法小结:建建立立模模型型个个 数数取取 值值右端项右端项等式或等式或不等式不等式极大或极小极大或极小新加新加变量变量系数系数两两个个三三个个以以上上xj0 xj无无约束约束xj 0 bi 0bi 0=max Zmin Zxs xa求求解解图图解解 法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj=xj-xj xj 0 xj 0令令 xj=-xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1-1加加松松弛弛变变量量xs加加入入人人工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=-ZminZ=max z0-M在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确A A