单纯形法大M法求解线性规划问题.ppt

《单纯形法大M法求解线性规划问题.ppt》由会员分享，可在线阅读，更多相关《单纯形法大M法求解线性规划问题.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、班级：物流113 队员：陈祥娟 冯雪萍 张献献 李起平线性规划各种解的情况线性规划各种解的情况1n 大大M法法 大大M M法法首首先先将将线线性性规规划划问问题题化化为为标标准准型型。如如果果约约束束方方程程组组中中包包含含有有一一个个单单位位矩矩阵阵I I，那那么么已已经经得得到到了了一一个个初初始始可可行行基基。否否则则在在约约束束方方程程组组的的左左边边加加上上若若干干个个非非负负的的人人工工变变量量，使使人人工工变变量量对对应应的的系系数数列列向向量量与与其其它它变变量量的的系系数数列列向向量量共共同同构构成成一一个个单单位位矩矩阵阵。以以单单位位矩矩阵阵为为初初始基，即可求得一个初始

2、的基本可行解。始基，即可求得一个初始的基本可行解。为为了了求求得得原原问问题题的的初初始始基基本本可可行行解解，必必须须尽尽快快通通过过迭迭代代过过程程把把人人工工变变量量从从基基变变量量中中替替换换出出来来成成为为非非基基变变量量。为为此此可可以以在在目目标标函函数数中中赋赋予予人人工工变变量量一一个个绝绝对对值值很很大大的的负负系系数数-。这这样样只只要要基基变变量量中中还还存存在在人工变量，目标函数就不可能实现极大化。人工变量，目标函数就不可能实现极大化。以以后后的的计计算算与与单单纯纯形形表表解解法法相相同同，只只需需认认定定是是一一个个很很大大的的正正数数即即可可。假假如如在在单单纯

3、纯形形最最优优表表的的基基变变量量中中还还包包含含人人工工变变量量，则则说说明明原原问问题题无无可可行行解解。否否则则最最优优解解中中剔剔除除人人工工变变量量的的剩剩余余部部分分即即为为原原问问题题的的初初始基本可行解。始基本可行解。2n两阶段法两阶段法 两两阶阶段段法法引引入入人人工工变变量量的的目目的的和和原原则则与与大大M M法法相相同同，所所不不同同的的是是处理人工变量的方法。处理人工变量的方法。两阶段法的步骤：两阶段法的步骤：l 求求解解一一个个辅辅助助线线性性规规划划。目目标标函函数数取取所所有有人人工工变变量量之之和和，并并取取极极小小化化；约约束束条条件件为为原原问问题题中中引

4、引入入人人工工变变量量后后包包含含一一个个单单位位矩矩阵阵的的标标准准型型的约束条件。的约束条件。如如果果辅辅助助线线性性规规划划存存在在一一个个基基本本可可行行解解，使使目目标标函函数数的的最最小小值值等等于于零零，则则所所有有人人工工变变量量都都已已经经“离离基基”。表表明明原原问问题题已已经经得得了了一一个个初初始始的的基基本本可可行行解解，可可转转入入第第二二阶阶段段继继续续计计算算；否否则则说说明明原原问问题题没没有有可可行行解，可停止计算。解，可停止计算。l 求求原原问问题题的的最最优优解解。在在第第一一阶阶段段已已求求得得原原问问题题的的一一个个初初始始基基本本可可行行解的基础上

5、，继续用单纯形法求原问题的最优解解的基础上，继续用单纯形法求原问题的最优解3单纯形表与线性规划问题的讨论单纯形表与线性规划问题的讨论 n无可行解无可行解 通通过过大大法法或或两两阶阶段段法法求求初初始始的的基基本本可可行行解解。但但是是如如果果在在大大法法的的最最优优单单纯纯形形表表的的基基变变量量中中仍仍含含有有人人工工变变量量，或或者者两两阶阶段段法法的的辅辅助助线线性性规规划划的的目目标标函函数数的的极极小小值值大大于于零零，那那么么该该线线性性规规划划就就不不存存在可行解。在可行解。人人工工变变量量的的值值不不能能取取零零，说说明明了了原原线线性性规规划划的的数数学学模模型型的的约约束

6、束条条件件出出现现了了相相互互矛矛盾盾的的约约束束方方程程。此此时时线线性性规规划划问问题题的的可可行行域域为为空空集。集。4例例1 1、求解下列线性规划问题、求解下列线性规划问题解：解：首先将问题化为标准型首先将问题化为标准型令，则令，则 故引入人工变量，故引入人工变量，并利用大并利用大M M法求解法求解5C -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

7、-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 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 在在以以上上最最优优单单纯纯形形表表中中，所所有有非非基基变变量量检检验验数数都都小小于于零零，但但在在该该表表中中人人工变量工变量x7=1为基

8、变量，所以原线性规划不存在可行解。为基变量，所以原线性规划不存在可行解。6n无无界界解解 无最优解与无可行解时两个不同的概念。无最优解与无可行解时两个不同的概念。无可行解是指原规划不存在可行解，从几何的角度解释是指无可行解是指原规划不存在可行解，从几何的角度解释是指 线性规划问题的可行域为空集；线性规划问题的可行域为空集；无最优解则是指线性规划问题存在可行解，但是可行解的目无最优解则是指线性规划问题存在可行解，但是可行解的目 标标函函数数达达不不到到最最优优值值，即即目目标标函函数数在在可可行行域域内内可可以以趋趋于于无无穷穷大大（或者无穷小）。无最优解也称为有限最优解，或无界解。（或者无穷小

9、）。无最优解也称为有限最优解，或无界解。l判别方法：判别方法：无最优解判别定理无最优解判别定理在求解极大化的线性规划问题过程中，若某单纯形表的检验在求解极大化的线性规划问题过程中，若某单纯形表的检验 行存在某个大于零的检验数，但是该检验数所对应的非基变量行存在某个大于零的检验数，但是该检验数所对应的非基变量 的系数列向量的全部系数都为负数或零，则该线性规划问题的系数列向量的全部系数都为负数或零，则该线性规划问题 无最优解，无最优解，可以可以可以可以7例例2 2、试用单纯形法求解下列线性规划问题：、试用单纯形法求解下列线性规划问题：解：引入松弛变量解：引入松弛变量x x3 3,x,x4 4化为标

10、准型化为标准型C 2 2 0 0 CXB B x1 x2 x3 x4 0X3 1-11100X4 2-1/2101Z02200因因但但所以原问题所以原问题无最优解无最优解8n 退化解 当当线线性性规规划划问问题题的的基基本本可可行行解解中中有有一一个个或或多多个个基基变变量量取取零零值值时时，称此基本可行解为退化解。称此基本可行解为退化解。产产生生的的原原因因：在在单单纯纯形形法法计计算算中中用用最最小小比比值值原原则则确确定定换换出出变变量量时时，有有时时存存在在两两个个或或两两个个以以上上相相同同的的最最小小比比值值，那那么么在在下下次次迭迭代代中中就就会会出现一个甚至多个基变量等于零。出

11、现一个甚至多个基变量等于零。遇遇到到的的问问题题：当当某某个个基基变变量量为为零零，且且下下次次迭迭代代以以该该基基变变量量作作为为换换出出变变量量时时，目目标标函函数数并并不不能能因因此此得得到到任任何何改改变变（由由旋旋转转变变换换性性质质可可知知，任任何何一一个个换换入入变变量量只只能能仍仍取取零零值值，其其它它基基变变量量的的取取值值保保持持不不变变）。通通过过基基变变换换以以后后的的前前后后两两个个退退化化的的基基本本可可行行解解的的坐坐标标形形式式完完全全相相同同。从从几几何何角角度度来来解解释释，这这两两个个退退化化的的基基本本可可行行解解对对应应线线性性规规划划可可行行域域的同

12、一个顶点，的同一个顶点，解解决决的的办办法法：最最小小比比值值原原则则计计算算时时存存在在两两个个及及其其以以上上相相同同的的最最小小比比值值时时，选选取取下下标标最最大大的的基基变变量量为为换换出出变变量量，按按此此方方法法进进行行迭迭代代一一定定能避免循环现象的产生（摄动法原理）。能避免循环现象的产生（摄动法原理）。9例例3 3、求解下述线性规划问题：、求解下述线性规划问题：解：解：引入松弛变量引入松弛变量化标准型化标准型10000-242-8030Z-5-60-420-805Z10001001x3 212060-2411x1 3321300-803x5 00-30-425-800Z110

13、0 1001x7 00106-1-2410 x1 30-1130-3-800 x5 0-11001001x7 000106-1-2410 x6 0000136-4-3210 x5 0 x7 x6 x5 x4 x3 x2 x1 b XB CB 000-242-803C 第第一一次次迭迭代代中中使使用用了了摄摄动动法法原原理理，选选择择下下标标为为6的的基基变量变量x6离基。离基。可得最优解可得最优解 ，目标函数值，目标函数值maxZ=，11n 无穷多最优解无穷多最优解 无穷多最优解判别原理：无穷多最优解判别原理：若若线线性性规规划划问问题题某某个个基基本本可可行行解解所所有有的的非非基基变变量量检检验验数数都都小小于于等等于于零零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例例4：最优表：最优表：非基变量检验非基变量检验数，数，所以有无穷多所以有无穷多最优解。最优解。最优解集为可行域两个顶点的凸组合：最优解集为可行域两个顶点的凸组合：C1 2 0 0 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 -11213