《运筹学》课程教学资源（PPT课件讲稿）单纯形法的一般描述、各种类型线性规划的处理、迭代过程中可能出现的问题及处理方法

四、单纯形法的一般描述: 1、初始可行解的确定 (1)初始可行基的确定 观察法—观察系数矩阵中是否含有现 成的单位阵? LP限制条件中全部是“<”类型的约束一 将新增的松弛变量作为初始基变量, 对应的系数列向量构成单位阵;

四、单纯形法的一般描述： 1、 初始可行解的确定 (1)初始可行基的确定  观察法——观察系数矩阵中是否含有现 成的单位阵？  LP限制条件中全部是“≤”类型的约束— — 将新增的松弛变量作为初始基变量， 对应的系数列向量构成单位阵；

线性规划限制条件都是“≥”或 类型的约束 先将约束条件标准化,再引入非负 的人工变量,以人工变量作为初始基变 量,其对应的系数列向量构成单位阵, 称为“人造基”; 然后用大M法或两阶段法求解;

先将约束条件标准化，再引入非负 的人工变量， 以人工变量作为初始基变 量，其对应的系数列向量构成单位阵， 称为“人造基”； 然后用大M法或两阶段法求解；  线性规划限制条件都是“≥”或“=” 类型的约束——

等式束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个 卓位降,用单位阵的每一个列向量对 应的决策变量作为“基变量”,这样, 出现在单纯形表格中的B()列(即约 束方程的右边常数)值正好就是基变 量的取值。 (注意:用旅基变量表杀基变量的表达式)

等式约束左端引入人工变量的目的 使约束方程的系数矩阵中出现一个 单位阵，用单位阵的每一个列向量对 应的决策变量作为“基变量”，这样， 出现在单纯形表格中的B(i)列（即约 束方程的右边常数）值正好就是基变 量的取值。 （注意：用非基变量表示基变量的表达式）

讨论 ①如果限制条件中既有“≤”类型的约束, 又有“≥”或“=”类型的约束,怎麽办? 构造“不完全的人造基” ②为什麽初始可行基一定要选单位阵? b列正好就是基变量的取值,检验数行 和b列交叉处元素也正好对应目标函数值, 因此称b列为解答列

①如果限制条件中既有“≤”类型的约束， 又有“≥”或“=”类型的约束，怎麽办？ 构造“不完全的人造基”！ 讨 论 ②为什麽初始可行基一定要选单位阵？ b列正好就是基变量的取值，检验数行 和b列交叉处元素也正好对应目标函数值， 因此称b列为解答列

(2)写出初始基本可行解 根据“用旅基变量表杀基变量的森达式”, 罪基委量取0,算出基变量,搭配在一起构成 初始基本可行解。 2、建方判别准则: (1)两个基本表达式的一般形式 就LP限制条件中全部是“≤”类型约束,新 增的松弛变量作为初始基变量的情况来描述:

（2）写出初始基本可行解—— 根据“用非基变量表示基变量的表达式” ， 非基变量取0，算出基变量，搭配在一起构成 初始基本可行解。 2、建立判别准则： （1）两个基本表达式的一般形式 就LP限制条件中全部是“≤”类型约束，新 增的松弛变量作为初始基变量的情况来描述：

此时LP的标准型为 °Maxz=∑cx+∑0x J= n+1 C1xX1+C12X+…+a1x+x n+l=6 a2ix+a22x2+.+a2nxn+xn2=b2 amx+ am2 2 +…+amxn+xn+m=bn 152 ≥0 9~n+m

          + + + + = + + + + = + + + + = = + + + + + + = = +   , , , 0 . . 0 1 2 1 1 2 2 2 1 1 2 2 2 2 2 2 1 1 1 1 2 2 1 1 1 1 1 n m m m m n n n m m n n n n n n n m j n j n j j j x x x a x a x a x x b a x a x a x x b a x a x a x x b st MaxZ c x x        此时LP的标准型为

初始可行基: 01 B0)=(Pn1,Pn+2 9-n+m 00 初始基本可行解: X0=(0,0,…0,b,b2…,bn)

              = + + + = 0 0 1 0 1 0 1 0 0 ( , , , ) 1 2 (0)        B Pn Pn  Pn m 初始可行基 ： 初始基本可行解： T m X (0,0, ,0,b ,b , ,b ) 1 2 (0) =  

一般(经过若干次迭代),对于基B, 用旅墓变出基变量的彩达式为: b 1.2….m n+I 用旅基变量表示目标妈數的达式

一般（经过若干次迭代），对于基B， 用非基变量表出基变量的表达式 为： x b a x i m n j n i i i j j , 1,2 , 1 = ' − ' =  = + 用非基变量表示目标函数的表达式：

z=2=∑x+=∑+)∑ n+1 ∑cb+∑(c-∑cm4),。∑n1,:;=∑cm ∑(1-:-)x 0.=C.-2 +∑

                = = = + = + = + = = + = = + = = + = = + = = + + = + = = + = + − = − = + − = = = + − = = + = + − n j j j j j j j j n j j m i j n i i j m i n i i m i n i i j j n j j m i n i i m i n j n i i j j n j j j m i n i i m i n j n i i i j j n j j j m i n i n i n j j j n m j j j Z x Z c z x c z c b c c a x Z c b z c a c b c x c a x Z c x c x c x c x c b a x 1 0 1 0 1 ' 1 ' 1 0 ' 1 1 ' 1 1 ' 1 1 ' 1 1 ' ' 1 1 1 1 ( ) ( ) , ( )  令 令

(2)最优性判别定理 若x0=(000b,b2…,b)是对应于基B的基本可 行解,非基变量的检验数,若对于 切非基变量的角指标j,均有0,则X0 为最优解。 (3)无“有限最优解”的判别定理 若X 2,…,bn)为一基本可行解,有 非基变量x,其检验数a>0,而对于 i=1,2,,m,均有a,≤0,则该线性规划问题 没有“有限最优解

若 是对应于基B的基本可 行解， 是非基变量 的检验数，若对于 一切非基变量的角指标j，均有 ≤0，则X(0) 为最优解。 (0,0, ,0, , , , ) ' ' 2 ' 1 (0) m X =  b b  b  j (0) j x  j （2）最优性判别定理 （3）无“有限最优解”的判别定理 若 为一基本可行解，有 一非基变量xk ,其检验数 , 而对于 i=1,2,…，m，均有 ，则该线性规划问题 没有“有限最优解”。 (0,0, ,0, , , , ) ' ' 2 ' 1 (0) m X =  b b  b  0  k 0 ' aik 