线性规划算法学习教案

1、线性规划线性规划(xin xn u hu)算法算法第一页，共26页。 代数式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n第1页/共26页第二页，共26页。线性规划线性规划(xin xn u hu)标准标准型型 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n 向量(xingling)式：maxZ=CTX pjxj=bi i=1,2,m xj 0 j=1,2,n矩阵式： maxZ=CTX AX=b X 0 第2页/共

2、26页第三页，共26页。线性规划线性规划(xin xn u hu)解的解的概念概念12( ,)( ,P )BB NBP P分解m若A =， 其中，可逆，称 为基矩阵1B2BNNnxxxX,xxxx基相应地 为，为变量非基变量B-11BNBNNx,xxxBxxbBB代入约束：(B,N)即+N=b,b-N-1B-1NBNxB bxxBx0令=0,b，称x=为基本解-1BNxB bBx0基本可行解若x=0称为， 为可行基第3页/共26页第四页，共26页。线性规划线性规划(xin xn u hu)解的解的性质性质可行域凸集（凸多面体）可行域非空至多有有限个顶点最优解若存在(cnzi)，必可在顶点达到线

3、性规划的基本定理：线性规划的基本可行解就是可行域的极点。 这一定理的重要性在于把可行域的极点这一几何概念与基本可行解这一代数概念联系起来，因而可以通过求基本可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。 第4页/共26页第五页，共26页。 计算计算(j sun)流程流程线性规划线性规划(xin xn u hu)的单的单纯形算法纯形算法初始基本可行解初始基本可行解是否最优解或是否最优解或无限最优解无限最优解? ?结束结束沿边界找新沿边界找新的基本可行解的基本可行解N NY Y第5页/共26页第六页，共26页。1. 初始基本可行初始基本可行(kxng)解的确定解的确定

4、从系数从系数(xsh)矩阵中找到一个可行基矩阵中找到一个可行基B，不妨设，不妨设B由由A的前的前m列组成，即列组成，即B=(P1,P2,Pm)。进行等价变换约束。进行等价变换约束方程两端分别左乘方程两端分别左乘B1 -11BNBNxxxBxBB即+N=b,b-N-1NB bx0(0)令=0,得初始基本可行解x-1-10B b(,)B b0NTTTBBcccT (0)对应的目标函数值z =c x第6页/共26页第七页，共26页。-11BNAXxBxB由=b,b-N，其目标函数值：BBNNx(,)x +xxNTTTTBBNccccTz=c x-1-1NN(B b-B Nx )+xTTBNcc-1-

5、1NB b(B N)xTTTBBNccc-10N+(B N)xTTNBzcc-10jjj R+(B P )x ,TjBzccR非基变量下标集-1NB NTTNBcc记-1jBTjBjccPjR即，(NN0)0,x，判别准则：当则得到最优解否则继续寻找改进的基为检验数本可行解-1BBB B0TTBcc注第7页/共26页第八页，共26页。3. 基变换基变换(binhun)转轴变换转轴变换(binhun)取某一非基变量(binling)xk换入基（即让xk0，其余非基变量(binling)仍为0）同时(tngsh)，再从基变量中换出一个变量xBr作为非基变量。如何求换入变量如何求换入变量xk和换出变

6、量和换出变量xBr？K=?，r=?kmax|0,0,0jjj Rk选令x其余非基变量-11BNAXxBxB由=b,b-N-11-11kkK0BxBP x0BB BKx b- （,P , ）b-kxkb-Y第8页/共26页第九页，共26页。3. 基变换基变换(binhun)转轴变换转轴变换(binhun)kbyxbyB111kBBmmmkx更详细地x =x-10jj0jj R+(B P )x+TjBkzzcczx从目标函数看从目标函数看xk越大越好，但从可行性看越大越好，但从可行性看xk又不能任意大。又不能任意大。若若yik0,i=1,，m,xk可任意取值，此时问题可任意取值，此时问题(wnt)

7、是无界的；是无界的；若若yik0,为保证可行性，即为保证可行性，即xBi=bi-yikxk0，应取，应取ikikbxymin|0ikikikbxyy令 rrkby注意注意(zh y)：xBr=0第9页/共26页第十页，共26页。3. 基变换基变换(binhun)转轴变换转轴变换(binhun)新可行解：新可行解：x=(xB1,xBr-1,0,xBr+1,xBm,0,，0,xk,0,，0)可以证明此解为新的基本可行解。这是因为原来可以证明此解为新的基本可行解。这是因为原来(yunli)的基的基PB1,PBm线性无关，而线性无关，而yk=B-1Pk,故故Pk=Byk=yikPBi，而，而PBr的系

8、数的系数yrk0，所以，用所以，用Pk代替代替Pr后的向量组后的向量组PB1,Pk,PBm线性线性无关，所以无关，所以x为基本可行解为基本可行解在新的基本可行解中，目标函数比原来增加了在新的基本可行解中，目标函数比原来增加了kxk。重复上述过程，直至所有的重复上述过程，直至所有的j均均0，得到最优解。因为，得到最优解。因为(yn wi)基本可行解的个数是有限的，因此在非退化基本可行解的个数是有限的，因此在非退化(r(A)=m)情情况下，经有限次迭代必能达到最优解。况下，经有限次迭代必能达到最优解。第10页/共26页第十一页，共26页。总结计算步骤：给定总结计算步骤：给定(i dn)初始基初始基

9、B步步1.令令xN=0,，xB=B-1b=b，z0=cBTxB ；步步2.检验数检验数j=cj-cBTB-1 Pj，j0，停止，得最优解，否则取，停止，得最优解，否则取kmaxj，转步，转步3；步步3. 解解yk=B-1Pk，若，若yk0，停止，停止,不存在不存在(cnzi)有限最优解有限最优解. 否则转步否则转步4；步步4.计算计算 xk进基，进基，xBr离基，用离基，用Pk替代替代PBr得新的可行基得新的可行基B， 转步转步1。min|0irikikbyyrrkby第11页/共26页第十二页，共26页。 例：用单纯形法的基本思路求解(qi ji)下面的线性规划问题： Max z = 150

10、0 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0321002101003001AC=(1500, 2500, 0, 0, 0)Tb=(65, 40, 75)T第12页/共26页第十三页，共26页。第一次迭代：第一次迭代：（1）取初始可行基）取初始可行基B0= (p3 , p4 , p5)，那么那么x3 ，x4 ，x5为基变量，为基变量，x1 ，x2为为非基变量。将基变量和目标非基变量。将基变量和目标(mbio)函函数用非基变量表示：数用非基变

11、量表示： z =1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2当非基变量当非基变量x1，x2=0时，相应的基变量时，相应的基变量和目标和目标(mbio)函数值为函数值为x3=65，x4=40，x5= 75，z = 0，得到当前的基本可行解：，得到当前的基本可行解：x(0) =(0,0,65,40,75)T，z = 0 。-11BNxBxBb-N-10BbTBcT(0)z =c x第13页/共26页第十四页，共26页。（2 2）最优性检验：）最优性检验： 在目标函数在目标函数z = 1500 x1

12、+ 2500 x2z = 1500 x1 + 2500 x2中，非基中，非基变量变量x1x1，x2x2的系数都是正数的系数都是正数(zhngsh)(zhngsh)，此解，此解非最优。取非最优。取kkmax1500, 2500max1500, 2500，（3 3）转轴变换：选择）转轴变换：选择x2x2为进基变量，另一个为进基变量，另一个非基变量非基变量x1x1保持零值不变。保持零值不变。-10jj0jj R+(B P )x+TjBkzzcczx第14页/共26页第十五页，共26页。 确定出基变量。在约束条件确定出基变量。在约束条件 x3 = 65 - 3 x1 - 2 x2 x3 = 65 -

13、3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 x5 = 75 - 3 x2中，当中，当x2x2的值从的值从0 0开始增加开始增加(zngji)(zngji)时，基变量时，基变量x3 x3 、x4 x4 、x5x5的值分别从当前的值的值分别从当前的值6565、4040和和7575开开始减少，当始减少，当x2x2增加增加(zngji)(zngji)到到2525时，时，x5x5首先下首先下降为降为0 0成为非基变量。这时，新的基变量为成为非基变量。这时，新的基变量为x3 x3 、x4 x4 、x2 x2 ，新的非

14、基变量为，新的非基变量为x1 x1 、x5 x5 ，当前的基，当前的基本可行解和目标函数值为：本可行解和目标函数值为：X(1) = (0X(1) = (0，2525，1515，1515，0)T0)T，z = 62500z = 62500。 22213ByP 65/2min 40/174/3第15页/共26页第十六页，共26页。第二次迭代：第二次迭代： （1）当前）当前(dngqin)的可行基为的可行基为B1 = (p2 , p3 , p4)，那么，那么x2 ，x3 ，x4为基变量，为基变量，x1 ，x5为非基为非基变量。将基变量和目标函数用非基变量表示：变量。将基变量和目标函数用非基变量表示：

15、 z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 第16页/共26页第十七页，共26页。 （2 2）选择进基变量。在目标函数）选择进基变量。在目标函数z = 62500 + 1500 x1 (2500/3) x5 z = 62500 + 1500 x1 (2500/3) x5 中，中，非基变量非基变量x1x1的系数是正数，因此的系数是正数，因此 x1 x1进基可以进基可以使目标函数使目标函数z z增大，于是增大，于是(ysh)(ysh)选择选

16、择x1x1进基，进基，使使x1x1的值从的值从0 0开始增加开始增加, , 另一个非基变量另一个非基变量x5x5保保持零值不变。持零值不变。 (3) (3)确定出基变量。在约束条件确定出基变量。在约束条件 x2 = 25 (1/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 x4 = 15 - 2 x1 + (1/3) x5 第17页/共26页第十八页，共26页。中，由于进基变量中，由于进基变量x1在两个约束条件中的在两个约束条件中的系数都是

17、负数，当系数都是负数，当x1的值从的值从0开始增加时，开始增加时，基变量基变量x3 、x4的值分别从当前的值的值分别从当前的值15、15开始减少，当开始减少，当x1增加到增加到5时，时，x3首先下首先下降为降为0成为非基变量。这时，新的基变量成为非基变量。这时，新的基变量为为x1 、x2 、x4 ，新的非基变量为，新的非基变量为x3 、x5 ，当前的基本可行，当前的基本可行(kxng)解和目标函解和目标函数值为：数值为：X(2) = (5，25，0，5，0)T，z = 70000。 第18页/共26页第十九页，共26页。第三次迭代：第三次迭代： （1）当前的可行基为）当前的可行基为B2 = (

18、p1 , p2 , p4 )，那么那么x1 ，x2 ，x4为基变量，为基变量，x3 ，x5为非基为非基变量。将基变量和目标函数变量。将基变量和目标函数(hnsh)用非基用非基变量表示：变量表示： z = 70000 500 x3 500 x5 x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5 x4 = 5 + (2/3) x3 (1/9) x5 第19页/共26页第二十页，共26页。 （2）选择）选择(xunz)进基变量。在目标函数进基变量。在目标函数 z = 70000 500 x3 500 x5 中，非基变量中，非基变量x3 、x5的系数均不是正数，因

19、此的系数均不是正数，因此进基都不可能使目标函数进基都不可能使目标函数z增大，于是得到最优增大，于是得到最优解，解， x* = (5，25，0，5，0)T，最优目标值为最优目标值为 z* = 70000。我们也称相应的基我们也称相应的基 B2 = (p1 , p2 , p4)为最优基。计算结束。为最优基。计算结束。 第20页/共26页第二十一页，共26页。1X(0) =(0,0,65,40,75)T，z = 0 。对应。对应(duyng)于图于图中的中的D、E交点交点X(1) = (0，25，15，15，0)T，z = 62500。对应。对应(duyng)于图中的于图中的C、D交点。交点。x* = (5，25，0，5，0)T， z* = 70000。对应。对应(duyng)于图的于图的A、C交点。交点。第21页/共26页第二十二页，共26页。单纯形表单纯形表 maxZ=CTX s.t.AX=b X 0 BNxxxBNcCcA=(B,N)NBNx. .xxTstBTBBNmaxzc x +c+N=b x0BNN. .xxxTstBTBBNmaxz+N=bzc x +c x0zxBxN右端项0BNb1cBcN0第22页/共26页第二十三页，共26页。1BN-1-1N. .xxB b(B N)xTTTBBNstBbccc-1maxz+N=Bz x0zxBxN右端