第二章线性规划讲义.ppt

推论若x0是原始线性规划的可行解,y0是对偶线性规划的可行解,且cTx0=bTy0,则x0与y0分别是原始线性规划问题与对偶线性规划问题的最优解. 推论2(补充) 对偶的线性规划都有最优解的充 要条件是两者都有可行解. 定理2.8.6 若原始线性规划问题与对偶线性规 划问题之一具有无界的目标函数值,则另一个无可行解. 对偶性定理 定理2.8.5 若原始线性规划问题与对偶线性规划问题之一有最优解,则另一个也有最优解,并且它们目标函数的最优值相等. 对偶的线性规划问题的解 两个互为对偶的线性规划的解的情况 (1)两个都有可行解¨两个都有最优解,最优值相等¨一个有最优解 (2)两个都无可行解(书中有错) (3)一个有可行解,无最优解(目标函数无界),则另一个无可行解 互补松弛性 §2.9 对偶单纯形法 单纯形方法与对偶单纯形方法 1. 最优性的判别 §2.6 初始基可行解的求法 2.6.1 大M单纯形法 大M方法算例 2.6.2 两阶段单纯形法 两阶段法算例 求解原线性规划的单纯形表 §2.8 线性规划的对偶理论 原始问题 对偶问题 对偶规划(定义2.8.1) 对合性 定理2.8.1 对偶线性规划的对偶问题是原始线性规划问题 对偶规划的写法 写出对偶规划 非对称形式的对偶线性规划 弱对偶性定理 矩阵-向量形式的标准型 矩阵-向量形式的标准型 可行域为凸集 一般形式转化为标准型 基本概念 基本概念 基本概念 §2.3 线性规划的基本定理 有可行解→有基可行解 有最优解→有最优的基可行解 单纯形方法的思路 找出一基可行解(极点) 若其不是最优,找到一个相邻极点 新的目标函数值不大于原目标函数值 经过有限次迭代给出最优解或判断无最优解。 §2.4 单纯形方法 规范式 2.4.1 基可行解是最优解的判断 准则 判别数 最优性条件 例2.4.1 考虑线性规划 判断无最优解 基可行解的转换 基可行解的转换 单纯形方法 如果线性规划是非退化的,则按照上面的方法 (进基,离基)迭代一次后,目标函数值有所下降. 经过有限次迭代之后,一定可以得到一个基可 行解,使得其所有判别数非负(得到最优解),或 者其有一个判别数是负的,但对应列向量的所 有分量非正(线性规划无最优解). 这种求解线性规划的方法称为单纯形方法. 单纯形法的迭代步骤 单纯形法的迭代的主要工作是将原来的规范式写为新的规范式. 通过初等行变换将主元变为1通过初等行变换将主元所在列其它元素变为0得到新的规范式 §2.5 单纯形表 第二章线性规划 §2.1 凸集与凸函数 凸集 设V是实数域R上的线性空间（或称为向量空间），若V上定义着正定对称双线性型g（g称为内积），则V称为（对于g的）内积空间或欧几里德空间（有时仅当V是有限维时，才称为欧几里德空间）。具体来说，g是V上的二元实值函数，满足如下关系： （1）g(x,y)=g(y,x)； （2）g(x+y,z)=g(x,z)+g(y,z)； （3）g(kx,y)=kg(x,y)； （4）g(x,x)=0，而且g(x,x)=0当且仅当x=0时成立 例2.1.2 超球||x||≤r为凸集 凸集的性质 X1 X2 X(1) X(2) X 图（1-7） X1 X2 X(1) X(2) -X(2) X(1) -X(2) 图（1-7） X X1 X2 X(1) X(2) X X(1) -X(2) y= ?(X(1) -X(2) ) (0 ? 1) X=X(2)+y = X(2)+ ?(X(1) -X(2) ) = ? X(1) +(1- ?)X(2) 图（1-7） X1 X2 X(1) X(2) X -X(2) X(1) -X(2) 图（1-7） X=X(2)+y = X(2)+ ?(X(1) -X(2) ) = ? X(1) +(1- ?)X(2) y= ?(X(1) -X(2) ) (0 ? 1) 极点 极点 凸函数 凸函数的例子 凸函数的几何性质 凸函数的几何性质 上图 对于一元凸函数f(x),可以发现,位于函数曲线 上方的图形是凸集.事实上这一结论对于多元 函数也是成立的,而且是充要条件,即有下面的 定理. 定理:设f(x)是定义在凸集 上的函数,则f(x)是凸函数的充要条件是其上图epi(f)为凸集,其中epi(f)= 证明:作业 凸函数的性质 凸函数的判断 凸函数的判断 一阶条件 二阶条件 凸规划 定理2.1.5证明(思路) §2.2 线性规划的标准型 与基本概念 线性规划的一般形式 线性规划的标准型