《运筹学单纯形法第部分精选课件.ppt》由会员分享，可在线阅读，更多相关《运筹学单纯形法第部分精选课件.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于运筹学单纯形法第部分第一页，本课件共有40页 先将先将约束条件标准化约束条件标准化，再，再引入非负的引入非负的人工变量人工变量，以人工变量作为初始基变量以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为其对应的系数列向量构成单位阵，称为“人造基人造基”；然后用然后用大大M法法或或两阶段法两阶段法求解；求解；线性规划限制条件都是线性规划限制条件都是“”或或“=”类型的约束类型的约束第二页，本课件共有40页等式约束左端引入人工变量的目的等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个使约束方程的系数矩阵中出现一个单单位阵位阵，用单位阵的每一个列向量对应的用单位阵的每一个
2、列向量对应的决策变量作为决策变量作为“基变量基变量”，这样，出现，这样，出现在单纯形表格中的在单纯形表格中的B(i)列（即约束方程列（即约束方程的右边常数）值正好就是基变量的取值。的右边常数）值正好就是基变量的取值。（注意：注意：用非基变量表示基变量的表达式用非基变量表示基变量的表达式）第三页，本课件共有40页如果限制条件中既有如果限制条件中既有“”类型的约束，类型的约束，又有又有“”或或“=”类型的约束，怎麽办？类型的约束，怎麽办？构造构造“不完全的人造基不完全的人造基”！讨讨 论论为什麽初始可行基一定要选为什麽初始可行基一定要选单位阵单位阵？b列正好就是基变量的取值，列正好就是基变量的取值
3、，检验数行检验数行和和b列交叉处元素也正好对应目标函数值列交叉处元素也正好对应目标函数值，因此称因此称b列为列为解答列解答列第四页，本课件共有40页（2）写出初始基本可行解）写出初始基本可行解 根根据据“用用非非基基变变量量表表示示基基变变量量的的表表达达式式”，非非基基变变量量取取0，算算出出基基变变量量，搭搭配配在在一一起起构构成成初初始始基本可行解基本可行解。2、建立判别准则：、建立判别准则：（1）两个基本表达式的一般形式）两个基本表达式的一般形式 就就LP限限制制条条件件中中全全部部是是“”类类型型约约束束，新新增增的的松弛变量作为初始基变量的情况来描述：松弛变量作为初始基变量的情况来
4、描述：第五页，本课件共有40页此时此时LP的标准型为的标准型为 第六页，本课件共有40页初始可行基初始可行基：初始基本可行解：初始基本可行解：第七页，本课件共有40页 一般（经过若干次迭代），对于基一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式用非基变量表出基变量的表达式 为：为：用非基变量表示目标函数的表达式：用非基变量表示目标函数的表达式：第八页，本课件共有40页第九页，本课件共有40页 若若 是是对对应应于于基基B的的基基本本可可行行解解，是是非非基基变变量量 的的检检验验数数，若若对对于于一一切切非非基基变变量量的的角角指指标标j，均均有有 0，则则X(0)为为最优解。
5、最优解。（2）最优性判别定理）最优性判别定理（3）无）无“有限最优解有限最优解”的判别定理的判别定理 若若 为一基本可行解，有一为一基本可行解，有一非基变量非基变量xk,其检验数其检验数 ,而对于而对于i=1,2,，m，均有，均有 ，则该线性规划问题，则该线性规划问题没有没有“有有限最优解限最优解”。第十页，本课件共有40页证明思路证明思路构造性证明构造性证明：依依据据用用非非基基变变量量表表示示基基变变量量的的表表达达式式构构造造一一族族可可行解，其对应的目标函数值趋于无穷大行解，其对应的目标函数值趋于无穷大。几何意义几何意义：沿着无界边界前进的一族可行解沿着无界边界前进的一族可行解第十一页
6、，本课件共有40页举例：举例：用非基变量表示基变量的表达式用非基变量表示基变量的表达式 代表两个约束条件：代表两个约束条件：x2对应的系数列向量对应的系数列向量P2=（1，3）T，当前的换入变量是当前的换入变量是 X2，按最小比值原则确定，按最小比值原则确定换出变量：换出变量：第十二页，本课件共有40页要求：要求：于是：于是：如果如果x2的系数列变成的系数列变成P2=（-1，0）T,则用非则用非基变量表示基变量的表达式就变成；基变量表示基变量的表达式就变成；可可行行性性自自然然满满足足,最最小小比比值值原原则则失失效效,意意即即x2的的值值可可以任意增大以任意增大原线性规划无原线性规划无“有限
7、最优解有限最优解”。第十三页，本课件共有40页 3、进行基变换、进行基变换（1）选选择择进进基基变变量量原原则则：正正检检验验数数（或或最最大大正正检检验验数数）所所对对应应的的变变量量进进基基，目目的的是是使使目目标函数得到改善（较快增大）标函数得到改善（较快增大）；进基变量对应的系数列称为进基变量对应的系数列称为主元列主元列。（2）出出基基变变量量的的确确定定按按最最小小比比值值原原则则确确定定出基变量出基变量，为的是保持解的可行性为的是保持解的可行性；出基变量所在的行称为出基变量所在的行称为主元行主元行。主元行和主元列的交叉元素主元行和主元列的交叉元素称为称为主元素主元素。第十四页，本课
8、件共有40页思考题思考题 这样进行基变换后得到的新解对应的系数列向这样进行基变换后得到的新解对应的系数列向量是否线性独立？量是否线性独立？4、主元变换（旋转运算或枢运算）、主元变换（旋转运算或枢运算）按按照照主主元元素素进进行行矩矩阵阵的的初初等等行行变变换换把把主主元元素素变变成成1，主主元元列列的的其其他他元元素素变变成成0（即即主主元元列列变变为单位向量）为单位向量）写出新的基本可行解，返回最优性检验。写出新的基本可行解，返回最优性检验。第十五页，本课件共有40页单纯形法小结单纯形法小结 求解思想求解思想 顶点的逐步转移，顶点的逐步转移，条件是条件是 使目标函数值不断得到改善。使目标函数
9、值不断得到改善。第十六页，本课件共有40页表格单纯形法求解步骤表格单纯形法求解步骤第一步：第一步：将将LP化为标准型化为标准型，并加以整理。并加以整理。引入适当的松驰变量、剩余变量和人工变量，引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，使约束条件化为等式，并且约束方程组的系数阵并且约束方程组的系数阵中有一个单位阵。中有一个单位阵。（这一步计算机可自动完成）（这一步计算机可自动完成）确定初始可行基，写出初始基本可行解确定初始可行基，写出初始基本可行解第十七页，本课件共有40页第二步：第二步：最优性检验最优性检验计算检验数，检查：计算检验数，检查：所有检验数是否所有检验数是否 0？
10、是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；还有正检验数还有正检验数检查相应系数列检查相应系数列 0？是是结束，该结束，该LP无无“有限最优解有限最优解”！不属于上述两种情况不属于上述两种情况，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？第十八页，本课件共有40页 选择（最大）选择（最大）正检验数正检验数对应的系数列为对应的系数列为主元列主元列，主元列对应的非基变量为，主元列对应的非基变量为换入变换入变量；量；最小比值对应的行为最小比值对应的行为主元行主元行，主元行主元行对对应的基变量为应的基变量为换出变量换出变
11、量。第三步：第三步：基变换基变换确定进基变量和出基变量。确定进基变量和出基变量。第十九页，本课件共有40页 利用矩阵的利用矩阵的初等行变换初等行变换把把主元列变成单位主元列变成单位向量，主元素变为向量，主元素变为1，进基变量对应的检验进基变量对应的检验数变成数变成0，从而得到一张新的单纯形表，返回，从而得到一张新的单纯形表，返回第二步。第二步。第四步第四步 换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解和相完成一次迭代，得到新的基本可行解和相应的目标函数值应的目标函数值第二十页，本课件共有40页该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之
12、一发生时停止 检验数行全部变为非正值；检验数行全部变为非正值；（得到最优解）得到最优解）或或主元列主元列 0 （最优解无界）（最优解无界）停止迭代的标志（停机准则）停止迭代的标志（停机准则）依据：最优性检验的两个定理依据：最优性检验的两个定理最优性判别定理；无最优性判别定理；无“有限最优解有限最优解”判断定理判断定理第二十一页，本课件共有40页计算机求解时的注意点计算机求解时的注意点1、输入数据中的分数，需输入数据中的分数，需先化为小数再执行输入过程先化为小数再执行输入过程先化为小数再执行输入过程先化为小数再执行输入过程。2、每每一一张张迭迭代代表表格格中中由由基基变变量量列列（Basic）和
13、和B(i)列列（解解答答列列）可可以以读读出出现现行行解解及及相相应应的的目目标标函函数数值值，同同时时显显示示进进基基变变量量和和出出基基变变量量，从从而而很很容容易易识识别别主主元元列列、主元行和主元素。主元行和主元素。3、最最终终表表显显示示最最优优解解、最最优优目目标标函函数数值值及及总总的的迭迭代代次次数数。如如遇遇该该线线性性规规划划无无可可行行解解或或无无“有有限限最最优优解解”，则则屏屏幕将显示有关信息：幕将显示有关信息：NO feasible solution.或或 *unbounded solution !第二十二页，本课件共有40页五、各种类型线性规划的处理五、各种类型线
14、性规划的处理1、分类及处理原则：、分类及处理原则：（1）类类型型一一：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型左左边边加加上上非非负负松松弛弛变变量量变变成成等等式式约约束束（约约束束条条件件标标准准化化），将将引引入入的的松松弛弛变变量量作作为为初初始始基基变变量量，则则初初始始可可行行基基是是一一个个单单位位阵阵，用用原原始始单单纯纯形形法法求解。求解。第二十三页，本课件共有40页（2）类类型型二二：目目标标要要求求是是“Max”，约约束束条条件件是是“=”类类型型左左边边引引入入非非负负的的人人工工变变量量，并并将将引引入入的的人人工工变变量量作作为为初初始始基基
15、变变量量，则则初初始始可可行行基基是是一一个个单单位位阵阵，然然后后用大用大M法或两阶段法法或两阶段法求解。求解。（3）类类型型三三：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型约约束束条条件件标标准准化化，左左边边减减去去非非负负的的剩剩余余变变量量，变变成成等等式式约约束，束，化为类型二化为类型二。第二十四页，本课件共有40页（4）类型四：）类型四：目标要求是目标要求是“Min”方法方法1化为极大化问题化为极大化问题 方法方法2按照极小化问题直接在单纯按照极小化问题直接在单纯形表格上计算处理，但形表格上计算处理，但 相应的原则要作改动相应的原则要作改动。第二十五页，本课
16、件共有40页2、处理人工变量的方法：、处理人工变量的方法：（1）大大M法法在在约约束束条条件件中中人人为为地地加加入入非非负负的的人人工工变变量量，以以便便使使它它们们对对应应的的系系数数列列向向量量构构成单位阵。成单位阵。问题：加入的人工变量是否合理？如何处理？问题：加入的人工变量是否合理？如何处理？在在目目标标函函数数中中，给给人人工工变变量量前前面面添添上上一一个个绝绝对对值值很很大大的的负负系系数数-M（M0），迭迭代代过过程程中中，只只要要基基变变量量中中还还存存在在人人工工变变量量，目目标标函函数数就就不不可可能能实实现极大化现极大化惩罚惩罚！第二十六页，本课件共有40页 最最优优
17、表表中中，基基变变量量不不包包含含人人工工变变量量，则则最最优优解解就就是是原原线线性性规规划划的的最最优优解解，不不影影响响目目标标函函数的取值；数的取值；最最优优表表中中，基基变变量量中中仍仍含含有有人人工工变变量量，表表明明原原线线性性规规划划的的约约束束条条件件被被破破坏坏，线线性性规规划划没没有有可可行解行解，也就，也就没有最优解没有最优解！结结 果果问题问题 结结果果中中求求得得的的最最优优解解是是哪哪个个线线性性规规划的最优解？为什麽？划的最优解？为什麽？第二十七页，本课件共有40页（2）两阶段法两阶段法 第第一一阶阶段段：建建立立辅辅助助线线性性规规划划并并求求解解，以判断原线
18、性规划是否存在基本可行解。以判断原线性规划是否存在基本可行解。辅助线性规划的结构：辅助线性规划的结构：目标函数目标函数W为所有为所有人工变量之和人工变量之和，目标要求是使，目标要求是使目标函数极目标函数极小化小化，约束条件与原线性规划相同。，约束条件与原线性规划相同。第二十八页，本课件共有40页 求解结果求解结果W最最优优值值=0即即所所有有人人工工变变量量取取值值全全为为0（为为什什麽麽？），均均为为非非基基变变量量，最最优优解解是是原原线线性规划的一个基本可行解，转入第二阶段；性规划的一个基本可行解，转入第二阶段；W最最优优值值=0但但人人工工变变量量中中有有等等于于0的的基基变变量量，构
19、构成成退退化化的的基基本本可可行行解解，可可以以转转化化为为情情况况；如何转化？如何转化？选一个不是人工变量的非基变量进基，选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来把在基中的人工变量替换出来第二十九页，本课件共有40页W最最优优值值0至至少少有有一一个个人人工工变变量量取取值值0,说说明明基基变变量量中中至至少少有有1个个人人工工变变量量,表表明明原原问问题没有可行解题没有可行解,讨论结束。讨论结束。问题讨论问题讨论教教材材P49辅辅助助线线性性规规划划的的结结构构是是：目目标标函函数数W为为所所有有人人工工变变量量之之和和的的相相反反数数，目目标标要要求求是是使使目目标标
20、函函数数极极大大化化，约约束束条条件件与与原原线线性性规规划相同。这与上述的讨论划相同。这与上述的讨论是否矛盾？是否矛盾？第三十页，本课件共有40页试比较：试比较：（1）（2）第三十一页，本课件共有40页（1）式目标要求改为极大化（或（）式目标要求改为极大化（或（2）式目标）式目标要求改为极小化）行不行？要求改为极小化）行不行？第二阶段：第二阶段：将将第第一一阶阶段段的的最最优优解解作作为为初初始始可可行行解解，目目标标函函数数换换成成原原问问题题的的目目标标函函数数，进进行行单单纯纯形形迭迭代代，求求出出最最优解。优解。问问题题讨讨论论：如如何何实实 施施？需需要要重重新新建建立立初初始始单
21、单纯纯形表吗？形表吗？第三十二页，本课件共有40页 实施中，在第一阶段最优表格中实施中，在第一阶段最优表格中划去划去人工变量列人工变量列，将表头部分和，将表头部分和CB列的价值列的价值系数系数换成原问题的价值系数换成原问题的价值系数(把目标函数把目标函数换成原线性规划的目标函数换成原线性规划的目标函数)，继续迭代，继续迭代，直至求出最优解。直至求出最优解。在大在大M法中，当人工变量出基后能否法中，当人工变量出基后能否立即划去立即划去该人工变量所在的系数列该人工变量所在的系数列？第三十三页，本课件共有40页3、用用表表格格单单纯纯形形法法直直接接计计算算极极小小化化线线性性规规划划时要修改哪些原
22、则？时要修改哪些原则？（初初始始表表？最最优优解解判判别别？换换入入变变量量？换换出出变变量量？旋转运算？引入人工变量？）旋转运算？引入人工变量？）最优性判别：最优性判别：所有检验数非负所有检验数非负 换换入入变变量量的的选选择择原原则则：（最最小小）负负检检验验数数所所对对应应的的变变量量进进基基，以以保保证证目目标标函函数数值值（较较快快）减减小；小；用用大大M法法求求解解时时，在在目目标标函函数数中中人人工工变变量量的的前面添上一个很大的正系数前面添上一个很大的正系数M；第三十四页，本课件共有40页六、迭代过程中可能出现的问题及处理方法六、迭代过程中可能出现的问题及处理方法1、为为确确定
23、定出出基基变变量量要要计计算算比比值值，该该比比值值=解解答答列列元元素素/主主元元列列元元素素。对对于于主主元元列列的的0元元素或负元素是否也要计算比值？素或负元素是否也要计算比值？（此此时时解解的的可可行行性性自自然然满满足足，不不必必计计算算；如如果果主主元元列列元元素素全全部部为为0元元素素或或负负元元素素，则则最最小小比比值值失失效效，线线性性规规划划无无“有有限限最最优优解解”）第三十五页，本课件共有40页2、现若干个相同的最小比值怎麽办？、现若干个相同的最小比值怎麽办？（说说明明出出现现了了退退化化的的基基本本可可行行解解，即即非非0分分量量的的个个数数小小于于约约束束方方程程的
24、的个个数数。按按照照“摄摄动动原原理理”所所得得的的规规则则，从从相相同同比比值值对对应应的的基基变变量量中中选选下下标标最最大大的的基基变变量量作作为为换换出出变变量量可可以以避避免免出出现现“死死循循环环”现象）现象）3、选选择择进进基基变变量量时时，同同时时有有若若干干个个正正检检验验数数，怎麽选？怎麽选？第三十六页，本课件共有40页（最最大大正正检检验验数数或或从从左左至至右右第第1个个出出现现的的正正检检验数所对应的非基变量进基）验数所对应的非基变量进基）课课堂堂练练习习：直直接接按按极极小小化化问问题题求求解解下下面面的的LP：第三十七页，本课件共有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第三十八页，本课件共有40页由最优表得：由最优表得：最优解为最优解为X*=（0，1，0，3，0）T,相应的目标函数最优值为相应的目标函数最优值为Zmin=2第三十九页，本课件共有40页感谢大家观看第四十页，本课件共有40页