林齐宁-数据、模型与决策一运筹学.ppt

运筹学OperationalResearch 林齐宁博士 教授北京邮电大学经济管理学院Tel mail linqining66 绪论 一 运筹学的起源与发展二 运筹学的定义和主要研究分支三 运筹学的特点及研究对象四 运筹学解决问题的方法步骤五 运筹学与其他学科的关系 一 运筹学的起源与发展 起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置 运输船队的护航 反潜作战中深水炸弹的深度 飞行员的编组 军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济 管理和机关学校及科研单位继续研究1952年 Morse和Kimball出版 运筹学方法 1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会 IFORS 我国于1982年加入IFORS 并于1999年8月组织了第15届大会 一 运筹学的起源与发展 1 中国运筹学会简介50年代中期 我国著名科学家钱学森 许国志等教授将运筹学从西方引入国内 1980年4月 中国数学会运筹学分会成立 1991年 中国运筹学会成立 历届学会理事长有 华罗庚 越民义 徐光辉 章祥荪 袁亚湘 2 中国系统工程学会简介1 1979年由钱学森 宋健 关肇直 许国志等21名专家 学者共同倡议并筹备 1980年11月18日在北京正式成立 第一届理事会理事长关肇直 第二 三届理事长许国志 第四 五届理事长顾基发 第六届理事长陈光亚 3 运筹学 系统工程主要研究人员构成1 数学 如华罗庚 越民义 徐光辉 章祥荪 袁亚湘 许国志 顾基发等 2 控制论 张仲俊 刘豹 陈珽 郑维敏 赵纯均 陈剑等3 管理等专业相关教学 科研技术人员 5 6 7 一 运筹学的起源与发展 4 相关研究机构和高校1 中国科学院数学与系统科学研究院系统科学研究所2 中国科学院数学与系统科学研究院应用数学研究所3 哈工大 胡运权 黄梯云 钱国明等4 天津大学 刘豹 顾培亮 张维 杜纲等5 西安交大 汪应洛 席酉民等6 上海交大 张仲俊 王浣尘等7 清华大学 郑维敏 赵纯均 陈剑等 8 大连理工 王众托 胡祥培等9 北航 顾昌耀 黄海军等10 北理工 吴沧浦 吴祈宗 张强等 9 二 运筹学的定义和主要研究分支 运筹学的定义为决策机构对所控制的业务活动作决策时 提供以数量为基础的科学方法 Morse和Kimball运筹学是把科学方法应用在指导人员 工商企业 政府和国防等方面解决发生的各种问题 其方法是发展一个科学的系统模式 并运用这种模式预测 比较各种决策及其产生的后果 以帮助主管人员科学地决定工作方针和政策 英国运筹学会运筹学是应用分析 试验 量化的方法对经济管理系统中人力 物力 财力等资源进行统筹安排 为决策者提供有根据的最优方案 以实现最有效的管理 中国百科全书现代运筹学涵盖了一切领域的管理与优化问题 称为ManagementScience 10 二 运筹学的定义和主要研究分支 运筹学的分支数学规划 线性规划 非线性规划 整数规划 动态规划 目标规划等图论与网路理论随机服务理论 排队论存储理论网络计划方法决策理论对策论系统仿真 随机模拟技术 系统动力学可靠性理论金融工程 11 三 运筹学的特点及研究对象 运筹学的特点 1 优化以整体最优为目标 从系统的观点出发 力图以整个系统最佳的方式来协调各部门之间的利害冲突 从而求出问题的最优解 所以运筹学可看成是一门优化技术 为解决各类问题提供优化方法2定量为所研究的问题提供定量的解决方案 如采用运筹学研究资源分配问题时 其求解结果是一个定量的最优资源分配方案 运筹学的研究对象 来自生产管理过程中的具体问题 如资源分配 物资调度 生产计划与控制等 12 四 运筹学解决问题的方法步骤 1 理清问题 明确目标2 建立模型讨论 什么叫模型3 求解模型 建立模型之后 需要设计相应算法进行求解 实际问题运算量一般都很大 通常需要用计算机求解 4 结果分析讨论 模型计算结果与已有的经验或知识进行比较1 模型计算结果和已有的经验或知识比较一致2 模型计算结果和已有的经验或知识差异较大你喜欢那一种情况 13 五 运筹学与其他学科的关系 运筹学目标分析 建模 求解和结果分析需要用到很多相关学科的知识 它与如下学科的知识关系比较密切 1 数学 学习 应用运筹学应该具备较广的数学知识 许多运筹学者来自数学专业就是这个原因 有人甚至认为运筹学是一门应用数学 2 管理学 运筹学研究对象是生产管理过程的具体问题 在利用运筹学理论和方法解决具体问题时 需要的涉及管理科学的有关理论 3 计算机 运筹学所研究的实际问题通常都是比较复杂 而且规模比较大 在求解这些问题时 必须借助计算机来完成 14 第一章线性规划 1 1线性规划模型1 1 1问题的提出一 例1 多产品生产问题 Max 另 问该工厂应如何安排生产才能使工厂的总收入最大 一 例1 多产品生产问题 Max 设x1 x2分别代表甲 乙两种电缆的生产量 f x 为工厂的总收入 则上述问题可用如下数学模型来表示 其中 OBJ Objective 表示目标 S t Subjectto 表示满足于 表示在满足铜 铅资源和需求等约束条件下 使工厂的总收入这一目标达到最大 最优解为 二 例2 配料问题 min 某混合饲料加工厂计划从市场上购买甲 乙两种原料生产一种混合饲料 混合饲料对VA VB1 VB2和VD的最低含量有一定的要求 已知单位甲 乙两种原料VA VB1 VB2和VD的含量 单位混合饲料对VA VB1 VB2和VD的最低含量以及甲 乙两种原料的单位价格如下表所示 问该该加工厂应如何搭配使用甲乙两种原料 才能使混合饲料在满足VA VB1 VB2和VD的最低含量要求条件下 总成本最小 二 例2 配料问题 min 设x1 x2分别代表混合单位饲料对甲 乙两种原料的用量 f x 表示单位混合饲料所需要的成本 则上述问题的线性规划数学模型如下 该数学模型的最优解为该问题的最优解为x1 3 69 x2 0 77 minf x 1 49 三 线性规划数学模型的特征和定义 1 线性规划数学模型的特征 1 有一组决策变量 x1 x2 xn 表示某一方案 这一组决策变量的具体值就代表一个具体方案 2 有一个目标函数 该目标函数根据其的具体性质取最大值或最小值 当目标为成本型时取最小 而当目标为效益型时取最大 3 有一组约束方程 包括决策变量的非负约束 4 目标函数和约束方程都是线性的 2 线性规划数学模型的定义定义1 1有一个目标函数和一组约束方程 且目标函数和约束方程都是线性的数学模型称为线性规划数学模型 四 线性规划数学模型的背景模型和思考 1 线性规划数学模型的背景模型 例1 1的多产品生产计划问题的数学模型称为线性规划的背景模型 把该背景模型的条件一般化后可叙述如下 用有限量的几种资源生产若干种产品 如何安排生产 才能使工厂的总收入或利润达到最大 2 背景模型的思考1 讨论 什么叫背景模型能够帮助我们理解和记住一些相对抽象和复杂问题的简单问题模型 2 背景模型的思考利用一些相对比较简单的问题来阐述一些相对复杂和抽象的运筹学中的一些基础概念和原理是本课程力求在教学中体现的第一个特点 希望大家用心体会 1 1 2线性规划数学模型的一般表示方式 21 1 和式 22 2 向量式 23 3 矩阵式 24 1 1 3线性规划的图解法 f x 36 线性规划问题的几个特点 1 线性规划的可行域为凸集 讨论 什么叫凸集 集合中任意两点连线上的一切点仍然在该集合中 在平面上为凸多边形 在空间上为凸几何体 讨论 最优解在那里取得 2 线性规划的最优解一定可在其凸集的某一顶点上达到 讨论 什么情况有最优解 最优解的存在性条件 3 线性规划若有可行域且其可行域有界 则一定有最优解 上述3个结论是线性规划的3个基础定理 可以用严格的数学方法进行证明 我们以简单 直观的图解法方式给出 相信大家是可以接受的 1 3线性规划求解的基础原理和单纯形法 1 3 1线性规划问题的标准形一 线性规划模型一般形式 二 求解思路1 规定一标准型线性的规划问题数学模型 2 如何把非标准形的线性规划问题数学模型转化为标准形线性规划问题数学模型 3 如何求解标准形线性规划问题数学模型 三 线性规划问题的标准形 在上述线性规划标准形中 决策变量的个数取n m个是习惯表示法 我们知道 对于线性规划背景模型 有m个约束方程 且每个约束方程的不等式均为 号 如果我们在每个约束方程的左边加上一个大于等于0的变量 则可将各个约束方程的 号转变为 此时 决策变量就有n m个 28 四 变换的方法 1 目标函数为min型 价值系数一律反号 令g x f x CX 有minf x max f x maxg x 2 第i个约束的bi为负值 则该行左右两端系数同时反号 同时不等号也要反向3 第i个约束为 型 在不等式左边增加一个非负的变量xn i 称为松弛变量 同时令cn i 04 第i个约束为 型 在不等式左边减去一个非负的变量xn i 称为剩余变量 同时令cn i 05 若xj 0 令xj xj 代入非标准型 则有xj 06 若xj 不限 令xj xj xj xj 0 xj 0 代入非标准型 29 五 变换举例 1 3 2线性规划问题的解和基础定理 本章开始到现在已讨论的内容 相信大部分读者都会感到比较容易理解和掌握 这一节我们将要讨论关于线性规划问题解的一些基础概念和定理 与前面讨论的内容相比 线性规划问题解的一些基础概念略显难一些 其中比较难的概念有线性规划问题的基和基础解等相关概念 为了帮助大家比较容易理解这些概念 我们先从大家熟悉的两个变量两个线性方程组这一简单问题入手 然后逐步过渡到我们所要讨论的线性规划问题的基和基础解等相关概念 著名数学家笛卡尔曾说过 他最擅长做的两件事是 1 第一做简单事 2 第二是将复杂事变为简单事 本课程将从大家熟悉的一些简单问题入手 然后逐步过渡到运筹学一些相对比较抽象和难的概念和原理 这是本课程教学力求的另一特点 一 线性方程组的解 考虑如下线性方程组的解 再考虑如下线性方程组的解 一 线性方程组的解 类似地 如果将方程组 3 中的变量x2或x1当成常数 分别移到其方程的右边后采用消元法进行求解 则也可得到如下两组通解及其特解 一 线性方程组的解 仔细观察和思考方程组 3 的三组通解 4 6 和 8 或三组特解 5 7 和 9 是如何得到的 以及能够得到这些通解或特解的条件是什么 根据求解线性方程组克莱姆条件可知 能够得到方程组 3 的通解 4 或特解 5 的条件是方程组 3 中的变量x1和x2的系数矩阵行列式不等于0 即 或变量x1和x2的系数矩阵B1是非奇异矩阵或变量x1和x2的系数列向量是线性无关 显然 这三个条件是等价的 一 线性方程组的解 同样 由于方程组组 3 中的变量x1和x3的系数矩阵行列式 B2 不等于0与变量x2和x3的系数矩阵行列式 B3 不等于0 即 才能得到方程组 3 的通解或特解 6 或 7 与通解或特解 8 或 9 将上面讨论的方程组 3 加上一目标函数和变量非负约束条件后就变成一标准型线性规划 如 一 线性方程组的解 对于上述标准型线性规划 10 称B1 B2和B3为线性规划 10 的基 因利用其中任何一个基B1或B2或B3 都能得到线性规划 10 的一组通解和特解 见式 4 9 变量x1和x2为基变量 变量x3为非基变量 令x3 0 得解 5 为线性规划 10 的基础解 但因该基础解中x1 1 0 不满足线性规划 10 的变量非负约束条件 因此 该基础解 5 是线性规划 10 的基础非可行解 变量x1和x3为基变量 变量x2为非基变量 令x2 0 得解 7 为线性规划 10 的基础解 该基础解中x1和x3均大于0 满足线性规划 10 的变量非负约束条件 因此 该基础解 7 是线性规划 10 的基础可行解 变量x2和x3为基变量 变量x1为非基变量 令x1 0 得解 9 为线性规划 10 的基础解 该基础解中x2和x3均大于0 满足线性规划 10 的变量非负约束条件 因此 该基础解 9 是线性规划 10 的基础可行解 二 标准型线性规划解的若干基础概念 标准型有n m个变量 m个约束行 基 的概念在标准型中 技术系数矩阵有n m列 即A P1 P2 Pn m A中线性独立的m列 构成该标准型的一个基 即B P1 P2 Pm B 0P1 P2 Pm 称为基向量与基向量对应的变量称为基变量 记为XB x1 x2 xm T 其余的变量称为非基变量 记为XN xm 1 xm 2 xm n T 故有X XB XN 最多有个基 二 标准型线性规划解的若干基础概念 可行解与非可行解满足约束条件和非负条件的解X称为可行解 不满足约束条件或非负条件的解X称为非可行解基础解对应某一基B且令其非基变量XN 0 求得基变量XB的值 称X XB XN T为基础解 其中 XB B 1b XN 0XB是基础解必须满足如下条件 1 非0分量的个数 m 2 m个基变量所对应的系数矩阵为非奇异的 3 满足m个约束条件 二 标准型线性规划解的若干基础概念 基础可行解与基础非可行解基础解XB的非零分量都 0时 称为基础可行解 否则为基础非可行解 退化解基础可行解的非零分量个数 m时 称为退化解可行基对应于基础可行解的基称为可行基最优解使目标函数达到最优的基础可行解称为最优解无穷多最优解当最优解的基变量组成不止一个时 线性规划有无穷多最优解 39 三 线性规划标准型问题解的关系 约束方程的解空间 基础解 可行解 非可行解 基础可行解 退化解 四 线性规划解的判定 对于某一线性规划的任意一个解X 我们如何判定X是基础解 或是基础可行解 或是基础非可行解 或是非可行解 或是可行解呢 判定步骤 1 写出给定线性规划问题的标准型线性规划 2 根据基础解的三个条件判定X是否是基础解 当三个条件均满足时 X才是基础解 否则X不是基础解 若X是基础解 转3 否则 转4 3 X是否满足非负约束 即其基变量值是否都大于0 若是 X是基础可行解 否则X是基础非可行解 4 将X代入给定线性规划的所有约束方程 包括非负约束 若X满足所有约束方程 则X为可行解 否则X为非可行解 41 五 线性规划解的判定举例 六 线性规划问题解的一些基本定理 42 定理1若线性规划问题存在可行域 则其可行域是凸集 定理2线性规划问题可行域的顶点与其基础可行解一一对应 定理3若线性规划问题存在可行域 则它必有基础可行解 定理4若线性规划问题存在可行域且其可行域有界 则它必有最优解 定理5若线性规划问题存在最优解 则其最优解一定可以在其可行域的某个顶点上取得 43 1 3 3单纯型法的基础原理 一 单纯形法的基础思路和步骤 一 基础思路从一个基础可行解出发 设法得到另一个更好的基础可行解 直到目标函数达到最优时 基础可行解即为最优解 二 基础步骤1 求一个基础可行解 称为初始基础可行解 求初始基础可行解的方法必须简单实用 且具有通用性 2 最优检验 即检验任一基础可行解是否是最优解 若是 则停止计算 否则 转3 3 确定改善方向 求得另一个更好的基础可行解 转2 直到求得最优解为止 通常把这三个基础步骤称为最优化三步曲 事实上 这三部曲对求解其它最优化问题 如非线性规划等 也是适用的 44 单纯型法的基础步骤 二 单纯性法基本原理 45 为了使大家比较直观容易地理解利用单纯形法求解线性规划问题三个步骤的基础原理 我们先以解线性方程组的方法来求解例1线性规划 解 一 标准化 二 选择初始基础可行解 46 从系数矩阵A中可知 x3 x4和x5的系数列向量P3 P4和P5是线性独立 这些向量可构成一个基B0 初始基 对应于基B0的变量x3 x4和x5为基变量 其它两个变量x1和x2为非基变量 即XB0 x3 x4 x5 T XN0 x1 x2 T 令非基变量x1 x2 0 可得一初始基础可行解X 0 0 0 10 8 7 T此时 对应于X 0 的目标函数f X 0 6x1 4x2 0 三 最优检验 47 将 2 式代入 1 的目标函数后可得f X 0 6x1 4x2 3 从目标函数 3 可知 非基变量x1和x2的系数都是正数 所以X 0 不是最优解 四 求另一个更好的基础可行解1 确定换入变量及其值从从目标函数 3 可知 非基变量x1的系数大于x2的系数 所以 可确定x1为换入变量 由于 所以 当另一个非基变量x2仍然为0时 由 4 式可得到换入变量x1的值为x1 Min 10 2 8 1 5 2 确定换出变量 48 由于基变量的个数只能等于约束方程的个数m 在本例中 m 3 所以 当有一个非基变量做为换入变量变为基变量时 就必须有一个基变量做为换出变量变为非基变量 即从所有基变量中 将其中一个大于0的基变量变为等于0的非基变量 该非基变量就是换出变量 从 4 式可知 当x1 5时 x3 0 所以x3为换出变量 由此得到线性规划 1 的一个新的基B1和一组新的基变量与非基变量 XB1 x1 x4 x5 T XN1 x3 x2 T 3 求另一个更好的基础可行解 49 将 1 约束方程中对应于基B1的非基变量x3和x2移到方程的右边后可得 令非基变量x2 x3 0 可得另一基础可行解X 1 5 0 0 3 7 T此时 对应于X 1 的目标函数f X 1 6x1 4x2 30 f X 0 0 五 最优检验 将 5 式代入 1 的目标函数后可得f X 30 x2 3x3 6 从目标函数 6 可知 非基变量x2的系数是正数 所以X 1 不是最优解 六 求另一个更好的基础可行解 50 1 确定换入变量及其值从从目标函数 6 可知 只有非基变量x2的系数为正 所以 可确定x2为换入变量 由于 所以 当另一个非基变量x3仍然为0时 由 7 式可得到换入变量x1的值为x2 Min 10 0 5 3 0 5 7 1 6 2 确定换出变量从 7 式可知 当x2 6时 x4 0 所以x4为换出变量 由此得到线性规划 1 的一个新的基B2和一组新的基变量与非基变量 B2 P1 P2 P5 XB2 x1 x2 x5 T XN2 x3 x4 T 51 3 求另一个更好的基础可行解 将 1 约束方程中对应于基B2的非基变量x3和x4移到方程的右边后可得 令非基变量x3 x4 0 可得另一基础可行解X 2 2 6 0 0 1 T此时 对应于X 2 的目标函数f X 2 6x1 4x2 36 f X 1 30 七 最优检验将 8 式代入 1 的目标函数后可得f X 36 2x3 2x4 9 从目标函数 9 可知 非基变量x3和x4的系数都是负数 所以X 2 是最优解 即X X 2 2 6 0 0 1 T f X 36 三 求初始基础可行解 背景模型 MAX 52 设线性规划问题为 另设bi 0 i 1 2 m 标准化后 若对xj和aij重新编号 则约束方程可化为