最优化方法第二章 单纯形法ppt课件.ppt

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

1、第二讲单纯形法单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法12.1单纯形法的一般原理1确定初始的基本可行解2判断现行的基本可行解是否最优3基本可行解的改进——基变换4用初等变换求改进了的基本可行解——旋转变换2Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下：（1）寻找一个初始的基本可行解。（2）检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否

2、则转一步。（3）移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（2）。3找出一个初始可行解是否最优转移到另一个目标函数（找更小的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代结束其步骤如下：41确定初始的基本可行解确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定.为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即其中为基变量x1，x2，…,xm的系数列向量构成的可行基，为非基变量xm+1，xm+2，…,xn的系数列向量构成的矩阵。

3、5线性规划问题基变换的矩阵表示==目标函数约束条件右边常数6===7线性规划问题基变换的表格表示C0AbCBCN0BNbCBCN0IB-1NB-1b8所以约束方程AX=b就可以表示为:得：若令所有非基变量XN=0,则基变量由此可得初始的基本可行解92.判断现行的基本可行解是否最优假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值其中　　　　　　　　　　　　　　　　　　分别表示基变量和非基变量所对应的目标函数系数子向量。怎样判定　　　　　　是否已经达到最小值???10zXBXNRHS10－(CBB-1N－CN)CBB-1b

4、0IB-1NB-1b11其中　　　　　称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均大于等于0，即σN≥0，那么现在的基本可行解就是最优解。12定理3.2设是对应基的基可行解，如果向量的第个分量，且向量，则原问题无界（无最优解）1314定理1：最优解判别定理对于线性规划问题若某个基本可行解所对应的检验向量　　　　　　　　，则这个基本可行解就是最优解。定理2：无穷多最优解判别定理若　　　　　是一个基本可行解，所对应的检验向量，其中存在一个检验数σm+k=0，则线性规划问题有无穷多最优解。15定理3：无有界最优解判别定理若

5、　　　　　是一个基本可行解，所对应的检验向量,其中存在一个检验数，且该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则线性规划问题无有界最优解。163.基本可行解的改进——基变换如果现行的基本可行解Ｘ不是最优解，即在检验向量σN=CN－CBB－1N中存在负的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：先从检验数为负的非基变量中确定一个换入变量，使它从非基变量变成基变量，再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量。由此可得一个新的基本可行解，由可知，这样的变换一定能使

6、目标函数值有所减少。17则选取对应的xm+k为换入变量，由于σm+k<0且为最小，换入变量和换出变量的确定：换入变量的确定—最大减小原则若其中有两个以上的检验数为负，那么为了使目标函数值下降得快些，通常要用“最大减小原则”，即选取最小负检验数所对应的非基变量为换入变量，即若因此当xm+k由零增至正值，假设检验向量可使目标函数值最大限度的减小。18如果确定Xm+k为换入变量，方程则选取对应的基变量Xl为换出变量。其中Pm+k为Ａ中与Xm+k对应的系数列向量。现在需在XB=(x1,x2,…,xm)T中确定一个基变量为换出变量。当xm+k由零慢慢增加到

7、某个值时，XB的非负性可能被打破。为保持解的可行性，可以按最小比值原则确定换出变量：换出变量的确定—最小比值原则194.用初等变换求改进了的基本可行解——旋转运算假设Ｂ是线性规划　　　　　　　　　　的可行基，则令非基变量　　　，则基变量　　　　　。可得基本可行解　。用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等“行变换”。变换的结果是将系数矩阵Ａ中的可行基Ｂ变换成单位矩阵I，把非基变量系数列向量构成的矩阵Ｎ变换成，把向量b变换成。20CBB-1aj－cj=zj－cj称为非基变量的检验数B-1aj=Yj，B-1b=b’，CBB-1b=z

8、0zXB…xj…RHSz1CB…-cj…00B…aj…bz10…CBB-1aj－cj…CBB-1b0I…B-1aj…B-1bz10…zj