第二章3单纯形方法.ppt

第,*,页,2.3,单 纯 形 算 法,理论方法,算法步骤,单纯形表,算例,理 论 方 法,定理2.3.1,理 论 方 法,说明原问题目标函数无下界,定 理 2.3.,4,对于任何非退化的线性规划问题,从任何基本可行解开始,经过有限次迭代,或得到一个基本可行的最优解,或作出该线性规划问题无界的判断,.,在单纯形法的一次迭代过程中，迭代前后的两个基有,m-1,个相同的列向量，这样的基称为相邻基。几何上可以严格证明相邻基所对应的要么是可行域多面凸集的相邻顶点，要么是同一个顶点（退化情形）。因此，直观讲，单纯形法就是从可行域多面凸集的一个顶点迭代到与其相邻的另一个顶点，直至找到最优解或判定问题无界。,单纯形法迭代步骤,:,适用于能找到一个基本可行解的,LP,问题,.,单纯形表：单纯形的全部计算过程在一个类似于增广矩阵的数表上进行所得的表格。,算 法 步 骤,单 纯 形 表,算例,标准型,：,检验数,x,1,x,2,x,3,x,4,x,5,x,6,RHS,基变量,1 2 1 1 0 0,2,基变量,2 1 3 0 1 0,1,基变量,2 2 1 0 0 1,6,x,1,x,2,x,3,x,4,x,5,x,6,RHS,检验数,1 3 3 0 0 0,0,x,4,1 2 1,1,0,0,2,x,5,2 1 3,0,1,0,1,x,6,2 2 1,0,0,1,6,x,1,x,2,x,3,x,4,x,5,x,6,RHS,检验数,1 3 3 0 0 0,0,x,4,1 2 1 1 0 0,2,x,5,2,1,3 0 1 0,1,x,6,2 2 1 0 0 1,6,x,1,x,2,x,3,x,4,x,5,x,6,RHS,检验数,-5 0 -6 0 -3 0,-3,x,4,-3,0,-5,1,-2,0,0,x,2,2,1,3,0,1,0,1,x,6,-2,0,-5,0,-2,1,4,最优解：,X*=(0,1,0,0,0,4),T,最优值,z*=-3,算 例,初 始 单 纯 形 表,迭 代 1,迭 代 2,x,1,x,2,x,3,x,4,x,5,RHS,检验数,0 1 2 0 0,0,x,1,1 0 0,x,2,0 1 0,x,3,0 0 1,x,1,x,2,x,3,x,4,x,5,RHS,检验数,0 0 0 3/2 -5/2,-7/2,x,1,1 0 0,x,2,0 1 0,x,3,0 0 1,因,，,但对应,的,，,由定理,2.3.2,此问题无界。,注：,该算法在实际应用中非常有效，被广泛采用，但在理论上不是多项式时间算法。,现在还有待解决的问题是如何给出初始基本可行解以及出现退化的时候如何处理。,