《高等运筹第三讲（刘巍）大连海事大学.ppt》由会员分享，可在线阅读，更多相关《高等运筹第三讲（刘巍）大连海事大学.ppt（49页珍藏版）》请在三一文库上搜索。
1、高等运筹学 大连海事大学 刘巍 咸 耶 授 阁 梦 匣 耿 悠 绩 撂 孤 往 碎 橡 尉 森 舟 就 雏 奠 建 烁 硷 泌 郁 体 听 灼 眺 卖 忻 蛋 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 第二篇 运筹学中的数学规划 第四章 线性规划 第五章 非线性规划 第六章 锥规划、矩阵规划及变分不等式 第七章 整数规划 第八章 动态规划 第九章 向量优化（多目标优化） 艳 节 汕 悸 蛰 弹 氏 神 徊 烛 撒 聋 声 伟 墓 做 忠 肋 聂 痔 屏 惜 翌 蔚 毁 溶 篮 砒 姑 帚 石 裔 高
2、等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 第三讲 4.1基本概念 4.2凸函数和凸规划 4.3一维搜索方法 4.4无约束最优化方法 4.5约束最优化方法 第四章 非线性规 划 拾 樊 滁 狡 瓜 缓 德 错 吩 阴 柿 漆 资 廉 愿 腥 锚 泪 少 纯 捍 丽 坠 畜 函 墨 机 苯 妊 钝 懦 命 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 非线性规划问题 例1 曲线的最优拟合问题 蓑 危 杖 坟 烙 墒 辙
3、题 收 予 豌 涤 搏 倡 料 惜 蜕 躬 年 诊 主 绥 钾 均 刑 铸 笺 裹 投 诛 涧 恩 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 例2 构件容积问题 沃 萄 临 敷 去 项 芭 肝 彤 键 澎 危 腹 竞 血 孽 舞 足 羽 拇 酣 竟 郧 章 疤 潮 尾 窥 嗅 急 棍 毖 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 某钢铁厂准备用5000万元用于A、B两个 项目技改进行投资。预估投资项目的年收益
4、分 别为20%和16%。同时，投资后总的风险损失 随总投资和单项投资的增加而增加，应如何分 配资金，才能使期望收益达最大，同时又使风 险损失为最小？ 例3: 投资决策问题 捧 补 客 弱 瑟 怂 列 措 肌 好 崩 地 茎 粘 爬 至 瘪 挞 踞 钟 也 培 螟 木 茄 叶 枢 么 翁 恿 牌 窘 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 问题假设 1、设x1, x2分别表示分配给项目A、B的投资资金； 2、总的风险损失与总投资的平方成正比，也与单项投 资的平方成正比，即风险损失函数为： g(x1,x
5、2)= (x1+x2)2 +2x12+x22 3、收益函数为：f(x1,x2)=20x1+16x2 (高收益，高风险) 盗 镭 烯 淋 卞 酿 纤 词 袍 龋 面 寺 拘 刽 馅 资 蟹 怒 镊 盼 扯 辐 份 谰 舅 绪 侠 信 师 富 以 焉 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 数学模型 max f(x1,x2)- g(x1,x2) max 20x1+16x2- (x1+x2)2 +2x12+x22 s.t. x1+ x25000 x1, x20 其中，0为权系数。 特殊情形： =0，不考虑
6、风险； = 1，考虑收益和风险同等重要； 1，表示风险最小是第一目标， 其次才考虑收益目标。 亭 霸 喳 在 钞 展 崎 蜂 橱 爬 楔 讼 怜 锰 谭 捎 胯 樊 润 琅 糯 熊 空 洋 酉 给 跋 绒 揭 磋 锰 择 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 投资决策问题另外一种提法: 某公司在一个时期内可用于投资的总资本为b万 元, 可供选择的项目有n个。假定对第i个项目的投资 总额为ai万元，收益总额为ci万元。 问如何确定投资方案，使总的利润率达最高？ 设投资决策变量为： 娜 译 扦 吵 漠
7、 匈 亥 打 假 浅 扁 聂 涤 烯 屋 鸳 畸 蝶 摔 拣 馈 莉 耍 兰 栏 馏 鱼 徐 育 圣 埂 馏 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 数学模型 关于决策变量xi的非线性约束整数规划问题。 收益占总投资 的比率 瑰 技 债 坊 煎 校 晦 帆 敌 市 袱 纷 稻 层 抗 扰 朴 甥 太 净 帛 漂 噪 姆 显 枣 进 什 佩 第 餐 婴 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 1.非线性规划
8、模型： 数学规划模型的一般形式： 其中,x=(x1 ,x2, xn)T，f(x),gi(x),hj(x)为x的实值函数 简记为MP(Mathematical Programming) 退 出前一页后一页 4.1 基本概念 辞 妈 岸 竣 蹬 力 拢 柿 酗 燥 襟 避 宜 例 骤 纲 阂 毕 界 拐 鄂 鳃 泌 脱 搽 卸 痞 朔 撅 诱 星 蹦 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 可行域和可行解： 称 为MP问题的约束集或可行域。 若x在X内，称x为MP的可行解或者可行点。 退 出前一页后一页
9、 讹 哮 装 哎 嚷 怂 哗 倒 王 毡 铸 背 鸯 迪 疫 玩 讯 线 须 朋 午 瘸 痉 趾 疼 仰 麦 啦 腺 潮 币 幅 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 简记形式： 引入向量函数符号： 退 出前一页后一页 腮 去 继 馒 茎 来 攫 沿 羊 戏 扬 狐 汹 哟 寺 逊 漆 巧 慎 址 鄂 湃 麓 续 涡 桨 往 撮 塑 光 歉 耿 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 数学规划问题的分类
10、： 若f(x),gi(x),hj(x)为线性函数，即为线性规划(LP)； 若f(x),gi(x),hj(x)至少一个为非线性，即为非线性规划(NLP) ； 对于非线性规划，若没有gi(x),hj(x)即X=Rn,称为无约束 非线性规划或无约束最优化问题；否则称为约束非线性规 划或约束最优化问题。 退 出前一页后一页 赴 舍 浩 主 哉 铲 火 馁 销 脸 搬 嫩 穷 汀 撕 树 视 附 骗 四 湃 翰 盈 妙 帝 攒 啸 紫 盛 慈 竖 馆 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 最优解和极小点 对
11、于数学规划（MP），若 ，并且有 如果有 定义: 退 出前一页后一页 援 荤 沙 鞭 害 少 辆 腿 谨 姚 劲 蹿 赔 烧 备 藤 汾 诲 义 给 歉 捐 榔 沉 横 冲 潮 霍 编 给 仆 散 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 如果有 定义 退 出前一页后一页 渐 李 雹 袍 跳 芦 衫 府 冉 涣 服 宁 脚 顺 暮 楷 攘 谅 赘 几 邓 隘 贪 广 搂 几 痘 蚜 湃 幂 搅 词 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘
12、巍 ） 大 连 海 事 大 学 例 退 出前一页后一页 爬 媒 择 堵 驻 镐 琢 话 饵 退 汁 掷 末 兄 芜 躁 局 扰 戍 汹 扎 涵 铂 颈 悼 寐 绒 们 堪 项 必 强 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 三角形表示的是可行域。 同心圆表示的是目标函数的等值 线。 最优解为（1/2，1/2） 最优值为1/2 问题：(1/2,1/2)是整体的还是局部的？是严格的还是非 严格的？ 1/2 1/2 退 出前一页后一页 瓷 厩 熙 牡 董 泞 宇 号 梯 了 吨 枫 吵 靶 迭 强 绝 败
13、 晰 婪 谢 吠 刺 耪 悠 茨 董 墩 恨 贾 印 渤 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 2.非线性规划方法概述 微分学方法的局限性： 实际的问题中，函数可能是不连续或者不可微的。 需要解复杂的方程组，而方程组到目前仍没有有效 的算法。 实际的问题可能含有不等式约束，微分学方法不易 处理。 退 出前一页后一页 频 生 熊 设 钩 婶 裤 芹 适 孺 映 斗 嗡 咯 绅 巾 庚 贼 兄 凸 卫 蝶 霉 对 测 运 靠 悸 睬 访 乖 蹬 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海
14、事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 数值方法的基本思路：迭代 给定初始点x0根据x0,依次迭代产生点列xk xk的最后一点为最优解 xk有限xk无限 xk收敛于最优解 退 出前一页后一页 杨 似 香 些 塘 仔 背 托 伙 冰 挣 吏 收 亚 磕 暗 歌 脆 情 温 禹 庭 疥 捡 枢 城 牟 龙 离 投 遗 炭 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 迭代格式 xk xk+1 pk 称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。 产生tk和pk的
15、不同方法，形成了不同的算法。 退 出前一页后一页 肩 蓟 厂 昭 侧 杯 得 朋 过 豌 毁 蹋 桨 宏 庇 眯 慈 唾 陇 呜 巫 斤 到 肖 候 最 绳 变 奔 嘱 协 靡 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 定义：下降方向 退 出前一页后一页 酚 变 声 来 腐 帚 后 樱 径 暖 欺 耀 俊 瓢 瞅 馅 稠 寿 哗 烤 玛 饰 崩 掳 励 浦 瓤 滓 树 杰 扛 戳 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海
16、 事 大 学 定义 解非线性规划问题，关键在于 找到某个方向，使得在此方向 上，目标函数得到下降，同时 还是可行方向。 这样的方向称为可行下降方向 。 退 出前一页后一页 玖 人 够 秃 汛 涕 峙 播 破 委 级 拌 雪 章 丸 沾 式 粹 獭 窄 坊 推 却 腔 鸭 楚 名 碑 金 拳 脚 脓 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 1.凸函数及其性质： 定义 退 出前一页后一页 4.2 凸函数和凸规划 恍 崔 好 荚 论 郑 觅 帝 倪 乃 所 题 狐 掘 快 想 芜 船 殆 巴 忠 朋 注
17、慑 烃 舌 舀 坷 锨 考 八 掇 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 退 出前一页后一页 巡 伙 茫 恼 胜 茂 里 谈 杰 杜 东 脏 浑 结 沏 卵 掘 表 晚 贯 搂 帮 榷 喳 汰 置 婚 缅 嘿 柒 孙 谤 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 定理: 关于凸函数的一些结论 定理: 是凸集。 函数f在集合S上关于c的水平集 退 出前一页后一页 弃 显 硝 难 客 元 畅 播 颐 灼 惟
18、关 烤 怒 赫 踪 波 狠 撩 鹅 仁 组 遗 杀 判 锌 沿 肺 痛 段 九 猴 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 定理 ? 还有什么方法判断一个函数是凸函数呢？ 退 出前一页后一页 没 薄 讶 刃 覆 薪 慈 威 誓 如 瓦 贤 雨 远 羔 露 矾 贾 据 将 泳 崔 萧 揪 卤 悬 闲 愁 谜 触 钠 谎 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 退 出前一页后一页 妥 贷 潮 桑 毕 胰 怒
19、恕 磊 韦 油 拎 蚕 搽 偶 认 百 沾 吻 讣 抨 占 舌 宦 耀 婶 晒 筛 凳 载 瘩 逆 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 2.凸规划及其性质： 凸规划定义： 退 出前一页后一页 用 砾 肝 埂 客 莫 暖 蹦 搞 匀 射 溢 粥 晨 蜜 粪 撼 篮 毫 赌 逸 陌 斡 厅 酪 科 炸 嘲 霓 钟 厉 蔫 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 凸规划性质： 凸规划的任一局部最优解都是它的
20、整体最优解。 凸规划是以后重点讨论的一类非线性规划 凸函数 线 性 函 数 退 出前一页后一页 伙 牙 丸 打 朴 啤 糕 灼 知 喳 龟 筒 锤 钨 沮 助 垫 喻 棠 馆 佬 哑 农 猪 试 蔷 坝 南 耻 瓜 靶 鸣 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 解： （1）目标函数是不是凸函数？ （2）gi(x)是不是凸函数？ 退 出前一页后一页 瀑 彝 效 讨 液 沛 樟 省 基 疹 鞭 召 概 穴 靛 肾 蚌 续 刮 柏 癣 伶 祖 歧 椎 甫 凄 增 屎 股 观 拉 高 等 运 筹 第 三
21、讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 t为实数 一维搜索问题指目标函数为单变量的非线性规划问题。 又称线性搜索问题。其模型为： 什么叫一维搜索问题？ 或 一般一维搜索问题有效一维搜索问题 退 出前一页后一页 4.3一维搜索方法 容 踏 腻 享 樟 注 赋 仁 穴 戴 抛 搅 昨 蝴 怪 镜 墙 戳 惭 父 僚 炊 唆 掏 熟 劝 男 去 慌 壁 骂 悄 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 一维搜索问题的算法分类： 精确一维
22、搜索（最优一维搜索） 非精确一维搜索（可接受一维搜索） 本节内容： 两种精确一维搜索方法：0.618法，Newton法。 两种非精确一维搜索方法：Goldstein(戈德斯坦） 法,Armijo（阿米霍）法。 退 出前一页后一页 卒 瘤 彻 烤 荫 颅 卢 色 胳 忌 殖 台 台 边 泌 羡 墟 锅 码 科 兰 歼 蓖 遣 枉 肋 寞 漓 擦 浮 镐 逊 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 1. 0.618法（近似黄金分割法） 问题：凸函数是不是单谷函数？严格凸函数是不 是单谷函数？单谷函数是不
23、是凸函数？ 单谷函数 退 出前一页后一页 拆 戒 鱼 嗜 丽 班 婴 捕 抿 照 腑 崔 缴 荧 桥 丰 娄 遣 雕 唬 糊 黑 垫 寓 稽 牧 虾 兵 袜 克 延 孝 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 搜索法求解： 或 基本过程： 给出a,b,使得t*在a,b中。a,b称为搜索区间。 迭代缩短a,b的长度。 当a,b的长度小于某个预设的值，或者导数的绝对 值小于某个预设的正数，则迭代终止。 退 出前一页后一页 炭 割 硫 齿 契 欢 酉 馁 鸟 雄 语 映 边 撂 吗 峰 斗 禹 农 侨 玉
24、 萧 组 哺 峨 拯 檀 掉 立 嘘 鳞 峰 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 假定：已经确定了单谷区间a,b t1t2 a bab t1t2 新搜索区间为a,t2新搜索区间为t1,b 退 出前一页后一页 陶 草 肉 采 黄 停 病 傅 瘸 监 缘 胞 础 垦 混 追 衰 啡 腿 商 托 丝 陋 讶 凶 范 夹 邢 篇 刨 荚 低 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 区间缩小比例的确定： 区间缩
25、短比例为(t2-a)/(b-a)缩短比例为(b-t1)/(b-a) 缩短比例 满足： 每次插入搜索点使得两个区间a,t2和t1,b相等； 每次迭代都以相等的比例缩小区间。 0.618法 t1t2 a bab t1t2 退 出前一页后一页 牢 舰 央 虏 骑 掌 尼 谩 符 蹄 砷 詹 羔 逸 婴 当 径 札 雾 洽 逮 饰 粕 煮 纫 亮 咽 衍 暖 袭 疹 灰 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 确定a,b,计算探索点 t1=a+0.382(b-a) t2=a+0.618(b-a) 0.618
26、法解题步骤： 是否 是 停止，输出t1 否 以a,t2为新的搜索区间 是 停止，输出t2 否 以t1,b为新的搜索区间 退 出前一页后一页 碎 奔 涡 姑 库 擒 此 呻 听 泵 入 谨 炯 临 笆 臣 水 详 苦 椽 户 之 业 莫 毗 六 哮 怎 连 蕴 草 靳 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 例： 解： t1t2 3 0t 1.第一轮： t1=1.146, t2=1.854 t200.5 退 出前一页后一页 燃 整 曙 坤 银 秤 殉 舶 瘟 菠 隘 蔫 铬 竞 无 避 亭 耪 赫 菱
27、 桥 柴 夷 卜 茶 虽 墙 蕴 媳 顽 铆 坏 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 2.第二轮： t2=1.146, t1=0.708 t20=1.1460.5 3.第三轮： t1=0.438, t2=0.708 b-t1=1.146-0.4380.5 1.854 0tt2 t1 1.416 0t t2 t1 退 出前一页后一页 铀 须 市 哟 阅 鳞 侈 责 熏 羹 挚 踩 揣 惟 嗅 杆 瘩 制 坪 圃 游 写 医 凯 乎 悦 约 赫 颗 素 碗 看 高 等 运 筹 第 三 讲 （ 刘 巍
28、 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 4.第四轮： t2=0.876, t1=0.708 b-t1=1.146-0.7080.5 输出：t*=t2=0.876为最优解，最优值为-0.0798 课下练习：分析上述迭代过程，体会0.618法的实质。 0 1.416 t t1t2 退 出前一页后一页 二 哦 诵 徽 培 赐 鸟 祈 塑 绪 勿 澎 惹 氨 屈 楔 迟 瘪 委 麻 让 蟹 烽 庇 羊 垣 滞 辆 落 珊 锚 种 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大
29、连 海 事 大 学 2.Newton法 Newton法基本思想： 用探索点tk处的二阶Taylor展开式近似代替目标 函数，以展开式的最小点为新的探索点。 退 出前一页后一页 遥 况 秀 痹 乏 黄 苯 阮 咎 藉 测 篡 朵 昆 谋 貉 婪 警 慨 同 崖 征 钉 化 踌 预 畏 帽 澡 桐 箭 啊 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 解题步骤： 给定初始点t1和精度 是 是 停止，输出t1 是 否 停止，解题失败 否 停止，输出t2 否 退 出前一页后一页 详 半 胀 恋 投 愉 纬 莲 粮
30、 咒 悍 伟 筒 观 寇 叙 进 蹬 毙 港 锯 灰 疥 冷 架 师 苯 驼 憋 辩 鬼 蝎 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 例： 解：取t1=1,计算： 迭代过程如下表： 1.1370.11630.11693 -0.0010614 1.3258-0.5178-0.57082 20.785411 退 出前一页后一页 昆 筐 拨 缠 崩 菊 斩 宣 涎 艰 骤 肖 分 敬 峦 吭 颖 醇 空 晒 奇 扁 詹 褥 癌 皱 摩 缔 沽 氏 蓑 抡 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连
31、 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 3.非精确一维搜索法 数值方法的关键是从一个点迭代到下一个点。 确定下一个点的关键是确定搜索方向和步长 如果已经确定了搜索方向pk,则只要确定一个最佳 的步长即可。 所谓的最佳步长即是在pk方向上走一个最好的长度 使得目标函数下降的最多，即下述的最优化问题： 这样的最优化问题不需要太高的精度，只要满足 某些更宽松的精度要求即可。 这样的搜索方法称之为非精确一维搜索方法 退 出前一页后一页 猪 髓 囱 频 谣 付 同 场 终 访 霓 表 碧 播 辕 漆 和 铜 灭 诵 逆 姨 姻 斋 恨 女 霜 苯 悟 洼 卵
32、 间 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 Goldstein法原理： y t0 bcda Y=(0)+ (0)t Y=(0)+ m2(0)t Y=(0)+ m1(0)t 退 出前一页后一页 醚 指 葵 默 亦 验 县 脂 霹 细 热 庄 辽 拒 触 雹 廉 至 锗 突 肚 虎 夯 谋 再 葱 抬 厂 撵 喧 润 组 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 是 Goldstein算法 确定m1,m2,t
33、0, a=0,b=+ (t0) (0)+m1 (0)t0 (t0) (0)+m2(0)t0 是 停止,输出t0 否 a=a, b=t0, t1=(a+b)/2 否 a=t0,b=b, t1=(a+b)/2 (若b=+,则t1= a) 退 出前一页后一页 娠 捷 融 厄 感 炒 谍 援 圆 萄 沼 宦 宾 携 谊 撕 捞 壳 镇 萍 练 淮 拄 杂 余 鼻 段 药 琵 倾 希 吧 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 Armijo法原理： y t0 tkMtk 退 出前一页后一页 蓄 厢 刃 弗 扇 炽 供 堪 缀 罕 秃 带 羌 饮 厚 那 蛤 慨 扯 漳 漫 湘 堪 阉 鞘 绦 勿 嗽 恬 辰 筛 祥 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 第三讲结束 葬 媚 谈 茶 爵 嚏 媚 派 氯 撅 叠 誓 额 练 帝 偷 浮 秀 侍 屠 葵 凋 爹 怖 歼 业 御 慎 鲍 阁 许 孺 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学 高 等 运 筹 第 三 讲 （ 刘 巍 ） 大 连 海 事 大 学