第4章线性规划求解的基本方法

《第4章线性规划求解的基本方法》由会员分享，可在线阅读，更多相关《第4章线性规划求解的基本方法（43页珍藏版）》请在金锄头文库上搜索。

1、1武汉理工大学 能源与动力工程学院能源与动力工程学院优化技术基础第第2节节 线性规划求解的基本方法线性规划求解的基本方法第四章第四章 线性规划线性规划2021/6/412武汉理工大学 能源与动力工程学院能源与动力工程学院第二章线性规划求解的基本方法基本思想：从可行集中某一个基本可行解（顶点）出发，转基本思想：从可行集中某一个基本可行解（顶点）出发，转换到另一个基本可行解（顶点），逐步改进目标函数的取值，换到另一个基本可行解（顶点），逐步改进目标函数的取值，直到求得最优的基本可行解。直到求得最优的基本可行解。三个关键问题：三个关键问题：（1 1）初始顶点（初始的基本可行解）如何确定？）初始顶点（

2、初始的基本可行解）如何确定？（2 2）怎样使最优搜索从一个顶点移到另一个顶点？）怎样使最优搜索从一个顶点移到另一个顶点？（3 3）如何判断所找到的顶点是不是最优点？）如何判断所找到的顶点是不是最优点？2.12.1单纯形法的基本思想单纯形法的基本思想2021/6/423武汉理工大学 能源与动力工程学院能源与动力工程学院例例: :求解线性规划问题求解线性规划问题max z=2x1+3x2 2x1+2x212 x1+2x2 8 4x1 16 4x2 12 x1,x20解：化为标准型求初始基本可行解解：化为标准型求初始基本可行解min z= - 2x1- 3x2 2x1+2x2+x3 = 12 x1+

3、2x2 +x4 =8 4x1 +x5 =16 4x2 +x6 =12 xj0 j=1,2,6s.t.s.t.基矩阵x3,x4,x5,x6基变量2021/6/434武汉理工大学 能源与动力工程学院能源与动力工程学院非基本量(设计变量)x1,x2令x1=x2=0,即得初始基本可行解x0代入目标函数z=0?最优解？基变换基变换2021/6/445武汉理工大学 能源与动力工程学院能源与动力工程学院2)基变换基变换换入换入: :将式中系数为将式中系数为负负、且为、且为最小最小的那个的那个非基变量换入非基变量换入，作，作为基变量。为基变量。x x2 2 基变量基变量换出：换出：x x1 1=0, =0,

4、X2 2 x x3 3,x,x4 4,x,x5 5,x,x6 6? ?2021/6/456武汉理工大学 能源与动力工程学院能源与动力工程学院2021/6/467武汉理工大学 能源与动力工程学院能源与动力工程学院4x2=124x1=162x1+2x2=12x1+2x2=86Q4Q3Q2Q1342468x2x102021/6/478武汉理工大学 能源与动力工程学院能源与动力工程学院引例说明引例说明：向量形式向量形式：P1x1+P2x2+P3x3+P4x4+P5x5=B.2.2单纯形法的计算步骤单纯形法的计算步骤2021/6/489武汉理工大学 能源与动力工程学院能源与动力工程学院.2.2单纯形法的

5、计算步骤单纯形法的计算步骤1 1、化一般的线性规划为标准形式，构造一个初始可行基、化一般的线性规划为标准形式，构造一个初始可行基）若约束条件均为）若约束条件均为“”情况，则引入情况，则引入非负松弛变量非负松弛变量xn+i，以形成一个，以形成一个m阶阶单位阵单位阵(称为初始可行基称为初始可行基)）若约束条件均为）若约束条件均为“”，或等式约束的系数矩阵不存在，或等式约束的系数矩阵不存在m阶单位阵为子矩阶单位阵为子矩阵的情况这时需引入阵的情况这时需引入“人为变量人为变量”2021/6/4910武汉理工大学 能源与动力工程学院能源与动力工程学院）作初始单纯形表，确定初始基本可行解）作初始单纯形表，确

6、定初始基本可行解scc1 c2 cn cn+1 cn+2 cn+mcBixBbix1x2xnxn+1xn+2xn+m0cn+1xn+1b1a11a12a1n100cn+2xn+2b2a21a22a1n010000cn+mxn+mbmam1am2amn0010 0 02021/6/41011武汉理工大学 能源与动力工程学院能源与动力工程学院c-2-30000scBixBbix1x2x3x4x5x600x3122210000x481201000x5164000100x612040001-2(-3)00000x3620100-1/230x4210010-1/220x5164000104-3x2301

7、0001/4/(-2)00003/42021/6/41112武汉理工大学 能源与动力工程学院能源与动力工程学院c-2-30000scBixBbix1x2x3x4x5x60x32001-201/24-2x1210010-1/2/0x58000-4124-3x23010001/41200020(-1/4)0x30001-1-1/40-2x1410001/400x64000-21/21-3x220101/2-1/800003/21/802021/6/41213武汉理工大学 能源与动力工程学院能源与动力工程学院单纯形法例题单纯形法例题目标函数目标函数：f(x)=-5x1-10x2约束方程约束方程：20

8、21/6/41314武汉理工大学 能源与动力工程学院能源与动力工程学院解解： 新的基本可行解新的基本可行解基本变基本变量序号量序号i i基基本本变变量量基基本本向向量量-5-10 000P1P2P3P4P51x3P3011002x4P4010103x5P50811001目标函数及检验数目标函数及检验数-5-10 000基本变量值基本变量值列向量列向量2021/6/41415武汉理工大学 能源与动力工程学院能源与动力工程学院由于由于不全大于，所以不是最优解不全大于，所以不是最优解（以检验数较小进行计算）（以检验数较小进行计算）L=1用用x x2 2去替换第个基本变量去替换第个基本变量2021/6

9、/41516武汉理工大学 能源与动力工程学院能源与动力工程学院基本变基本变量序号量序号i基基本本变变量量基基本本向向量量-5-10 000P1P2P3P4P51xP2-10 717002x4P400103x5P50 10-701目标函数及检验数目标函数及检验数0070 00基本变量值基本变量值列向量列向量2021/6/41617武汉理工大学 能源与动力工程学院能源与动力工程学院由于非基本变量所对应的列，还有由于非基本变量所对应的列，还有检验数等于检验数等于的（第的（第一列），故说明还有一个顶点是最优解所以还可以第一列），故说明还有一个顶点是最优解所以还可以第一列所对应的非基本变量一列所对应的非

10、基本变量x1去替换基本变量去替换基本变量x52021/6/41718武汉理工大学 能源与动力工程学院能源与动力工程学院变换后的单纯形表变换后的单纯形表基本变量序号i基本变量基本向量-5-10 000P1P2P3P4P51xP2-10 60114 0-12x4P400013xP1-5 210-1402目标函数及检验数目标函数及检验数0070 00基本变量值列向量最优解最优解x*=(2 6 0 3/14 0)T2021/6/41819武汉理工大学 能源与动力工程学院能源与动力工程学院单纯形方法的计算步骤及框图单纯形方法的计算步骤及框图(1)(1)将约束条件变换成等式，形成将约束条件变换成等式，形成

11、m m阶阶n n维的线性规划问题，求得基本可行解维的线性规划问题，求得基本可行解(2)(2)对系数阵的每一列计算检验数：对系数阵的每一列计算检验数：(3)(3)若某个列的且某些元素若某个列的且某些元素 I I 有，则选定有，则选定Q Q列所对列所对应的变量应的变量X XQ Q作为替换的非基本变量作为替换的非基本变量, ,求新的基本可行解求新的基本可行解. .对于初始基本可行解对于初始基本可行解k=0,k=0,若每一列的检验数全部大于等于零，则即若每一列的检验数全部大于等于零，则即为最优解，迭代结束若某个列的且全部元素，为最优解，迭代结束若某个列的且全部元素，则此问题无解则此问题无解(4)(4)

12、再计算每一列的检验数再计算每一列的检验数, ,再判断再判断, ,如此迭代直至找到最优解如此迭代直至找到最优解. .2021/6/41920武汉理工大学 能源与动力工程学院能源与动力工程学院输入：初始基本可行解输入：初始基本可行解x(0)及相应的约束、方程组系数矩阵、目标函数系数阵及相应的约束、方程组系数矩阵、目标函数系数阵计算检验数打印停2021/6/42021武汉理工大学 能源与动力工程学院能源与动力工程学院计算机运行程序计算机运行程序(用单纯形法求解线性规划问题用单纯形法求解线性规划问题)2021/6/42122武汉理工大学 能源与动力工程学院能源与动力工程学院#define N 20#i

13、nclude #include /*从A中获取基变量，放入B中*/void InitB(double ANN,int BN,int m,int n) int i,j,k,l;for(i=0;in;i+)k=-1;for(j=0;j1e-6&fabs(Aji)1e-6)k=-1;break;if(fabs(Aji-1)1e-6)k=j;l=i;if(k!=-1)Bk=l; 注：若求解其他类似问题，请把程序中注：若求解其他类似问题，请把程序中m,n,A,bm,n,A,b换成相应的换成相应的约束个数，变量个数，增广矩阵（方程左边的系数矩阵），约束个数，变量个数，增广矩阵（方程左边的系数矩阵），方程右

14、边的系数矩阵。方程右边的系数矩阵。2021/6/42223武汉理工大学 能源与动力工程学院能源与动力工程学院/*求得一个基本可行解，放入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;2021/6/42324武汉理工大学 能源与动力工程学院能源与动力工程学院main()int i,j,k,l,flag=1;int m,n; /*m表示约束条件数，n表示变量数,A表示增广矩阵，c表示目标函数系数向量*/double AN

15、N=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=0;for(j=0;jm;j+

16、)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;2021/6/42425武汉理工大学 能源与动力工程学院能源与动力工程学院if(flag=0) break;min=1e20;l=-1; /*求中的大于零的最小值*/for(i=0;i0&bai=min)min=bai;l=i;if(l=-1)printf(解无界！n);break;/*用1/Alk乘主行元,化主行元为1*/temp=Alk;bl/=Alk;

17、for(j=0;jn;j+)Alj/=temp;for(i=0;im;i+)if(i!=l)temp=Aik;for(j=0;jn;j+)Aij-=temp*Alj;bi-=temp*bl;InitB(A,B,m,n);2021/6/42526武汉理工大学 能源与动力工程学院能源与动力工程学院InitB(A,B,m,n);Getx(A,B,b,x,m,n);sum=0;for(i=0;i0,这表示原问题这表示原问题无无可行解，可行解，应停止计算。应停止计算。2021/6/43738武汉理工大学 能源与动力工程学院能源与动力工程学院第二阶段第二阶段：当：当w=0w=0并已得到原规划的基本可行解时

18、，并已得到原规划的基本可行解时，把所获得的基本可行解作为原问题的一个初始可行解，把所获得的基本可行解作为原问题的一个初始可行解，并将目标函数的系数改换成原问题的目标函数系数，并将目标函数的系数改换成原问题的目标函数系数，就形成第二阶段的初始单纯形表，继续用单纯形法求就形成第二阶段的初始单纯形表，继续用单纯形法求出最优解。出最优解。注注：第一阶段最终表中：第一阶段最终表中w=0,w=0,而未得到原规划的基而未得到原规划的基本可行解时，需本可行解时，需继续迭代继续迭代或或去掉多余约束去掉多余约束。2021/6/43839武汉理工大学 能源与动力工程学院能源与动力工程学院例如：用二阶段法求解例如：用

19、二阶段法求解用单纯形法求解用单纯形法求解2021/6/43940武汉理工大学 能源与动力工程学院能源与动力工程学院cj0000011cbxbbix1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-201000116-1(-3)01000x4103-20100-1/1x610100-11-210x31-201000-1/0(-1)001030x4123001-22-50x210100-11-20x31-201000000000112021/6/44041武汉理工大学 能源与动力工程学院能源与动力工程学院因所有的检验数因所有的检验数 ，表示目标函数达

20、到最小值。，表示目标函数达到最小值。 W=0 W=0 x xminmin=(0,1,1,12,0,0,0)T=(0,1,1,12,0,0,0)T因人为变量因人为变量x x6 6=x=x7 7=0,=0,又（又（0 0，1 1，1 1，1212，0 0）T T是原问题的基本是原问题的基本可行解，可以开始第二阶段的计算。可行解，可以开始第二阶段的计算。将第一阶段的最终计算表中的将第一阶段的最终计算表中的人为变量取消人为变量取消，并将目标函数，并将目标函数的的系数系数换成换成原问题原问题的的目标函数的系数目标函数的系数，作为第二阶段计算的，作为第二阶段计算的初始表初始表。2021/6/44142武汉理工大学 能源与动力工程学院能源与动力工程学院cj00000icbxbbix1x2x3x4x50x4123001-241x210100-1/1x31-20100/(-1)0001-3X141001/3-2/31X210100-11x390012/34/30001/31/3第二阶段：第二阶段：最优解最优解 x=(4,1,9)T, zmin=-22021/6/44243武汉理工大学 能源与动力工程学院能源与动力工程学院部分资料从网络收集整理而来，供大家参考，感谢您的关注！