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

1线性规划LinearProgramming（LP）基本理论线性规划的标准型定义：maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.…其中bj≥0，j=（1，2，…n）am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）将一般线性规划问题化为标准型1、max——min2、不等式约束——等式约束3、自由变量（无非负约束）——xj≥0（非负约束）注意：以上转化是等价的，即转化后的标准型与原线性规划问题同解2线性规划LinearProgramming（LP）基本理论可行解满足所有约束条件的向量X=（x1，x2，…，xn）T可行域全部可行解的集合最优解使目标函数达到极值的可行解唯一最优解有唯一可行解使目标函数达到极值无穷多最优解有无穷多可行解使目标函数达到极值无界最优解存在可行解使目标函数值∣Z∣≥M（M是任意大的正数）有界最优解存在可行解使目标函数值∣Z∣≥M（M是任意大的正数）基矩阵B满秩系数矩阵A（nm）的任一个mm满秩子矩阵即由矩阵A的任意m列线性无关的列向量构成的矩阵非基矩阵N即由矩阵A去掉B的m列所余下的n-m列向量构成的矩阵3线性规划LinearProgramming（LP）基本理论基向量基矩阵B的向量pi=（a1i，a2i，…，ami）Ti=1，2，…，m非基向量非基矩阵N的向量pj=（a1j，a2j，…，amj）Tj=m+1，…，n-m基变量与基向量pi对应的变量xixB=（x1，x2，…，xm）T非基变量与非基向量pj对应的变量xjxN=（xm+1，…，xn-m）T基本解在约束条件AX=b中不妨设基矩阵B是A的前m个列向量。于是AX=b可改写为：BxB+NxN=b，然后令xN=0，即可解得xB=B-1b，则X=（xB，xN）T=（B-1b，0）T，称为对应基矩阵B的基本解基本可行解若基本解中B-1b≥0，则称其为对应B的基本可行解凸集这样的点集合----其集合中任意两点的连线上的全部点都在该点集合内4线性规划LinearProgramming（LP）基本理论极点（顶点）凸集上不在两个不同点的连线上的点线性规划基本定理1线性规划所有可行解组成的集合S={X|AX=b，X≥0}是凸集线性规划基本定理2X是线性规划问题的基本可行解的充要条件是X为凸集S={X|AX=b，X≥0}的极点线性规划基本定理3给定线性规划问题，A是秩为m的mn矩阵，（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解5线性规划LinearProgramming（LP）基本理论线性规划的标准型的向量和矩阵表达形式向量式：矩阵式：maxZ=c1x1+c2x2+…+cnxnmaxZ=CXs.t.p1x1+p2x2+…+pnxn=bs.t.AX=bxj≥0（j=1，2，…n）X≥0式中：pj=（a1j，a2j，…，amj）TC=（c1，c2，…，cn）a11a12…a1nX=（x1，x2，…，xn）TA=a21a22…a2nb=（b1，b2，…，bm）T……………am1am2…amn6单纯形方法是Dantzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本算法。单纯形法的初步讨论例1.8求解LP问题MaxZ=50X1+30X2s.t.4X1+3X2≤1202X1+X2≤50X1，X2≥0（1.17）线性规划LinearProgramming（LP）单纯形法、单纯形表7线性规划LinearProgramming（LP）单纯形法、单纯形表单纯形方法由以下步骤构成：将原问题转化为标准型模型：MaxZ=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50X1，X2，X3，X4≥0（1.18）此线性规划问题转化为了一个含有四个变量的线性规划问题，X3，X4为松弛变量（或剩余变量）。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下---8线性规划LinearProgramming（LP）单纯形法、单纯形表确定初始基可行解：通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此取：X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为MaxZ=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0（1.19）称为关于基的典式——1、等式约束条件中显含基可行解2、目标函数中不含基变量9线性规划LinearProgramming（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前的系数都为正，表明目标函数值有增加的可了可能。只要将目标函数中系数为正的某非基变量与某一基变量地位对换。换基迭代：进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足：1、新的解仍是基本可行解；2、目标函数值将得到改善。10线性规划LinearProgramming（LP）单纯形法、单纯形表选择入基变量：由于在目标函数Z1=50X1+30X2中X1，X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快越好，因此系数最大的X1入基。选择出基变量：X1入基后，其值从零增加并由于约束条件的原因会引起其他变量的变化。由典式（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线性规划LinearProgramming（LP）单纯形法、单纯形表所以可令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X2=20-X3+2X4Z3=1350-5X3-15X412第三个基本可行解X3=（15，20，0，0）T，其对应的目标函数值Z3=1350。此时松弛变量都是非基变量（取值为零），这表明资源已用尽；并且目标函数值Z3=1350-5X3-15X4中非基变量X3，X4的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。单纯形法小结：单纯形法是这样一种迭代算法——如下图…当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。X1X2X3...XkZ1Z2Z3...Zk保持单调增保持可行性保持可行性保持可行性保持可行性保持单调增保持单调增保持单调增线性规划LinearProgramming（LP）单纯形法、单纯形表13对于给定的线性规划问题：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2对此问题添加m个松弛变量后s.t.…可得下面线性规划问题并且是am1x1+am2x2+…+amnxn≤bm典式的形式。xj≥0（j=1，2…n）maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn+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）线性规划LinearProgramming（LP）单纯形法、单纯形表14单纯形表：将上面典式中各变量及系数填写在一张表格中就形成下面的单纯形表表格中B-1b列即为基本可行解中基变量的值，rj行即为目标函数中各变量的系数称其为检验数。由单纯形表进行迭代：选择Xj入基：当rj行中选择Xi出基：当cj=maxci∣ci0线性规划LinearProgramming（LP）单纯形法、单纯形表cBxBB-1bx1x2…xnxn+1xn+1…xn+10xn+1b1a11a12…a1n110xn+1b2a21a22…a2n12……………0xn+1bmam1am2…amn1mrjc1c2…cn00…0i=minbi/aij∣aij015换基迭代：当确定了入基变量Xj、出基变量Xi后，以aij作为主元对单纯形表进行初等行变换（取主运算），即将aij所在列除将aij变换为1外的其余元素都变换为0。注意这种变换只能采用初等行变换!最优解检验：1、当迭代进行至某一步时，rj行中所有检验数均小于等于零，则迭代结束。表中当前所指基本可行解即为最优解。2、当迭代进行至某一步时，rj行中所有检验数均小于等于零，且此时至少有一个非基变量所对应的检验数rk等于零，则原线性规划问题有无穷多个最优解。3、当迭代进行至某一步时，rj行中至少有一个检验数rk大于零，且该检验数对应的列中a1k，a2k，…amk，均小于等于零，则原线性规划问题最优解无界（maxZ→+∞）。线性规划LinearProgramming（LP）单纯形法、单纯形表16线性规划LinearProgramming（LP）单纯形法、单纯形表单纯形方法的矩阵描述：设线性规划问题maxZ=CXmaxZ=CX+0XSs.t.AX≤bs.t.AX+IXS=b（I式）X≥0X，XS≥0其中b≥0，I是mm单位矩阵。对上面（I式）经过迭代，并设最终的最优基矩阵为B（不妨设B为A的首m列，则将（I式）改写后有标准化maxZ=CBXB+CNXN+0XSs.t.BXB+NXN+IXS=bXB，XN，XS≥0（I式）maxZ=CBB-1+（CN-CBB-1）XN-CBB-1XSs.t.XB+B-1NXN+B-1XS=bXB，XN，XS≥0（B式）B式中最优目标函数值Z*=CBB-1，检验数CN-CBB-1≤0，-CBB-1≤0单纯形方法迭代17单纯形方法的矩阵描述：线性规划LinearProgramming（LP）单纯形法、单纯形表XBXSXNXSB-1bbNICN0rjXBBCB对应I式的单纯形表——I表XBXBXNXSB-1bB-1bB-1NB-1CN-CBB-1-CBB-1rjXBI0…...对应B式的单纯形表——B表18人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我