数学规划及其应用1-2.pptVIP

线性规划1-2 例： 0 10 0 -7 0 0 0 3 0 0 7/2 0 7/4 -4 0 0 0 21/4 0 0 -5/2 8 0 0 0 0 3/2 0 8 0 1 0 -1/2 0 0 3 0 0 0 3 5 0 5/4 0 0 -2 0 15/4 0 3 -7/6 0 0 0 0 0 -5/2 8 0 0 0 0 0 3 5 0 3/4 0 0 0 2 9/4 0 10 0 -7 0 0 0 0 0 0 7/2 0 0 0 3/2 0 8 0 16个基本解： 线性规划1-2 例： 16个基本解： 0 10 0 -7 0 0 0 3 0 0 7/2 0 7/4 -4 0 0 0 21/4 0 0 -5/2 8 0 0 0 0 3/2 0 8 0 1 0 -1/2 0 0 3 0 0 0 3 5 0 5/4 0 0 -2 0 15/4 0 3 -7/6 0 0 0 0 0 -5/2 8 0 0 0 0 0 3 5 0 3/4 0 0 0 2 9/4 0 10 0 -7 0 0 0 3 0 0 7/2 0 0 0 3/2 0 8 0 7个基本可行解： 线性规划1-2 例： 0 3 0 0 7/2 0 0 0 3/2 0 8 0 0 0 0 3 5 0 0 0 0 3 5 0 3/4 0 0 0 2 9/4 0 3 0 0 7/2 0 0 0 3/2 0 8 0 7个基本可行解： 但 相应的基： 相应的基： 即不同的基对应相同的基本可行解。 线性规划1-2 例： 0 3 0 0 7/2 0 0 0 3/2 0 8 0 0 0 0 3 5 0 3/4 0 0 0 2 9/4 7个基本可行解： 4个不同的基本可行解： -3 -3 0 -9/4 是最优解， * 第一章 线性规划 基本概念 基本定理 第二节 基本概念和基本定理 基变量、非基变量 基本解、基 基本可行解、可行基 最优基本可行解、最优基 非退化基本可行解 退化基本可行解 线性规划1-2 线性规划的标准形： 一.基本概念： 线性规划1-2 设 因此A中有m列线性无关，不妨设前m列线性无关 （非基矩阵） 称为 的一个基（基矩阵） 基列 非基列 注：(LP)的基不惟一。 线性规划1-2 例： 该(LP)有5个基： 不是基 线性规划1-2 基变量：与基列相对应的分量称为基变量 非基变量：与非基列相对应的分量称为非基变量 基列 非基列 注释：基变量，非基变量由基列，非基列来确定。 线性规划1-2 例： 该(LP)有5个基,基列决定基变量： 线性规划1-2 例： 线性规划1-2 基本解： 是 的解，称为(LP) 关于基B的基本解. 则： 令： 注：基本解完全由基来决定，一个基对应一个基本解。 线性规划1-2 例： 基本解 线性规划1-2 例： 该(LP)有5个基,5个基对应5个基本解： 第一章 线性规划 基本概念 基本定理 第二节 基本概念和基本定理 基变量、非基变量 基本解、基 基本可行解、可行基 最优基本可行解、最优基 非退化基本可行解退化基本可行解 线性规划1-2 基本解： 基本可行解： ，则称X为(LP)关于 可行基B的基本可行解。 可行基： 若 0 3 基： 是 的解，称为(LP) 关于基B的基本解. (可行域的顶点) 线性规划1-2 例： 基本解 基本可行解 B是可行基 0 3 线性规划1-2 例： 该(LP)有5个基,5个基对应都是基本可行解： 第一章 线性规划 基本概念 基本定理 第二节 基本概念和基本定理 基变量、非基变量 基本解、基 基本可行解、可行基 最优基本可行解、最优基 非退化基本可行解退化基本可行解 线性规划1-2 线性规划1-2 定理1-1（最优性判别定理） 对于 的基 B，若有 且 ，则基本可行解 是 的最优解，称为最优基本可行解, B称为最优基。最优值为 。 证明： 对 有 是最优解 线性规划1-2 证明： 定理1-1（最优性判别定理） 对于 的基 B，若有 且 ，则基本可行解 是 的最优解，称为最优基本可行解, B称为最优基。 检验数向量 非基变量检验数向量 线性规划1-2 例： 该(LP)有5个基,5个基对应都是基本可行解： 目标值： 最优目标值：1 是最优解 都是最优基 线性规划1-2 例： 是基本可行解，B是可行基。 是最优基本可行解，B是最优基。 最优目标值:1 第一章 线性规划 基本概念 基本定理 第二节 基本概念和基本定理 基变量、非基变量 基本解、基 基本可行解、可行基 最优基本可行解、最优基 非退化基本可行解退化基本可行解 线性规划1-2 对比概念： 第一章 线性规划