最优化 第二章 线性规划

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

最优化理论算法及工程应用

第2章 章

线性规划

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划线性规划：目标函数是线性的， 线性规划：目标函数是线性的，约束条件是 线性等式或不等式。 线性等式或不等式。

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划的历史 渊源要追溯到 渊源要追溯到Euler、Liebnitz、Lagrange等 、 、 等 George Dantzig, Non Neumann(Princeton)和 和 Leonid Kantorovich在1940’s创建了线性规划 在 ’ 创建了线性规划 1947年, George Dantzig于发明了单纯形法 年 于发明了单纯形法 1979年，L. Khachain找到了求解线性规划的一 年 找到了求解线性规划的一 种有效方法(第一个多项式时间算法 椭球内点法) 第一个多项式时间算法- 种有效方法 第一个多项式时间算法-椭球内点法 1984年，Narendra Karmarkan发现了另一种求 年 发现了另一种求 解线性规划的有效方法， 解线性规划的有效方法，已证明是单纯形法的强 有力的竞争者(投影内点法 投影内点法) 有力的竞争者 投影内点法 现在求解大规模、退化问题最有效的是原-对偶 现在求解大规模、退化问题最有效的是原 内点法

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

EX. 运输问题

产销平衡 不平衡 产销平衡/不平衡的运输问题 平衡 不平衡的运输问题

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划的一般形式

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划的标准形

向量表示： 向量表示：

标准形的特征：极小化、等式约束、 标准形的特征：极小化、等式约束、变量非负

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

一般形式

转化

标准形

称

松弛(slack)/盈余 盈余(surplus)变量 松弛 盈余 变量

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

EX. 化成标准形等 价 表 示 为

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

基本解与基变量其中 满秩假定： 满秩假定： m<n,且 的行向量线性无关 ，且A的行向量线性无关 ，且 个线性无关列组成的矩阵. 定义 设B是A 的m个线性无关列组成的矩阵 置 是 个线性无关列组成的矩阵 所有与B无关列对应的变量为零 无关列对应的变量为零， 所有与 无关列对应的变量为零，称所得方程组 的解是Ax=b的基本解 的基本解(basic solution) 的解是 的基本解 ； 称B是基(basis); 是 称与B对应的变量为基变量(basic variables) 对应的变量为基变量 称与 对应的变量为基变量

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

基本可行解的非负基本解是标准形 标准形的 定义 称 的非负基本解是标准形的基 本可行解(basic feasible solution);例. 基本可行解及几何意义

基本可行解的个数不超过 基本可行解的个数不超过

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划的基本定理考虑线性规划标准形，其中 是秩为 是秩为m的 × 阶 考虑线性规划标准形，其中A是秩为 的m×n阶 矩阵，则以下结论成立： 矩阵，则以下结论成立：

i) 若有可行解，则必存在基本可行解； 若有可行解， 必存在基本可行解 基本可行解； ii) 若有解，则必有某个基本可行解是最优解 若有解， 必有某个基本可行解是

最优解 是最优解.

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

极点与基本可行解的等价性定理考虑线性规划标准形，其中 是秩为 是秩为m的 × 考虑线性规划标准形，其中A是秩为 的m×n 矩阵， 矩阵，令 当且仅当x是线性规划的基本可行解 则x是 K 的极点当且仅当 是线性规划的基本可行解 是 的极点当且仅当 是线性规划的基本可行解.

推论： 推论：i) 若K非空，则至少有一个极点 非空， 非空 则至少有一个极点. ii) 若线性规划有解，则必有一个极点是最优解 若线性规划有解，则必有一个极点是最优解. iii) K的极点是有限集 的极点是有限集. 的极点是有限集

几 何 形 式

线 性 规 划 基 本 定 理 的

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

例1 .K 有3个极点 个极点 个基本解， 有3个基本解，均可行 个基本解

例2.

K 有2个极点 个极点 个基本解， 个 有3个基本解，2个可行 个基本解

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

例3.Subject to

5个极点 个极点 -极点

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划问题解的几种情况

第二章 线性规划2.1 线性规划的标准形2.2 线性规划的基可行解2.3 单纯形法2.5单纯形表2.6初始基可行解的确定与大M单纯形法

线性规划解的几何特征 线性规划解的几何特征 有解：唯一解/多个解(整条边、面、甚至 有解：唯一解/多个解(整条边、 有顶点解 整个可行集) 整个可行集) 无界：没有有限最优解 无界： 不可行：没有可行解 不可行： 无解

可行集：多边形(二维) →多边集(高维空间) 可行集：多边形(二维) 多边集(高维空间) 给出有效的代数刻画和严谨的几何描述， 给出有效的代数刻画和严谨的几何描述，从理论上证 有效的代数刻画 实上述几何特征， 实上述几何特征，并寻求有效算法