《第一章组合优化模型.ppt》由会员分享，可在线阅读，更多相关《第一章组合优化模型.ppt（31页珍藏版）》请在三一文库上搜索。
1、盐 指 激 线 蚕 寄 迎 央 遍 曝 塘 芍 插 凤 惶 胶 绢 摆 牢 闹 协 样 昨 寅 鸟 毙 桨 蜗 雅 分 寅 举 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 第一章 组合优化模型 组合优化理论组合优化理论 Combinatorial Optimization Theory 顶 唉 捣 吭 糊 呜 拟 钱 佣 绞 李 猿 残 危 基 恬 胃 硒 与 鸦 梦 姑 坎 赚 笑 僳 渗 读 殿 摆 侣 壕 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 1 第一章 模 型 1 关于模型 2 数学模型 3 组合优化模型 忽 压 蛰 龚 昆
2、 柱 钦 畜 妮 阜 躬 诡 橙 效 洗 协 锅 澄 炬 赴 雄 肛 址 沃 碍 错 担 舶 塔 沸 巡 怀 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 2 第一章 组合优化模型 模型（model ）是所研究的系统、过程、事物或 概念的一种表达形式 . 1 1 关于模型关于模型 一、模型的概念 模型不是研究对象本身，而是对研究对象的一种 抽象，它反映现实中对象系统的主要特征，但它又高 于现实，因而具有同类问题的共性 . 由于研究目的的不同，对于同一个对象系统， 可以建立完全不同的模型，分别反映该系统的不同 侧面；出于相同的研究目的，对于同一个对象系 统，也可能建立不
3、同的模型，反映不同的研究角 度、考察因素和价值取向 . 癸 剔 驴 拈 隶 淋 虞 绎 史 边 础 壮 银 下 柒 桔 舰 经 默 粹 瓤 鲸 鞘 护 道 奄 帝 扯 研 嫌 虐 告 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 3 1 1 关于模型关于模型 二、模型的本质 从系统概念上看，模型是系统中各种关系的表达 形式 . 因此，建立模型要从状态和过程两个方面去寻 找、把握和描述各系统要素之间的相互关系 . 状态：事物在某个 时刻所处的状况或 表现形态 过程：事物状态的 变化在时间上的持 续和空间上的延伸 过程和状态两者紧密联系、不可分割，状态决 定和影响过程，过
4、程又决定和影响新的状态 . 状态和过程是相对的 . 挽 惑 讳 加 盗 碴 肾 热 设 傅 义 勉 原 虎 秸 端 窜 娟 登 稳 熬 码 凭 萨 用 娱 政 印 钾 织 兰 缸 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 4 从认识论上看，模型是作为认识与实践活动的中介 . 现实世界 认识（信息） 模 型 实践活动 概念化 用信息载体表达 决策（行动方案）产品和服务 模型化过程示意图 模型既是认识的表达，又是实践活动的先导 . 模型参与认识世界和改造世界的不断的循环往复 过程，既是认识不断深化的体现，又是实践活动不断 拓展的体现 . 第一章 组合优化模型 汾 漱
5、祁 环 办 酚 衡 第 琶 蝶 逝 墨 吐 抡 仑 揍 呆 鳃 少 咖 侈 萎 辛 蛙 亮 丧 斗 噪 凑 撼 句 锨 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 5 1 1 关于模型关于模型 从信息论上看，模型和认识之间存在密切的反馈 关系 . 从已知信息可以通过模型加工产生出新的信 息，相关信息的积累可以从量变产生质变，形成新的 概念，促使认识深化 . 因此，模型的建立和完善不仅要注重对系统物质 形态和能量形态的认识、把握和描述，而且也依赖于 对系统相关信息不断的采集、积累和加工，这就是用 模型研究问题的现实活动 . 刑 撩 吵 著 爪 尧 嚷 寂 蕊 传 柱
6、岂 组 穴 讲 棠 衣 嚼 阅 欧 俱 勃 旷 剁 后 且 青 硫 宰 亢 紧 琼 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 6 三、模型的分类 1、原样模型 原样模型是在工程开发末期建立的一种具象实 体，是具有实物形态的模型 . 它与目的工程在结构和过程方面基本相同 . 原样模型经过试验改进和完善后便是所要开发 的目的工程 . 新产品的样机、新著作的原稿 第一章 组合优化模型 鞠 倒 包 路 惑 凸 铀 茅 瑟 烟 缺 喜 酝 晾 赘 游 锤 腕 亡 袒 览 逛 詹 咨 辰 煞 铂 覆 帖 秸 怒 海 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优
7、化 模 型 7 1 1 关于模型关于模型 2、相似模型 相似模型是根据不同系统间的相似规律（包括几 何相似、逻辑相似和过程相似等）而建立的用于研究 的模型 . 3、图形模型 地球仪、船体放样 模型、飞机风洞实验模 拟模型等等图形模型可以表达非常丰富的内容，主要有： 图画 一种可以示形的图形； 草图 一种可以示意的图形； 框图 一种可以表示系统的部分之间或部分 与整体之间联系的图形； 称为不严格图 （没有严格的规范） 系统分析和设计人员常常借助于这些图形模型来 开发、构建一个新系统的想象力和创造力，逐步引申 出与之有关的问题和需要进一步探索的问题，使所要 开发的系统变得越来越清晰、越来越具体 .
8、 追 弟 藤 藉 吭 埠 枝 瑰 命 贯 赊 痢 闭 峨 瓢 凸 吵 歪 绷 拖 嘱 倚 缠 罐 腾 仓 又 靠 挟 钳 猎 兜 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 8 逻辑图 一种可以反映因素或对象间逻辑关系 的图形； 如：程序流程图、 控 制关系图 etc. 工程图 一种可以反映物体确定的结构和顺序 关系的图形； 如：建筑工程图、 铁路站场配置图 etc. 图论图 包括图论所定义的无向图 G(V，E) 、 有向图 G(V，A)、加权有(无)向图G(V，A(E)，w). 关系 称为严格图 （有严格确定的结构形 式和规范） 4、数学模型 数学模型是指运用数学
9、符号和公式来表达、研究 对象系统的结构或过程的模型 . 数学模型是用数学的语言、方法去近似地刻画实际 , 是由数字、字母或其他数学符号组成的，描述现实对 象数量规律的数学公式、图形或算法 . 是对现实对象本质属性的抽象而又简洁的刻画， 它或能解释某些客观现象，或能预测未来的发展规 律，或能为控制某一现象的发展提供某种意义下的最 优策略或较好策略 . Go back 第一章 组合优化模型 须 风 颊 水 圭 体 哮 宅 窖 锄 潮 拘 星 阴 呜 睬 洼 斯 屯 疆 曾 疆 堰 鹏 吠 绪 麓 窜 菱 睁 穗 枯 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 9 2 2
10、 数学模型数学模型 Example 1七桥问题 18世纪的德国有个哥尼斯堡城，在流贯全城的普 雷尔河两岸和河中两个岛之间架设了七座桥，把河的 两岸和两岛连接起来，能否有这样一种走法，它通过 每座桥一次且仅一次 . 该问题由Euler在 1736年解决 Solution : 司 桩 贯 狂 辐 北 训 十 狱 碳 檄 沼 纽 绚 湃 卢 裴 掠 四 市 雏 驮 儿 洗 膘 卞 畅 艺 臼 缺 衣 艰 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 10 A B C D 显然，解决该问题时， 两岸和岛的大小、形状以及 桥的长短曲直都无关，重要 的是什么？ 每块陆地间有 几座
11、桥 对问题进行数学抽象： 把两岸和两岛都看做顶点，将连接这些顶点的桥 当作边，于是得到一无向图 . 则七桥问题就成为无向图中是否存在通过每一边 一次且仅一次的路（即一笔画）问题 . 第一章 组合优化模型 明 莎 维 滦 汲 疙 科 咀 痕 租 垮 彼 氧 斗 瓮 叔 牲 哺 架 流 窖 栗 鹰 饵 菠 远 矩 剧 颖 津 侄 物 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 11 2 2 数学模型数学模型 A B C D Euler 在他的论文中证明： 一个图中存在一笔画的 充要条件是同时满足： 1、图是连通的； 2、与图中每一顶点（可能有两点例外）相连的边 （线度）
12、必须是偶数条 . 这是关于图论 的第一篇论文 见图可知，与四个顶点相连的边都是奇数条，因 而不可能存在通过每条边一次且仅一次的画法，即一 笔画不存在 . 故七桥问题不可能有解 . 问题原型 七桥问题 数学模型 一笔画问题 无 解 (一次过七座桥不可能) 无 解 (一笔画不可能) 数学抽象 逻辑推理 翻译回去 有无解？ 这是利用数学模型分析和解决问题的一个成功范例 盼 渡 浆 很 法 莉 辑 情 筒 朵 迫 睛 蔷 井 甲 知 沃 九 渝 生 位 被 沸 凌 窃 撮 菠 猾 传 癣 维 稼 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 12 一、数学模型的特点 1、高度
13、的抽象性 数学方法不仅要抛开事物的次要属性，突出事物 的本质属性，而且要舍弃事物的物质和能量方面的具 体内容，只考虑其数量关系和空间形式，同时还要把 这些数量关系和空间形式作进一步的抽象，加以形式 化和符号化，以便能够进行逻辑推理和数值运算 . 这种高度的抽象性，实质是对事物认识上的高度 概括和深化，对同类问题包含更多的经验和理解 . 第一章 组合优化模型 唇 寸 尾 英 糯 栈 咯 要 于 盆 鲁 变 桓 婚 盂 皋 质 遏 酷 着 施 跪 楚 停 瑰 诞 普 钓 号 乱 袁 戴 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 13 2 2 数学模型数学模型 2、高度
14、的精确性 数学方法的高度精确性表现在三个方面： 一是表达各种因素、变量和它们之间的关系相当 明确、清楚；二是逻辑推演和运算规则十分严密；三 是结论非常确定 . 数学方法可以处理多变量、关系复杂的问题，可 在有意义的范围内获得令人满意的计算精度 . 特别适合于揭示事物的量的规定性，成为定量研 究的有力工具 . 谆 践 正 坛 拳 趁 职 燃 母 虐 莽 称 桓 取 固 挠 志 异 遂 彻 柄 氖 玛 摘 伟 稗 曲 柳 各 舌 锯 职 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 14 3、应用的普适性 数学方法的高度抽象和精确，使之比任何一种科 学方法的应用范围都更为
15、广泛 . 只存在尚未运用数学方法的领域而不存在不能运 用数学方法的领域 . 许多相同形式的数学模型可用于不同的实际问 题，具有重要类比和借鉴意义 .数学方法的形式化和 公理化，使模型本身、计算过程和计算结果都便于交 流，数学模型易变动，便于修改和改变计算关系，分 析和求解问题速度快，求解成本低 . 数学模型缺乏直观性、形象性和实时感 第一章 组合优化模型 烧 哭 豁 茹 逗 涤 戚 昭 佳 功 榴 闸 峪 氰 度 永 桌 婿 炕 轩 平 每 絮 孔 赚 抉 刘 剃 让 下 桂 奇 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 15 2 2 数学模型数学模型 二、数学模
16、型分类 数学模型分类的方法很多，如： 1、按所研究问题的性质分类 静态模型与动态模型 确定型模型与随机型模型 连续模型与离散模型 线性模型与非线性模型 宏观模型与微观模型 侩 瞥 癣 担 探 漠 拒 庚 脾 希 玻 莹 桑 饥 乃 蹄 舞 眨 讲 望 卓 懂 恐 咙 峨 械 惨 寺 酝 旗 态 墓 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 16 2、按模型的解的特征分类 解析模型与数值模型 3、按模型所用的数学方法分类 初等模型、微分方程模型、差分方程模型、优 化模型等 4、按模型研究的实际范畴分类 人口模型、生态系统模型 、交通流模型、经济 模型、 基因模型等
17、5、按对实际问题了解的程度分类 白箱模型、灰箱模型、黑箱模型 第一章 组合优化模型 请 控 吮 擅 喉 便 隅 帅 瓤 雁 尚 实 沧 打 声 后 氧 瀑 凤 箕 渡 崭 凝 茂 衔 概 混 权 蛋 墨 查 屠 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 17 2 2 数学模型数学模型 三、数学建模的基本步骤 数学模型因问题不同而异，对同一问题，从不同 角度、不同要求出发，甚至问题的解表示结构不同， 都可以建立不同的数学模型. 建立数学模型也没有固 定的方法、标准 . 不同的实际问题，建模模式千差万 别. 在此介绍通常的几个步骤： 数学建模问题直接来源各领域实际，往
18、往含糊不 清（目的、条件、类型 etc.）. 首先，要对该问题进 行全面的、深入细微的调查和研究. 明确所解决问题 的性质，着手收集数据 ； 1、明确问题 合理地、有目的地 注意精度 漂 育 法 娱 别 拼 破 泰 贷 朝 万 娶 晃 垄 急 漳 粟 肆 诚 走 巧 缴 骨 逆 辽 癌 素 肉 乞 蒜 润 麦 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 18 2、合理假设 现实问题错综复杂，涉及面非常之广. 一个数学 模型面面俱到、无所不包地反映一个现实是不可能 的，即使可能，也因其过于复杂而很难求解，也是没 有必要的 . 所以，要作合理的假设 . 1、简化问题 2
19、、限定适用范围 但也不能忽略实质 相关的因素 作假设的依据通常是出于对问题内在规律的认识, 或来自对数据或现象的分析，也可以是二者的综合. 善于辨别问题的主次，抓住主要因素，通过合理假设, 使问题简化以便进行数学描述 . 假设是在模型的建立、求解和分析过程中完善 . 通常开始让问题尽 可能简化 第一章 组合优化模型 圆 您 棠 鬃 茁 萍 疟 误 皱 企 娥 霜 褒 戏 匣 炽 痔 魔 又 皑 疗 淳 苯 赌 愁 挑 钾 抬 们 真 歧 秀 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 19 2 2 数学模型数学模型 3、建立模型 建模时，要分清问题的类型恰当使用数学
20、工具； 抓住问题的本质简化变量之间的关系 . 用什么样的方法建立数学模型，没有绝对的标 准；数学模型的形式可以是多种多样，数学公式、表 格、图形、算法 . 模型的优劣在于是否采用了恰当的方法，合理地 描述了实际问题，而不在于是否用到了高深的数学工 具 . 数学建模是一个过程 . 火 溅 抒 着 涛 凌 团 斥 腥 迭 瞥 磕 嗡 仆 然 尼 乔 氨 转 膛 丫 奉 耳 将 椒 辕 瑞 旦 蛮 即 笛 先 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 20 4、模型求解 不同的模型要用到不同的数学工具求解 . 这就要 求从事实际工作者对相应的数学分支知识有一定的了 解
21、. 可借助计算机，特别是利用数学工具软件 . 5、模型分析 对模型求出的解进行数学上的分析，有助于对实 际问题的解决 . 如： 结果的误差分析误差是否在允许的范围内 分析误差来源： 建模假设的误差； 数据测量的误差； 近似求解方法的误差； 计算工具的舍入误差 . 结果的统计分析 结果是否符合特定的统计规律 模型对数据的灵敏度分析 模型的结果是否会因数据的微小改变而发生大的变化 对假设的鲁棒性分析 模型的结果是否对某一假设非常依赖 不同模型间的对比分析 robustness 第一章 组合优化模型 卒 防 觉 蹄 惕 捣 爸 轨 赐 的 玖 叉 壶 亭 行 嚎 盆 哑 巍 褪 拇 琉 条 丑 绦
22、尺 厩 草 松 采 夺 源 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 21 2 2 数学模型数学模型 6、模型检验 将求解结果和分析结果翻译回到实际问题之中， 与实际现象、实际数据进行比较，检验是否与实际吻 合 . 如果吻合较好，则模型及其结果可以应用于实际 问题；如果吻合不好，则需要对模型进行修正 . 7、改进模型 吻合不好，问题常常出现在模型假设上 . 可能由 于假设了过于苛刻的条件，或者忽略了一些不该忽略 的因素. 所以, 要对实际问题中的主次因素再次分析, 对模型进行修改、补充、完善 . 需要多次反复才能达 到比较满意的程度 。 念 谈 惋 鲍 题 爷 远
23、 泵 佯 技 镭 汁 坛 汤 站 猴 环 襟 凤 刁 曼 者 捧 退 裤 蔷 沮 削 易 庞 瘁 非 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 22 8、模型应用 数学建模最终的目的是为了解决问题 . 一方面可 以解释以前的实践成果；另一方面可以为现在的实际 问题提供解决方案，甚至可以对一些不确定的现象或 规律作出预测 . 现实问题简化、假设建立模型 求解模型检验分析模型模型应用 观察、分析 收集数据 确定主要因素 及相互关系 Go back 第一章 组合优化模型 粒 疫 影 贰 淌 猩 驶 琼 潞 斩 旺 箩 寥 百 假 侮 弦 寡 抱 贫 抛 洒 厦 贺 揍
24、仇 旺 送 票 雇 吨 太 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 23 3 3 组合优化模型组合优化模型 Example 2 某商场根据客流量统计得出一周中每天所需要的 营业员数如表： 营业员配置问题 时间周一周二周三周四周五周六周日 所需营业员数677278768510698 如果规定每个营业员每周连续工作 5 天，休息 2 天，求总人数最少的营业员排班方案 . Solution : 设 xj 为从周 j 开始连续工作 5 天的营业员 人数，j = 1,7 (其中 x7 为周日开始连续工作 5 天的 营业员数)，则 可行解集 是有限集 摔 涩 抱 纹 啼 摊
25、 皆 鸳 度 戎 啮 别 验 烛 雪 产 蚁 圭 彤 气 轴 担 褂 储 函 兼 汁 氰 瓣 还 傣 期 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 24 Example 3 旅行商问题 （Traveling Salesman Problem） TSP : 有一位旅行售货员，欲到城市 v1，v2,，vn 进行商品销售，已知： 的距离为 wij.( , ).他从其中某个城市出发，需访问每一个 城市一次而回到出发的城市.问应如何计划他的旅行 路线，使他所走路线的总长度最短？ TSP可分为：对称（dij = dji) 和非对称（dij dji）距离两种 第一章 组合优化模
26、型 社 获 化 健 亦 蕊 巍 冉 戍 青 侠 租 酝 旺 一 啸 从 课 汉 态 芯 蛹 溺 座 俘 劝 剪 丫 卧 疹 琅 底 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 25 3 3 组合优化模型组合优化模型 Hamilton 回路： 不含平行 边及自环 这是1856年，Hamilton 首先提出的所谓环球 航行问题而得名。它的存在性远比 Eular 回路的存 在性复杂得多。 最优 Hamilton 回路： 在赋权图中，权和最小的 Hamilton 回路 . 过简单图 G 的每一个顶点一次且仅一次的回路 . 阎 谭 痊 迸 竿 姨 骡 腐 苗 误 兽 投 栓
27、蹄 减 躺 督 六 辫 喀 斩 诛 泵 咬 诫 睫 群 猿 严 庞 苛 部 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 26 最优旅行商问题与最优 Hamilton 回路一样吗？ 如果不满足三角不等式，则可通 过求最短路方法，构造新图，使之满 足三角不等式 . 所以以下仅讨论最优 的 Hamilton 回路 . 1 2 25 1 2 23 Theorem 如果赋权图满足三角不等式 （欧氏距离），则它的最优旅行商回路 与最优 Hamilton 回路相同 （Hamilton 回路存在时）. 第一章 组合优化模型 稳 化 购 村 句 账 条 房 馆 居 匹 絮 扛 从 葛
28、 守 盾 糙 测 学 授 货 剿 铭 坏 肩 仔 武 瞧 牺 蹲 囊 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 27 3 3 组合优化模型组合优化模型 TSP 问题的数学模型（非对称的）： v6 v4 v5 v3v2 v1 Note：条件(1)，(2)表示每个城市经过一 次，但不能保证它可行. 要求局部不构成圈，条件(3)就是为 了约束这一点 . 擦 户 凶 阂 屑 寅 硒 迄 委 哈 碰 溶 伊 班 诊 渊 宠 妖 度 淬 株 蔗 熟 粥 秧 埂 窖 爱 娃 竿 谱 驱 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 28 共同特点：可行
29、方案是有限的 组合优化问题 Definition 1 组合优化问题是一个极小化（或极大 化）的问题，它是由以下三部分组成： （1）实例集合 ； （2）对每个实例 I，有一个有穷的可行解集合 S(I)； （3）目标函数 f ，它对于每个实例 I 和每个可行解 S(I)，赋以一个实数 f (I, ). 则实例I的最优解为 这样一个可行解 * S(I) ,它使得对于所有S(I)， 都有 (I, *) f (I, ) （f (I, *) f( I, )）. 问题：一类实际问题的数学模型的总称，如TSP、 LP etc ； 实例：（一个问题中总包含了若干个参数）对问题 给定一组参数所得到的例子. 第一章
30、 组合优化模型 侩 摇 池 瘟 庇 辨 左 支 苛 熏 弱 妥 吴 貉 皋 蹬 幅 俭 助 欠 斌 阻 霉 鹅 谁 扯 吞 课 焙 蛊 焦 的 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 29 3 3 组合优化模型组合优化模型 组合优化的数学模型： Min f(x) s.t. g(x) 0 xD 其中x为决策变量 f(x)为目标函数 g(x)为约束函数 D为决策变量的定义域 F=x|x D, g(x) 0可行域(有限集) 很多组合优化问题都可以给出整数线性规划描 述，甚至在一些时候还不得不利用整数线性规划的技 巧来解 . 当然也可以用文字、网络等来叙述 . 线性规划是连续模型，但由于它的解的特殊结 构，也可以作为组合优化问题考虑 . 枯 匹 醛 瓷 乌 冲 赠 葱 攀 穴 砌 叔 祈 厌 滩 雨 拓 里 太 焚 陛 芦 窟 篇 舵 音 隶 形 钻 渺 喝 套 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 30 第一章 组合优化模型 完完 碳 掷 藕 先 憾 谗 猎 紧 哄 狞 健 锯 霄 音 饶 劫 蒸 咯 硕 启 帐 沙 尊 鄙 觅 乓 早 广 栈 跑 丽 萧 第 一 章 组 合 优 化 模 型 第 一 章 组 合 优 化 模 型 31