第9章线性规划方法及其应用 ppt课件

第 9章 线性规划方法及其应用 * 1 线性规划 （ Linear Programming） 作为运筹学的一个重要分支 ，是研究较早、理论较完善、应用最广泛的一个学科。它所 研究的问题主要包括两个方面： 一是在一项任务确定后，如 何以最低成本（如人力、物力、资金和时间等）去完成这一 任务； 二是如何在现有资源条件下进行组织和安排，以产生 最大收益。 因此，线性规划是求一组变量的值，使它满足一 组线性式子，并使一个线性函数的值最大（或最小）的数学 方法。线性规划不仅仅是一种数学理论和方法，而且已成为 现代管理工作中帮助管理者做出科学决策的重要手段。 Date 2 1、 康托洛维奇 生产组织与计划中的数学方法 ,一 本小册子， 1939; 2、康托洛维奇 “最佳资源利用的经济计算 ” 1942完成、 1959发表的著作 ； 3、自 1947年 丹兹格 （ G.B.Dantzing）提出求解 线性规划问题的一般方法 -单纯形法之后，线性规划 在理论上趋于成熟，应用日益广泛与深入； 随着电子计算机的发展和计算速度的不断提高， 其适用的领域更加广泛，它已成为必不可少的重要手 段之一。 Date 3 4、 1975年库伯曼斯 (Koopmans)因对资源最 优分配理论的贡献而获诺贝尔经济学奖 ； 5、 冯 诺伊曼 和摩根斯坦 1944年发表的 对 策论与经济行为 涉及与线性规划等价的对策问题 及线性规划对偶理论。 Date 4 l 线性规划方法 是数学规划中发展较快、 应用较广和比较成熟的一个分支。 l 最优化 /运筹学 的最基本的方法之一，网 络规划，整数规划，目标规划和多目标 规划都是以线性规划为基础的。 l 解决稀缺资源最优分配的有效方法，使 付出的费用最小或获得的收益最大。 l 线性规划的基础是线性变换。 Date 5 数 学 规 划 非线性规划 整数规划 动态规划 学 科 内 容 多目标规划 双层规划 组 合 优 化 最优计数问题 网络优化 排序问题 统筹图 随 机 优 化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要内容 Date 6 9.1 线性规划是什么 9.2 建立线性规划模型的一般步骤 9.3 线性规划问题的图解法 9.4 线性规划问题解的性质 9.5 解线性规划问题的单纯形法 9.6 线性规划的应用 Date 7 9.1 线性规划是什么 Date 8 9.1 线性规划是什么 我们先通过几个实际问题来认识什么是线性规划 . 【 例 9.1】 某企业生产 三种产品，这些产品分别需要 甲、乙两种原料 .生产每种产品一吨所需原料和每天原料总限 量及每吨不同产品可获利润情况如表 9.1所示 . 表 9.1 企业生产数据表 1. 利润最大化问题 Date 9 9.1 线性规划是什么 试问：该企业怎样安排生产才会使每天的利润最大？ 解 设该企业每天生产产品 的数量分别为 （ 单位：吨），则总利润的表达式为 我们希望在现有资源条件下总利润最大 .现有资源的限制为 （原料甲的限制） （原料乙的限制 ） 此外，由于未知数（我们称之为 决策变量 ） 是计划产量， 应有为非负的限制，即 Date 10 9.1 线性规划是什么 由此得到问题的数学模型为 其中 为英文 “subject to”的缩写，表示决策变量 受它 后面的条件约束 . 最优解为 （具体解法后面介 绍 ），代入总利润的表达式 得对应的目标函数 最大值为 250.由此得到该企业在现有资源条件下，日 生产的最优 安排是：产品 不生产， 生产 25吨， 生产 25吨，可实现最大利 润 250千元 /日 . 其中 为英文 的缩写，表示决策变量 受它 后面的条件约束 最优解为 （具体解法后面介 绍 ），代入总利润的表达式 得对应的目标函数 最大值为 由此得到该企业在现有资源条件下，日 生产的最优 安排是：产品 不生产， 生产 吨， 生产 吨，可实现最大利 润 千元 日 其中 为英文 的缩写，表示决策变量 受它 后面的条件约束 最优解为 （具体解法后面介 绍 ），代入总利润的表达式 得对应的目标函数 最大值为 由此得到该企业在现有资源条件下，日 生产的最优 安排是：产品 不生产， 生产 吨， 生产 吨，可实现最大利 润 千元 日 其中 为英文 的缩写，表示决策变量 受它 后面的条件约束 最优解为 （具体解法后面介 绍 ），代入总利润的表达式 得对应的目标函数 最大值为 由此得到该企业在现有资源条件下，日 生产的最优 安排是：产品 不生产， 生产 吨， 生产 吨，可实现最大利 润 千元 日 其中 为英文 的缩写，表示决策变量 受它 后面的条件约束 最优解为 （具体解法后面介 绍 ），代入总利润的表达式 得对应的目标函数 最大值为 由此得到该企业在现有资源条件下，日 生产的最优 安排是：产品 不生产， 生产 吨， 生产 吨，可实现最大利 润 千元 日 Date 11 9.1 线性规划是什么 类似于例 9.1的这类问题称为最优生产计划问题 .其一般描述是利 用 种资源 组织生产 种产品 .以 表示 资源 的限制， 表示产品 的单位利润， 表示单位产品 消耗资源 的数量（代表该企业当 前的技术水平），情况如表 9.2所示 . 现在的问题是：如果该企 业生产的这 种产品 都可以卖出，如何合理充分地 利用现有的资源，给出一个使总利润达到最大的产品生产计划？ Date 12 有了解决上述问题的经验，我们可以假设产品 的计划产量分别为 单位，则问题的数学模型 为 9.1 线性规划是什么 Date 13 模型中 的都是实际 问题给定的常数；未知量 为决策变量 .这类决策问 题的应用领域非常广泛 . 注 本章的数学模型均可用软件求解。 2. 成本最小化问题 【 例 9.2】 某钢铁厂熔炼一种新型不锈钢，需要 4种合金 为原料经测定这 4种原料关于元素铬（ Cr）、锰（ Mn）和镍（ Ni） 的质量分数（ %）、单价以及这种新型不锈钢所需铬、锰和镍的最 低质量分数，情况如表 9.3所示 . 假设熔炼时质量没有损耗，问： 要熔炼 100吨这样的不锈钢，应选用原料 各多少吨，能 够使成本最小？ 9.1 线性规划是什么 Date 14 9.1 线性规划是什么 下料问题的一般描述：已知有一批原材料，每根长度为 L ，由于生产的需要，要求截出规格分别为 的零 件 根 . 问：如何截取使得总用料最省？即要求 制定一个既能满足生产的需要，又使得使用的原材料数量 最少的下料方案 .同样可以仿照例 9.4的建模过程列出此一 般问题的数学模型 . 总之，类似例 9.1、 9.2的实际问题很多，而且形式多种多 样 . 通过这些问题，我们可以看到上述各种问题的 共同点 ，即每一个问题都用一组决策变量 来表示某 一方案，追求的目标可以用关于决策变量 的 线性函数刻画，或是最大化或是最小化，而要达到目标的 条件又都有一定的限制，每个限制条件均可由关于决策变 量 的线性等式或不等式表示 . Date 15 9.1 线性规划是什么 这类问题所构成的数学模型 ,称为 线性规划 模型 . 有时也直接将线性规划模型称为线性规划问题 . 针对这类模型 ,可以用根据数学理论设计的计算机 软件，如软件求解，得出实际问题需要的答案。 Date 16 9.2 建立线性规划模型的 一般步骤 Date 17 9.2 建立线性规划模型的一般步骤 从 9.1 节中对实际问题建立数学模型的过程，可以得到 一般线性规划问题建模过程如下： 第 1步 理解要解决的问题 . 搞清在什么条件下追求什么 目标 . 第 2步 定义 决策变量 . 每一个问题都用一组决策变量 来表示某一方案；这组决策变量的值就代表一 个具体方案，一般这些变量取值 是非负的 . 第 3步 确定 约束条件 . 用一组决策变量的线性等式或不 等式来表示在解决问题过程中所必须遵循的约束条件 . 第 4步 列出 目标函数 . 按实际问题的不同，用决策变量 的线性函数最大化或最小化形式写出所要追求的目标，称 之为目标函数 . Date 18 9.2 建立线性规划模型的一般步骤 对于一些比较复杂的线性规划问题，为了便于建立其数学 模型，常需要把反映问题的背景数据资料用表格形式归类 综合，以揭示各个量之间的内在联系 . 线性规划的一般形式可表示为： Date 19 9.2 建立线性规划模型的一般步骤 其中称 为目标函数， 为决策变量， 为约束常数，后面的式子为 约束条件 .这里的 为常数 . 当要求决策变量 均为整数时，称（ 9.1） 为 纯整数线性规划问题 ； 当要求决策变量 均取 0或 1时，称（ 9.1） 为 整数线性规划问题 . 当要求决策变量 既取实数又取整数时， 称（ 9.1）为混合整数线性规划问题 . 我们把满足所有约束条件的解称为线性规划问题（ 9.1） 的 可行解 .全体可行解的集合称为问题（ 9.1）的 可行域 , 记为 .使目标函数值最大（或最小）的可行解称为该线性 Date 20 9.2 建立线性规划模型的一般步骤 规划问题的 最优解 ，与此最优解相应的目标函数值称为 最优 目标函数值 ， 简称 最优值 .因此，若记 ， 求解线性规划问题（ 9.1），本质上就是寻找一点 ， 使得 均满足不等式 【 例 9.3】 某工厂在计划期内要安排生产甲、乙两种产 品，已知生产单位产品所需要的设备（台时）， A、 B两 种原材料的消耗以及资源的限制情况如表 2.11所示 .问： 该工厂应分别生产多少甲产品和乙产品才能使工厂获利 最大？ Date 21 9.2 建立线性规划模型的一般步骤 解 首先，确定决策变量 .工厂目前要决策的是甲产品和乙产品的生 产量，可以分别用变量 来表示 .由于它们表示产品产量，所以 只取非负数 . 其次，根据问题的限制条件，列出表示约束条件的线性不等式： Date 22 9.2 建立线性规划模型的一般步骤 ，（非负限制） ，（台时数限制） ，（原材料 限制） ，（原材料 限制） 最后，根据实际问题所追求的目标，列出其线性函数表达式 . 由于问题的目标是工厂获利最大，假如产品都能销售，则总利 润可表示为 ，最大利润记为 Date 23 9.2 建立线性规划模型的一般步骤 综上所述，就得到了描述该问题的线性规划模型： Date 24 计算最优解为： 即在现有资源条件下，该企业在计划期内生 产的最优计划是： 产品甲生产 100单位， 产品乙生产 200单位， 可实现最大利润 130000元 . 9.2 建立线性规划模型的一般步骤 Date 25 9.2 建立线性规划模型的一般步骤 【 例 9.4】 某医院护士 24小时值班，每次值班 8小 时 .不同时段需要的护士人数不等 .据统计，各时 段所需护士的最少人数如表 2.9所示 . 如何安排才 能做到安排最少的护士就能满足工作的需要？ Date 26 9.2 建立线性规划模型的一般步骤 解 设 为时段 开始上班的人数， .目标是 要求护士的总数最少 .因为每个护士都工作 8小时，即连续 工作 2个时段后休息，所以问题的线性规划模型为： Date 27 9.2 建立线性规划模型的一般步骤 计算最优解为： 故该医院需雇用 150名护士，最佳安排见表 9.10所示 . Date 28 9.2 建立线性规划模型的一般步骤 线性规划的一般形式，可行解、最优解等 概念 线性规划问题建模过程： 第 1步 理解要解决的问题。 第 2步 定义决策变量。 第 3步 确定约束条件。 第 4步 列出目标函数。 Date 29 9.3 线性规划问题的图解法 Date 30 9.3 线性规划问题的图解法 1. 图解法 对一个线性规划问题建立数学模型之后，就面临着如何求 解的问题 .这里先介绍含有两个决策变量 的线性规划 问题的图解法 .它简单直观，有助于了解线性规划问题求 解的基本原理 . Date 31 图解法的步骤可概括为： （ 1）在平面上建立直角坐标系 ； （ 2）图示约束条件，找出可行域（由于 ，可 行域必位于第一象限）； （ 3）图示目标函数，即画出目标函数等值线； （ 4）对 （或 ）问题朝着增大（或减少）纵截 距的方向平行移动目标函数等值线，至与可行域的边界相 切时为止 .切点（即某个边界点）就是代表最优解的点； （ 5）寻找该点的坐标得到最优解 . 以下结合实例来具体说明 . Date 32 9.3 线性规划问题的图解法 【 例 9.5】 用图解法求解线性规划问题 Date 33 9.3 线性规划问题的图解法 解 先画出线性规划的可行域如图 9.1阴影部分 . 再画出目标函数等值线，朝着增大纵截距的方向 平行移动等值线至点 . 最后求解线性方程组 求解得到点 的坐标，从而得到最优解 ，最大值 Date 34 9.3 线性规划问题的图解法 Date 35 9.3 线性规划问题的图解法 【 例 9.6】 用图解法求解线性规划问题 解 先画出线性规划的可行域，如图 9.2阴影部分 . Date 36 9.3 线性规划问题的图解法 Date 37 9.3 线性规划问题的图解法 再画出目标函数等值线，朝着增大纵截距的方向平行移动等 值线至点 B.最后求解线性方程组 得到解出点 B的坐标 ，从而得到最优解 ，最大值 例 9.5与例 9.6中求解得到的问题的最优解是惟一的，但对一 般线性规划问题，求解结果还可能出现其他情况 . Date 38 9.3 线性规划问题的图解法 2. 线性规划解的其他情况 （ 1）多重最优解的情况 【 例 9.9】 若将例 9.5中的目标函数变为 ，则代表目标函数的直线平移到最优 位置后将和直线 重合 .此时，不仅顶点 A ， B都代表了最优解，而且线段上 AB的所有点都代表 了最优解 .这个线性规划问题有无穷多最优解，这些 最优解都对应着相同的最大值 Date 39 MAX Date 40 9.3 线性规划问题的图解法 （ 2）无界解的情况 （ 3）无可行解的情况 Date 41 9.3 线性规划问题的图解法 （ 2）无界解的情况 【 例 9.10】 对下述线性规划问题 用图解法求解结果如图 2.3(a) 所示 . 从图中可以看出， 由于可行域是无界区域，当目标函数等值线沿箭头方向平 行移动时，始终与该无界区域相交 . 此时，目标函数值无 上界，因此无最优解，也称 最优解无界 . Date 42 9.3 线性规划问题的图解法 （ 3）无可行解的情况 【 例 9.11】 对线性规划问题 由图 2.3(b)可以看出，同时满足所有约束条件的点不存在 ，即可行域为空集，也就是没有可行解，故不存在最优解 . Date 43 9.3 线性规划问题的图解法 当根据实际问题建立的线性规划模型的求解结果出现（ 2 ） , （ 3）两种情况时，一般说明建模有错误 .前者缺乏必 要的约束条件，后者是有矛盾的约束条件，建模时应注意 .下面再给出一个求目标函数最小化的线性规划问题 . 【 例 9.12】 求解线性规划 Date 44 9.3 线性规划问题的图解法 解 画出此线性规划问题的可行域，如图中的阴影部分 . 目标函数 ，它在坐标平面上可表示为以 f为 参数，以 -2/4为斜率的一组等值线 .当等值线移动到 B点时 ，目标函数在可行域中取最小值 .B点的坐标可以从线性方 程组 中求出，为 .这就是所求线性规划问题的最优 解，且 . Date 45 9.3 线性规划问题的图解法 Date 46 9.3 线性规划问题的图解法 1.通过图解法了解线性规划有几种解的形式 2.作图的关键有三点 (1)可行解区域要画正确 (2)目标函数增加的方向不能画错 (3)目标函数的直线怎样平行移动 Date 47 9.4 线性规划问题解的性质 Date 48 1. 线性规划问题的标准形 前面曾给出了线性规划问题的一般形式， 可以看出，其中有的要求目标函数最大化 ，有的要求目标函数最小化；约束条件可 以是 “”或 “”形式的不等式，也可以是等 式；决策变量一般是非负约束，但也允许 在 范围内取值，即无约束。为了 进一步研究和讨论，就需要把线性规划问 题的一般形式化为统一的标准形式 。 9.4 线性规划问题解的性质 Date 49 线性规划的一般形式可表示为： Date 50 这里的标准形式有以下规定： （ 1）目标函数是求最大值； （ 2）所有约束条件均用等式表示； （ 3）所有决策变量均取非负数； （ 4）所有约束常数均为非负数 . 9.4 线性规划问题解的性质 Date 51 于是，具有个约束条件和个决策变量的线性 规划问题的 标准形 为： 9.4 线性规划问题解的性质 Date 52 在约束条件 0（ j = 1， 2， ， n） 下，求一组未知变量（ j = 1， 2， ， n） 的值，使得 。常记为如下更为紧凑的形式 或 其缩写形式为： Date 53 其中 b和 C为已知非负常数， A为已知常数矩阵，且 rank(A)=m。一般可以通过以下方法，把 非标准形线性规划 问题化为标准形： （ 1）目标函数的标准化 如果线性规划问题是求目标函数的最小值，即 则令 ，得 ，这就 同标准形的目标函数的形式一致了 .但要注意，如果要求原 问题的最优值，应取最优值的相反数 . 9.4 线性规划问题解的性质 Date 54 （ 2）约束条件的标准化 当约束条件为 形式的不等式时，可在不等式左边加上一 个非负的新变量（称为 松弛变量 (slack variables) ），把不 等号变为等号； 当约束条件为 形式的不等式时，可在不等式左边减去一 个非负的新变量（称为 剩余变量 ），把不等号变为等号 . 9.4 线性规划问题解的性质 Date 55 （ 3）决策变量的标准化 如果某一决策变量是一个符号不受限 制的 “自由变量 ”，可以引入两个非负的新 变量 和 ，并作变换 ， 将决策变量标准化。 9.4 线性规划问题解的性质 Date 56 （ 4）约束常数的标准化 如果有某约束常数为负数，可在等 式（或不等式）两边同时乘以，把约束常 数变为正数 . 9.4 线性规划问题解的性质 Date 57 【 例 9.13】 把下面的线性规划问题化为标准形： 【 解 】 此例只有约束条件不符合标准形，为此引入非负的松 弛变量 ，并分别把它们加到第 1个和第 2个不等式的左 边，即得标准形： 注意，所加松弛变量 表示没有被利用的资源，当然也 没有利润，所以在目标函数 中的系数应为零 . 9.4 线性规划问题解的性质 Date 58 9.4 线性规划问题解的性质 【 例 9.14】 将下面线性规划问题化为标准形 【 解 】 令 ，把求 改为求 ；用 替换 ，其中 ；在第 1个约束不等式的左边加入松弛变量 ，在第 2个约束不等式的左边减去剩余变量 ，这样即可得 到该问题的标准形为 Date 59 ， 9.4 线性规划问题解的性质 标准形 原问题 Date 60 2.线性规划的解 可行解与最优解 满足约束条件（即满足线性约束和非负约束） 的一组变量为可行解。所有可行解组成的集合称为 可行域。 使目标函数最大或最小化的可行解称为最优解 。 Date 61 基本解与基本可行解 在线性规划问题中，将 约束方程组的 mn阶矩 阵 A写成由 n个列向量组成的分块矩阵 Date 62 如果 B是 A中的一个 m阶的非奇异子阵，则称 B 为该线性规划问题的一个基。不失一般性，不妨设 则称 为基向量，与基向量相对应的向量 为基变量，而其余的变量为 非基变量。 Date 63 如果 是方程组 的 解 , 则 就是方程 组 的一个解，它称之为对应于基 B 的 基本解 ，简称基解。 满足非负约束条件的基本解，称为 基本 可行解 。对应于基本可行解的基，称为可行 基。 Date 64 线性规划问题的以上几个解的关系，可用下 图来描述： Date 65 【 定义 9.1】 如果集合 K中任意两点 s,t之间连线上所有的 点都是集合 K中的点，即对于任意的 ，都有 ，则称 K为凸集 . 例如图 9.5中（ a） , （ b） , （ c）为凸集，而（ d） , （ e）不是凸集 . 3. 线性规划问题解的基本性质 (a) (b) (c) (d) (e) 图 9.5 凸集与非凸集示例 9.4 线性规划问题解的性质 Date 66 【 定理 9.1 】 线性规划问题的可行域 是一个凸集 . 这两个定理我们不给予数学证明 .结合图解法，我们可以清晰 地了解到线性规划问题解的有关性质 .定理 9.1说明：联结线性 规划问题任意两个可行解的线段上的点（坐标）仍是可行解 . 定理 9.2则告诉我们：如果一个线性规划问题有最优解，则一 定可以从可行域的有限个顶点中找到 . 【 定理 9.2 】 若可行域非空有界，则线性规划问题的最优值一 定可以在可行域的某个顶点上达到 . 9.4 线性规划问题解的性质 Date 67 【 定义 9.2 】 如果凸集 K中的点 x不能成为任何线段的内 点，即对任意 ，都不存在 ，使 得 ，则称 x 为 K 的一个顶点 . 例如三角形、正方形、凸多边形、凸无界区域的顶点及 圆周上的点，都是相应凸集的顶点 . 从图解法的例子中知道线性规划问题的可行域是一个凸集 ，且如果问题有最优值，都是在顶点上达到 . 这些性质推广到一般，就是下面几个重要定理 . 9.4 线性规划问题解的性质 Date 68 9.4 线性规划问题解的性质 1.将非标准形化为标准形的方法 2.线性规划问题的解 3.线性规划问题解的性质 （ 1）线性规划问题的可行域 是一个凸集。 （ 2）若可行域非空有界，则线性规划问题的最优 值一定可以在可行域的某个顶点上达到。 Date 69 9.5 解线性规划问题的单纯形法 Date 70 单纯形法是求解线性规划的一种通用方法， 1947年由美国 数学家丹兹格（ G.B.Dantzig）给出 .下面结合 9.1中的利润最 大化问题介绍单纯形法的基本内容 .由 9.1中的例 9.1提供的 数 学模型 为 : 9.5 解线性规划问题的单纯形法 Date 71 （ 1）先化为标准形 . 引入松弛变量 得到 标准形 9.5 解线性规划问题的单纯形法 Date 72 （ 2）再把目 标 函数 改写成 并把它加入到 约 束方程 组 中去，即得到方程 组 9.5 解线性规划问题的单纯形法 Date 73 将此方程 组 的系数及常数 项 b列成一个数表，即 . 9.5 解线性规划问题的单纯形法 称此表 为 初始 单纯 形表 .表中的数字被分成了 4部分，位于 左下角的每个数字称 为检验 数 .此 时 与 对应 的 检验 数都是 负 数，因此，若不令 ，只要有一个 是正数， 则 它与 负 数相乘后仍是 负 数，移 项 到右 边 ， 函数 值 就会增大，为此转到下一步 . Date 74 （ 3）在 负检验 数中 选绝对值 最大的 负 数（即 7），在 对应 的列中，将 该 列中的正数分 别 去除 对应 的常数 项 ， 选择 比 值 最小者所 对应 的元素 为 主元（称 为 最小比 值 原 则 ） .在 这 里 然后用矩 阵 的初等行 变换 ，将主元化 为 1，把同列的其他元 素化 为 0.这 一 过 程如下： 将矩 阵 可知位于第 2行、第 3列的元素 3为 主元， 标为 , 9.5 解线性规划问题的单纯形法 Date 75 的第 2行乘以 1/3，得 再将矩 阵 的第 2行乘以（ 2）加到第 1行，第 2行乘以 7加 到第 3行，得 此 时 的目 标 函数 值 已 经 由原来的 0增加到 700/3. 由于 检验 数中 仍有 负 数，按照最小比 值 原 则 ，可知位于第 1行、第 2列的元素 4/3为 主元 . 同 样 用矩 阵 的初等行 变换 ，将主元化 为 1，把同列 的其他元素化 为 0， 9.5 解线性规划问题的单纯形法 Date 76 过 程如下： 将矩 阵 A的第 1行乘以 3/4，得 这时 表中已 经 没有 负检验 数，表明目 标 函数已 经 达到最大 值 .最 后 这张 表称 为 最 优单纯 形表 .易知最 优 解 为 最 优值为 250.从而原 线 性 规 划 问题 的最 优 解 为 对应 的目 标 函数最 优值为 250. 9.5 解线性规划问题的单纯形法 再将矩阵的第 2行乘以（ 2）加到第 1行，第 2行乘以 7加到 第 3行，得 Date 77 上述求解线性规划问题的方法称为 单纯形法 . 单纯形法步骤如下 ： 第 1步，将线性规划化成标准形； 第 2步，写出初始单纯形表； 第 3步，对检验数进行检验 .若检验数均为非负数，则得到 最优单纯形表 .若有负数，则在检验数绝对值最大的负数所对 应的列中，按最小比值原则选主元，用初等行变换化主元为 1 ，主元所在列其余元素化为 0，得到一张新单纯形表 .再检验该 表是否为最优单纯形表，若不是，重复上述过程，直到得出最 优单纯形表 . 第 4步，从最优单纯形表直接写出最优解和最优值 . 9.5 解线性规划问题的单纯形法 Date 78 从上例求解 过 程看到， 单纯 形表中 所对应的列始终不变， 故在实际计算中可省去不写 .上例的求解过程本质上是矩阵的 初等行变换过程，我们可以把此例的单纯形法求解过程简化为 9.5 解线性规划问题的单纯形法 Date 79 9.5 解线性规划问题的单纯形法 所以最优解及最优值分别为 【 注 1】 若在 计 算 过 程中， 单纯 形表出 现 某 检验 数 为负 ，但 其所在的列无正元素的情况， 则 可以 证 明 该问题 无最 优 解 . Date 80 【 解 】 引入松弛 变 量，化 为标 准形 9.5 解线性规划问题的单纯形法 【 例 9.15】 解线性规划问题 Date 81 初始单纯形表为 由于 检验 数 1所在列无正数元素，故此 问题 无最 优 解 . 9.5 解线性规划问题的单纯形法 Date 82 【 注 2】 在上例的初始 单纯 形表中，由虚 线 隔开的左上部分， 所在列的元素构成一个二 阶单 位矩 阵 我 们 称 为基变量 . 一般地， 对 含有 n个 变 量、 m个 约 束的 线 性 规 划 问题 ， 当把它化 为标 准形后，若恰有一个 m阶单 位矩 阵 ，就可以用 前面的 单纯 形法求出最 优 解（若最 优 解存在）；若基 变 量不 足 m个， 则 用改 进单纯 形法或 对 偶 单纯 形法求解 . 由于 这 两 种方法用到 较 多的数学知 识 ， 这 里不再介 绍 ，但 WinQSB 软 件中的 线 性 规 划程序已 经 包含了改 进单纯 形法和 对 偶 单纯 形 法 . 9.5 解线性规划问题的单纯形法 Date 83 9.5 解线性规划问题的单纯形法 1.判断基本可行解 .有 3种情形： 已是最优解， 是无界 解， 不能确定 .前 2种情形计算结束，第 3种情形需要继 续迭代，先进基后出基，初等变换求下一个基本可行解， 直到出现最优解或无界解为止。 2.判定方法 唯一最优解的判定 ：所有非基变量的检验数非零 ,则线 规划具有唯一最优解。 多重最优解的判断 :最优表中存在非基变量的检验数为零 , 则线则性规划具有多重最优解。 无界解的判断 : 某个检验数大于 0且该检验数所在列中所 有元素小或等于，则线性规划具有无界解。 Date 84 9.6 线性规划的应用 Date 85 9.6 线性规划的应用 线性规划在国内外很多部门的规划、管理、决策过程中有大 量成功的应用，并收到了良好的效果 .但是，应用线性规划来解 决某一类实际问题时，由于问题的复杂性和情况的多变性，要 真正建立一个反映实际问题的、能得出正确结论的理想模型， 并不是一件容易的事情 .它要求建模者具有丰富的经验、较强的 创造力和比较熟练的技巧 .本节通过一些被简化了的问题，介绍 建立线性规划模型的基本思路和基本技巧 . Date 86 1.办 学 规 模 问题 【 例 9.16】 某人准 备 投 资 1200万元 办 一所中学， 为 了考 虑 社会效益和 经济 效益， 对该 地区教育市 场进 行 调查 ，得出一 组 数据，如表 9.12所示 . 表 9.12 市 场调查 表 9.6 线性规划的应用 班级 班级学生数 配备教师数 硬件建设费（万元） 教师年薪（万元） 初中 50 2.0 28 1.2 高中 40 2.5 58 1.6 根据物价部 门 的有关文件，初中是 义务 教育 阶 段，收 费标 准适当控制 ， 预计 除 书费 、 办 公 费 外，初中每个学生每年可收取 600元，而高中每个 学生每年可收取 1500元 .因生源和 环 境等条件限制， 办 学 规 模以 20 30个（ 含 20与 30）班 为 宜 .教 师实 行聘任制 .初、高中的教育周期均 为 3年 .请 你合 理地安排招生 计 划，使年利 润 最大 . 问 ：大 约经过 多少年可以收回全部投 资 ？ Date 87 解 设初中编制班数为 x,高中编制班数为 y,又设年利润为 f , （ 单位：万元），那么 即 .于是此 问题 的 线 性 规 划模型 为 解得最优解 代入 中得 9.6 线性规划的应用 Date 88 故学校的最优规模和招生计划分别为 最优规模：初中 18个班，高中 12个班； 招生计划：第 1年初中招生 6个班约 300人，高中招生 4个班约 160人 .以后每年按此计划招生 . 设经过 n年可收回投 资 . 第 1年利 润为 第 2年利 润为 211.6=23.2(万元 ); 以后每年的利 润 均 为 34.8万元 .故依 题 意 应 有 解得 (年 ).即 约经过 36年可以收回全部投 资 . 9.6 线性规划的应用 Date 89 2. 投资问题 【 例 9.17】 某投资人在今后 3年内有 A,B,C,D共 4个投资项目 ，项目 A在 3年内每年初投资，年底可获利润 20%，并可将本 金收回；项目 B在第 1年年初投资，第 2年年底可获利润 60%， 并将本金收回，但该项目投资不得超过 5万元；项目 C在第 2年 初投资，第 3年底收回本金，并获利润 40%，但该项目投资不 得超过 3万元；项目 D在第 3年初投资，于该年底收回本金，且 获利润 30%，但该项目投资不得超过 2万元 .该投资人准备拿出 6万元资金，问如何制订投资计划，使该企业在第 3年底，投资 的本利之和最大？ 9.6 线性规划的应用 Date 90 【 解 】 这是一个连续投资问题 .设决策变量 xij为第 j年投资到第 i 个 项目的资金 (i= 1,2,3,4,分别对应于项目 A,B,C,D； 分别 对应于投资年份 ),见列表 9.13. 表 9.13 投资项目 投 资 机会 项目名称 第 1年年初 第 2年年初 第 3年年初 A B C D 9.6 线性规划的应用 Date 91 下面分析每年资金的使用情况并建立线性规划模型 . 第 1年初， 有 A, B两个项目，企业只能提供 6万元资金，故有 : .项目 B不得超过 5万元，有 第 2年初 ，有 A,C两个投资项目 .此时第 1年初投资到项目 A的资 金已全部收回，本利和为 .这些资金可用于第 2年的投资， ，而且要求 9.6 线性规划的应用 于是 ； ； Date 92 9.6 线性规划的应用 第 3年初 ，第 1年初投资到项目 B的资金全部收回，本利和 为 ; 第 2年初投资于项目 A的资金也全部收回，本利和为 以上两笔资金可供该年继续投资 .第 3年内还有 A, D两个项 目的投资，可得 ，而且要求 第 3年底 ，到期把所有本利和收回 .所能收回的资金有第 2年 初投资到项目 C的本利和 ，第 3年初投资到项目 A的 本利和 及投资到项目 D的本利和 ，则第 3年底获 得的本利和为 ; Date 93 将上述目标函数和约束条件整理后即可得出该问题完整的 线 性规划模型 : 求解得到最优投资方案如表 9.14所示，且在第 3年底收回投 资的本利和最大为 11.528万元 . 9.6 线性规划的应用 Date 94 表 9.14 最优投资方案 投资机会 项目名称 第 1年年初 第 2年年初 第 3年年初 A X11=1 X12=1.2 X13=7.44 B X21=5 C X32=0 D X43=2 9.6 线性规划的应用 Date 95 3.人力资源分配问题 【 例 9.19】 某百货商场售货员的需求经过统计分析如表 9.16所示 . 为了保证售货员充分休息，售货员每周工作 5天， 休息 2天，并要求休息的 2天是连续的，问：应该如何安排售 货员的作息时间，既满足工作需要，又使配备的售货员人数 最少？ 表 9.16 售货人员需求统计表 时间 所需售货员人数 星期日 28 星期一 15 星期二 24 星期三 25 星期四 19 星期五 31 星期六 28 9.6 线性规划的应用 Date 96 【 解 】 设 xj为星期 j开始休息的人数（ j=1,2, ，分别 对应星期