运筹学单纯形法第部分.ppt

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

1、关于运筹学单纯形法第部分现在学习的是第1页，共40页 先将先将约束条件标准化约束条件标准化，再，再引入非负的引入非负的人工变量人工变量，以人工变量作为初始基变量以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为其对应的系数列向量构成单位阵，称为“人造基人造基”；然后用然后用大大M法法或或两阶段法两阶段法求解；求解；线性规划限制条件都是线性规划限制条件都是“”或或“=”类型的约束类型的约束现在学习的是第2页，共40页等式约束左端引入人工变量的目的等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个使约束方程的系数矩阵中出现一个单单位阵位阵，用单位阵的每一个列向量对应的决用单位

2、阵的每一个列向量对应的决策变量作为策变量作为“基变量基变量”，这样，出现在单，这样，出现在单纯形表格中的纯形表格中的B(i)列（即约束方程的右边列（即约束方程的右边常数）值正好就是基变量的取值。常数）值正好就是基变量的取值。（注意：注意：用非基变量表示基变量的表达式用非基变量表示基变量的表达式）现在学习的是第3页，共40页如果限制条件中既有如果限制条件中既有“”类型的约束，类型的约束，又有又有“”或或“=”类型的约束，怎麽办？类型的约束，怎麽办？构造构造“不完全的人造基不完全的人造基”！讨讨 论论为什麽初始可行基一定要选为什麽初始可行基一定要选单位阵单位阵？b列正好就是基变量的取值，列正好就是

3、基变量的取值，检验数行检验数行和和b列交叉处元素也正好对应目标函数值列交叉处元素也正好对应目标函数值，因此称因此称b列为列为解答列解答列现在学习的是第4页，共40页（2）写出初始基本可行解）写出初始基本可行解 根根据据“用用非非基基变变量量表表示示基基变变量量的的表表达达式式”，非非基基变变量量取取0，算算出出基基变变量量，搭搭配配在在一一起起构构成成初初始始基基本可行解本可行解。2、建立判别准则：、建立判别准则：（1）两个基本表达式的一般形式）两个基本表达式的一般形式 就就LP限限制制条条件件中中全全部部是是“”类类型型约约束束，新新增增的松弛变量作为初始基变量的情况来描述：的松弛变量作为初

4、始基变量的情况来描述：现在学习的是第5页，共40页此时此时LP的标准型为的标准型为 现在学习的是第6页，共40页初始可行基初始可行基：初始基本可行解：初始基本可行解：现在学习的是第7页，共40页 一般（经过若干次迭代），对于基一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式用非基变量表出基变量的表达式 为：为：用非基变量表示目标函数的表达式：用非基变量表示目标函数的表达式：现在学习的是第8页，共40页现在学习的是第9页，共40页 若若 是是对对应应于于基基B的的基基本本可可行行解解，是是非非基基变变量量 的的检检验验数数，若若对对于于一一切切非非基基变变量量的的角角指指标标j，均

5、均有有 0，则则X(0)为为最优解。最优解。（2）最优性判别定理）最优性判别定理（3）无）无“有限最优解有限最优解”的判别定理的判别定理 若若 为一基本可行解，有一为一基本可行解，有一非基变量非基变量xk,其检验数其检验数 ,而对于而对于i=1,2,，m，均有，均有 ，则该线性规划问题，则该线性规划问题没有没有“有有限最优解限最优解”。现在学习的是第10页，共40页证明思路证明思路构造性证明构造性证明：依依据据用用非非基基变变量量表表示示基基变变量量的的表表达达式式构构造造一一族族可可行解，其对应的目标函数值趋于无穷大行解，其对应的目标函数值趋于无穷大。几何意义几何意义：沿着无界边界前进的一族

6、可行解沿着无界边界前进的一族可行解现在学习的是第11页，共40页举例：举例：用非基变量表示基变量的表达式用非基变量表示基变量的表达式 代表两个约束条件：代表两个约束条件：x2对应的系数列向量对应的系数列向量P2=（1，3）T，当前的换入变量是当前的换入变量是 X2，按最小比值原则确定，按最小比值原则确定换出变量：换出变量：现在学习的是第12页，共40页要求：要求：于是：于是：如果如果x2的系数列变成的系数列变成P2=（-1，0）T,则用非基变则用非基变量表示基变量的表达式就变成；量表示基变量的表达式就变成；可可行行性性自自然然满满足足,最最小小比比值值原原则则失失效效,意意即即x2的的值值可可

7、以任意增大以任意增大原线性规划无原线性规划无“有限最优解有限最优解”。现在学习的是第13页，共40页 3、进行基变换、进行基变换（1）选选择择进进基基变变量量原原则则：正正检检验验数数（或或最最大大正正检检验验数数）所所对对应应的的变变量量进进基基，目目的的是是使使目目标函数得到改善（较快增大）标函数得到改善（较快增大）；进基变量对应的系数列称为进基变量对应的系数列称为主元列主元列。（2）出出基基变变量量的的确确定定按按最最小小比比值值原原则则确确定定出出基变量基变量，为的是保持解的可行性为的是保持解的可行性；出基变量所在的行称为出基变量所在的行称为主元行主元行。主元行和主元列的交叉元素主元行

8、和主元列的交叉元素称为称为主元素主元素。现在学习的是第14页，共40页思考题思考题 这样进行基变换后得到的新解对应的系数列向这样进行基变换后得到的新解对应的系数列向量是否线性独立？量是否线性独立？4、主元变换（旋转运算或枢运算）、主元变换（旋转运算或枢运算）按按照照主主元元素素进进行行矩矩阵阵的的初初等等行行变变换换把把主主元元素素变变成成1，主主元元列列的的其其他他元元素素变变成成0（即即主主元元列列变变为单位向量）为单位向量）写出新的基本可行解，返回最优性检验。写出新的基本可行解，返回最优性检验。现在学习的是第15页，共40页单纯形法小结单纯形法小结 求解思想求解思想 顶点的逐步转移，顶点

9、的逐步转移，条件是条件是 使目标函数值不断得到改善。使目标函数值不断得到改善。现在学习的是第16页，共40页表格单纯形法求解步骤表格单纯形法求解步骤第一步：第一步：将将LP化为标准型化为标准型，并加以整理。并加以整理。引入适当的松驰变量、剩余变量和人工变量，使引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，约束条件化为等式，并且约束方程组的系数阵中有并且约束方程组的系数阵中有一个单位阵。一个单位阵。（这一步计算机可自动完成）（这一步计算机可自动完成）确定初始可行基，写出初始基本可行解确定初始可行基，写出初始基本可行解现在学习的是第17页，共40页第二步：第二步：最优性检验最优性检验

10、计算检验数，检查：计算检验数，检查：所有检验数是否所有检验数是否 0？是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；还有正检验数还有正检验数检查相应系数列检查相应系数列 0？是是结束，该结束，该LP无无“有限最优解有限最优解”！不属于上述两种情况不属于上述两种情况，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？现在学习的是第18页，共40页 选择（最大）选择（最大）正检验数正检验数对应的系数列为对应的系数列为主元列主元列，主元列对应的非基变量为，主元列对应的非基变量为换入变量；换入变量；最小比值对应的行为最小比值对应

11、的行为主元行主元行，主元行主元行对对应的基变量为应的基变量为换出变量换出变量。第三步：第三步：基变换基变换确定进基变量和出基变量。确定进基变量和出基变量。现在学习的是第19页，共40页 利用矩阵的利用矩阵的初等行变换初等行变换把把主元列变成单位向主元列变成单位向量，主元素变为量，主元素变为1，进基变量对应的检验数变成进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。，从而得到一张新的单纯形表，返回第二步。第四步第四步 换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相应完成一次迭代，得到新的基本可行解和相应的目标函数值的目标函数值现在学习

12、的是第20页，共40页该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值；检验数行全部变为非正值；（得到最优解）得到最优解）或或主元列主元列 0 （最优解无界）（最优解无界）停止迭代的标志（停机准则）停止迭代的标志（停机准则）依据：最优性检验的两个定理依据：最优性检验的两个定理最优性判别定理；无最优性判别定理；无“有限最优解有限最优解”判断定理判断定理现在学习的是第21页，共40页计算机求解时的注意点计算机求解时的注意点1、输入数据中的分数，需输入数据中的分数，需先化为小数再执行输入过程先化为小数再执行输入过程先化为小数再执行输入过程先化为小数再执

13、行输入过程。2、每每一一张张迭迭代代表表格格中中由由基基变变量量列列（Basic）和和B(i)列列（解解答答列列）可可以以读读出出现现行行解解及及相相应应的的目目标标函函数数值值，同同时时显显示示进进基基变变量量和和出出基基变变量量，从从而而很很容容易易识识别别主主元元列列、主主元行和主元素。元行和主元素。3、最最终终表表显显示示最最优优解解、最最优优目目标标函函数数值值及及总总的的迭迭代代次次数数。如如遇遇该该线线性性规规划划无无可可行行解解或或无无“有有限限最最优优解解”，则则屏屏幕幕将将显示有关信息：显示有关信息：NO feasible solution.或或 *unbounded so

14、lution !现在学习的是第22页，共40页五、各种类型线性规划的处理五、各种类型线性规划的处理1、分类及处理原则：、分类及处理原则：（1）类类型型一一：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型左左边边加加上上非非负负松松弛弛变变量量变变成成等等式式约约束束（约约束束条条件件标标准准化化），将将引引入入的的松松弛弛变变量量作作为为初初始始基基变变量量，则则初初始始可可行行基基是一个单位阵是一个单位阵，用，用原始单纯形法原始单纯形法求解。求解。现在学习的是第23页，共40页（2）类类型型二二：目目标标要要求求是是“Max”，约约束束条条件件是是“=”类类型型左左边边引引

15、入入非非负负的的人人工工变变量量，并并将将引引入入的的人人工工变变量量作作为为初初始始基基变变量量，则则初初始始可可行行基基是是一一个个单单位位阵阵，然然后后用用大大M法或两阶段法法或两阶段法求解。求解。（3）类类型型三三：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型约约束束条条件件标标准准化化，左左边边减减去去非非负负的的剩剩余余变变量量，变变成成等等式式约约束束，化为类型二化为类型二。现在学习的是第24页，共40页（4）类型四：）类型四：目标要求是目标要求是“Min”方法方法1化为极大化问题化为极大化问题 方法方法2按照极小化问题直接在单纯按照极小化问题直接在单纯形表格

16、上计算处理，但形表格上计算处理，但 相应的原则要作改动相应的原则要作改动。现在学习的是第25页，共40页2、处理人工变量的方法：、处理人工变量的方法：（1）大大M法法在在约约束束条条件件中中人人为为地地加加入入非非负负的的人人工工变变量量，以以便便使使它它们们对对应应的的系系数数列列向向量量构构成成单单位阵。位阵。问题：加入的人工变量是否合理？如何处理？问题：加入的人工变量是否合理？如何处理？在在目目标标函函数数中中，给给人人工工变变量量前前面面添添上上一一个个绝绝对对值值很很大大的的负负系系数数-M（M0），迭迭代代过过程程中中，只只要要基基变变量量中中还还存存在在人人工工变变量量，目目标标

17、函函数数就就不不可可能能实实现现极极大大化化惩罚惩罚！现在学习的是第26页，共40页 最最优优表表中中，基基变变量量不不包包含含人人工工变变量量，则则最最优优解解就是原线性规划的最优解，不影响目标函数的取值；就是原线性规划的最优解，不影响目标函数的取值；最最优优表表中中，基基变变量量中中仍仍含含有有人人工工变变量量，表表明明原原线线性性规规划划的的约约束束条条件件被被破破坏坏，线线性性规规划划没没有有可可行解行解，也就，也就没有最优解没有最优解！结结 果果问题问题 结结果果中中求求得得的的最最优优解解是是哪哪个个线线性性规规划划的最优解？为什麽？的最优解？为什麽？现在学习的是第27页，共40页

18、（2）两阶段法两阶段法 第第一一阶阶段段：建建立立辅辅助助线线性性规规划划并并求求解解，以判断原线性规划是否存在基本可行解。以判断原线性规划是否存在基本可行解。辅助线性规划的结构：辅助线性规划的结构：目标函数目标函数W为所有为所有人工变量之和人工变量之和，目标要求是使，目标要求是使目标函数极小目标函数极小化化，约束条件与原线性规划相同。，约束条件与原线性规划相同。现在学习的是第28页，共40页 求解结果求解结果W最最优优值值=0即即所所有有人人工工变变量量取取值值全全为为0（为为什什麽麽？），均均为为非非基基变变量量，最最优优解解是是原原线线性性规规划的一个基本可行解，转入第二阶段；划的一个基

19、本可行解，转入第二阶段；W最最优优值值=0但但人人工工变变量量中中有有等等于于0的的基基变变量量，构构成成退退化化的的基基本本可可行行解解，可可以以转转化化为为情情况况；如如何何转化？转化？选一个不是人工变量的非基变量进基，选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来把在基中的人工变量替换出来现在学习的是第29页，共40页W最最优优值值0至至少少有有一一个个人人工工变变量量取取值值0,说说明明基基变变量量中中至至少少有有1个个人人工工变变量量,表表明明原原问问题题没有可行解没有可行解,讨论结束。讨论结束。问题讨论问题讨论教教材材P49辅辅助助线线性性规规划划的的结结构构是是：目

20、目标标函函数数W为为所所有有人人工工变变量量之之和和的的相相反反数数，目目标标要要求求是是使使目目标标函函数数极极大大化化，约约束束条条件件与与原原线线性性规规划划相相同同。这与上述的讨论这与上述的讨论是否矛盾？是否矛盾？现在学习的是第30页，共40页试比较：试比较：（1）（2）现在学习的是第31页，共40页（1）式目标要求改为极大化（或（）式目标要求改为极大化（或（2）式目）式目标要求改为极小化）行不行？标要求改为极小化）行不行？第二阶段：第二阶段：将将第第一一阶阶段段的的最最优优解解作作为为初初始始可可行行解解，目目标标函函数数换换成成原原问问题题的的目目标标函函数数，进进行行单单纯纯形形

21、迭迭代代，求求出最优解。出最优解。问问题题讨讨论论：如如何何实实 施施？需需要要重重新新建建立立初初始始单单纯形表吗？纯形表吗？现在学习的是第32页，共40页 实施中，在第一阶段最优表格中实施中，在第一阶段最优表格中划去人划去人工变量列工变量列，将表头部分和，将表头部分和CB列的价值系数列的价值系数换成原问题的价值系数换成原问题的价值系数(把目标函数换成把目标函数换成原线性规划的目标函数原线性规划的目标函数)，继续迭代，直，继续迭代，直至求出最优解。至求出最优解。在大在大M法中，当人工变量出基后能否法中，当人工变量出基后能否立立即划去即划去该人工变量所在的系数列该人工变量所在的系数列？现在学习

22、的是第33页，共40页3、用用表表格格单单纯纯形形法法直直接接计计算算极极小小化化线线性性规规划划时时要要修修改哪些原则？改哪些原则？（初初始始表表？最最优优解解判判别别？换换入入变变量量？换换出出变变量量？旋转运算？引入人工变量？）？旋转运算？引入人工变量？）最优性判别：最优性判别：所有检验数非负所有检验数非负 换换入入变变量量的的选选择择原原则则：（最最小小）负负检检验验数数所所对对应的变量进基应的变量进基，以保证目标函数值（较快）减小；，以保证目标函数值（较快）减小；用用大大M法法求求解解时时，在在目目标标函函数数中中人人工工变变量量的的前前面面添上一个很大的正系数添上一个很大的正系数M

23、；现在学习的是第34页，共40页六、迭代过程中可能出现的问题及处理方法六、迭代过程中可能出现的问题及处理方法1、为为确确定定出出基基变变量量要要计计算算比比值值，该该比比值值=解解答答列列元元素素/主主元元列列元元素素。对对于于主主元元列列的的0元元素素或负元素是否也要计算比值？或负元素是否也要计算比值？（此此时时解解的的可可行行性性自自然然满满足足，不不必必计计算算；如如果果主主元元列列元元素素全全部部为为0元元素素或或负负元元素素，则则最最小小比值失效比值失效，线性规划，线性规划无无“有限最优解有限最优解”）现在学习的是第35页，共40页2、现若干个相同的最小比值怎麽办？、现若干个相同的最

24、小比值怎麽办？（说说明明出出现现了了退退化化的的基基本本可可行行解解，即即非非0分分量量的的个个数数小小于于约约束束方方程程的的个个数数。按按照照“摄摄动动原原理理”所所得得的的规规则则，从从相相同同比比值值对对应应的的基基变变量量中中选选下下标标最最大大的的基基变变量作为换出变量量作为换出变量可以避免出现可以避免出现“死循环死循环”现象）现象）3、选选择择进进基基变变量量时时，同同时时有有若若干干个个正正检检验验数数，怎怎麽选？麽选？现在学习的是第36页，共40页（最最大大正正检检验验数数或或从从左左至至右右第第1个个出出现现的的正正检检验验数所对应的非基变量进基）数所对应的非基变量进基）课

25、堂练习课堂练习：直接按极小化问题求解下面的：直接按极小化问题求解下面的LP：现在学习的是第37页，共40页 CB XB cj xj b 1 2 0 0 M X1 X2 X3 X4 X5 M 0 X5 X4 2 3 -1 2 -1 0 1 1 0 0 1 0 2/2 _ -Z-2M 1+M M 0 2-2M 0 2 0 X2 X4 1 3-1/2 1 -1/2 0 1/2 1 0 0 1 0 -Z -2 2 0 1 0 M-1 j现在学习的是第38页，共40页由最优表得：由最优表得：最优解为最优解为X*=（0，1，0，3，0）T,相应的目标函数最优值为相应的目标函数最优值为Zmin=2现在学习的是第39页，共40页感感谢谢大大家家观观看看现在学习的是第40页，共40页