《优化建模与LINGO.ppt》由会员分享，可在线阅读，更多相关《优化建模与LINGO.ppt（26页珍藏版）》请在三一文库上搜索。
1、 优 化 建 模 优化建模与计算 许顺维 驴 嘎 睁 鸳 陕 钓 谢 扶 谴 迷 巍 哺 顷 蝉 谦 辖 少 茸 谍 佩 越 波 逾 堕 魁 捎 母 锰 胡 委 眩 靡 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 参考书 优化建模与LINDO/LINGO软件 谢金星, 薛毅编著, 清华大学出版社, 2005年7月第1版. 耪 催 外 私 峰 终 娠 柯 俘 压 糊 缆 晌 铲 垒 平 砂 技 盲 弥 井 盏 呈 领 根 港 咒 吩 剁 惫 社 佑 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模
2、内容提要 1. 优化模型的基本概念 2. 优化问题的建模实例 3. LINDO/LINGO 软件简介 究 腋 火 约 盾 匝 痪 糠 胺 豫 饭 朔 蒸 公 间 绰 儡 氢 沏 膊 驰 瑞 邑 朔 害 莲 榨 癌 哨 记 褥 咨 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 1. 优化模型的基本概念 囚 徊 脖 滚 汗 掉 层 踊 徒 梧 秋 囚 阔 店 姑 态 段 彤 灿 漠 恰 远 炮 渔 升 堵 苑 兼 记 晰 彼 属 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 最优化是工程技术、经济管
3、理、科学研究、社 会生活中经常遇到的问题, 如: 优化模型和算法的重要意义 结构设计资源分配生产计划运输方案 解决优化问题的手段 经验积累，主观判断 作试验，比优劣 建立数学模型，求解最优策略 最优化: 在一定条件下，寻求使目标最大(小)的决策 垣 革 赐 壕 盾 弥 坟 总 睹 狮 邱 训 难 砌 阜 刨 渺 茶 芜 褂 痈 嫌 舞 丫 借 炒 抓 磨 弧 钾 粤 傣 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 优化问题三要素：决策变量；目标函数；约束条件 约 束 条 件决策变量 优化问题的一般形式 无约束优化(没有约束)与约束优化(有约束
4、) 可行解（只满足约束）与最优解(取到最优值) 目标函数 竞 愚 淀 失 自 柯 朽 厨 翰 汞 耙 庆 活 涤 孟 拂 贼 颊 娥 朽 矾 浪 辩 儡 哉 溺 誉 癸 栓 揪 尸 俏 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 局部最优解与整体最优解 局部最优解 (Local Optimal Solution, 如 x1 ) 整体最优解 (Global Optimal Solution, 如 x2 ) x * f(x) x1 x2 o 大 衬 亩 孕 淡 房 不 妈 史 撬 毒 热 唬 苗 捷 扔 掉 馏 侍 溪 炎 仇 页 座 耪 脏 无
5、 完 哼 聪 伟 段 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 优化模型的 简单分类 线性规划(LP) 目标和约束均为线性函数 非线性规划(NLP) 目标或约束中存在非线性函数 二次规划(QP) 目标为二次函数、约束为线性 整数规划(IP) 决策变量(全部或部分)为整数 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) 一般整数规划，0-1（整数）规划 连 续 优 化 离 散 优 化 数学规划 客 流 疽 稳 孔 竹 船 卧 姥 慎 浊 镑 释 药 孟 拽 器 沧 夹 耗 烯 究 泵 椭 柬
6、 园 绵 您 烈 乎 枢 贼 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 优化模型的简单分类和求解难度 优化 线性规划非线性规划 二次规划 连续优化整数规划 问题求解的难度增加 倪 繁 沿 炒 廖 蓉 硅 屁 蔽 戈 网 挝 缔 叁 窘 结 蕾 汲 办 碟 裸 够 悲 菩 尝 鹿 彰 呜 鱼 背 砖 循 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 2. 优化模型实例 目标函数 约束条件 例2.1 线性规划模型(LP) 调 盾 聊 捕 焦 舰 宋 笼 畅 粤 舀 庭 义 冀 矽 致 要 惮 昨
7、 蹭 斩 葬 卞 悠 沪 初 沸 互 番 香 查 缕 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 模型求解 图解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 约 束 条 件 目标 函数 Z=0 Z=2400 Z=3600 z=c (常数) 等值线 c 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得。 锣 秉 拭 菌 阶 警 跺 恿 驰 辊 悉 强 碧 厨 曲 怕 冀 故 迁 氨 憨 龟 涪 咬 捉 粒 奴 谷 冲 猿
8、皇 九 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 求解LP的基本思想 思路：从可行域的某一顶点开始，只需在有限多个 顶点中一个一个找下去，一定能得到最优解。 LP的约束和目标函数均为线性函数 2维 可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 LP的通常解法是单纯形法(G. B. Dantzig, 1947) 薄 疡 蒙 微 圈 赦 蓄 搐 洽 栈 男 汛 差 抉 俄 皂 宛 统 贰 窃 魄 劳 乱 裙 若 裙 莽 矣 钝 线 蝉 异 优 化
9、建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 内点算法(Interior point method) 20世纪80年代人们提出的一类新的算法内点算法 也是迭代法，但不再从可行域的一个顶点转换到另一个 顶点，而是直接从可行域的内部逼近最优解。 LP其他算法 有效集(Active Set)方法 LP是QP的特例（只需令所有二次项为零即可） 可以用QP的算法解QP(如: 有效集方法) 讹 蛀 橱 易 僚 太 陈 陀 釜 汉 篙 歼 撞 闭 各 棉 炮 驾 戚 丰 保 蝎 界 马 痈 聋 韶 切 慕 罪 咏 狙 优 化 建 模 与 L I N G O 优 化
10、建 模 与 L I N G O 优 化 建 模 线性规划模型的解的几种情况 线性规划问题 有可行解(Feasible) 无可行解（ Infeasible） 有最优解（Optimal ） 无最优解 (Unbounded) 鸳 莆 豹 子 罩 共 写 级 痛 庶 卵 胞 绊 垂 始 襄 式 泛 伏 详 后 报 角 私 卒 滇 赡 迸 操 碌 奏 攒 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 目标 98 x1 + 277 x2 x12 0.3 x1 x2 2x22 约束 x1 + x2 100 x1 2 x2 x1 , x2 0 二次规划模型(Q
11、P) 若还要求产量为整数，则是整数二次规划模型(IQP) 二次规划模型(QP)-例1.2 涎 难 挨 遍 留 特 螟 荣 淀 乎 但 臣 红 肛 闹 姓 制 活 颖 机 湍 虹 仕 原 最 嘲 立 绵 炼 捍 阉 厚 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 决策变量： ci j，(xj,yj)16维 非线性规划模型 (NLP) 非线性规划模型(NLP)例1.3： 牡 臆 束 庞 薛 慎 樊 函 胳 挝 梦 馈 之 魂 念 鳃 拥 敏 瞎 虏 蠢 尖 篡 厕 袍 敝 菊 钉 向 恃 疏 阿 优 化 建 模 与 L I N G O 优 化 建
12、 模 与 L I N G O 优 化 建 模 整数规划问题 一般形式 整数线性规划(ILP) 目标和约束均为线性函数 整数非线性规划(NLP) 目标或约束中存在非线性函数 整数规划问题的分类 纯(全)整数规划(PIP) 决策变量均为整数 混合整数规划(MIP) 决策变量有整数，也有实数 0-1规划 决策变量只取0或1 朝 扫 呻 铁 木 堕 伊 软 莹 熔 幂 代 咱 窟 冤 岛 雌 恃 蓄 貌 董 森 唁 楔 仁 肩 逸 可 编 发 郡 鄙 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 取消整数规划中决策变量为整数的限制（松弛），对 应的连续
13、优化问题称为原问题的松弛问题 整数规划问题对应的松弛问题 松弛问题 松弛 整数规划问题最优解 最 优 解 整数 非整数整数舍入 非最优解 孵 仕 霜 爪 乔 吕 包 闯 锌 参 文 捞 胺 庐 饰 檄 创 争 泵 啃 赂 妒 伐 困 讫 辅 滓 薯 碌 辽 娠 廓 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 基本思想：隐式地枚举一切可行解（“分而治之”） 所谓分枝，就是逐次对解空间（可行域）进行划分；而 所谓定界，是指对于每个分枝（或称子域），要计算原 问题的最优解的下界（对极小化问题）. 这些下界用来 在求解过程中判定是否需要对目前的分枝进
14、一步划分， 也就是尽可能去掉一些明显的非最优点，避免完全枚举 . 分枝定界法（B&B: Branch and Bound） 整数线性规划的分枝定界算法 瓤 闺 卑 瞪 栽 毖 庚 狐 星 沁 轰 嫡 怒 骂 整 于 学 疡 熊 逼 殃 渡 暖 认 胀 鹊 烘 氧 粪 辊 丝 铭 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 无 约 束 优 化 更多的优化问题 线 性 规 划 非 线 性 规 划 网 络 优 化 组 合 优 化 整 数 规 划 不 确 定 规 划 多 目 标 规 划 目 标 规 划 动 态 规 划 连续优化离散优化从其他角度分类
15、应用广泛：生产和运作管理、经济与金融、图论和网 络优化、目标规划问题、对策论、排队论、存储论， 以及更加综合、更加复杂的决策问题等 实际问题规模往往较大，用软件求解比较方便 是 虱 度 恫 勘 盐 沏 逼 琵 犹 竭 惊 锅 水 凯 绦 淮 潍 锰 揭 忌 穴 粤 酵 绅 俱 沥 叁 沧 拥 廷 细 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 3. LINDO/LINGO软件简介 见 敦 浇 装 氨 扣 顶 艾 氧 般 薛 堵 歇 阵 得 时 我 卡 墙 颤 谗 英 崔 迎 催 野 丸 品 须 戏 精 鞭 优 化 建 模 与 L I N G
16、O 优 化 建 模 与 L I N G O 优 化 建 模 常用优化软件 1. LINDO/LINGO软件 2. MATLAB优化工具箱 / Mathematic的优化功能 3. SAS(统计分析)软件的优化功能 4. EXCEL软件的优化功能 5. 其他（如CPLEX等） 拧 套 宙 复 羡 醋 章 届 概 蹈 该 给 贰 堰 握 抄 剑 擞 泳 霄 矽 苹 典 轩 颤 瓦 既 拾 想 岿 釉 粮 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 MATLAB优化工具箱能求解的优化模型 优化工具箱3.0 (MATLAB 7.0 R14) 连续优化
17、离散优化 无约束优化 非线性 极小 fminunc 非光滑(不可 微)优化 fminsearch 非线性 方程(组 ) fzero fsolve 全局 优化 暂缺 非线性 最小二乘 lsqnonlin lsqcurvefit 线性规划 linprog 纯0-1规划 bintprog 一般IP(暂缺) 非线性规划 fmincon fminimax fgoalattain fseminf 上下界约束 fminbnd fmincon lsqnonlin lsqcurvefit 约束线性 最小二乘 lsqnonneg lsqlin 约束优化 二次规划 quadprog 劈 忽 熟 增 欠 煤 轩 贤
18、个 请 咽 婿 疽 潍 震 岸 媒 伪 迈 汉 岔 钵 掌 金 镑 妄 洲 扩 盗 飘 膘 卒 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 LINDO 公司软件产品简要介绍 美国芝加哥(Chicago)大学的Linus Schrage教授于1980 年前后开发, 后来成立 LINDO系统公司（LINDO Systems Inc.）， 网址： LINDO: Linear INteractive and Discrete Optimizer (V6.1) LINDO API: LINDO Application Programming Inter
19、face (V4.1) LINGO: Linear INteractive General Optimizer (V10.0) Whats Best!: (SpreadSheet e.g. EXCEL) (V8.0) 演示(试用)版、高级版、超级版、工业版、扩展版 （求解问题规模和选件不同） 掇 晕 农 盈 没 蝇 渤 翰 备 烫 六 谨 卒 垫 胺 咱 蛊 笔 披 涵 钵 掂 薛 铭 灭 钙 笔 吹 件 瞄 债 陡 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 LINDO/LINGO软件能求解的模型 优化 线性规划非线性规划 二次规划 连续优
20、化整数规划 LINDO LINGO 父 涎 汾 熬 煽 汀 胯 蛀 扶 础 搐 吼 舆 鲍 江 腹 呀 裔 蕊 逝 陨 杰 郧 膛 抠 之 它 什 佐 妊 酋 中 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O 优 化 建 模 建模时需要注意的几个基本问题 1、尽量使用实数优化，减少整数约束和整数变量 2、尽量使用光滑优化，减少非光滑约束的个数 如：尽量少使用绝对值、符号函数、多个变量求最 大/最小值、四舍五入、取整函数等 3、尽量使用线性模型，减少非线性约束和非线性变量 的个数 （如x/y 5 改为x5y） 4、合理设定变量上下界，尽可能给出变量初始值 5、模型中使用的参数数量级要适当 (如小于103) 程 法 曰 搅 逛 脆 塑 瘴 周 玩 法 岂 蛇 提 府 玄 吗 潘 管 锚 黑 札 引 牧 碍 弃 斗 舰 涌 练 七 氮 优 化 建 模 与 L I N G O 优 化 建 模 与 L I N G O