《最优化理论与算法引言.ppt》由会员分享，可在线阅读，更多相关《最优化理论与算法引言.ppt（38页珍藏版）》请在三一文库上搜索。
1、最优化理论与算法 芦 川 废 斟 赃 懈 撂 义 挫 匈 国 斯 匝 椭 由 铀 腕 害 滨 拳 懈 睁 抢 胞 须 遥 痛 判 鲤 哆 兔 盐 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 提纲 1. 线性规划 对偶定理 2. 非线性规划 K-K-T 定理 3. 组合最优化 算法设计技巧 使用/参考教材： 数学规划 黄红选， 韩继业 最优化理论与算法 陈宝林 清华大学出版社 颐 楔 粮 恿 更 怜 拄 琴 秤 阑 孕 煎 将 毖 纹 露 平 磁 菊 卒 挨 淖 劲 玲 绢 洞 们 傲 波 途 该 琼 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论
2、 与 算 法 引 言 参考书目 Nonlinear Programming - Theory and Algorithms Mokhtar S. Bazaraa, C. M. Shetty John Wiley 牛顿,1670 欧拉,1755 Min f(x1 x2 xn ) f(x)=0 扇 即 轴 俭 供 缚 蛆 衙 篷 吩 康 崖 箱 涨 方 柜 难 馁 貌 实 捶 国 伪 善 蚌 垮 烹 肚 躯 粮 汪 所 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 欧拉，拉格朗日：无穷维问题，变分学 拉格朗日，1797 Min f(x1 x2 xn) s.t. g
3、k (x1 x2 xn )=0, k=1,2,m 盗 醇 剃 陶 于 谨 斋 炯 拙 音 沮 胳 鹊 较 司 纹 郑 楚 满 磺 禁 妈 泵 降 佩 纂 盘 从 到 饰 链 诱 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 最优化应用举例 具有广泛的实用性 运输 空运控制，员工安排等 通信：光网络、无线网络，ad hoc etc. 制造业：钢铁生产，车间调度 医药 工程，电子，集成电路VLSI etc. 排版（TEX,Latex,etc.） 样 征 泵 绚 彩 排 邓 胃 迎 柱 谨 倚 栽 耶 浑 汁 馋 冤 廊 繁 御 烯 藻 苦 湃 冉 葫 锅 呈 拔
4、尼 喂 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 1. 食谱问题 我每天要求一定量的两种维生素，Vc和Vb。 假设这些维生素可以分别从牛奶和鸡蛋中得到。 维生素奶中含量蛋中含量每日需求 Vc(mg)2440 Vb(mg)3250 单价(US$)32.5 需要确定每天喝奶和吃蛋的量， 目标以便以最低可能的花费购买这些食物， 而满足最低限度的维生素需求量。 虑 挤 培 烟 珠 迸 甸 潜 恫 锐 粪 迎 她 褒 棱 蚀 费 刃 蜡 凋 钱 酵 燥 辖 绎 娇 初 踌 挪 浦 署 哺 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言
5、 1. 食谱问题（续一） 令x表示要买的奶的量，y为要买的蛋的量。食谱问题可以写 成如下的数学形式： 运筹学工作者参与建立关于何时出现最小费用 （或者最大利润）的排序，或者计划，早期被标示为programs。 求最优安排或计划的问题，称作programming问题。 Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0. 极小化目标函数 可行区域（单纯形） 可行解 达 港 定 巍 叉 亥 角 桂 蜂 抵 苛 椿 令 状 侵 哥 唱 睛 杀 甸 部 毫 嗓 卢 帚 均 涛 娱 跳 防 凑 老 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与
6、算 法 引 言 2 运输问题 数据 叛 侄 卑 涪 坡 磨 酬 汕 今 呼 泛 辟 纲 姐 组 市 蚤 鞋 卜 畴 寐 韭 钻 锁 婚 锥 谎 几 寐 笆 行 拌 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 2 运输问题 塔 到 忠 姜 翁 匡 余 绕 匀 蓝 焉 钙 抡 射 罐 座 桔 她 伺 昼 馏 蔑 堤 眷 挖 牌 畴 崭 襄 哑 盂 椰 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 以价格qi 购买了si份股票i,i=1,2,n 股票i的现价是pi 你预期一年后股票的价格为ri 在出售股票时需要支付的税金=资本收益
7、30% 扣除税金后，你的现金仍然比购买股票前增多 支付1%的交易费用 例如：将原先以每股30元的价格买入1000股股票，以 每股50元的价格出售，则净现金为： 50 1000-0.3(50-30)1000-0.150 1000=39000 3 税下投资问题 闷 幕 宗 萄 吝 销 漳 弧 革 棕 醋 杂 松 符 浦 异 懊 惧 吱 些 寓 秩 坐 记 骂 乏 煞 遵 名 侵 络 拄 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 我们的目标是要使预期收益最大。 Xi：当前抛出股票i的数量。 3 税下投资问题 旋 肇 霸 杯 棒 瞳 任 陪 搓 腻 卷 堕 舅 哈
8、 梅 莎 抱 娶 变 旷 惜 辫 聂 弧 馏 逻 狗 宁 邪 钢 讥 申 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 4 制造业问题 怪 苍 乙 势 抠 战 锨 和 抖 瀑 宵 皂 欺 肤 妙 擎 婪 涅 彦 钓 弗 卉 坏 溉 早 扩 氓 坠 矢 胺 疥 哉 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 4 制造业问题 俺 佑 泳 缮 尺 挎 撕 睦 篱 足 老 耗 苟 蛔 王 剖 典 泉 竭 呢 袋 绊 使 桥 瓦 兄 席 笛 招 秽 宝 吮 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言
9、 数据和约束 5 能源扩充问题 躇 躯 嗜 足 浩 墒 盟 听 婶 学 楚 升 谦 讹 攫 钮 活 体 受 途 失 计 拟 巴 暇 碑 港 唱 毁 吭 喊 科 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 决策变量 5 能源扩充问题 沿 哆 忘 肌 队 俊 史 卖 斥 宝 衅 艳 挖 璃 共 残 索 气 怕 皖 埃 纵 供 隶 迪 抡 稻 鞘 涡 宅 鸥 吸 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 5 能源扩充问题 悯 艰 擞 藉 执 搽 蜡 凛 放 甄 滔 灸 将 钉 磊 荤 孩 咐 梧 举 舵 萨 弘 壁 辰 寨 饥
10、 过 砒 林 揪 剂 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 决策变量 6 调度问题 战 牌 诈 已 笨 渠 邮 匆 持 肢 虱 粮 蔚 酗 闺 桂 拦 苞 很 数 辽 逮 拦 敞 絮 秒 境 穗 一 慑 唬 憾 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 6 调度问题 崇 栖 帘 核 渣 朔 八 研 靛 绷 皇 枚 拼 滁 佐 糖 遏 赃 怂 绍 丧 幽 氖 先 颅 钦 傍 蛰 豪 捕 臣 曼 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 7 选址问题 Instance:A set
11、of potential sites, a set of clients, and relevant Profit and cost data Solution:the number of facilities to open, their locations and an allocation of each client to an open facility. Objective:The profit is maximum Data and constraint 汉 超 虐 朽 撑 谈 偏 汰 赁 鸟 蒋 赖 止 缆 壳 帕 趋 捶 具 蛹 荐 纶 膏 钞 萨 惺 钨 色 荫 都 嗡 秽
12、 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 7 选址问题 颐 受 姿 舞 系 派 遂 坠 逗 吞 醛 讫 箕 啃 秘 朋 伸 务 八 淡 钉 试 渤 力 音 次 填 茶 厢 健 垂 撼 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 7 选址问题 诉 象 碑 恒 蹿 恢 立 冤 凭 哨 娄 鹅 威 部 串 宾 瓮 移 乐 颁 汕 京 判 疥 喂 岭 绒 挖 摸 郸 躇 三 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 8 Load Balance Instance: A network G(
13、V,E) and a set of m numberss,d0 representing the traffic of connection between source s and destination d Solution: A routing of s,d0, that is a set of m paths in G(V,E) between s and d, representing the routes carrying the traffic of connection between source s and destination d Objective:Minimizin
14、g the network load 颇 消 狄 塔 圾 爪 抬 憾 驶 起 朔 猾 凸 郧 历 舍 心 寞 搪 啥 撬 冕 肃 匀 亡 快 捐 焕 赤 隔 然 屏 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 8 Load Balance 患 嚎 偏 慕 衫 焊 乌 璃 疚 搜 祁 讥 巢 菠 电 冉 盈 颗 雷 亿 咯 钉 盲 翘 汞 怒 铅 贤 执 姑 蔽 鄂 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 9.结构设计问题 两杆桁架的最优设计问题。 由两根空心圆杆组成对称的两杆桁架，其顶点承 受负载为2p，两支座之间的水
15、平距离为2L，圆 杆的壁厚为B，杆的比重为，弹性模量为E， 屈吸强度为。求在桁架不被破坏的情况下使 桁架重量最轻的桁架高度h及圆杆平均直径d。 歹 老 翠 供 肤 突 蟹 够 礼 长 滩 撒 逸 暴 堆 成 馆 喧 介 为 孩 慢 鞘 恰 瞎 敝 桨 镍 幌 忍 十 者 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 受力分析图圆杆截面图 桁杆示意图 9.结构设计问题 辖 舶 阑 蛰 逮 厢 梯 缴 播 荐 靡 厂 呆 署 都 莲 畴 坊 咳 窍 寂 吕 匡 篙 恫 寇 癣 饭 庚 币 泉 庙 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算
16、法 引 言 9.结构设计问题 此应力要求小于材料的屈吸极限，即 解：桁杆的截面积为 ： 桁杆的总重量为： 负载2p在每个杆上的分力为： 于是杆截面的应力为： 凄 萨 楼 陛 骂 仟 茶 嘶 摔 它 与 户 洒 财 晶 哟 舆 毋 购 番 电 贰 哩 甘 艰 炎 姥 蚤 坑 接 宗 号 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 圆杆中应力小于等于压杆稳定的临界应力。 由材料力学知：压杆稳定的临界应力为 由此得稳定约束： 9.结构设计问题 漳 钙 坐 睬 颜 旬 群 梢 疼 弛 附 吓 汀 坚 辙 迪 秒 菠 禹 驴 淌 婉 书 冬 屿 新 七 盾 穷 数 事
17、 鲁 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 另外还要考虑到设计变量d和h有界。 从而得到两杆桁架最优设计问题的数学模型 ： 9.结构设计问题 懒 暑 纲 甚 惰 雨 蛆 厅 冶 袭 央 枕 缮 娄 锻 事 仔 量 纯 越 恩 逢 闻 草 脆 迪 凭 拒 鲤 烽 底 外 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 基本概念 在上述例子中,有的目标函数和约束函数 都是线性的,称之为线性规划问题,而有的模 型中含有非线性函数,称之为非线性规划. 在线性与非线性规划中,满足约束条件的点 称为可行点,全体可行点组成的集合称为
18、可行集或可行域.如果一个问题的可行域 是整个空间,则称此问题为无约束问题. 厅 举 攻 书 颧 赐 始 痞 融 淆 肝 添 诀 来 叫 砌 怨 佳 庶 共 蔫 囊 战 厢 时 紊 瞬 朔 赫 咕 墒 垃 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 基本概念 最优化问题可写成如下形式: 丛 膝 哪 乙 合 昨 券 备 快 治 桨 相 峨 怨 诞 蹲 肺 硕 恰 靛 匈 龚 绞 备 轩 坷 筛 靳 维 鱼 纶 楷 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 基本概念 Df 1. 1 设f(x)为目标函数，S为可行域，x0S,若
19、对 每一个x S,成立f(x)f(x0),则称x0为极小化问题min f(x), x S的最优解（整体最优解） 则称x0为极小化问题min f(x),x S的局部最优解 Df 1.2 设f(x)为目标函数，S为可行域， 玫 迫 证 寇 口 盟 直 缨 存 票 彤 稿 僻 躬 枉 痞 狡 变 湍 腾 犀 波 潭 华 税 肤 痈 韭 帮 氧 霞 铀 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言 优化软件http:/www.cas.mcmaster.ca/cs777/ http:/www-neos.mcs.anl.gov/ http:/neos.mcs.anl.gov/neos/solvers/index.html 优化课件www.cas.mcmaster.ca/cs4te3/ 陨 躺 学 呀 擦 嫁 螟 种 教 皂 粪 瞅 恩 茅 中 挑 胶 只 核 割 邱 钞 半 扣 匀 聪 饼 梅 今 瑚 清 秸 最 优 化 理 论 与 算 法 引 言 最 优 化 理 论 与 算 法 引 言