单纯形法的预备知识.pptVIP

单纯形法的预备知识 1. 线性规划的标准型 (The Standard Form of LP) 单纯形法的预备知识 单纯形法的预备知识 单纯形法的预备知识 单纯形法的预备知识 如何将非标准型转化为标准型 单纯形法的预备知识 例 1 单纯形法的预备知识 例 2 单纯形法的预备知识 2 线性规划的解的概念 单纯形法的预备知识 单纯形法的预备知识 单纯形法的预备知识 单纯形法的预备知识 则求解如下： 非基变量 基变量 基本解 基可行解 {x1, x2} {x3, x4, x5} (0, 0, 100, 80, 40) Y {x1, x3} {x2, x4, x5} (0, 100, 0, -20, 40) N {x1, x4} {x2, x3, x5} (0, 80, 20, 0, 40) Y {x1, x5} { x2 x3, x4} 无解 - {x2, x3} {x1, x4, x5} (50, 0, 0, 30, -10) N {x2, x4} {x1, x3, x5} (80, 0, -60, 0, -40) N {x2, x5} {x2, x3, x4} (40, 0, 20, 40, 0) Y {x3, x4} {x1, x2, x5} (20, 60, 0, 0, 20) Y {x3, x5} {x1, x2, x4} (40, 20, 0, 20, 0) Y {x4, x5} {x1, x2, x3} (40, 40, -20, 0, 0) N 单纯形法的预备知识 单纯形法的预备知识 3 线性规划的基本理论 单纯形法的预备知识 单纯形法的预备知识 定理 1. 任何线性规划问题的可行域都是凸集. 单纯形法的预备知识 小结 1. 线性规划问题的标准型 2 线性规划问题的有关解的概念 3 线性规划问题的基本理论 * * 定义 简写为 令 向量形式 令 矩阵形式 如果第 i 个约束条件为 “ ≤ ”, 则在该不等式的左边加上非负 松弛变量 si ，把不等式变为等式. (iii) 如果第 i 个约束条件为 “≥”, 则在该不等式的左边减去非负 剩余变量 ei ，把不等式变为等式. (i) 如果是求目标函数极小化的问题，即 min z=CX，则令 w= -z，转化为对w 实现极大化，即 max w= -CX . (v) 如果变量 xi 无符号限制，可令 其中 (iv) 如果第 i 个约束条件的右端项 bi ≤0, 则在该约束的两端同时 乘以 “-1”, 然后再做相应的变换. AX=b --- m 个方程，n 个变量 (mn)，其中R(A)=m. 基(Basis)： 称 A 中任一个 m 阶可逆矩阵 B 为线性规划问题 的一个基 基向量 (Basic Vector)： 若记基 则称 为基 B 中的一个基向量 （非）基变量 (Basic Variable)： 与基向量 相对应的变量 称为基 变量。 否则称为非基变量 基本解 (Basic Solution)： 取 A 中一个基 ，则对应的基变量为 这时称相应的非基变量取值均为零的条件下,满足约束条件AX=b 的解为 基本解 基 基本解 例 3. 求下面方程组的所有基本解。 基变量 非基变量 基本解 {x1, x2} {x3} (2, 1, 0) {x1, x3} {x2} (3, 0, -1) {x2, x3}