第二章线性规划山大刁在筠运筹学讲义.doc

第二章 线性规划 教学重点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶和对偶理论，灵敏度分析。 教学难点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶性，灵敏度分析。 教学课时：24学时 主要教学环节的组织：首先通过各种形式的例子归纳出线性数学规划的一般形式，然后在详细讲解主要内容的基础上，尽可能以图形和例题的形式给以形象的说明，使学生对知识点有更直观、具体的认识。再通过大量习题巩固知识，也可以应用软件包解决一些实际问题。 第一节 线性规划问题 教学重点：线性规划问题的实例，线性规划的一般形式、规范形式和标准形式 教学难点：线性规划一般形式转换成标准形式。 教学课时：2学时 主要教学环节的组织：首先通过几个实例总结出线性规划问题的一般形式，再介绍如何将一般形式转换成标准形式。 1、线性规划问题举例 生产计划问题 某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划 单位产品所需原料数量（公斤） 产品Q1 产品 Q2 产品 Q3 原料可用量 （公斤/日） 原料P1 2 3 0 1500 原料P2 0 2 4 800 原料P3 3 2 5 2000 单位产品的利润（千元） 3 5 4 ? 可控因素(所求变量)：设每天生产3种产品的数量分别为. 目标：使得每天的生产利润最大，就是使得利润函数： 达到最大. 受制条件： 每天原料的需求量不超过可用量： 原料： 原料： 原料： 蕴含约束：产量为非负数 模型 s.t. 运输问题 一个制造厂要把若干单位的产品从两个仓库发送到零售点，仓库 能供应的产品数量为，零售点 所需的产品的数量为。假设供给总量和需求总量相等，且已知从仓库 运一个单位产品往的运价为。问应如何组织运输才能使总运费最小？ 求解 设表示从仓库 运往零售点 的产品数量。 模型： min s.t. 2、线性规划模型 为待定的决策变量， 为价值向量， 为价值系数， 为右端向量， 矩阵为系数矩阵? 线性规划模型的概念 可行解（或可行点）：满足所有约束条件的向量 可行集（或可行域）：所有的可行解的全体 最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合} 最优值：最优解的目标函数值 线性规划解的情况： 无解或不可行 无界 但目标函数在可行域上无界 有最优解 且目标函数在D上有有限的 现象规划模型的规范形式和标准形式： 规范形式： 标准形式： 形式转换 一般形式转换成规范式： 等式化成不等式： 自由变量化成非负变量： 令自由变量，其中为非负变量 或 目标函数的最大问题向最小问题的转换 例：将下述问题转换成标准形式： 解： 第二节 可行域与基本可行解 教学重点：线性规划问题的图解法，可行区域的几何结构和线性规划基本定理。 教学难点：线性规划的基本定理。 教学课时：4学时 主要教学环节的组织：首先通过图解法求出两个变量时可行区域的结构和最有点的位置，再进行一般情况下可行区域的结构进行讨论，得到线性规划的基本定理。 1、图解法 对于只有两个变量的线性规划问题可以用图解法求解： 变量用直角坐标系中的点表示，约束条件用坐标系中的半空间或直线的交表示，可行区域是一个凸多面体，目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。 例1、 例2、若将例2.2.1中的目标函数改为求的最小值 当目标函数改变后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解 目标函数值可能出现的情况： 1、可行域是空集； 2、可行域无界无最优解； 3、最优解存在且唯一，则一定在顶点上达到； 4、最优解存在且不唯一，一定存在顶点是最优解。 从图解法的几何直观易得： 线性规划的可行域是若干个半平面的交集，它形成了一个有界或无界的凸多边形。 对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。 2、可行区域的结构 定义2.2.1：设是维欧氏空间的点集，若对任意 的和任意都有就称是一个凸集。 定理2.2.1：线性规划的可行域是凸集 证明：略。 定理2.2.2：任意多个凸集的交还是凸集 定义2.2.2：超平面 半空间 ； 定义2.2.3：多面凸集 定义2.2.4：设 为凸集，如果对任意和， 都有,则称x为S的顶点。 基本可行解 令，其中为A的一个满秩子方阵， =(,)。 分块 左乘 即 =