运筹学讲座2009 终稿.ppt

邓寿年 1运筹学简介 名称的由来OperationResearch运筹帷幄 史记 运作研究 运筹学的由来与发展 运筹学 OperationsResearch 直译为 运作研究 运筹学是运用科学的方法 如分析 试验 量化等 来决定如何最佳地运营和设计各种系统的一门学科 运筹学能够对经济管理系统中的人力 物力 财力等资源进行统筹安排 为决策者提供有依据的最优方案 以实现最有效的管理 通常以最优 最佳等作为决策目标 避开最劣的方案 运筹学思想的出现可以追溯到很早 田忌齐王赛马 对策论 孙子兵法等都体现了优化的思想 OperationalResearch 这一名词最早出现在第二次世界大战期间 美 英等国家的作战研究小组为了解决作战中所遇到的许多错综复杂的战略 战术问题而提出的 战后这些研究成果被应用到生产 经济领域 并得到迅速发展 有关理论和方法的研究 实践不断深入 1947年美国数学家丹捷格 G B Dantzig 提出了求解线性规划的有效方法 单纯形法 1 分析与表述问题 2 建模 3 求解 4 评估各个方案 对解的检验 5 对解的有效控制 6 方案实施 7 评估 考察问题是否得到完满解决 运筹学解决问题的过程 线性规划 数学规划 非线性规划 整数规划 动态规划 学科内容 多目标规划 双层规划 组合优化 最优计数问题 网络优化 排序问题 统筹图 随机优化 对策论 排队论 库存论 决策分析 可靠性分析 运筹学的主要分支 2线性规划 linearprogramming 常山机器长生产i ii两种产品 这两产品分别要在A B C三种不同的设备上加工 每生产i产品要用各设备分别为2h 4h 0h 生产ii产品为2h 0h 5h 设备的生产能力分别为 12h 16h 15h每生产一件i产品可以获得利润为2元 每生产一件ii产品可以获得利润为3元 问企业应安排生产两种产品各多少件 使总的利润最大 maxz 2x1 3x2 s t2x1 2x2 0 任务分配问题 某车间有甲 乙两台机床 可用于加工三种工件 假定这两台车床的可用台时数分别为800和900 三种工件的数量分别为400 600和500 且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表 问怎样分配车床的加工任务 才能既满足加工工件的要求 又使加工费用最低 解设在甲车床上加工工件1 2 3的数量分别为x1 x2 x3 在乙车床上加工工件1 2 3的数量分别为x4 x5 x6 可建立以下线性规划模型 优化问题 一般指用 最好 的方式 使用或者分配有限的资源 即劳动力 原料 机器 使得费用最小或利润最大 线型规划问题的组成要素 1 决策变量 为实现目标采取的方案 措施 是问题的未知量 记为X 2 目标函数 问题要达到的要求 为决策变量的函数 3 约束条件 决策变量取值时受到的资源的限制 表示为含决策变量的不等式或等式 建立线型规划模型的步骤 确定决策变量 表示目标函数 界定约束条件 能归结为线型规划的模型 问题目标能用某种效益指标度量大小 能用线型函数描述目标的要求 为达到目标存在多种方案 目标是在一定约束条件下实现的 条件可以用线型不等式来描述 线性规划模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 0自由变量线性规划的标准形式目标函数 min约束条件 变量符号 0 价值向量 资源向量 矩阵型标准型 线性规划的标准型 standardmodel 线性规划的标准型 对目标函数求极小 决策变量一律为非负变量 约束条件除变量的非负条件外 一律为等式约束 各种形式的线性规划模型一律为等式约束 若目标函数为 则可令f z 此问题转化为求 若约束条件含则引进有称为松弛变量 若约束条件含 则引进新变量 有称为剩余变量 若约束条件含则引进 于是 若变量的符号不受限制 则可引进两个新量 并以代入目标函数及约束中消去 而在约束条件中增加例 把线性规划化为标准型 分析 令 将maxz改为求minf 用代替 其中 对不等式约束分别引进松弛变量和剩余变量 于是 原问题化为标准型 例把问题转化为标准形式 求解线性规划模型的基本算法 图解法 1 建立直角坐标系 2 由约束条件作出X的可行域 全部可行解所组成的集合 3 作横穿可行域的等值线 4 判定最优解5 计算出最优解及最优值 对于只有两个变量的线性规划问题可以用图解法求解 maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 目标函数z x1 3x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 用MATLAB优化工具箱解线性规划 命令 x linprog c A b 2 模型 minz cX 命令 x linprog c A b Aeq beq 注意 若没有不等式 存在 则令A b 命令 1 x linprog c A b Aeq beq VLB VUB 2 x linprog c A b Aeq beq VLB VUB X0 注意 1 若没有等式约束 则令Aeq beq 2 其中X0表示初始点 4 命令 x fval linprog 返回最优解 及 处的目标函数值fval 解编写M文件xxgh1 m如下 c 0 4 0 28 0 32 0 72 0 64 0 6 A 0 010 010 010 030 030 03 0 02000 0500 00 02000 050 000 03000 08 b 850 700 100 900 Aeq beq vlb 0 0 0 0 0 0 vub x fval linprog c A b Aeq beq vlb vub 解 法一c 634 A 010 b 50 Aeq 111 beq 120 vlb 30 0 20 vub x fval linprog c A b Aeq beq vlb vub 法二 c 634 A b Aeq 111 beq 120 vlb 30 0 20 vub 120 50 120 x fval linprog c A b Aeq beq vlb vub 3非线性规划 nonlinearprogramming 定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题 非线性规划的基本概念 一般形式 1 其中 是定义在En上的实值函数 简记 其它情况 求目标函数的最大值或约束条件为小于等于零的情况 都可通过取其相反数化为上述一般形式 建立非线型规划模型的步骤 确定决策变量 表示目标函数 界定约束条件 一般形式 1 其中 是定义在En上的实值函数 简记 34 例 约束回归 某大学希望为它的毕业生安排工作位置 为简单起见 假设每个毕业生接受政府部门 工业界或科学院中的一个位置 35 估计人数 实际人数 36 1 首先建立M文件fun m 定义目标函数F X functionf fun X f F X 一般非线性规划的matlab求解 其中X为n维变元向量 G X 与Ceq X 均为非线性函数组成的向量 其它变量的含义与线性规划相同 用Matlab求解上述问题 基本步骤分三步 37 3 建立主程序 非线性规划求解的函数是fmincon 命令的基本格式如下 1 x fmincon fun X0 A b 2 x fmincon fun X0 A b Aeq beq 3 x fmincon fun X0 A b Aeq beq VLB VUB 4 x fmincon fun X0 A b Aeq beq VLB VUB nonlcon 5 x fmincon fun X0 A b Aeq beq VLB VUB nonlcon options 6 x fval fmincon 7 x fval exitflag fmincon 8 x fval exitflag output fmincon 输出极值点 M文件 迭代的初值 参数说明 变量上下限 38 1 先建立M文件fun4 m 定义目标函数 functionf fun4 x f exp x 1 4 x 1 2 2 x 2 2 4 x 1 x 2 2 x 2 1 x1 x2 0s t 1 5 x1x2 x1 x20 x1x2 100 例 2 再建立M文件mycon m定义非线性约束 function g ceq mycon x g 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 ceq 39 3 主程序youh3 m为 x0 1 1 A b Aeq 11 beq 0 vlb vub x fval fmincon fun4 x0 A b Aeq beq vlb vub mycon x1 x2 0s t 1 5 x1x2 x1 x20 x1x2 100 M文件mycon m定义非线性约束 function g ceq mycon x g 1 5 x 1 x 2 x 1 x 2 x 1 x 2 10 ceq 4图与网络 Graph Network 图论的基本概念 一 图的概念 1 图的定义 2 顶点的次数 3 子图 二 图的矩阵表示 1 关联矩阵 2 邻接矩阵 图的定义 定义 定义 顶点的次数 关联矩阵 注 假设图为简单图 邻接矩阵 注 假设图为简单图 最短路问题及其算法 一 基本概念 二 固定起点的最短路 三 每对顶点之间的最短路 基本概念 返回 固定起点的最短路 最短路是一条路径 且最短路的任一段也是最短路 假设在u0 v0的最短路中只取一条 则从u0到其余顶点的最短路将构成一棵以u0为根的树 因此 可采用树生长的过程来求指定顶点到其余顶点的最短路 七桥问题的由來 十八世纪东普鲁士哥尼斯堡城 今俄罗斯加里宁格勒 的普莱格尔河 它有两个支流 在城市中心汇成大河 中间是岛区 河上有7座桥 将河中的两个岛和河岸连结 如图所示 由于岛上有古老的哥尼斯堡大学 有教堂 还有哲学家康德的墓地和塑像 因此城中的居民 尤其是大学生们经常沿河过桥散步 渐渐地 爱动脑筋的人们提出了一个问题 一个散步者能否一次走遍7座桥 而且每座桥只许通过一次 最后仍回到起始地点 这就是七桥问题 一个著名的图论问题 解決七橋問題的尤拉 尤拉 LeonardEuler 1707 1783 瑞士人 出身於牧師家庭 13歲考入大學 16歲已經獲得碩士學位 1727年到俄國聖彼得科學院工作 1741年轉到德國 任柏林科學院物理數學所所長 1766年回到俄國 直至去世 他在1735年 由於過度工作的關係 引至右眼失明 1771年又因眼疾引致左眼失明 1783年逝世於俄國的聖彼得堡 著作有無窮微量分析入門 無窮小分析引論 1748 微分學原理 1755 關於曲面上曲線的研究 1766 積分學原理 1768 1770 方程的積分法研究 等 尤拉是數學史上最多產的數學家 我們現在習以為常的數學符號很多都是尤拉所發明介紹的 例如 函數符號f x 圓周率 自然對數的