运筹学第一章 1.4 大M法和两阶段法

1、，用单位阵的每一个列向量对应用单位阵的每一个列向量对应的决策变量作为的决策变量作为“基变量基变量”，这样，出，这样，出现在单纯形表格中的现在单纯形表格中的b(i)列（即约束方列（即约束方程的右边常数）值正好就是基变量的取程的右边常数）值正好就是基变量的取值。值。 ( (注意注意: :用非基变量表示基变量的表达式用非基变量表示基变量的表达式) )构造构造“不完全的人造基不完全的人造基”！，（2）写出初始基本可行解）写出初始基本可行解根据根据“用非基变量表示基变量的表达式用非基变量表示基变量的表达式”，。 0,. .021221122222212111121211111mnmmnnmnmmnnnn

2、nnmnnjjnjjjxxxbxxaxaxabxxaxaxabxxaxaxatsxxcmaxz非基变量非基变量基变量基变量100010001),(21)0(mnnnpppb ： tmbbbx), 0 , 0 , 0 (21) 0(mixabxnjjijiin,2 , 1,1 njjjxzz10miijinjjjjacczc1), 0 , 0 , 0 (21) 0 (mbbbxj)0(jxj 若若为一基本可行解，有为一基本可行解，有一非基变量一非基变量xk,其检验数其检验数,而对于而对于i=1,2,，m，均有，均有，则该线性规划问题，则该线性规划问题。), 0 , 0 , 0 (21) 0(mb

3、bbx0k0ika432543216363xxxxxxxx代表两个约束条件：代表两个约束条件：663354324321xxxxxxxx06360343254321xxxxxxxx 于是：于是：如果如果x2的系数列变成的系数列变成p2=（-1，0）t,则用非则用非基变量表示基变量的表达式就变成；基变量表示基变量的表达式就变成；06060343254321xxxxxxxx可行性自然满足可行性自然满足,最小比值原则失效最小比值原则失效,意即意即x2的值的值可以任意增大可以任意增大原线性规划无原线性规划无“有限最优解有限最优解”。3/6 , 1/3min3/61/3222xxx 原则：原则：，；进基变

4、量对应的系数列称为进基变量对应的系数列称为。，；出基变量所在的行称为出基变量所在的行称为。称为称为。 表格单纯形法求解步骤表格单纯形法求解步骤第一步：将第一步：将lp化为标准型，化为标准型，引入适当的松驰变量、剩余变量和人工变引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，量，使约束条件化为等式，第二步：最优性检验第二步：最优性检验是是结束，写出最优解和目标函数最优值；结束，写出最优解和目标函数最优值；检查相应系数列检查相应系数列0？是是结束，该结束，该lp无无“有限最优解有限最优解”！，转入下一步，转入下一步基变换。基变换。确定是停止迭代还是转入基变换？确定是停止迭代还是转入基变

5、换？选择（最大）选择（最大）对应的系数列对应的系数列为为，主元列对应的非基变量为，主元列对应的非基变量为最小比值对应的行为最小比值对应的行为，主元行，主元行对应的基变量为对应的基变量为。确定进基变量和出基变量。确定进基变量和出基变量。利用矩阵的利用矩阵的把把，从而得到一张新的单纯形，从而得到一张新的单纯形表，返回第二步。表，返回第二步。换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算)完成一次迭代，得到新的基本可行解完成一次迭代，得到新的基本可行解和相应的目标函数值和相应的目标函数值该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止在约束条件中人为地加入非负在约束条件

6、中人为地加入非负的人工变量，以便使它们对应的系数列向量构的人工变量，以便使它们对应的系数列向量构成单位阵。成单位阵。在在，迭代过程中，迭代过程中，只要基变量中还存在人工变量，目标函数就不只要基变量中还存在人工变量，目标函数就不可能实现极大化可能实现极大化！结果结果中求得的最优解是哪个线性中求得的最优解是哪个线性规划的最优解？为什麽？规划的最优解？为什麽？大大m法举例法举例0,93124. .3max3213232132131xxxxxxxxxxxtsxxz加入松弛变量、加入松弛变量、剩余变量和人剩余变量和人工变量：工变量：0,93124. .376543217326532143217631xx

7、xxxxxxxxxxxxxxxxxtsmxmxxxmaxz1、为确定出基变量要计算比值，该比值、为确定出基变量要计算比值，该比值=解答解答列元素列元素/主元列元素。主元列元素。2、出现若干个相同的最小比值怎麽办？、出现若干个相同的最小比值怎麽办？（说明出现了退化的基本可行解，即非（说明出现了退化的基本可行解，即非0分量分量的个数小于约束方程的个数。按照的个数小于约束方程的个数。按照“摄动原理摄动原理”所得的规则，从相同比值对应的基变量中选下所得的规则，从相同比值对应的基变量中选下标最大的基变量作为换出变量可以避免出现标最大的基变量作为换出变量可以避免出现“死循环死循环”现象）现象）3、选择进基变量时，同时有若干个正检、选择进基变量时，同时有若干个正检验数，怎麽选？验数，怎麽选？选一个不是人工变量的非基变量进基，选一个不是人工变量的非基变量进基，把在基中的人工变量替换出来把在基中的人工变量替换出来（1）. .21t sxxxminzmnnn.21tsxxxmaxzmnnn（2） 建立辅助线性规划问题得：建立辅助线性规划问题得：0,10234