运筹学02单纯形法

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

1、设线性规划的标准形式：maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)可行域：由约束条件(2)、(3)所围成的区域；可行解：满足(2)、(3)条件的解X=(x1，x2，…，xn)T为可行解；基：设A是约束条件方程组的m×n维系数矩阵,其秩为m，B是A中m×m阶非奇异子矩阵，则称B为线性规划问题的一个基。设复习:线性规划问题解的概念B==(p1,p2,…,pm)a11a12…a1ma21a22…a2m………am1am2…amm基向量、非基向量、基变量、非基变量：称pj(j=1,2,…,m）为基向量

2、，其余称为非基向量；与基向量pj(j=1,2,…,m）对应的xj称为基变量，其全体写成XB=（x1，x2，…，xm）T；否则称为非基变量，其全体经常写成XN。基解：对给定基B,设XB是对应于这个基的基变量XB=(x1，x2，…，xm)T；令非基变量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T称为基解。基可行解：所有决策变量满足非负条件(xj≥0)的基解,称作基可行解。可行基：基可行解所对应的基底称为可行基。写出下述线性规划问题对应的基、基变量、基解、基可行解和可行基。定理2：X是线性规划问题的基可行解的充

3、要条件是它对应于可行域D的顶点。（线性规划问题的基可行解X对应于可行域D的顶点。）定理3：若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到最优.§3单纯形法（SimplexMethod）例子：求解线性规划问题线性规划问题的最优解，可以从基可行解中找到图解法有局限性；枚举法计算量大；§3.1单纯形法的引入0Q4Q31123234Q2Q1X1X2x1+2x2=84x1=164x2=12解:首先:将该问题化成标准形第二:找初始可行解(即一个顶点)。系数矩阵A=(p1p2p3p4p5)矩阵形式因为p3，p4，p5线性独立，故B=(p3,p4

4、,p5)构成一个基底，对应的基变量x3，x4，x5解出来为（用非基变量表示基变量）x3=8-x1-2x2x4=16-4x1(a)x5=12-4x2将(a)代入目标函数中得z=0+2x1+3x2令非基底变量x1=x2=0，则有z=0。这时得到一个基可行解X(0)=(0,0,8,16,12)T---原点第三:判别从目标函数中得知，非基底变量的系数为正，因此，将非基变量换入基底后可使目标函数增大，转入第四步第四:换基底(旋转迭代)确定换入变量：由于z=0+2x1+3x2中非基底变量x2系数贡献最大3，故换入基底为x2。换入变量已定，必须从x3，x4，x5换出一

5、个，并且要保证其余均是非负的，即x3，x4，x50。x3=8-2x20x4=160x5=12-4x20由此，只要选择x2=min(8/2，-，12/4)=3，对应基底变量x5=0，从而确定用x2和x5对调，即将x5换出。有x3=2-x1+1/2x5x4=16-4x1(b)x2=3-1/4x5将(b)代入目标函数中得z=9+2x1-3/4x5令非基变量为零，又得到另一个基可行解X(1)=(0,3,2,16,0)T–顶点Q4返回第三步：非基变量x1的系数是正的，还可增大，X(1)不是最优解。重复上述步骤。由于x1的系数是正的，从而x1为转入变量，再由

6、x3=2-x10x4=16-4x10x2=30只要选x1=min{2，16/4，-}=2上式就成立，因为x1=2时，基变量x3=0，从而由x1换出x3，得x1=2-x3+1/2x54x1+x4=16(c)x2=3-1/4x5高斯消去法（行变换）得x1=2-x3+1/2x5x4=8-2x5+4x3x2=3-1/4x5代入目标函数中，得z=13-2x3+1/4x5令非基变量x3=x5=0，又得到另一个基可行解X(2)X(2)=(2,3,0,8,0)T–新顶点Q3同理，返回第三步，再迭代，x5作为转入变量x1=2+1/2x50x4=8-2x50x2=

7、3-1/4x50只要取x5=min{-，8/2，12}=4就有上式成立。x5=4时，x4=0，故决定用x5换x4x1=4-1/4x4x5=4-1/2x4+2x3x2=2+1/8x4–1/2x3代入得z=14-3/2x3–1/8x4，令x3，x4=0得z=14。新基可行解为X(3)=(4,2,0,0,4)T–为最优解，新顶点Q2最优目标值z=14。从实际例子中分析单纯形法原理的基本框架为第一步：将线性规划模型变换成标准型，确定一个初始可行解（顶点）。第二步：对初始基可行解最优性判别，若最优，停止；否则转下一步。第三步：从初始基可行解向相邻的基可行解

8、（顶点）转换，且使目标值有所改善—目标函数值增加，重复第二和第三步直到找到最优解