最优化方法课件ecture2 LP基本性质.pptVIP

基和基本解 （1）系数矩阵A中任意m列所组成的m阶可逆子方阵B，称为(LP)的一个基(矩阵)，变量xj，若它所对应的列Pj包含在基B中，则称xj为基变量，否则称为非基变量。基变量的全体称为一组基变量，记 按列分块 称x为(LP)的基本解。 基矩阵为： 求基解 只有x(1)和x(5)为基本可行解。 线性规划问题解的关系 约束方程的 解空间 基解 可行解 非可行解 基本可行解 可行解、基解和基本可行解举例 可行解、基本解和基本可行解举例 基本可行解与极点之间的关系 定理 设 是LP的可行域， ，则 是 的极点 是LP的基本可行解 基可行解的存在性 定理1．如果 LP 有可行解,则一定存在基本可行解. 定理2．如果 LP 有最优解，则存在一个基本可行解是最优解。 结论：若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解。 Ex Homework 一、 陈宝林书 P36 3， 4 Homework * * 最优化方法 Optimization 第二章 线性规划的基本性质 主要内容 线性规划的标准形 线性规划的图解法 线性规划的基本性质 LP的标准形 1、极小化型 2、约束方程为等式 3、所有的决策变量为非负值 4、约束方程的右端项系数为非负值 矩阵形式 (LP) 非标准形LP模型转化为标准形LP模型 目标函数是极大化的转化 决策变量无约束转化为非负约束 不等式约束转化为等式约束(松弛变量) 决策变量有上下界的转换 含有绝对值 两变量线性规划问题的图解法 1.线性不等式的几何意义— 半平面 作出LP问题的可行域 作出目标函数的等值线 移动等值线到可行域边界得到最优点 2.图解法步骤 例 Z=36 结论：若LP问题存在最优解，则必在 可行域的某个极点上找到。 一般的，当等值线沿目标函数法向量(梯度)方向平 行移动时，目标函数值逐步增加；当等值线沿目标函 数法向量反方向平行移动时，目标函数值逐步减少。 x1 x2 50 100 150 150 100 50 l2 O A B C z=500 z=1000 z=1260 (30,80) 几种特殊情况 LP存在多个最优解 l1 LP问题无可行解 50 150 100 150 50 x 2 O 100 l 1 x 1 l 2 LP问题存在无界解 判断：若LP的可行域无界，则该LP可能存在无界解。 O x 1 x 2 2 3 1 4 1 2 3 l 1 l 2 A B z C 图解法的作用 能解决少量问题 LP问题 有可行解 有最优解 唯一解 无穷多解 无最优解（可行域为无界） 无可行解（无解） 规律1： 揭示了线性规划问题的若干规律 Ex 将下列线性规划变成标准形式 LP问题的基本性质 可行解： 满足LP模型的约束条件且满足非负条件的解。 例： 定理1: 线性规划(LP)的可行域是凸集。 最优极点 代入标准形 定理2．设线性规划(L)的可行域非空，则 （1）(L)存在有限最优解的充要条件是对任意的j, cd(j)≥0, 其中d(j)为可行域的极方向。 （2）若(L)存在有限最优解，则目标函数的最优值可在 某个极点达到。 * * 非基变量 基变量 图中的点 解 x1, x2 x3 =10 x4 =8 x5 =7 O 基本可行解 x1, x3 x2 =10 x4 =-2 x5 =-3 F 基本解 x1, x4 x2 =8 x3 =2 x5 =-1 E 基本解 x1, x5 x2 =7 x3 =3 x4 =1 A 基本可行解 x2, x3 x1 =5 x4 =3 x5 =7 D 基本可行解 x2, x4 x1 =8 x3 =-6 x5 =7 H 基本解 x3, x4 x1 =2 x2 =6 x5 =1 C 基本可行解 最优解 x3, x5 x1 =1.5 x2 =7 x4 =-0.5 G 基本解 x4, x5 x