第一章 线性规划及单纯形法.pptVIP

第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 e.g. 1 资源的合理利用问题 第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 e.g. 2 营养问题 第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 三个基本要素： 第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 线性规划问题的标准形式： 第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 　３、右端项bi 0时，只需将等式两端同乘（-1） 则右端项必大于零 第一章 线性规划及单纯形法 §1 线性规划问题及其数学模型 LP的几种表示形式： §2 线性规划问题的图解法 定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x1,x2,…,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D={ x | Ax = b ,x≥0 }。 §2 线性规划问题的图解法 第一章 线性规划及单纯形法 LP问题图解法的基本步骤： §2 线性规划问题的图解法 第一章 线性规划及单纯形法 §2 线性规划问题的图解法 由以上两例分析可得如下重要结论： §2 线性规划问题的图解法 图解法优点： §3 线性规划问题解的基本性质 讨论如下 LP 问题： 第一章 线性规划及单纯形法 定义 3 在上述 LP 问题中，约束方程组（2）的系数 矩阵 A 的任意一个 m×m 阶的非奇异的子方阵 B （即 |B|≠0），称为 LP 问题的一个基阵或基。 §3 线性规划问题解的基本性质 第一章 线性规划及单纯形法 §3 线性规划问题解的基本性质 基本解唯一吗？ 最多有多少？ 第一章 线性规划及单纯形法 LP 问题解的基本性质 §3 线性规划问题解的基本性质 定理 2 证明 第一章 线性规划及单纯形法 假定有δi≠0， §3 线性规划问题解的基本性质 再由 的取法知，在式 (7) 的诸式中， 至少有一个等于零，于是所作的可行解 中，它的 非零分量的个数至少比 x 的减少1，如果这些非零分量所对应 的列向量线性无关，则 为基可行解，定理成立。 §3 线性规划问题解的基本性质 定理 3 证明 第一章 线性规划及单纯形法 LP 问题解的几何意义 §3 线性规划问题解的基本性质 定义 6 设 则称 第一章 线性规划及单纯形法 定理 5 设 D 为 LP 问题的可行解集， ，则 x 是 D 的极点的充分必要条件是 x 为 LP 问题的基可行解。 §3 线性规划问题解的基本性质 Note: §4 单纯形法的基本原理 单纯形法（Simplex Method）是1947年由 G.B. Dantzig 提出，是解 LP 问题最有效的算法之一， 且已成为整数规划和非线性规划某些算法的基础。 第一章 线性规划及单纯形法 单纯形法引例 §4 单纯形法的基本原理 因为x2 的系数大，所以x2 换入基变量。 第一章 线性规划及单纯形法 因为x1 的系数大，所以x1 换入基变量。 §4 单纯形法的基本原理 目标函数用非基变量表示时，非基变量的系数 称为检验数 第一章 线性规划及单纯形法 单纯形法的基本原理 §4 单纯形法的基本原理 如果记 第一章 线性规划及单纯形法 定理 7 在 LP 问题 的典式 (1b) ～(3b)中， 如果有 §4 单纯形法的基本原理 定理 8 在 LP 问题 的典式 (1b) ～(3b)中， 第一章 线性规划及单纯形法 定理 9 在 LP 问题的典式 (1b) ～(3b)中，如果检验 数满足最优准则 σj ≤ 0 ( j = m+1 ,…,n )，且其中有一 个 σk = 0 ( m+1 ≤ k ≤n )，则该 LP 问题有无穷多个 最优解。 §5 单纯形法的计算步骤 第一章 线性规划及单纯形法 如何得到单纯形表？ §5 单纯形法的计算步骤 e.g.4 列出如下 LP 问题的初始单纯形表。 第一章 线性规划及单纯形法 单纯形法求解 LP 问题的计算步骤： §5 单纯形法的计算步骤 第一章 线性规划及单纯形法 §5 单纯形法的计算步骤 思考： §6 单纯形法的进一步讨论 一、初始可行基的求法 §6 单纯形法的进一步讨论 (1)大 M 法 第一章 线性规划及单纯形法