《（推荐）第4章线性规划求解的基本方法.ppt》由会员分享，可在线阅读，更多相关《（推荐）第4章线性规划求解的基本方法.ppt（42页珍藏版）》请在三一文库上搜索。
1、1,优化技术基础,第2节 线性规划求解的基本方法,第四章 线性规划,2,第二章线性规划求解的基本方法,基本思想：从可行集中某一个基本可行解（顶点）出发，转换到另一个基本可行解（顶点），逐步改进目标函数的取值，直到求得最优的基本可行解。,三个关键问题： （1）初始顶点（初始的基本可行解）如何确定？ （2）怎样使最优搜索从一个顶点移到另一个顶点？ （3）如何判断所找到的顶点是不是最优点？,2.1单纯形法的基本思想,3,例:求解线性规划问题,max z=2x1+3x2 2x1+2x212 x1+2x2 8 4x1 16 4x2 12 x1,x20,解：化为标准型求初始基本可行解,min z= - 2
2、x1- 3x2 2x1+2x2+x3 = 12 x1+2x2 +x4 =8 4x1 +x5 =16 4x2 +x6 =12 xj0 j=1,2,6,s.t.,s.t.,基矩阵,x3,x4,x5,x6,基变量,4,非基本量(设计变量)x1,x2 令x1=x2=0,即得,初始基本可行解,x0代入目标函数,z=0,?,最优解？,基变换,5,2)基变换,换入:将式中系数为负、且为最小的那个非基变量换入，作为基变量。x2 基变量 换出：x1=0, X2 x3,x4,x5,x6?,6,7,4x2=12,4x1=16,2x1+2x2=12,x1+2x2=8,6,Q4,Q3,Q2,Q1,3,4,2,4,6,8
3、,x2,x1,0,8,引例说明：,向量形式：,P1x1+P2x2+P3x3+P4x4+P5x5=B,.2单纯形法的计算步骤,9,.2单纯形法的计算步骤,1、化一般的线性规划为标准形式，构造一个初始可行基,）若约束条件均为“”情况，则引入非负松弛变量xn+i，以形成一个m阶单位阵(称为初始可行基),）若约束条件均为“”，或等式约束的系数矩阵不存在m阶单位阵为子矩阵的情况这时需引入“人为变量”,10,）作初始单纯形表，确定初始基本可行解,11,12,13,单纯形法例题,目标函数：f(x)=-5x1-10 x2,约束方程：,14,解：,新的基本可行解,15,由于,不全大于，所以不是最优解 （以检验数
4、较小进行计算）,L=1,用x2去替换第个基本变量,16,基本变量值,列向量,17,由于非基本变量所对应的列，还有检验数等于的（第一列），故说明还有一个顶点是最优解所以还可以第一列所对应的非基本变量x1去替换基本变量x5,18,变换后的单纯形表,基本变量值,列向量,最优解x*=(2 6 0 3/14 0)T,19,单纯形方法的计算步骤及框图,(1)将约束条件变换成等式，形成m阶n维的线性规划问题，求得基本可行解,(2)对系数阵的每一列计算检验数：,(3)若某个列的且某些元素 I 有，则选定Q列所对应的变量XQ作为替换的非基本变量,求新的基本可行解.,对于初始基本可行解k=0,若每一列的检验数全部
5、大于等于零，则即为最优解，迭代结束若某个列的且全部元素，则此问题无解,(4)再计算每一列的检验数,再判断,如此迭代直至找到最优解.,20,输入：初始基本可行解x(0)及相应的约束、方程组系数矩阵、目标函数系数阵,计算检验数,打印,停,21,计算机运行程序,(用单纯形法求解线性规划问题),22,#define N 20 #include #include /*从A中获取基变量，放入B中*/ void InitB(double ANN,int BN,int m,int n) int i,j,k,l; for(i=0;i1e-6 ,if(fabs(Aji-1)1e-6) k=j; l=i; if(k
6、!=-1) Bk=l; ,注：若求解其他类似问题，请把程序中m,n,A,b换成相应的约束个数，变量个数，增广矩阵（方程左边的系数矩阵），方程右边的系数矩阵。,23,/*求得一个基本可行解，放入x中*/ void Getx(double ANN,int BN,double bN,double xN,int m,int n) int i,j ; for(i=0;in;i+) xi=0; for(i=0;im;i+) xBi=bi; ,24,main() int i,j,k,l,flag=1; int m,n; /*m表示约束条件数，n表示变量数,A表示增广矩阵，c表示目标函数系数向量*/ doub
7、le ANN=2,2,1,0,0,0,1,2,0,1,0,0,4,0,0,0,1,0,0,4,0,0,0,1,cN=-2,-3; double bN=12,8,16,12;/*b表示方程右边的系数*/ double aN,c2N,baN,xN=0,sum=0,min,temp; /*x表示可行解，初始化为0,c2表示即检验数,ba表示（主行元）*/ int BN ; /*B表示基变量*/ m=4;n=6; InitB(A,B,m,n); Getx(A,B,b,x,m,n);,while(flag) flag=0;min=1e20; for(i=0;in;i+) /*求各行的检验数*/ sum=
8、0; for(j=0;jm;j+) sum+=cBj*Aji; c2i=ci-sum; for(j=0;jm;j+) if(i=Bj) break; if(jm) continue; if(c2i0) flag=1; if(c2imin) /* 取最小检验数*/ min=c2i; k=i; ,25,if(flag=0) break; min=1e20; l=-1; /*求中的大于零的最小值*/ for(i=0;i0 ,/*用1/Alk乘主行元,化主行元为1*/ temp=Alk; bl/=Alk; for(j=0;jn;j+) Alj/=temp; for(i=0;im;i+) if(i!=l
9、) temp=Aik; for(j=0;jn;j+) Aij-=temp*Alj; bi-=temp*bl; InitB(A,B,m,n); ,26,InitB(A,B,m,n); Getx(A,B,b,x,m,n); sum=0; for(i=0;in;i+) printf(x(%d)=%f n,i+1,xi); sum+=ci*xi; printf(目标函数最小值为%fn,sum); ,程序运行,程序运行结果,x(1)=4.000000 x(2)=2.000000 x(3)=0.000000 x(4)=0.000000 x(5)=0.000000 x(6)=4.000000 目标函数最小值
10、为 14.000000 Press any key to continue,故本题目标函数最大值为14 对应的,27,.3人为变量法,当线性规划问题的约束条件中出现”(或”=”)的形式时,如:,2x1+ 3x2- 5x3 =7 X1 + 2x2+ 3x3 -x5 =10 -4x1+ 3x2+ 2x4 + 2x6 = 25 xj0 j=1,2,3,4,5,6,28,原目标函数及约束条件,标准型,29,一、大M单纯形法,原理:若有n维m阶的线性规划问题,求X,使f(x)=CTX min 并满足约束方程 AX=B,X0 其中:C-目标函数系数所构成的列向量,现转而求另一个线性规划问题:,求 ,使g(
11、X,Y)=CTX+mETY min,并满足约束方程 AX+Y=B, X、Y0,式中；m-充分大的一个正数； ET（1，1，.，1） Y-人造变量,Y=(y1,y2,yn)T,30,从而可找到初始基本可行解:,其中:,为非基本变量(零分量),为基本变量,继而用单纯形法求解,等价问题的讨论:,(1)若原问题有最优解,m是一个充分大的正数,又Y0,要使目标函数g(X,Y)达到最小值,就必须使Y=0,使最优解为,(2)如果(X* 0)T是转换后的线性规划的最优解, Y=0, g(X,Y)=CTX+mETY =CTX+0=f(x) AX+Y=B AX=B,31,例1: min f(x)= -x1 -2x
12、2 -3x3 +x4,并满足:,在约束方程中添加人造变量x5,x6,使原问题变成以下问题:,min g(x)= -x1 -2x2 -3x3 +x4+m(x5+x6),并满足:,初始基本可行解:X(0)=(0 0 0 10 15 20)T,32,解：,初始单纯形表:,基本变量值,列向量,33,根据单纯形法规则,确定用x3去替换基本变量x6,替换后见表:,基本变量值,列向量,此列可不再列出,34,然后用x2去替换x5,最后得最优解,原问题的最优解为:,注意: 如果人造变量始终不能从基底中替换出来,则说明原问题无最优解,35,P31例2: min z=-3x1+x2+x3,min z=-3x1+x2
13、+x3+0 x4+0 x5,松弛变量,剩余变量,min z=-3x1+x2+x3+0 x4+0 x5+Mx6+Mx7,自由变量,36,二、二阶段单纯形法,处理人为变量的另一种方法，这种方法是将加入人为变量后的线性规划问题分为两个阶段来求解。,37,第一阶段：要判断原问题是否存在基本可行解，具体办法是：先在各约束方程中加入人为变量，并使人为变量之和作为新的目标函数，同时求目标函数的最小：,用单纯法对上述规划求解，若得到w=0,说明愿问题有可行解。若这一阶段的最终计算表现出w0,这表示原问题无可行解，应停止计算。,38,第二阶段：当w=0并已得到原规划的基本可行解时，把所获得的基本可行解作为原问题
14、的一个初始可行解，并将目标函数的系数改换成原问题的目标函数系数，就形成第二阶段的初始单纯形表，继续用单纯形法求出最优解。,注：第一阶段最终表中w=0,而未得到原规划的基本可行解时，需继续迭代或去掉多余约束。,39,例如：用二阶段法求解,用单纯形法求解,40,41,因所有的检验数 ，表示目标函数达到最小值。 W=0 xmin=(0,1,1,12,0,0,0)T 因人为变量x6=x7=0,又（0，1，1，12，0）T是原问题的基本可行解，可以开始第二阶段的计算。 将第一阶段的最终计算表中的人为变量取消，并将目标函数的系数换成原问题的目标函数的系数，作为第二阶段计算的初始表。,42,第二阶段：,最优解 x=(4,1,9)T, zmin=-2,