运筹学电子教案-LP单纯形法、表

1、1,线性规划Linear Programming（LP）基本理论,线性规划的标准型 定义： max z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 s. t. 其中bj0， j =（1，2，n） am1x1 + am2x2 + amnxn = bm xj 0 （j=1，2 n） 将一般线性规划问题化为标准型 1、maxmin 2、不等式约束等式约束 3、自由变量（无非负约束）xj0 （非负约束） 注意：以上转化是等价的，即转化后的标准型与原线性规划问题同 解,2,线性规划Linear

2、Programming（LP）基本理论,可行解 满足所有约束条件的向量 X =（x1，x2，xn）T 可行域 全部可行解的集合 最优解 使目标函数达到极值的可行解 唯一最优解 有唯一可行解使目标函数达到极值 无穷多最优解 有无穷多可行解使目标函数达到极值 无界最优解 存在可行解使目标函数值Z M（M是任意大 的正数） 有界最优解 存在可行解使目标函数值Z M（M是任意大 的正数） 基矩阵B 满秩系数矩阵A（n m）的任一个mm满秩子矩阵 即由矩阵A的任意m列线性无关的列向量构成的矩阵 非基矩阵N 即由矩阵A去掉B的m列所余下的n-m列向量构成的 矩阵,3,线性规划Linear Programm

3、ing（LP）基本理论,基向量 基矩阵B的向量pi=（a1i，a2i，ami）T i =1，2，m 非基向量 非基矩阵N的向量pj=（a1j，a2j，amj ）T j = m+1， n-m 基变量 与基向量pi对应的变量xi xB=（x1，x2，xm）T 非基变量 与非基向量pj对应的变量xj xN=（xm+1，xn-m）T 基本解 在约束条件AX = b中不妨设基矩阵B是A的前m个列向 量。于是AX = b可改写为： B xB + N xN = b，然后令 xN =0，即可解得xB= B -1 b， 则X=（ xB ， xN ）T=（ B -1 b， 0）T ，称为对应基矩 阵B的基本解 基

4、本可行解 若基本解中B -1 b0，则称其为对应B的基本可行解 凸集 这样的点集合-其集合中任意两点的连线上的全部点 都在该点集合内,4,线性规划Linear Programming（LP）基本理论,极点（顶点） 凸集上不在两个不同点的连线上的点 线性规划基本定理 1 线性规划所有可行解组成的集合S=X| AX = b， X 0是凸集 线性规划基本定理 2 X是线性规划问题的基本可行解的充要条件是 X为凸集S=X| AX = b，X 0的极点 线性规划基本定理 3 给定线性规划问题， A是秩为m的mn矩阵， （i） 若线性规划问题存在可行解，则必存在基本可行解 （ii） 若线性规划问题存在有界

5、最优解，则必存在有界最 优基 本可行解,5,线性规划Linear Programming（LP）基本理论,线性规划的标准型的向量和矩阵表达形式 向量式： 矩阵式： max Z=c1x1+c2x2+cnxn max Z=CX s.t. p1x1+p2x2+pnxn=b s.t. AX = b xj0 （j=1，2，n） X 0 式中：pj=（a1j，a2j，amj）T C =（c1，c2，cn） a11 a12 a1n X =（x1，x2，xn）T A= a21 a22 a2n b =（b1，b2，bm）T am1 am2 amn,6,单纯形方法是Dantzig于1947年首先发明的。近50年来

6、，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本算法。 单纯形法的初步讨论 例1.8 求解LP问题 Max Z=50X1+30X2 s.t. 4X1+3X2 120 2X1+ X2 50 X1，X2 0 （1. 17）,线性规划Linear Programming（LP）单纯形法、单纯形表,7,线性规划Linear Programming（LP）单纯形法、单纯形表,单纯形方法由以下步骤构成： 将原问题转化为标准型模型： Max Z=50X1+30X2 s.t. 4X1+3X2+X3 =120 2X1+ X2+ X4= 50 X1，X2，X3，X

7、40 （1.18） 此线性规划问题转化为了一个含有四个变量的线性规划问题，X3，X4为松弛变量（或剩余变量）。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使 Z 取得Max的X1，X2，X3，X4的值，由此分析如下-,8,线性规划Linear Programming（LP）单纯形法、单纯形表,确定初始基可行解： 通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此 取：X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为 Max Z =50X1+30X2 s.t. X3 = 120 - 4X1- 3X2 X4= 50 -

8、2X1- X2 （1.19） X1，X2，X3，X40 （1.19）称为关于基的典式 1、等式约束条件中显含基可行解 2、目标函数中不含基变量,9,线性规划Linear Programming（LP）单纯形法、单纯形表,在典式（1.19）中令： X1=X2 =0， 我们得到一个基本可行解 X1 =（ X1，X2，X3，X4 ）T=（0，0，120，50）T ，其对应的目标函数值 Z1 = 50X1 + 30X2 = 0 最优性检验： 基本可行解 X0是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，表明目标函数值有增加

9、的可了可能。只要将目标函数中系数为正的某非基变量与某一基变量地位对换。 换基迭代： 进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足： 1、新的解仍是基本可行解； 2、目标函数值将得到改善。,10,线性规划Linear Programming（LP）单纯形法、单纯形表,选择入基变量： 由于在目标函数Z1=50X1+30X2 中X1，X2的系数都为 正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化 的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。 选择出基变量： X1入基后，其值从零增加并由于约束条件的原因会引 起其他变量的变化。

10、由典式（1.19）以及变量必须取正值的条件，我 们可以得到下列不等式关系： X3 = 120 - 4X1- 3X2 0 X4= 50 - 2X1- X2 0 因为迭代后X2仍为非基变量（仍会令其取值为零），则上式可简化为： 120 - 4X1 0 由此可以看出，虽然我们希望X1入基后取正值，且 50 - 2X1 0 取值越大目标值增加越大，但是，X1又得受到约束。 显然，只有取X1 =min（120/4，50/2）=25时，才能使上述不等式成立 并且恰使基变量X4变为零，这正好满足非基变量必须取值零的条件，,11,线性规划Linear Programming（LP）单纯形法、单纯形表,所以可令

11、X4出基，新的典式方程变为： 4X1+ X3 =120- 3X2 2X1 = 50- X2 - X4 化简后得： X3 = 20- X2 + 2X4 X1 = 25-0.5X2 -0.5X4 代入目标函数可得： Z2 =1250+5X2-25X4 令非基变量X2 =X4 = 0，即可得一个新的基本可行解 X2 =（ 25，0，20，0）T ，其对应的目标函数值Z2 =1250，并完成了第一次迭代。 由于目标函数 Z2 =1250+5X2-25X4中X2的系数仍为正，该解X2仍不是 最优解。重复上述迭代过程得到：X2入基，X3出基，则新的典式变为： X1 = 15 +0.5X3 - 1.5X4

12、X2 =20 - X3 + 2X4 Z3 =1350 -5X3 - 15X4,12,第三个基本可行解 X3 =（ 15，20，0，0）T，其对应的目标函数值Z3= 1350 。此时松弛变量 都是非基变量（取值为零），这表明资源已用 尽；并且目标函数值Z3 =1350 -5X3 - 15X4中非基变量X3，X4的系数全 为负值，说明目标函数已无法进一步改善，因此该解已是最优解。 单纯形法小结： 单纯形法是这样一种迭代算法如下图 当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是 线性规划问题的最优解，迭代结束。,X1 X2 X3 . Xk,Z1 Z2 Z3 . Zk,保持单调增,保

13、持可行性,保持可行性,保持可行性,保持可行性,保持单调增,保持单调增,保持单调增,线性规划Linear Programming（LP）单纯形法、单纯形表,13,对于给定的线性规划问题： max Z=c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn b1 a21x1 + a22x2 + a2nxn b2 对此问题添加m个松弛变量后 s. t. 可得下面线性规划问题并且是 am1x1 + am2x2 + amnxn bm 典式的形式。 xj 0 （j=1，2 n） max Z=c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn

14、+ xn+1 = b1 a21x1 + a22x2 + a2nxn + xn+2 = b2 s. t. am1x1 + am2x2 + amnxn + xn+m = bm xj 0 （j=1，2 n，n+1，n+2，n+m）,线性规划Linear Programming（LP）单纯形法、单纯形表,14,单纯形表： 将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表 表格中B -1b列即为基本可行解中基变量的值， rj行即为目标函数中各 变量的系数称其为检验数。 由单纯形表进行迭代： 选择Xj入基：当rj行中 选择Xi出基：当,cj= max cici 0,线性规划Linear Pro

15、gramming（LP）单纯形法、单纯形表,cB xB B -1 b x1 x2 xn xn+1 xn+1 xn+1 0 xn+1 b1 a11 a12 a1n 1 1 0 xn+1 b2 a21 a22 a2n 1 2 0 xn+1 bm am1 am2 amn 1 m rj c1 c2 cn 0 0 0,i = min bi/aijaij 0,15,换基迭代：当确定了入基变量Xj 、出基变量Xi后，以aij作为主元对单 纯形表进行初等行变换（取主运算），即将aij所在列除将 aij变换为1外的其余元素都变换为0。注意这种变换只能采 用初等行变换! 最优解检验： 1、 当迭代进行至某一步时，

16、rj行中所有检验数均小于等于零， 则迭代结束。表中当前所指基本可行解即为最优解。 2、 当迭代进行至某一步时，rj行中所有检验数均小于等于零， 且此时至少有一个非基变量所对应的检验数rk等于零，则 原线性规划问题有无穷多个最优解。 3、 当迭代进行至某一步时，rj行中至少有一个检验数rk大于零， 且该检验数对应的列中a1k，a2k，amk，均小于等于零，则 原线性规划问题最优解无界（ max Z +）。,线性规划Linear Programming（LP）单纯形法、单纯形表,16,线性规划Linear Programming（LP）单纯形法、单纯形表,单纯形方法的矩阵描述： 设线性规划问题 m

17、ax Z = CX max Z = CX + 0XS s.t. AX b s.t. AX + I XS = b （I 式） X 0 X ，XS 0 其中 b 0 ，I是mm单位矩阵。 对上面（I 式）经过迭代，并设最终的最优基矩阵为B（不妨设B为A的首m列，则将（I 式）改写后有,标准化,max Z = CBXB + CNXN + 0XS s.t. BXB + NXN + I XS = b XB ，XN，XS 0 （I 式）,max Z = CB B -1+（CN- CB B -1）XN - CB B -1XS s.t. XB + B -1NXN + B -1XS = b XB ，XN，XS

18、0 （B 式）,B 式中最优目标函数值Z*= CB B -1 ，检验数 CN- CB B -1 0， - CB B -1 0,单纯形方法迭代,17,单纯形方法的矩阵描述：,线性规划Linear Programming（LP）单纯形法、单纯形表,XB,XS,XN,XS,B-1b,b,N,I,CN,0,rj,XB,B,CB,对应I 式的单纯形表 I 表,XB,XB,XN,XS,B-1b,B-1b,B-1N,B-1,CN- CB B -1,- CB B -1,rj,XB,I,0,.,对应B 式的单纯形表 B 表,18,人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显 然的基本可行解（如松弛变量作为基变量的一个初始基 本可行解），这样我们就可以马上进入单纯形表的运算 步骤。然而，并非所有问题标准化之后我们都可得到 一个显然的初始基本可行解，这时就需