第二章单纯形法(编辑修改稿)

第二章单纯形法(编辑修改稿)内容摘要：

6 1 739。 39。 X = ( ,0 , , 0 , 0 )55T* 6 1 739。 39。 X = X = ( , 0 , , 0 , 0 )55T* 81Z=52B3B N 4N152 3 1 1 7xC = ( 3 ,5 )x 10 5 5 5 5X = ,X = x ,B = ,N = , ,b =C = ( 2 , 1 ,1 )x 0 1 6 1 2 6x5 5 5 5                     27 表格单纯形法 通过例１我们发现 ， 在单纯形法的求解过程中 ， 有下列重要指标：  每一个基本可行解的检验向量 根据检验向量可以确定所求得的基本可行解是否为最优解。 如果不是最优又可以通过检验向量确定合适的换入变量。  每一个基本可行解所对应的目标函数值 通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加 ， 直至求得最优目标函数为止。 在单纯形法求解过程中 ， 每一个基本可行解Ｘ都以 某个经过初等行变换的 约束方程组中的单位矩阵 Ι 为可行基。 当Ｂ =Ｉ时 ， Ｂ 1=Ｉ ， 易知： 1N N Bσ =C C B N1BZ = C B bN N Bσ =C C N BZ=C b28 可将这些重要结论的计算设计成如下一个简单的表格 ， 即单纯形表来完成： C CB CN θ CB XB b X1 X2 Xm X m+1 Xm+2 Xn C1 C2 . . Cm X1 X2 . Xm b1 b2 . . bm I N θ1 θ2 . . θm Z CBb 0 CN CBN 29 例 试利用单纯形表求例 1中的最优解解： 得初始的单纯形表： C =(5 ,2 , 3 , 1 , 1 )1 2 2 1 0 8( A b ) =3 4 1 0 1 71 2 3 4 51 2 3 41 2 3 51 2 3 4 5m a xZ =5x 2x 3x x xx 2x 2x x 83x 4x x x 7 x ,x ,x ,x ,x 0          N N Bσ =C C NBZ=C b 初始基本可行解 ， Z= 1， X=(0 ,0 ,0 , 8 , 7 ) T 1 2 2 1 0 8 x4 1 3 0 4 0 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 30 换入变量 ， 换出变量 ， ２为主元进行旋转变换 3x 4x基本可行解 ， Z= 15， X=(0 ,0 ,4 , 0 , 3 ) T1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 1 2 2 1 0 8 x4 1 3 0 4 0 0 1 Z 3 4 1 0 1 7 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 8/2 7/1 31 最优解 最优值 6 1 7X , 0 , , 0 , 055T   换入变量 ， 换出变量 ， ５ /２为主元进行旋转变换 1x 5xN N Bσ = C C N 0 81Z5 4/1/2 1/2 1 1 1/2 0 4 x3 3 1 4 0 2 0 15 Z 3/5/2 5/2 3 0 1/2 1 3 x5 1 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 0 2/5 1 3/5 1/5 17/5 x3 3 0 26/5 0 9/5 2/5 81/5 Z 1 6/5 0 1/5 2/5 6/5 x1 5 x1 x2 x3 x4 x5 b XB CB Θ 5 2 3 1 1 C 32 例 用单纯形方法求解线性规划问题 解：本题的目标函数是求极小化的线性函数， 可以令 则 这两个线性规划问题具有相同的可行域和最优解， 只是目标函数相差一个符号而已。 1213241 2 5jm inZ = x 2xx x 4x x 3x 2x x 8x 0 j 1,2 ,3,4 ,5   ，1239。 Z = Z = x + 2 x39。 1 2 1 2m inZ = x 2x m a x x + 2xZ33 0 1 0 1 0 3 x2 2 0 0 1 2 1 2 x3 0 0 1 0 1 0 3 x2 2 4/1 1 0 1 0 0 4 x3 0 3/1 0 1 0 1 0 3 x4 0 _ 1 0 1 0 0 4 x3 0 0 0 0 0 1 8 Z’ 1 0 0 2 1 2 x1 1 1 0 0 2 0 6 Z’ 2/1 1 0 0 2 1 2 x5 0 1 2 0 0 0 0 Z’ 8/2 1 2 0 0 1 8 x5 0 x1 x2 x3 x4 x5 b XB CB Θ 1 2 0 0 0 C 最优解 最优值  X 2 , 3 , 2 , 0 , 0 T  39。 m a xZ = 8 o r m i nZ = 82/2 3/1 34 因为非基变量 x4的检验数 σ 4=0， 由无穷多最优解判别定理 ， 本例的线性规划问题存在无穷多最优解。 事实上若以 x4为换入变量 ， 以 x3为换出变量 ， 再进行一次迭代 ， 可得一下单纯形表： 最优解 最优值 最优解的一般表示式 39。 m a xZ = 8 o r m i nZ = 8 X 4 , 2 , 0 , 1 , 0 T  X ( 2 , 3 , 2 , 0 , 0 ) ( 1 ) 4 , 2 , 0 , 1 , 0 , 0 1 .TT       C 1 2 0 0 0 Θ CB XB b x1 x2 x3 x4 x5 0 2 1 x4 x2 x1 1 2 4 0 0 1/2 1 1/2 0 1 1/2 0 1/2 1 0 1 0 0 Z’ 8 0 0 0 0 1 35 对于极小化的线性规划问题的处理：  先化为标准型 ， 即将极小化问题变换为极大化问题 ， 然后利用单 纯形方法求解 ．  直接利用单纯形方法求解 ， 但是检验是否最优的准则有所不同 ， 即： 若某个基本可行解的所有非基变量对应的检验数 （ 而不是 ≤ ０ ） ， 则基本可行解为最优解 ． 否则采用最大减少原则 （ 而非最大增加原则 ） 来确定换入变量 ， 即： 若 则选取对应的非基变量 xm+k为换入变量．  确定了换入变量以后，换出变量仍采用最小比值原则来确定。 N N Bσ = C C N 0 j j m + km in σ /σ 0 ,m + 1 j n = σ36 借助人工变量求初始的基本可行解 若约束方程组含有 “ ≥ ” 不等式 ， 那么在化标准形时除了在方程式左端减去剩余变量 ， 还必须在左端加上一个非负的人工变量。 因为人工变量是在约束方程已为等式的基础上 ， 人为的加上去的一个新变量 ， 因此 加入人工变量后的约束方程组与原约束方程组是不等价的。 加上人工变量以后 ， 线性规划的基本可行解不一定是原线性规划的问题的基本可行解。 只有当基本可行解中所有人工变量都为取零值的非基变量时 ， 该基本可行解对原线性规划才有意义。 因为此时只需去掉基本可行解中的人工变量部分 ， 剩余部分即为原线性规划的一个基本可行解 ． 而这正是我们引入人工变量的主要目的。 37 考虑线性规划问题： 为了在约束方程组的系数矩阵中得到一个 m阶单位矩阵作为 初始可行基 ， 在每个约束方程组的左端加上一个人工变量 可得到： njjj= 1ni j j ij= 1jm a xZ = c x a x = b , i=1 ,2 ,. .. ,m x 0, j=1 ,2 ,. .. ., n n+ ix ( i=1 ,2 , m )njjj= 1ni j j n+ i ij= 1jm a x Z = c x a x + x = b , i= 1 ,2 ,. .. ,m x 0 ,j= 1 ,2 ,. .. ., n + m 38 ———————————————————————— 添加了 m个人工变量以后 ， 在系数矩阵中得到一个 m阶单位矩阵 ，以该单位矩阵对应的。