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

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

2、非基变量表示基变量的表达式”， 。 2021/3/116 0, . . 0 21 2211 222222121 111212111 11 mn mmnnmnmm nnn nnn mn nj j n j jj xxx bxxaxaxa bxxaxaxa bxxaxaxa ts xxcMaxZ 非基变量非基变量基变量基变量 2021/3/117 100 010 001 ),( 21 )0( mnnn PPPB ： T m bbbX), 0 , 0 , 0 ( 21 ) 0( 2021/3/118 mixabx n j jijiin ,2 , 1, 1 n j jjx ZZ 1 0 m i ijin

3、jjjj acczc 1 2021/3/119 ), 0 , 0 , 0 ( 2 1 ) 0 ( m bbbX j )0( j x j 若若为一基本可行解，有为一基本可行解，有 一非基变量一非基变量xk,其检验数其检验数,而对于而对于 i=1,2,，m，均有，均有，则该线性规划问题，则该线性规划问题 。 ), 0 , 0 , 0 ( 2 1 ) 0( m bbbX 0 k 0 ik a 2021/3/1110 4325 4321 636 3 xxxx xxxx 代表两个约束条件：代表两个约束条件： 663 3 5432 4321 xxxx xxxx 2021/3/1111 0636 03 43

4、25 4321 xxxx xxxx 于是：于是： 如果如果x2的系数列变成的系数列变成P2=（-1，0）T,则用非则用非 基变量表示基变量的表达式就变成；基变量表示基变量的表达式就变成； 0606 03 4325 4321 xxxx xxxx 可行性自然满足可行性自然满足,最小比值原则失效最小比值原则失效,意即意即x2的值的值 可以任意增大可以任意增大原线性规划无原线性规划无“有限最优解有限最优解”。 3/6 , 1/3min 3/6 1/3 2 2 2 x x x 2021/3/1112 原则：原则： ， ； 进基变量对应的系数列称为进基变量对应的系数列称为。 ，； 出基变量所在的行称为出基

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

6、停止迭代还是转入基变换？ 2021/3/1116 选择（最大）选择（最大）对应的系数列对应的系数列 为为，主元列对应的非基变量为，主元列对应的非基变量为 最小比值对应的行为最小比值对应的行为，主元行，主元行 对应的基变量为对应的基变量为。 确定进基变量和出基变量。确定进基变量和出基变量。 2021/3/1117 利用矩阵的利用矩阵的把把 ， ，从而得到一张新的单纯形，从而得到一张新的单纯形 表，返回第二步。表，返回第二步。 换基迭代（旋转运算、枢运算换基迭代（旋转运算、枢运算) 完成一次迭代，得到新的基本可行解完成一次迭代，得到新的基本可行解 和相应的目标函数值和相应的目标函数值 2021/3

7、/1118 该迭代过程直至下列情况之一发生时停止该迭代过程直至下列情况之一发生时停止 2021/3/1119 2021/3/1120 2021/3/1121 在约束条件中人为地加入非负在约束条件中人为地加入非负 的人工变量，以便使它们对应的系数列向量构的人工变量，以便使它们对应的系数列向量构 成单位阵。成单位阵。 在在， ，迭代过程中，迭代过程中， 只要基变量中还存在人工变量，目标函数就不只要基变量中还存在人工变量，目标函数就不 可能实现极大化可能实现极大化！ 2021/3/1122 结果结果中求得的最优解是哪个线性中求得的最优解是哪个线性 规划的最优解？为什麽？规划的最优解？为什麽？ 202

8、1/3/1123 大大M法举例法举例 0, 93 12 4 . . 3max 321 32 321 321 31 xxx xx xxx xxx ts xxZ 加入松弛变量、加入松弛变量、 剩余变量和人剩余变量和人 工变量：工变量： 0, 93 12 4 . . 3 7654321 732 65321 4321 7631 xxxxxxx xxx xxxxx xxxx ts MxMxxxMaxZ 2021/3/1124 1、为确定出基变量要计算比值，该比值、为确定出基变量要计算比值，该比值=解答解答 列元素列元素/主元列元素。主元列元素。 2021/3/1125 2、出现若干个相同的最小比值怎麽办

9、？、出现若干个相同的最小比值怎麽办？ （说明出现了退化的基本可行解，即非（说明出现了退化的基本可行解，即非0分量分量 的个数小于约束方程的个数。按照的个数小于约束方程的个数。按照“摄动原理摄动原理” 所得的规则，从相同比值对应的基变量中选下所得的规则，从相同比值对应的基变量中选下 标最大的基变量作为换出变量可以避免出现标最大的基变量作为换出变量可以避免出现 “死循环死循环”现象）现象） 3、选择进基变量时，同时有若干个正检、选择进基变量时，同时有若干个正检 验数，怎麽选？验数，怎麽选？ 2021/3/1126 2021/3/1127 选一个不是人工变量的非基变量进基，选一个不是人工变量的非基变量进基， 把在基中的人工变量替换出来把在基中的人工变量替换出来 2021/3/1128 （1） . . 21 t s xxxMinZmnnn . 21 ts xxxMaxZmnnn （2） 2021/3/1129 2021/3/1130 建立辅助线性规划问题得：建立辅助线性规划问题得： 0, 1023