线性规划的基本概念和基本定理.ppt

运筹学 §3 线性规划的基本概念与基本定理 一、线性规划问题的基与解 1. 可行解 —— 满足约束条件(1-1)(1-2)的解. 2. 最优解 —— 满足(1-3)式的可行解. 3. 基 —— 设r(Am?n)=m , 若B是A的m?m非奇异矩阵, 则称 B是线性规划问题的一个基. 4. 基向量 —— 基B的每一列向量, 共有m个. 5. 非基向量 ——A的不属于B的每一列向量, 共有n-m个. 6. 基变量 —— 与基向量相对应的变量, 共有m个. 7. 非基变量 ——与非基向量相对应的变量, 共有n-m个. 设有标准型: §3 线性规划的基本概念与基本定理 一、线性规划问题的基与解 3. 基 —— 设r(Am?n)=m , 若B是A的m?m非奇异矩阵, 则称 B是线性规划问题的一个基. 4. 基向量 — 基B的每一列向量, 共有m个. 5. 非基向量 —A的不属于B的每一列向量, 共有n-m个. 6. 基变量 — 与基向量相对应的变量, 共有m个. 7. 非基变量 —与非基向量相对应的变量, 共有n-m个. 设有标准型: 8. 基本解 — 令所有非基变量=0, 求出的满足约束条件(1-1)的解. 9. 基本可行解 — 满足约束条件(1-2)的基本解. 10. 最优基本可行解 — 满足约束条件(1-3)的基本可行解. 3. 基 —— 设r(Am?n)=m , 若B是A的m?m非奇异矩阵, 则称 B是线性规划问题的一个基. 4. 基向量 — 基B的每一列向量, 共有m个. 5. 非基向量 —A的不属于B的每一列向量, 共有n-m个. 6. 基变量 — 与基向量相对应的变量, 共有m个. 7. 非基变量 —与非基向量相对应的变量, 共有n-m个. 8. 基本解 — 令所有非基变量=0, 求出的满足约束条件(1-1)的解. 9. 基本可行解 — 满足约束条件(1-2)的基本解. 10. 最优基本可行解 — 满足约束条件(1-3)的基本可行解. 例 找出所有基本解, 并指出其 中的基本可行解和最优解. 3. 基 —— 设r(Am?n)=m , 若B是A的m?m非奇异矩阵, 则称 B是线性规划问题的一个基. 4. 基向量 — 基B的每一列向量, 共有m个. 5. 非基向量 —A的不属于B的每一列向量, 共有n-m个. 6. 基变量 — 与基向量相对应的变量, 共有m个. 7. 非基变量 —与非基向量相对应的变量, 共有n-m个. 8. 基本解 — 令所有非基变量=0, 求出的满足约束条件(1-1)的解. 9. 基本可行解 — 满足约束条件(1-2)的基本解. 10. 最优基本可行解 — 满足约束条件(1-3)的基本可行解. 二、几何意义上的几个概念 1. 凸集 2. 凸组合 3. 顶点 8. 基本解 — 令所有非基变量=0, 求出的满足约束条件(1-1)的解. 9. 基本可行解 — 满足约束条件(1-2)的基本解. 10. 最优基本可行解 — 满足约束条件(1-3)的基本可行解. 二、几何意义上的几个概念 1. 凸集 2. 凸组合 3. 顶点 三、线性规划问题的基本定理 1. 若线性规划问题存在可行域, 则可行域为凸集. 2. 线性规划问题的基本可行解对应于可行域的顶点. 3. 若线性规划问题有可行解, 则一定有基本可行解. 4. 若线性规划问题有有限最优解, 则最优值一定可在可行 域的顶点上达到.