最优化理论与方法2单纯形法

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

1、第2章线性规划的基本性质o2.1标准形式及图解法o2.2基本性质2.1标准形式o一般线性规划问题总可以写成下列标准形式：nmincjxjj1n(2.1.1)s.t.aijxjbii1,...,mj1x0j1,...,njo用矩阵表示：mincxs.t.Axb(2.1.2)x0其中，A是mXn矩阵，c是n维行向量，b是m维列向量。为了计算方便，一般假设b0，即b的每个分量都是非负数。表示定理o设S{x

2、Axb,x0}为非空多面集，则有：(1)(k)n极点集非空，且存在有限个极点x,...,x.n极方向集为空集的充要条件是S有界。若

3、S无界，则存在有限个极方向(1)(l).d,...,dnx∈S的充要条件是：kl(j)(j)xjxjdj1j1kj1,j10,j1,...,k,j0,j1,...,l.j定理与结论o线性规划的可行域是凸集。o设线性规划(2.1.2)的可行域非空，则有下列结论：(j)n线性规划(2.1.2)存在有限最优解的充要条件是所有cd为非负数，(j)其中d是可行域的极方向。n若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点）极点是个几何概念，直观性强，但不便于演算，因此需要研究极点的代数含义。

4、基本可行解o又若1，则称Bb0xB1bBxB1box称为方程组的一个基本解；xB为约束条件x0Nx0NoB称为基矩阵，简称基；Axb,x0的基本可行解，oxB的各分量称为基变量；称B为可行基矩阵，o基变量的全体x,x,...,x称为一组基；B1B2BmxB,xB,...,xB为一组可行基；12moxN的各分量称为非基变量；o若1，则称基本可行解是非退化的Bb0基本可行解；1o若Bb0且至少有一个分量是零，则称此时的基本可行解是退化的基本可行解；同时，此基本可行解对应的基被称为退化的

5、可行基。基本可行解的个数o若A是mXn矩阵，A的秩为m时，基本可行解的个数不会超过：nn!mm!(nm)!定理与推理o线性规划的可行域是凸集。o设线性规划(2.1.2)的可行域非空，则有下列结论：(j)n线性规划(2.1.2)存在有限最优解的充要条件是所有cd为非负数，(j)其中d是可行域的极方向。n若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点）o线性规划的可行域的极点集与基本可行解集等价；o当线性规划(2.1.2)有可行解，则一定存在基本可行解。o当线性规划(2.1.2)存在最优解时，则一定存在

6、一个基本可行解是目标函数的最优解。（最优基本可行解）第3章单纯形方法o3.1单纯形方法原理o3.2两阶段法o3.3修正单纯形法单纯形方法的基本思想o就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。o怎样实现基本可行解的转换？minfcxs.t.Axb表格形式的单纯形法x0minfminf11s.t.fcxcx0s.t.xBNxBbBBNNBN11BxBNxNbf0xB(cBBNcN)xNcBBbx0,x0x0,x0BNBNfxx右端BNx0IB

7、-1NB-1bBmf10cB-1N-ccB-1bBNBo显然，在单纯形表中包含了单纯形方法所需的全部数据。表格形式的单纯形法进基变量离基xBxBxBxjxk1rm变量x100yybB11j1k1x010yybBrrjrkrx001yybBmmjmkmf000zjcjzkckcBb主元brbizcmax{zc}xmin

8、y0kkjjkikyyrkiko显然，在单纯形表中包含了单纯形方法所需的全部数据。表格形式的单纯形法o解的几种情况在单纯形表上的体现(min型

9、)：n唯一最优解：终表非基变量判别数均小于零；n多重最优解：终表非基变量判别数中有等于零的；n无界解：任意表有正判别数相应的系数列均非正。omax型单纯形表与min型的区别仅在于：判别数反号，即，n令负判别数中最小的对应的变量进基；n当判别数均大于等于零时为最优。两阶段法o用单纯形法消去人工变量（如果可能），即把人工变量变为非基变量，求出原问题的一个基本可行解；xn首先引入人工变量。令Axxab，即(A,I)bmxx0,x0aax0,x0an消去人工变量的一种方法是解如下第一阶段问题：设得到的最优基本可行解是TTT，此T(x,x)

10、minexaa时必有下列三种情况之一：s.t.Axxb（1）x