《运筹学5单纯形法》PPT课件

《《运筹学5单纯形法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章单纯形法1.线性规划问题的解2单纯形法3求初始基的人工变量法1.线性规划问题的解(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。基阵非基阵基向量非基向量基变量非基变量令则定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。定义在线性规划问题的一个

2、基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。基本解中最多有m个非零分量。基本解的数目不超过个。非可行解解的集合：可行解基本解最优解基本可行解解空间例现有线性规划问题试求其基本解、基本可行解并判断是否为退化解。解:(1)首先将原问题转化为标准型引入松弛变量x3和x4(2)求基本解由上式得可能的基阵由于所有

3、B

4、≠0,所以有6个基阵和6个基本解。对于基阵令则对

5、于基阵令则为基本可行解，B13为可行基为基本可行解，B12为可行基对于基阵令则对于基阵令则对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基0ABCDE1基本解为边界约束方程的交点；2基对应于可行解可行域极点；3相邻基本解的脚标有一个相同。(2)解的基本性质判别可行解为基可行解的准则定理1线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.线性规划问题的基本定理:定理2和定理3定理2线性规划问题有可行解,则它必有基可行解.定理3若线性规划问题有最优解,

6、则一定存在一个基可行解是它的最优解.几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.2单纯形法例1MaxZ=40X1+50X2X1+2X2+X3=303X1+2X2+X4=602X2+X5=24X1…X50(1

7、)单纯形法的引入解：(1)、确定初始可行解B=(P3P4P5)=IZ=0+40X1+50X2X3=30-(X1+2X2)X4=60-(3X1+2X2)X5=24-2X2令X1=X2=0X(1)=(0,0,30,60,24)TZ(1)=0(2)、判定解是否最优Z=0+40X1+50X2当X1从0↗或X2从0↗Z从0↗∴X(1)不是最优解(3)、由一个基可行解→另一个基可行解。∵50>40选X2从0↗，X1=0X3=30-2X20X230/2X4=60-2X20X260/2X5=24-2X20X22

8、4/2X2=min(30/2,60/2,24/2)=12X2：进基变量，X5：出基变量。B2=(P3P4P2)Z=0+40X1+50X2④X3+2X2=30-X1①X4+2X2=60-3X1②2X2=24-X5③③×1/2，③代入④式，①－③，②－③Z=600+40X1-25X5X3=6-X1+X5X4=36-3X1+X5X2=12-1/2X5令X1=X5=0X(2)=(0,12,6,36,0)TZ(2)=600(2)'判断∵40>0∴X(2)不是最优解。(3)'选X1从0↗，X5=0X3=6-X10X4

9、=36-3X10X2=120X1=min(6/1,36/3,1)=6X1进基，X3出基。B3=(P1P4P2)Z=840-40X3+15X5X1=6-X3+X5X4=18+3X3-2X5X2=12-1/2X5令X3=X5=0X(3)=(6,12,0,18,0)TZ(3)=840(2)"∵15>0∴X(3)不是(3)"选X5从0↗，X3=0X1=6+X50X4=18-2X50X2=12-1/2X50X5=min(18/2,12/1/2)=9X5进基，X4出基。B4=(P1P5P2)Z=975-35/

10、2X3-15/2X4X1=15+1/2X3-1/2X4X5=9+3/2X3-1/2X4X2=15/2-3/4X3+1/4X4令X3=X4=0X(4)=(15,15/2,0,0,9)TZ(4)=9750(0,0)X2X1ADCB(0,12)(6,12)(15,7.5)X(4)X(1)X(2)X(3)Z=40X1+50X2单纯形法小结：单纯形法是这样一种迭代算法——如下图…当Zk中非基变量的系数的系数全为负值时，这时