最优化方法课件_图解法和LP基本定理.pptVIP

第三节 LP基本定理 * * 线 性 规 划 Linear Programming 邵红梅 考虑如下约束数学规划模型 其中: 都是线性函数. 即: 3. LP基本定理 4. 单纯形法 1. 图解法 5. 大M法 第二章 线性规划（LP） 6. LP对偶理论（对偶单纯形法） 2.LP标准形 * 7. 灵敏度分析及应用 确定可行域： 画约束直线，确定满足约束条件的半平面，所有半平面的交集，即为线性规划的可行域。 确定目标函数的等值线及优化方向： 画一条目标函数等值线，并确定目标函数优化的方向。 平行移动目标函数等值线，通过观察得到线性规划的最优解。 图解法的步骤 * 第一节 图解法 例1. 用图解法求解线性规划问题 二、例题解析 * x1 x2 o -3X1 -4X2 =-12(≥) Lo： 0 = 2X1 + X2 D 此点是唯一最优解， 且最优目标函数值 min Z=-7 可行域 * 解： 例2. x1 x2 o X1 - 1.9X2 = 3.8 (≤) X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = -3.8(≥) X1 + 1.9X2 = 10.2 (≤) （7.6，2） D L0： 0=3X1+5.7X2 max Z （3.8，4） 30.6 = 3X1+5.7X2 蓝色线段上的所有点都是最 优解。这种情形为有无穷多最 优解，但是最优目标函数值 max Z=30.6是相同的。 可行域 * 例2. x1 x2 O 10 20 30 40 10 20 30 40 50 50 可行域是空集 无可行解(即无最优解) max Z=3x1+4x2 * 例3. 2X1 + X2 = 40(≤) X1 +1.5 X2 = 30(≤) X1 + X2 = 50(≥) 线性规划的图解法启示： 线性规划问题的解有多种情形； 若线性规划的可行域非空，则一定是凸集（区域内任意两点连线都在其中）； 线性规划问题若有最优解,则最优解在可行域的某顶点上达到. 优缺点 简单、直观、便于初学者理解和记忆； 仅适用于低维情况，通常适用于含两个或三个变量的情况。 * 对于高维情况, 怎么求解呢? ----- 单纯形法 第二节 线性规划的标准形 * 线性规划的形式是多种多样的: 目标函数求极大(极小); 约束可能有等式约束, 也可能有不等式约束; 决策变量有的受非负约束,有的是无限制. 为了方便研究, 考虑将各种形式的LP化为一种统一 的形式, 这种形式即被称为LP的标准形式. * 一、LP标准形 三大特点 目标函数：min 约束条件：= 变量符号：≥0 二、化LP为标准型的方法 * * 例1 2. 举例 分析:共有4处不符合标准形的要求. 解: * 则相应的标准形为 * 例2 分析:共有5处不符合标准形的要求. 解: * 则相应的标准形为 将LP化为标准形后,如何求最优解呢? 有一个定理给出了这个问题的答案, 这就是LP基本定理. * LP标准形的矩阵形式 其中 * 考虑具有标准形的LP: 一、线性规划的基本概念 约束系数矩阵A是m×n 矩阵, m≤n，并且 r (A)＝m. 当 m＝n 时，基矩阵唯一; 当 m n 时，基矩阵就可能有多个，但数目不超过 个。 1. 基矩阵: 若A中的m×m子矩阵B满足 r (B)＝m, 即 则称B是LP问题的一个基矩阵（简称为基）。 于是A中至少有一个m×m子矩阵B，使得：r (B)＝m。 约束方程的系数矩阵为： 例1 设 易看出 r（A）=2，2 阶子矩阵有 = 10个，而基矩阵只有9个， * 2. 基向量: 基矩阵对应的列向量称为基向量，其余列向量称为非基向量. 3. 基变量: 基向量对应的变量称为基变量，非基向量对应的变量称为非基变量(自由变量)。 例如：对于基B2而言，x1 , x4是基变量，x2 , x3 , x5是非基变量。 x1 x4 思考：基变量的选取唯一吗？取法有多少种？ 【注】基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。 4. 基本解: 对于某一确定的基B，令所有的自由变量等于零, 求出 Ax=b的解，称这组解为LP问题的关于基Ｂ 的基本解。 5. 基可行解: 非负的基本解称为基可行解（基本可行解）. 【注】基可行解也被定义为“可行的基本解”。 * 注: 基变量的选取方式 有限, 所以基本解的个数也为有限个. 可见：求基可行解要