运筹学--大M法和两阶段法.pptx

四、单纯形法的一般描述：四、单纯形法的一般描述：1、初始可行解的确定初始可行解的确定 (1)初始可行基的确定初始可行基的确定观察法观察法系数矩阵中是否含有现成的单位阵？系数矩阵中是否含有现成的单位阵？LP限制条件中全部是限制条件中全部是“”类型的约束类型的约束将将新新增增的的松松弛弛变变量量作作为为初初始始基基变变量量，对对应应的系数列向量构成单位阵；的系数列向量构成单位阵；先将约束条件标准化，再引入非负先将约束条件标准化，再引入非负的人工变量，的人工变量，以人工变量作为初始基变以人工变量作为初始基变量，其对应的系数列向量构成单位阵，量，其对应的系数列向量构成单位阵，称为称为“人造基人造基”；然后用大然后用大M法或两阶段法求解；法或两阶段法求解；线性规划限制条件都是线性规划限制条件都是“”或或“=”类型的约束类型的约束等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个使约束方程的系数矩阵中出现一个单位阵单位阵，用单位阵的每一个列向量对应用单位阵的每一个列向量对应的决策变量作为的决策变量作为“基变量基变量”，这样，出，这样，出现在单纯形表格中的现在单纯形表格中的B(i)列（即约束方程列（即约束方程的右边常数）值正好就是基变量的取值。的右边常数）值正好就是基变量的取值。(注意注意:用非基变量表示基变量的表达式用非基变量表示基变量的表达式)如果限制条件中既有如果限制条件中既有类型的约束，类型的约束，又有又有“”或或“=”类型的约束，怎麽办？类型的约束，怎麽办？构造构造“不完全的人造基不完全的人造基”！讨讨论论为什麽初始可行基一定要选为什麽初始可行基一定要选单位阵单位阵？b列正好就是列正好就是基变量的取值基变量的取值，检验数行，检验数行和和b列交叉处元素也正好对应列交叉处元素也正好对应目标函数值目标函数值，因此称因此称b列为列为解答列解答列（2）写出初始基本可行解）写出初始基本可行解根根据据“用用非非基基变变量量表表示示基基变变量量的的表表达达式式”，非非基基变变量量取取0，算算出出基基变变量量，搭搭配配在在一一起起构构成初始基本可行解成初始基本可行解。2、建立判别准则：、建立判别准则：（1）两个基本表达式的一般形式）两个基本表达式的一般形式LP限限制制条条件件中中全全部部是是“”类类型型约约束束，新新增增的的松松弛弛变变量量作作为为初初始始基基变变量量的的情情况况来来描描述：述：此时此时LP的标准型为的标准型为非基变量非基变量基变量基变量初始可行基初始可行基：初始基本可行解：初始基本可行解：一般（经过若干次迭代），对于基一般（经过若干次迭代），对于基B，用非基变量表出基变量的表达式用非基变量表出基变量的表达式为：为：用非基变量表示目标函数的表达式：用非基变量表示目标函数的表达式：若若是是对对应应于于基基B的的基基本本可可行行解解，是是非非基基变变量量的的检检验验数数，若若对对于于一一切切非非基基变变量量的的角角指指标标j，均均有有0，则则X(0)为最优解。为最优解。（2）最优性判别定理）最优性判别定理（3）无）无“有限最优解有限最优解”的判别定理的判别定理 若若为一基本可行解，有为一基本可行解，有一非基变量一非基变量xk,其检验数其检验数,而对于而对于i=1,2,，m，均有，均有，则该线性规划问题，则该线性规划问题没有没有“有限最优解有限最优解”。举例：用非基变量表示基变量的表达式举例：用非基变量表示基变量的表达式代表两个约束条件：代表两个约束条件：x2对应的系数列向量对应的系数列向量P2=（1，3）T，设：当前的换入变量是设：当前的换入变量是X2，按最小比，按最小比值原则确定换出变量：值原则确定换出变量：要求：要求：于是：于是：如果如果x2的系数列变成的系数列变成P2=（-1，0）T,则用非则用非基变量表示基变量的表达式就变成；基变量表示基变量的表达式就变成；可可行行性性自自然然满满足足,最最小小比比值值原原则则失失效效,意意即即x2的的值值可可以以任任意意增增大大原原线线性性规规划划无无“有有限限最最优优解解”。3、进行基变换、进行基变换（1）选选择择进进基基变变量量原原则则：正正检检验验数数（或或最最大大正正检检验验数数）所所对对应应的的变变量量进进基基，目目的的是是使目标函数得到改善（较快增大）使目标函数得到改善（较快增大）；进基变量对应的系数列称为进基变量对应的系数列称为主元列主元列。（2）出出基基变变量量的的确确定定按按最最小小比比值值原原则则确确定出基变量定出基变量，为的是保持解的可行性为的是保持解的可行性；出基变量所在的行称为出基变量所在的行称为主元行主元行。主元行和主元列的交叉元素主元行和主元列的交叉元素称为称为主元素主元素。4、主元变换（旋转运算或枢运算）、主元变换（旋转运算或枢运算）按按照照主主元元素素进进行行矩矩阵阵的的初初等等行行变变换换把把主主元元素素变变成成1，主主元元列列的的其其他他元元素素变变成成0（即主元列变为单位向量）（即主元列变为单位向量）写出新的基本可行解，返回最优性检验写出新的基本可行解，返回最优性检验。例例1.8的表格单纯形法计算过程：的表格单纯形法计算过程：表格单纯形法求解步骤表格单纯形法求解步骤第一步：将第一步：将LP化为标准型，化为标准型，并加以整理。并加以整理。引入适当的松驰变量、剩余变量和人工变引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，量，使约束条件化为等式，并且约束方程组的并且约束方程组的系数阵中有一个单位阵。系数阵中有一个单位阵。（这一步计算机可自动完成）（这一步计算机可自动完成）确定初始可行基，写出初始基本可行解确定初始可行基，写出初始基本可行解第二步：最优性检验第二步：最优性检验计算检验数，检查：计算检验数，检查：所有检验数是否所有检验数是否0？是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；还有正检验数还有正检验数检查相应系数列检查相应系数列0？是是结束，该结束，该LP无无“有限最优解有限最优解”！不属于上述两种情况不属于上述两种情况，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变换？选择（最大）选择（最大）正检验数正检验数对应的系数列对应的系数列为为主元列主元列，主元列对应的非基变量为，主元列对应的非基变量为换换入变量；入变量；最小比值对应的行为最小比值对应的行为主元行主元行，主元行，主元行对应的基变量为对应的基变量为换出变量换出变量。第三步：基变换第三步：基变换确定进基变量和出基变量。确定进基变量和出基变量。利用矩阵的利用矩阵的初等行变换初等行变换把把主元列变成单主元列变成单位向量，主元素变为位向量，主元素变为1，进基变量对应的进基变量对应的检验数变成检验数变成0，从而得到一张新的单纯形，从而得到一张新的单纯形表，返回第二步。表，返回第二步。第四步第四步换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解完成一次迭代，得到新的基本可行解和相应的目标函数值和相应的目标函数值该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止检验数行全部变为非正值；检验数行全部变为非正值；（得到最优解）得到最优解）或或主元列主元列0（最优解无界）（最优解无界）停止迭代的标志（停机准则）停止迭代的标志（停机准则）依据：最优性检验的两个定理依据：最优性检验的两个定理最优性判别定理；无最优性判别定理；无“有限最优解有限最优解”判断定理判断定理五、各种类型线性规划的处理五、各种类型线性规划的处理1、分类及处理原则：、分类及处理原则：（1）类类型型一一：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型左左边边加加上上非非负负松松弛弛变变量量变变成成等等式式约约束束（约约束束条条件件标标准准化化），将将引引入入的的松松弛弛变变量量作作为为初初始始基基变变量量，则则初初始始可可行行基基是是一一个个单单位位阵阵，用用原原始单纯形法求解。始单纯形法求解。（2）类类型型二二：目目标标要要求求是是“Max”，约约束束条条件件是是“=”类类型型左左边边引引入入非非负负的的人人工工变变量量，并并将将引引入入的的人人工工变变量量作作为为初初始始基基变变量量，则则初初始始可可行行基基是是一一个个单单位位阵，然后用大阵，然后用大M法或两阶段法求解。法或两阶段法求解。（3）类类型型三三：目目标标要要求求是是“Max”，约约束束条条件件是是“”类类型型约约束束条条件件标标准准化化，左左边边减减去去非非负负的的剩剩余余变变量量，变变成成等等式约束，化为类型二。式约束，化为类型二。2、处理人工变量的方法：、处理人工变量的方法：（1）大大M法法在在约约束束条条件件中中人人为为地地加加入入非非负负的的人人工工变变量量，以以便便使使它它们们对对应应的的系系数数列列向向量量构构成单位阵。成单位阵。问题：加入的人工变量是否合理？如何处理？问题：加入的人工变量是否合理？如何处理？在在目目标标函函数数中中，给给人人工工变变量量前前面面添添上上一一个个绝绝对对值值很很大大的的负负系系数数-M（M0），迭迭代代过过程程中中，只只要要基基变变量量中中还还存存在在人人工工变变量量，目目标标函函数数就就不不可能实现极大化可能实现极大化惩罚惩罚！最最优优表表中中，基基变变量量不不包包含含人人工工变变量量，则则最最优优解解就就是是原原线线性性规规划划的的最最优优解解，不不影影响响目目标标函数的取值；函数的取值；最最优优表表中中，基基变变量量中中仍仍含含有有人人工工变变量量，表表明明原原线线性性规规划划的的约约束束条条件件被被破破坏坏，线线性性规规划划没有可行解，也就没有最优解！没有可行解，也就没有最优解！结结果果问题问题结结果果中中求求得得的的最最优优解解是是哪哪个个线线性性规规划的最优解？为什麽？划的最优解？为什麽？大大M法举例法举例加入松弛变量、加入松弛变量、剩余变量和人剩余变量和人工变量：工变量：六、迭代过程中可能出现的问题及处理方法六、迭代过程中可能出现的问题及处理方法1、为为确确定定出出基基变变量量要要计计算算比比值值，该该比比值值=解解答答列列元元素素/主主元元列列元元素素。对对于于主主元元列列的的0元元素素或或负负元素是否也要计算比值？元素是否也要计算比值？（此此时时解解的的可可行行性性自自然然满满足足，不不必必计计算算；如如果果主主元元列列元元素素全全部部为为0元元素素或或负负元元素素，则则最最小小比比值值失效，线性规划无失效，线性规划无“有限最优解有限最优解”）2、出现若干个相同的最小比值怎麽办？、出现若干个相同的最小比值怎麽办？（说说明明出出现现了了退退化化的的基基本本可可行行解解，即即非非0分分量量的的个个数数小小于于约约束束方方程程的的个个数数。按按照照摄摄动动原原理理”所所得得的的规规则则，从从相相同同比比值值对对应应的的基基变变量量中中选选下下标标最最大大的的基基变变量量作作为为换换出出变变量量可可以以避避免免出出现现“死循环死循环”现象）现象）3、选选择择进进基基变变量量时时，同同时时有有若若干干个个正正检检验数，怎麽选？验数，怎麽选？（最最大大正正检检验验数数或或从从左左至至右右第第1个个出出现现的的正正检验数所对应的非基变量进基）检验数所对应的非基变量进基）（2）两阶段法两阶段法第第一一阶阶段段：建建立立辅辅助助线线性性规规划划并并求求解解，以判断原线性规划是否存在基本可行解。以判断原线性规划是否存在基本可行解。辅助线性规划的结构目标函数辅助线性规划的结构：目标函数W为所有为所有人工变量之和，目标要求是使目标函数极人工变量之和，目标要求是使目标函数极小化，约束条件与原线性规划相同。小化，约束条件与原线性规划相同。求解结果求解结果W最最优优值值=0即即所所有有人人工工变变量量取取值值全全为为0（为为什什麽麽？），均均为为非非基基变变量量，最最优优解解是是原原线性规划的一个基本可行解，转入第二阶段；线性规划的一个基本可行解，转入第二阶段；W最最优优值值=0但但人人工工变变量量中中有有等等于于0的的基基变变量量，构构成成退退化化的的基基本本可可行行解解，可可以以转转化化为为情情况况；如何转化？；如何转化？选一个不是人工变量的非基变量进基，选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来把在基中的人工变量替换出来W最最优优值值0至至少少有有一一个个人人工工变变量量取取值值0,说说明明基基变变量量中中至至少少有有1个个人人工工变变量量,表表明明原原问题没有可行解问题没有可行解,讨论结束。讨论结束。（1）+=+.21t sxxxMinZmnnn-=+.21tsxxxMaxZmnnn（2）试比较试比较（1）式目标要求改为极大化（或（）式目标要求改为极大化（或（2）式）式目标要求改为极小化）行不行？目标要求改为极小化）行不行？第二阶段：第二阶段：将将第第一一阶阶段段的的最最优优解解作作为为初初始始可可行行解解，目目标标函函数数换换成成原原问问题题的的目目标标函函数数，进进行行单单纯纯形迭代，求出最优解。形迭代，求出最优解。建立辅助线性规划问题得：建立辅助线性规划问题得：化成标准化成标准型，整理型，整理得：得：