第二章 线性规划及单纯型法.ppt

第二章线性规划及单纯型法 2.1线性规划问题及其模型 2.2.1线性规划图解法 2.2.2 线性规划解的性质 2.3单纯形法原理 2.4单纯形法计算步骤 2.5单纯形法的进一步讨论 2.1 线性规划问题及其数学模型 问题的提出 例: 生产计划问题 该计划的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x1、 x2 ? 0 决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution) 线性规划问题的共同特征 一组决策变量X值表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化 线性规划模型的一般形式 线性规划问题的标准形式 标准形式为: 简写为 用向量表示 用矩阵表示 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 “?” 约束： 减去非负剩余变量； 解 ：标准形为 图解法求解步骤 由全部约束条件作图求出可行域； 作目标函数等值线，确定使目标函数最优的移动方向； 平移目标函数的等值线，找出最优点，算出最优值。 线性规划问题求解的 几种可能结果 (a) 唯一最优解 线性规划问题求解的 几种可能结果 图解法的几点结论:（由图解法得到的启示） 可行域是有界或无界的凸多边形。 若线性规划问题存在最优解，它一定可以在可行域的顶点得到。 若两个顶点同时得到最优解，则其连线上的所有点都是最优解。 解题思路：找出凸集的顶点，计算其目标函数值，比较即得。 练习：用图解法求解LP问题 图解法 —（练习）  图解法 —（练习）  图解法 —（练习）  图解法 —（练习）  图解法 —（练习）  图解法 图解法 图解法 线性规划问题解的概念 标准型 可行解:满足AX=b, X=0的解X称为线性规划问题的可行解。 最优解：使Z=CX达到最大值的可行解称为最优解。 基：若B是矩阵A中m×m阶非奇异子矩阵（B≠0），则B是线性规划问题的一个基。不妨设： 求解 基解：称上面求出的X解为基解。 基可行解：非负的基解X称为基可行解 可行基：对应基可行解的基称为可行基 例：求基解、基可行解、最优解。 线性规划问题的几何意义 基本概念 凸集： 顶点:若K是凸集，X∈K；若X不能用不同的两点 的线性组合表示为： 则X为顶点. 凸组合： 基本定理 证明: 引理：可行解X为基可行解 X的正分量对应的列向量线性无关 几点结论： 线性规划问题的可行域是凸集。 基可行解与可行域的顶点一一对应，可行域有有限多个顶点。 最优解必在顶点上得到。 求解LP的基本思路 1、构造初始可行基； 2、求出一个基可行解（顶点） 3、最优性检验：判断是否最优解； 4、基变化，转2。要保证目标函数值比 原来更优。 2.3 单纯形法原理 本节通过一个引例，可以了解利用单纯形法求解线性规划问题的思路，并将每一次的结果与图解法作一对比，其几何意义更为清楚。 求解线性规划问题的基本思路 1、构造初始可行基； 2、求出一个基可行解（顶点） 3、最优性检验：判断是否最优解； 4、基变化，转2。要保证目标函数值比 原来更优。 第1步 确定初始基可行解 第2步 求出基可行解 第3步 最优性检验 分析目标函数 第4步 基变换 换入基变量： 继续迭代, 可得到: 结合图形法分析（单纯形法的几何意义） 1、初始基可行解的确定 观察法:直接观察得到初始可行基 ≤约束条件: 加入松弛变量即形成可行基。（下页） ≥约束条件: 加入非负人工变量, 以后讨论. (1) 最优解判别定理：若： 为基可行解，且全部 则 为最优解。