线性规划问题单纯形法.ppt

《线性规划问题单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章单纯形法与单纯形表1线性规划LinearProgramming（LP）图解法的启示线性规划问题解的可能情况a.唯一最优解b.无穷多最优解c.无解（没有有界最优解，无可行解）若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。2线性规划LinearProgramming（LP）单纯形法单纯形方法是G.B.Danzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。3线性规划

2、LinearProgramming（LP）单纯形法给定线性规划问题（标准形式）maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）4线性规划LinearProgramming（LP）单纯形法一、线性规划问题的解的概念可行解最优解基基解（基本解）基可行解可行基5线性规划LinearProgramming（LP）单纯形法二、凸集及其顶点凸集顶点（极点）凸集凹集6线性规划LinearP

3、rogramming（LP）12345678基解（可行）基解（不可行）7线性规划LinearProgramming（LP）单纯形法三、线性规划基本定理基本定理1线性规划所有可行解组成的集合S={X

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

5、AX=b，X≥0}的极点。基本定理3给定线性规划问题，A是秩为m的mn矩阵，（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。8线性规划LinearProgramming（LP）单纯形法

6、单纯形法迭代原理及其思路单纯形法的初步讨论例1.8求解LP问题化为标准型MaxZ=50X1+30X2s.t.4X1+3X2≤1202X1+X2≤50X1，X2≥0MaxZ=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50X1，X2，X3，X4≥0（1.18）9线性规划LinearProgramming（LP）单纯形法此线性规划问题转化为了一个含有四个变量的标准形线性规划问题，X3，X4为松弛变量。为求解上面的LP问题，我们要考虑满足约束条件s.t.并使Z取得Max的X1，X2，X3，X4的值，由此分析如下---1

7、0线性规划LinearProgramming（LP）单纯形法确定初始基可行解：通过观察可以发现，松弛变量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≥011线性规划LinearProgramming（LP）单纯形法典式（1.19）或（1.18）称为关于基的典式——1、等式约束条件中显含基可行解2、目标函数中不含基变量MaxZ

8、=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50(1.18)X1，X2，X3，X4≥0MaxZ=50X1+30X2s.t.X3=120-4X1-3X2X4=50-2X1-X2（1.19）X1，X2，X3，X4≥012线性规划LinearProgramming（LP）单纯形法在典式（1.19）中令：X1=X2=0，我们得到一个基本可行解X1=（X1，X2，X3，X4）T=（0，0，120，50）T，其对应的目标函数值Z1=50X1+30X2=013线性规划LinearProgramming（LP）单纯形法最优性检

9、验：基本可行解X1是最优解吗？显然不是。应寻找更好的解。从问题的数学角度分析，在典式（1.19）的目标函数中，非基变量X1，X2前的系数都为正，而此时的X1，X2均取零值，表明只要增加其值，则目标函数值有增加的可能。因此，将目标函数中系数为正的某一非基变量与某一基变量地位对换。14线性规划LinearProgramming（LP）单纯形法换基迭代：进行换基就是要从非基变量中选一个变量入基，再从基变量中选一个变量出基。并且换基后仍需满足：新的解仍是基本可行解；目标函数值将得到改善。15线性规划LinearProgramming（LP）单纯形法选

10、择入基变量：由于在目标函数Z1=50X1+30X2中X1，X2的系数都为正，哪一个入基都可使目标函数值得到改善。对于求目标函数极大化的问题，我们希望目标值增加得越快