纯形法（第三章线性规划.ppt

1,一、求解LP问题的单纯形法 1.单纯形法的求解原理,单纯形法引例,Step2. 确定换入换出变量，进行第一次迭代,Step1. 确定初始基可行解。,初始基可行解为：X1=(0 0 360 200 300)T,f1=0,*,f2 =360,Step3.确定新的换入换出变量，进行第二次迭代,*,目标函数值 f 3 = 428。,即当A产品生产20kg，B产品生产24kg，工厂才能获得最大利润428百元。x3=84代表煤的剩余量为84t，x4 = x5 = 0表示电力和劳动日完全利用，没有剩余。,X3为最优解,5,2.单纯形法的主要步骤,Step1. 标准化，找初始基可行解，建立初始的单纯形表； 对于(max , )，松弛变量对应的列构成一个单位阵 Step2.检验当前基可行解是否为最优解 所有检验数 j 0，则得到最优解（若存在k 0，且pk 0,则该问题无最优解，停止计算） 否则进行下一步。 Step3.换基迭代（改进基可行解） 从 j 0 中找最大者 k ，其对应变量xk称为换入变量（若最大判别数有同样大的，选对应下标小的变量为换入变量) xk所在列称为主元列 确定换入变量的最大值和换出变量 最小比值原则,6,设第 l 行使 最小，则第 l 行对应的基变量x l称为换出变量，第 l 行称为主元行，alk 称为主元。 Step4.迭代过程 迭代过程以主元alk为中心进行，即要将主元 alk变为1，主列上其它元素变为0，得到一个新的单纯形表，同时得到一个新的基可行解。 转回Step2。,7,3. 单纯形表及其格式,max f =40x1+ 50x2,例1 用单纯形法求解下列LP问题,max f =40x1+ 50x2+0x3 +0x4+0x5,标准化,建立初始单纯形表,基变量,*,30/2=15,60/2=30,24/2=12,40 50 0 0 0,0 0 0,第一步迭代,基变量,6/1=6,36/3=12,_,40 50 0 0 0,0 0 50,第二步迭代,基变量,18/2=9,12/0.5=24,_,40 50 0 0 0,40 0 50,第三步迭代,基变量,该问题的最优解为：X=(15, 7.5, 0, 0, 9)T,40 50 0 0 0,40 0 50,例2 用单纯形法求解下列LP问题,基变量,1 1 0 0 0,0 0 0,0,-1,2,8,9,3,-2,0,0,2,-1,-2,x1,1,该问题具有无界解,例2 用单纯形法求解下列LP问题,max f =x1+ x2+2x3 -x4,x1 +x3 - x4 =1 -x1 +x2 +2x4 =0 x1 , , x4 0,max f =x1+ x2+2x3 -x42 -x4,基变量,此问题具有无穷多最优解 max f =2,总结：解的判别,1、最优解的判别： 若X（x1x2.xn）T为对应于基B的一个基可行解，且所有j 0，则X为最优解。 2、无穷多最优解的判别： 若X（x1x2.xn）T为一个基可行解，存在所有j 0，又存在某一非基变量xk对应的判别数k = 0,则此LP问题有无穷多解。 3、无界解的判别： 若X（x1x2.xn）T为一个基可行解，其中某个非基变量xk对应的判别数k 0，且对应的系数矩阵aik 0,则此LP问题具有无界解。（或称无最优解，最优解 无穷）,20,4 .人工变量的引入及其解法 当约束条件为“”型，引入剩余变量和人工变量,由于所添加的剩余变量的系数为1，不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法 大M法 两阶段法,（1）两阶段法：,作辅助问题,解题过程：,max = -y1 - y2- -ym,从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或判断具有无界解。,第二阶段:,例3 用两阶段法求解下列LP问题,引入人工变量x6 , x7构造下列辅助问题：,x3,0,0,-2,1,3,0,-1,10,0,0,-3,1,1,0,1,1,x3,0,0,-2,1,12,-1,x2,0,-2,-5,0,0,0,0,-1,1,-1,2,-1,2,x1,1/3,-2/3,4,1,0,2/3,-4/3,0,-1/3,-1/3,-2,9,得到原问题的最优解为：X*=（4 1 9 0 0）T f * =2,（2） 大M法:,Mx6 Mx7,(M为任意大的正数),3 -1 -1 0 0 -M -M,0 -M -M,3 -1 -1 0 0 -M -M,0 -M -1,3 -1 -1 0 0 -M -M,0 -1 -1,3 -1 -1 0 0,3 -1 -1,得到原问题的最优解为：X*=（4 1 9 0 0）T f * =2,34,练习：,标准化：,大M法的一些说明,大M法实质上与原单纯形法一样，M可看成一个很大的常数 人工变量被迭代出去后就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便 因此提出了两阶段法 计算机中常用大M法 两阶段法手算可能容易,36,单纯型法的一些具体问题 a.关于无界解问题,可行区域不闭合(缺约束条件) 单纯型表中入变量 x j* 对应的列中所有,37,b.关于多重解问题,多个基可行解都是最优解，这些解在同一个超平面上，且该平面与目标函数等值面平行 最优单纯形表中有非基变量的检验数为0 最优解的线性组合仍是最优解，即 X=k1X1+k2X2，k1+k2=1,38,c.关于无可行解问题,约束条件互相矛盾，无可行域 单纯形表迭代到最优解时，人工变量仍在基变量中,39,d.关于退化问题,退化问题的原因很复杂 当单纯形表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法,一、判断题,1、线性规划问题的每一个基解对应可行域的一个顶点。 2、图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的。 3、线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点。 4、若x1、x2分别是某一线性规划问题的最优解，则 x1 x1+2x2也是该线性规划问题的最优解，其中1 2为正的实数。 5、对一个有n个变量、m个约束的标准形的线性规划问题，其可行域 的顶点恰好为Cnm,6、单纯形法迭代的过程就是从一个基可行解（顶点）到另一个基可行解（顶点）的过程。 7、用单纯形方法，正的判别数对应的变量都可以作为换入变量。 8、线性规划问题的数学模型增加约束条件，可行域范围一般缩小，减少约束条件，可行域范围一般扩大。,2、计算题,下表是求极大化线性规划问题的单纯形表，表中无人工变量，a1 ，a2，a3，d，c1，c2为待定常数，试说明这些常数满足什么条件，能使以下结论成立：,(1)表