运筹学电子教案-LP单纯形法、表课件.ppt

《运筹学电子教案-LP单纯形法、表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划LinearProgramming（LP）基本理论线性规划的标准型定义：maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.…其中bj≥0，j=（1，2，…n）am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）将一般线性规划问题化为标准型1、max——min2、不等式约束——等式约束3、自由变量（无非负约束）——xj≥0（非负约束）注意：以上转化是等价的，即转化后的标准型与原线性规划问题同解1线性规划LinearProgramming（LP）基本理论可行解满足所有约束条件的向

2、量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列向量构成的矩阵2线性规划LinearProgramming（LP）基本理论基向量基矩阵B的向量pi=（a1i，a2i，…，ami）Ti=1，2，…，m

3、非基向量非基矩阵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的基本可行解凸集这样的点集合----其集合中任意两点的连线上的全部点都在该点集合内3线性规划LinearProgram

4、ming（LP）基本理论极点（顶点）凸集上不在两个不同点的连线上的点线性规划基本定理1线性规划所有可行解组成的集合S={X

5、AX=b，X≥0}是凸集线性规划基本定理2X是线性规划问题的基本可行解的充要条件是X为凸集S={X

6、AX=b，X≥0}的极点线性规划基本定理3给定线性规划问题，A是秩为m的mn矩阵，（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解4线性规划LinearProgramming（LP）基本理论线性规划的标准型的向量和矩阵表达形式向量式：矩阵式：maxZ=c1x1+c2x2+…+cnxnmaxZ=CXs.

7、t.p1x1+p2x2+…+pnxn=bs.t.AX=bxj≥0（j=1，2，…n）X≥0式中：pj=（a1j，a2j，…，amj）TC=（c1，c2，…，cn）a11a12…a1nX=（x1，x2，…，xn）TA=a21a22…a2nb=（b1，b2，…，bm）T……………am1am2…amn5单纯形方法是Dantzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本算法。单纯形法的初步讨论例1.8求解LP问题MaxZ=50X1+30X2s.t.4X1+3X2≤1202X1+X2≤50X1，X2≥0（1

8、.17）线性规划LinearProgramming（LP）单纯形法、单纯形表6线性规划LinearProgramming（LP）单纯形法、单纯形表单纯形方法由以下步骤构成：将原问题转化为标准型模型：MaxZ=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50X1，X2，X3，X4≥0（1.18）此线性规划问题转化为了一个含有四个变量的线性规划问题，X3，X4为松弛变量（或剩余变量）。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下---7线性规划LinearProgramming（LP）单纯形法、单

9、纯形表确定初始基可行解：通过观察可以发现，松弛变量X3和X4对应的等式约束条件中的系数矩阵为单位矩阵可以作为初始可行基矩阵。因此取：X3，X4为基变量；X1，X2为非基变量。则（1.18）可变为MaxZ=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥0（1.19）称为关于基的典式——1、等式约束条件中显含基可行解2、目标函数中不含基变量8线性规划LinearProg