最优化方法 第二章第二讲 单纯形法

《最优化方法 第二章第二讲 单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3单纯形法单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解1单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转回到步骤（2）。1947年，Dantzig提出的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。2一、引例用单纯形方法求解下列线性规划：minz=－6x1－4x22x1+3x2≤1004x1+2x2≤120x1、x2≥0解

2、：化为标准型minz=－6x1－4x2+0x3+0x42x1+3x2+x3=1004x1+2x2+x4=120x1、x2，x3，x4≥03基本解如下表基基本解可行否目标值对应图中的点B1=（P1，P2）X1=（20，20，0，0）T√200BB2=（P1，P3）X2=（30，0，40，0）T√180CB3=（P1，P4）X3=（50，0，0，－80）T×——DB4=（P2，P3）X4=（0，60，－80，0）T×——EB5=（P2，P4）X5=（0，100/3，0，160/3）T√400/3AB6=

3、（P3，P4）X6=（0，0，100，120）T√0OABCDEOx1x22x1+3x2=1004x1+2x2=120minz=－6x1－4x22x1+3x2+x3=1004x1+2x2+x4=120x1、x2，x3，x4≥04（1）找初始可行基：B1=（P3，P4）现成的初始可行基；此时，XB=（x3，x4）T，XN=（x1，x2）T用XN表示Z和XB有：minz=－6x1－4x2x3=100－2x1－3x2+x4=120－4x1－2x2令XN=(0,0)T有XB=(100,120)T则有：X（1

4、）=（0，0，100，120）T为对应于基B1的基可行解。问：X（1）是否最优呢？——否称非基变量在目标函数中的系数为——检验数。minz=－6x1－4x22x1+3x2+x3=1004x1+2x2+x4=120x1、x2，x3，x4≥0因为：x1和x2在目标函数中的系数为负，当x1↑，z；x2↑，z。5（2）寻找可行基B2，使其对应的基可行解X（2）能使目标函数值增加。选：x1>0则有：X（2）=（x1，0，x3，x4）Tminz=－6x1－4x2x3=100－2x1－3x2+x4=120－4x1

5、－2x2要使为X（2）基可行解，x3，x4中必有一个为零，而另一个大等于零。只要取x1=min｛100/2，120/4｝=30就有x3=40，x4=0这样X（2）=（30，0，40，0）T因为P1，P3线性无关，因此，B2=（P1，P3）为一个基而X（2）为对应于B2的基可行解此时XB=（x1，x3）T，XN=（x2，x4）T用XN表示Z和XB有：minz=－180－x2＋（3/2）x4x1=30－（1/2）x2－（1/4）x4x3=40－2x2+（1/2）x4问：X（2）是否最优呢？——否因为：x

6、2在目标函数中的系数为负，当x2↑，z。6（3）寻找可行基B3，使其对应的基可行解X（3）能使目标函数值增加。选：x2>0则有：X（3）=（x1，x2，x3，0）Tminz=－180－x2＋（3/2）x4x1=30－（1/2）x2－（1/4）x4x3=40－2x2+（1/2）x4要使为X（3）基可行解，x1，x3中必有一个为零，而另一个大等于零。只要取x2=min｛30/（1/2），40/2｝=20就有x1=20，x3=0这样X（3）=（20，20，0，0）T因为P1，P2线性无关，因此，B3=（P

7、1，P2）为一个基而X（3）为对应于B3的基可行解此时XB=（x1，x2）T，XN=（x3，x4）T用XN表示Z和XB有：minz=－200+（1/2）x3+（5/4）x4x1=20+（1/4）x3－（3/8）x4x2=20－（1/2）x3+（1/4）x4问：X（3）是否最优呢？——是，7从引例可以总结出求解过程：（1）确定初始基及其基可行解；（2）判断是否为最优解，是停止，否则转下一步；（3）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。8确定初始的基本可行解确定初始的基本可行

8、解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定.在线性规划标准型中设法得到一个m阶单位矩阵I作为初始可行基Ｂ。若在化标准形式前，m个约束方程都是“≤”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i(i=12…m)。9判断现行的基本可行解是否最优设有标准形式的线性规划问题：minz=cX；AX=b，X≥0；现假定A中存在一可行基B,且B为单位阵这样AX=b可以描述成如下形式，也就是用非基变量表示基变量x