单纯形法大M法求解线性规划问题.ppt

《单纯形法大M法求解线性规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章单纯形法单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法1考虑到如下线性规划问题其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。根据线性规划基本定理：如果可行域Ｄ={Ｘ∈Ｒn/ＡＸ=ｂ，Ｘ≥0}非空有界，则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。这个重要的定理启发了Dantzig的单纯形法，即将寻优的目标集中在D的各个顶点上。单纯形法的一般原理2Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解

2、出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（2）。3确定初始的基本可行解确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量构成的可行基，Ｎ=(Ｐm+1，

3、Pm+2，…Pn)为非基变量xm+1，xm+2，…xn的系数列向量构成的矩阵。4所以约束方程　就可以表示为用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：若令所有非基变量,则基变量由此可得初始的基本可行解5问题：要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。基由系数矩阵Ａ中m个线性无关的系数列向量构成。但是要判断m个系数列向量是否线性无关并非易事。即使系数矩阵Ａ中找到了一个基B，也不能保证该基恰好是可行基。因为不能保证基变量ＸB=Ｂ-1b≥0。为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。但是求逆阵Ｂ-1也是一件麻烦的事。结论：在线性规划标准化过程中设法得到一个m

4、阶单位矩阵I作为初始可行基Ｂ，6若在化标准形式前，约束方程中有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量．若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规划标准化过程中作如下处理：若在化标准形式前，m个约束方程都是“≤”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量xn+i(i=12…m)。7判断现行的基本可行解是否最优假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值

5、其中分别表示基变量和非基变量所对应的价值系数子向量。8要判定　　　　　　是否已经达到最大值，只需将代入目标函数，使目标函数用非基变量表示，即：其中　　　　　　　　称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN≤0，那么现在的基本可行解就是最优解。9定理1：最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量　　　　　　　　　　，则这个基本可行解就是最优解。定理2：无穷多最优解判别定理若　　　　　是一个基本可行解，所对应的检验向量，其中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。10基本可行解的改进如果现行的基本

6、可行解Ｘ不是最优解，即在检验向量中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。由此可得一个新的基本可行解，由可知，这样的变换一定能使目标函数值有所增加。11换入变量和换出变量的确定：换入变量的确定—最大增加原则假设检验向量　　　　　　　　　　　　　　　　，若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即

7、选取最大正检验数所对应的非基变量为换入变量，即若则选取对应的　　为换入变量，由于　　　　且为最大，因此当　　　由零增至正值，可使目标函数值最大限度的增加。12换出变量的确定—最小比值原则如果确定　　为换入变量，方程其中　　为Ａ中与　　　对应的系数列向量。现在需在　　　　　　　中确定一个基变量为换出变量。当　　由零慢慢增加到某个值时，的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：若则选取对应的基变量　为换出变量。13定理3：无最优解判别定理若是一个基本可行解