工程优化课件.pdf

工程优化课件 穆学文 2010 91 工程优化方法工程优化方法 硕士研究生课程硕士研究生课程 理学院数学系 穆学文理学院数学系 穆学文 E mail mxw1334 教材及其参考书目教材及其参考书目 计划学时数 计划学时数 46学时 教材 学时 教材 1 最优化计算方法最优化计算方法 陈开周 西安电子科技大学出版社 陈开周 西安电子科技大学出版社 1985 2 最优化理论与算法最优化理论与算法 陈宝林陈宝林 清华大学出版社 清华大学出版社 2003 主要参考书目 主要参考书目 1 最优化理论与方法最优化理论与方法 袁亚湘袁亚湘 孙文渝孙文渝 科学出版社 科学出版社 1997 2 最优化方法最优化方法 唐焕文唐焕文 秦学志秦学志 大连理工大学出版社 大连理工大学出版社 1985 3 非线性规划数值方法非线性规划数值方法 袁亚湘 上海科学技术出版社 袁亚湘 上海科学技术出版社 1993 考核方法考核方法 到课率到课率 作业作业 期末考试期末考试 课件下载地址 邮箱 课件下载地址 邮箱 xdmuxw 密码 密码 xd123456 背景知识背景知识 基本概念及其应用基本概念及其应用 最优化问题举例最优化问题举例 优化问题的数学模型及其分类优化问题的数学模型及其分类 最优解与极值点最优解与极值点 常用的数学软件常用的数学软件 第一章 基础知识第一章 基础知识 1背景知识背景知识 运筹学理论的一部分运筹学理论的一部分 最早起源于中国古代最早起源于中国古代 公元前公元前6世纪孙武所著的 孙子兵法 世纪孙武所著的 孙子兵法 孙膑孙膑 斗马术斗马术 田忌与齐王赛马 博弈论 田忌与齐王赛马 博弈论 运筹帷幄之中 决胜千里之外运筹帷幄之中 决胜千里之外 这千古名句也 可以说是对张良运筹思想的赞颂和褒奖 这千古名句也 可以说是对张良运筹思想的赞颂和褒奖 国外起源与发展国外起源与发展 1896年 年 V Pareto首次从数学角度提出多目标优化问 题 引进了 首次从数学角度提出多目标优化问 题 引进了Pareto最优的概念 最优的概念 1935 38年 英国为了正确地运用新研制的雷达系统来对 付德国飞机的空袭 在皇家空军中组织了一批科学家 进行新战术试验和战术效率评价的研究 并取得了满意 的效果 他们把自己从事的这种工作命名为 年 英国为了正确地运用新研制的雷达系统来对 付德国飞机的空袭 在皇家空军中组织了一批科学家 进行新战术试验和战术效率评价的研究 并取得了满意 的效果 他们把自己从事的这种工作命名为 Operational Research 运筹学 或直译为作战研究运筹学 或直译为作战研究 1939年 苏联的 年 苏联的 总结了他 对生产组织的研究 写了 生产组织与计划中的数学方 法 一书 是线性规划应用于工业生产问题的经典著作 总结了他 对生产组织的研究 写了 生产组织与计划中的数学方 法 一书 是线性规划应用于工业生产问题的经典著作 1947年年 G B Dantzig提出了单纯形方法后 线性规划便 迅速形成为一个独立的分支 并逐级发展起来 提出了单纯形方法后 线性规划便 迅速形成为一个独立的分支 并逐级发展起来 背景知识 续 背景知识 续 工程优化课件 穆学文 2010 92 英国运筹学会英国运筹学会1948年成立 年成立 1948 53年是运筹学俱乐部 年是运筹学俱乐部 1953年年11月起改名为学会 月起改名为学会 二次大战胜利后 美英各国不但在军事部门继续保留了 运筹学的研究核心 而且在研究人员 组织的配备及研 究范围和水平上 都得到了进一步的扩大和发展 同时 运筹学方法也向政府和工业等部门扩展 二次大战胜利后 美英各国不但在军事部门继续保留了 运筹学的研究核心 而且在研究人员 组织的配备及研 究范围和水平上 都得到了进一步的扩大和发展 同时 运筹学方法也向政府和工业等部门扩展 1951年出版了新版 年出版了新版 1946年的原版是保密的 年的原版是保密的 1948年才 撤销保密 的 年才 撤销保密 的P M Morse和和G E Kimball的 运筹学方法 的 运筹学方法 Methods of Operations Research 这是二战结束后 对战时整个运筹学工作做系统的专业叙述的一本著作 这是二战结束后 对战时整个运筹学工作做系统的专业叙述的一本著作 1951年年 H W Kuhn与与A W Tucker提出了提出了Kuhn Tucker条 件 标志着非线性规划理论的初步形成 条 件 标志着非线性规划理论的初步形成 背景知识 续 背景知识 续 1952年年5月美国运筹学会成立 并创刊 月美国运筹学会成立 并创刊 Operations Research 1953年年 R Bellman提出动态规划的名称 并阐述了最优 化原理 提出动态规划的名称 并阐述了最优 化原理 1954年 年 D R Dantzig等研究旅行推销员问题时提出了分 解的思想 成为整数规划中两大方法 等研究旅行推销员问题时提出了分 解的思想 成为整数规划中两大方法 割平面法与分枝 定界法的萌芽 割平面法与分枝 定界法的萌芽 1955年年 G Dantzig首先考虑出现随机变量的线性规划问 题 这是最早提出的随机规划中的有补偿二阶段问题 首先考虑出现随机变量的线性规划问 题 这是最早提出的随机规划中的有补偿二阶段问题 1956年年 L R Ford Jr 与与 D R Fulkerson提出并解决了网 络最大流问题 加强了图论与线性规划的联系 促进了 优化理论的研究 提出并解决了网 络最大流问题 加强了图论与线性规划的联系 促进了 优化理论的研究 背景知识 续 背景知识 续 1959年年1月月1日 国际运筹学会联合会日 国际运筹学会联合会 1FORS 正式宣告 成立 当时的联合会只包括英 美 法三个国家的运筹 学会 首任 正式宣告 成立 当时的联合会只包括英 美 法三个国家的运筹 学会 首任 1959 61年 主席 当时称为秘书 到年 主席 当时称为秘书 到1968 年第四届时才改称主席 为英国的年第四届时才改称主席 为英国的Charles Goodeve 背景知识 续 背景知识 续 运筹学理论在中国的研究与发展运筹学理论在中国的研究与发展 1957年 经中国科学院力学研究所所长钱学森的倡导 在该所成立了由许国志领导的国内第一个运筹学研究组 年 经中国科学院力学研究所所长钱学森的倡导 在该所成立了由许国志领导的国内第一个运筹学研究组 后成室后成室 刘源张 周华章 桂湘云等是该组最早的一 批研究人员 从此在我国开始了现代运筹学的研究 当 年秋季 又有大学毕业生顾基发 董泽清 徐映波 陈 锡康 郭绍僖 李秉全等分配进入该组 刘源张 周华章 桂湘云等是该组最早的一 批研究人员 从此在我国开始了现代运筹学的研究 当 年秋季 又有大学毕业生顾基发 董泽清 徐映波 陈 锡康 郭绍僖 李秉全等分配进入该组 1958年 中国科学院数学研究所所长华罗庚率领广大研 究人员 包括吴文俊 越民义 万哲先 王元等在内 也开展了运筹学应用课题的研究 并影响和带动了全国 范围内各部门 各高校的运筹学应用和推广工作 运输 和农业等部门的 年 中国科学院数学研究所所长华罗庚率领广大研 究人员 包括吴文俊 越民义 万哲先 王元等在内 也开展了运筹学应用课题的研究 并影响和带动了全国 范围内各部门 各高校的运筹学应用和推广工作 运输 和农业等部门的 图上作业法图上作业法 打麦场设计打麦场设计 中国 邮递员问题 中国 邮递员问题 是典型的成果 是典型的成果 背景知识 续 背景知识 续 1959年年2月 山东大学在数学系中设置了国内最早的一 个运筹学专门化 由谢力同与郑汉鼎执教 自当年暑假 开始 每年都有运筹学方向的学生毕业 为我国运筹学 事业的发展作出了重要贡献 月 山东大学在数学系中设置了国内最早的一 个运筹学专门化 由谢力同与郑汉鼎执教 自当年暑假 开始 每年都有运筹学方向的学生毕业 为我国运筹学 事业的发展作出了重要贡献 1959年 中国科学院数学研究所成立了运筹学研究室 研究人员都由所内其它室组调入 孙克定任研究室主任 该室最早的一批研究人员有排队论组的越民义 吴方 徐光煇 韩继业 对策论组的吴文俊 江加禾 施闺芳 数学规划组的朱永津 应玫茜 马仲蕃 凌开诚等 与 此同时 全国范围内很多高校也有大批教师转入运筹学 领域 年 中国科学院数学研究所成立了运筹学研究室 研究人员都由所内其它室组调入 孙克定任研究室主任 该室最早的一批研究人员有排队论组的越民义 吴方 徐光煇 韩继业 对策论组的吴文俊 江加禾 施闺芳 数学规划组的朱永津 应玫茜 马仲蕃 凌开诚等 与 此同时 全国范围内很多高校也有大批教师转入运筹学 领域 背景知识 续 背景知识 续 1965年起 华罗庚和他的小分队在全国工业部门开始普 及推广统筹法的群众运动 在此后的二十年中 为普及 推广双法 统筹法与从 年起 华罗庚和他的小分队在全国工业部门开始普 及推广统筹法的群众运动 在此后的二十年中 为普及 推广双法 统筹法与从1970年开始普及推广的优选法 他们走访了全国 年开始普及推广的优选法 他们走访了全国23个省市中几百个城市的几千个工厂 并向数百万人开设讲座开展工作 取得了巨大的社会效 益和经济效益 个省市中几百个城市的几千个工厂 并向数百万人开设讲座开展工作 取得了巨大的社会效 益和经济效益 1965年华罗庚 统筹方法平话及其补充 一书由中国工 业出版社出版 年华罗庚 统筹方法平话及其补充 一书由中国工 业出版社出版 1970年起 华罗庚和他的小分队开始在全国范围内普及 推广优选法的群众运动 从此 统筹与优选双法变得家 喻户晓 双法的普及推广也取得了极为可观的社会 经 济效益 年起 华罗庚和他的小分队开始在全国范围内普及 推广优选法的群众运动 从此 统筹与优选双法变得家 喻户晓 双法的普及推广也取得了极为可观的社会 经 济效益 1971年华罗庚 优选法平话及其补充 一书由国防工业 出版社出版 年华罗庚 优选法平话及其补充 一书由国防工业 出版社出版 背景知识 续 背景知识 续 工程优化课件 穆学文 2010 93 1980年年4月月22 26日在山东济南 召开了中国数学会运筹 学会成立暨第一届代表大会 中国运筹学倡导者之一 中国科学院副院长华罗庚主持了会议 有来自各地科研 机构 高等院校 军事部门 工交企业等有关单位的 日在山东济南 召开了中国数学会运筹 学会成立暨第一届代表大会 中国运筹学倡导者之一 中国科学院副院长华罗庚主持了会议 有来自各地科研 机构 高等院校 军事部门 工交企业等有关单位的82 名代表出席 华罗庚在大会开幕式与闭幕式上均发表了 讲话 回顾了他在全国范围普及推广 名代表出席 华罗庚在大会开幕式与闭幕式上均发表了 讲话 回顾了他在全国范围普及推广 双法双法 的经验和成 果 勉励大家以克敌攻坚的进取精神积极开展运筹学研 究 会议作了 的经验和成 果 勉励大家以克敌攻坚的进取精神积极开展运筹学研 究 会议作了12个专题学术报告和个人成果的几十个分 组报告 中国数学会理事长华罗庚被推选兼任运筹学会 理事长 越民义 许国志 余潜修为副理事长 桂湘云 为秘书长 推选常务理事 个专题学术报告和个人成果的几十个分 组报告 中国数学会理事长华罗庚被推选兼任运筹学会 理事长 越民义 许国志 余潜修为副理事长 桂湘云 为秘书长 推选常务理事11名 理事名 理事42名 会议决定学 会挂靠在中科院应用数学所 名 会议决定学 会挂靠在中科院应用数学所 背景知识 续 背景知识 续 2基本概念及其应用基本概念及其应用 最优化技术是一门较新的学科分支 它是在本 世纪五十年代初在电子计算机广泛应用的推动下才 得到迅速发展 并成为一门直到目前仍然十分活跃 的新兴学科 最优化技术是一门较新的学科分支 它是在本 世纪五十年代初在电子计算机广泛应用的推动下才 得到迅速发展 并成为一门直到目前仍然十分活跃 的新兴学科 最优化所研究的问题是在众多的可行 方案中怎样选择最合理的一种以达到最优目标 最优化所研究的问题是在众多的可行 方案中怎样选择最合理的一种以达到最优目标 将达到最优目标的方案称为将达到最优目标的方案称为最优方案最优方案或或最优决 策 最优决 策 搜寻最优方案的方法称为 搜寻最优方案的方法称为最优化方法最优化方法 关于最 优化方法的数学理论称为 关于最 优化方法的数学理论称为最优化理论最优化理论 最优化问题至少有两要素 一是可能的 方案 二是要追求的目标 后者是前者的函 数 如果第一要素与时间无关就称为静态最 优化问题 否则称为动态最优化问题 本科程专门讲授静态最优化问题 最优化问题至少有两要素 一是可能的 方案 二是要追求的目标 后者是前者的函 数 如果第一要素与时间无关就称为静态最 优化问题 否则称为动态最优化问题 本科程专门讲授静态最优化问题 最优化技术应用范围十分广泛 在我们日常 生活中 在工农业生产 社会经济 国防 航空 航天工业中处处可见其用途 如结构最优设计 电子器件最优设计 光学仪器最优设计 化工工 程最优设计 标腔最优配方 运输方案 机器最 优配备 油田开发 水库调度 饲料最优配方 食品结构优化等等 最优化技术应用范围十分广泛 在我们日常 生活中 在工农业生产 社会经济 国防 航空 航天工业中处处可见其用途 如结构最优设计 电子器件最优设计 光学仪器最优设计 化工工 程最优设计 标腔最优配方 运输方案 机器最 优配备 油田开发 水库调度 饲料最优配方 食品结构优化等等 最优化技术工作被分成两个方面 一是由实 际生产或科技问题形成最优化的数学模型 二是 对所形成的数学问题进行数学加工和求解 对于 第二方面的工作 目前已有一些较系统成熟的资 料 但对于第一方面工作即如何由实际问题抽象 出数学模型 目前很少有系统的资料 而这一工 作在应用最优化技术解决实际问题时是十分关键 的基础 没有这一工作 最优化技术将成为无水 之源 难以健康发展 最优化技术工作被分成两个方面 一是由实 际生产或科技问题形成最优化的数学模型 二是 对所形成的数学问题进行数学加工和求解 对于 第二方面的工作 目前已有一些较系统成熟的资 料 但对于第一方面工作即如何由实际问题抽象 出数学模型 目前很少有系统的资料 而这一工 作在应用最优化技术解决实际问题时是十分关键 的基础 没有这一工作 最优化技术将成为无水 之源 难以健康发展 因此 我们在学习本科程时要尽可能了 解如何由实际问题形成最优化的数学模型 为了便于大家今后在处理实际问题时建立最优 化数学模型 下面我们先把有关数学模型的一 些事项作一些说明 数学模型 因此 我们在学习本科程时要尽可能了 解如何由实际问题形成最优化的数学模型 为了便于大家今后在处理实际问题时建立最优 化数学模型 下面我们先把有关数学模型的一 些事项作一些说明 数学模型 对现实事物或问题的数学抽象或描述对现实事物或问题的数学抽象或描述 工程优化课件 穆学文 2010 94 建立数学模型时要尽可能简单 而且要能 完整地描述所研究的系统 但要注意到过于简 单的数学模型所得到的结果可能不符合实际情 况 而过于详细复杂的模型又给分析计算带来 困难 因此 具体建立怎样的数学模型需要丰 富的经验和熟练的技巧 即使在建立了问题的 数学模型之后 通常也必须对模型进行必要的 数学简化以便于分析 计算 建立数学模型时要尽可能简单 而且要能 完整地描述所研究的系统 但要注意到过于简 单的数学模型所得到的结果可能不符合实际情 况 而过于详细复杂的模型又给分析计算带来 困难 因此 具体建立怎样的数学模型需要丰 富的经验和熟练的技巧 即使在建立了问题的 数学模型之后 通常也必须对模型进行必要的 数学简化以便于分析 计算 建立最优化问题数学模型的三要素 建立最优化问题数学模型的三要素 1 决策变量和参数 决策变量是由数学模型 的解确定的未知数 参数表示系统的控制变量 有 确定性的也有随机性的 决策变量和参数 决策变量是由数学模型 的解确定的未知数 参数表示系统的控制变量 有 确定性的也有随机性的 2 约束或限制条件 由于现实系统的客观物 质条件限制 模型必须包括把决策变量限制在它们 可行值之内的约束条件 而这通常是用约束的数学 函数形式来表示的 约束或限制条件 由于现实系统的客观物 质条件限制 模型必须包括把决策变量限制在它们 可行值之内的约束条件 而这通常是用约束的数学 函数形式来表示的 一般的模型简化工作包括以下几类 一般的模型简化工作包括以下几类 1 将离散变量转化为连续变量 将离散变量转化为连续变量 2 将非线性函数线性化 将非线性函数线性化 3 删除一些非主要约束条件 删除一些非主要约束条件 3 目标函数 这是作为系统决策变量的 一个数学函数来衡量系统的效率 即系统追 求的目标 目标函数 这是作为系统决策变量的 一个数学函数来衡量系统的效率 即系统追 求的目标 2 最优化问题举例最优化问题举例 最优化在运输 自动控制 机械设计 采 矿冶金 经济管理等科学技术各领域中有广 泛应用 下面举几个实例 最优化在运输 自动控制 机械设计 采 矿冶金 经济管理等科学技术各领域中有广 泛应用 下面举几个实例 例例1 把半径为把半径为1的实心金属球熔化后 铸成一个 实心圆柱体 问圆柱体取什么尺寸才能使它的表 面积最小 的实心金属球熔化后 铸成一个 实心圆柱体 问圆柱体取什么尺寸才能使它的表 面积最小 解解 1 决定圆柱体表面积大小有两个决策变量 圆柱体底面半径 决定圆柱体表面积大小有两个决策变量 圆柱体底面半径 r 高 高 h 2 问题的约束条件是所铸圆柱体重量与球重 相等 即 问题的约束条件是所铸圆柱体重量与球重 相等 即 23 4 3 rhR 即即 2 4 0 3 r h 问题追求的目标是圆柱体表面积最小 即问题追求的目标是圆柱体表面积最小 即 2 22rhr 2 2 min22 4 0 3 rhr str s t Subject to 固定固定 minimize min 则得原问题的数学模型 则得原问题的数学模型 工程优化课件 穆学文 2010 95 利用在高等数学中所学的利用在高等数学中所学的Lagrange乘子 法可求解本问题 乘子 法可求解本问题 分别对分别对r h 求偏导数求偏导数 并令 其等于零 并令 其等于零 有有 22 4 22 3 L r hrhrr h 2 2 2420 20 4 0 3 L hrrh r L rr h L r h 2hr 33 22 2 33 rh 此时圆柱体的表面积为此时圆柱体的表面积为 2 3 2 6 3 例例2 多参数曲线拟合问题 已知两个物理量 多参数曲线拟合问题 已知两个物理量 x 和和 y 之间的依赖关系为之间的依赖关系为 其中和是待定参数其中和是待定参数 为确定这些参数为确定这些参数 对对x y 测得测得m 个实验点个实验点 试将确定参数的问题表示成最优化问题试将确定参数的问题表示成最优化问题 2 1 4 3 5 1ln 1 exp a ya xa a a 1234 aaaa5 a 1 12 2 mm x yx yxy 将测量点沿垂线方向到曲线的距离的平方和作 为这种 将测量点沿垂线方向到曲线的距离的平方和作 为这种 偏差偏差 的度量的度量 即即 x y 解解 很显然对参数和任意给定的一 组数值 很显然对参数和任意给定的一 组数值 就由上式确定了就由上式确定了 y 关于关于 x 的一个函数关 系式 的一个函数关 系式 在几何上它对应一条曲线在几何上它对应一条曲线 这条曲线不一 定通过那 这条曲线不一 定通过那m个测量点个测量点 而要产生而要产生 偏差偏差 1234 a a a a 5 a 2 2 1 1 4 3 5 1ln 1exp m i i i a Sya xa a a 显然偏差显然偏差S越小越小 曲线就拟合得越好曲线就拟合得越好 说明 参数值就选择得越好 从而我们的问题就转 化为 说明 参数值就选择得越好 从而我们的问题就转 化为5维无约束最优化问题 即 维无约束最优化问题 即 2 2 1 1 4 3 5 min 1ln 1 exp m i i i a ya xx a a 例例3 旅游售货员问题 旅游售货员问题 旅游线路安排 预定景点走且只走一次 路上时间最短 旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路配送线路 货郎担问题 送货地到达一次 总路程最短 货郎担问题 送货地到达一次 总路程最短 旅行团从出发要遍游城市 已知从到的旅费为 问应如何安排行 程使总费用最小 旅行团从出发要遍游城市 已知从到的旅费为 问应如何安排行 程使总费用最小 0 v 12 n v vv j v i v ij c 模型 模型 模型 模型 变量变量 是否从是否从 i 第个城市到第第个城市到第 j 个城市个城市 约束约束 每个城市只能到达一次 离开一次每个城市只能到达一次 离开一次 1 0 ij x 1 0 ij x 工程优化课件 穆学文 2010 96 目标目标 总费用最小总费用最小 00 nn ijij ij c x 00 0 0 min 1 1 2 1 1 2 1 0 1 2 1 2 nn ijij ij n ij j n ij i ij c x xin stxjn xin jn 例例4 混合饲料配合 以最低成本确定满 足动物所需营养的最优混合饲料 设每天需 要混合饲料的批量为 混合饲料配合 以最低成本确定满 足动物所需营养的最优混合饲料 设每天需 要混合饲料的批量为100磅 这份饲料必须 含 至少 磅 这份饲料必须 含 至少0 8 而不超过而不超过1 2 的钙的钙 至少至少22 的蛋白质的蛋白质 至多至多5 的粗纤维 假定主要配料 包括石灰石 谷物 大豆粉 这些配料的主 要营养成分为 的粗纤维 假定主要配料 包括石灰石 谷物 大豆粉 这些配料的主 要营养成分为 配料 每磅配料中的营养含量 钙蛋白质纤维 每磅成本 元 石灰石 谷物 大豆粉 0 380 0 00 0 00 0 001 0 09 0 02 0 002 0 50 0 08 0 0164 0 0463 0 1250 123 123 123 123 23 23 123 min0 01640 04630 1250 100 0 3800 0010 0020 012 100 0 3800 0010 0020 008 100 0 090 500 22 100 0 020 080 05 100 0 0 0 xxx stxxx xxx xxx xx xx xxx 解解 根据前面介绍的建模要素得出此问题的数学模 型如下 根据前面介绍的建模要素得出此问题的数学模 型如下 设是生产设是生产100磅混合饲料所须的 石灰石 谷物 大豆粉的量 磅 磅混合饲料所须的 石灰石 谷物 大豆粉的量 磅 123 x xx 例例5 背包问题 背包问题 邮递包裹 把形状可变的包裹用尽量少的车辆运走 邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品 旅行背包 容量一定的背包里装尽可能的多的物品 装箱问题装箱问题 某人出国留学打点行李 现有三个旅行包 容积大小分别为 某人出国留学打点行李 现有三个旅行包 容积大小分别为1000毫升 毫升 1500毫升和毫升和2000毫 升 根据需要列出需带物品清单 其中一些物 品是必带物品共有 毫 升 根据需要列出需带物品清单 其中一些物 品是必带物品共有7件 其体积大小分别为件 其体积大小分别为400 300 150 250 450 760 190 单位毫升 尚有 单位毫升 尚有10件可带可不带物品 如果不带将在目的 地购买 通过网络查询可以得知其在目的地的 价格 单位美元 这些物品的容量及价格分 别见下表 试给出一个合理的安排方案把物品 放在三个旅行包里 件可带可不带物品 如果不带将在目的 地购买 通过网络查询可以得知其在目的地的 价格 单位美元 这些物品的容量及价格分 别见下表 试给出一个合理的安排方案把物品 放在三个旅行包里 工程优化课件 穆学文 2010 97 物品物品12345678910 体积体积200350500430320120700420250100 价格价格1545100705075200902030 问题分析 问题分析 变量变量 对每个物品要确定是否带同时要确定 放在哪个包裹里 如果增加一个虚拟的包裹 把不带的物品放在里面 则问题就转化为确 定每个物品放在哪个包裹里 如果直接设变 量为每个物品放在包裹的编号 则每个包裹 所含物品的总容量就很难写成变量的函数 为此我们设变量为第 对每个物品要确定是否带同时要确定 放在哪个包裹里 如果增加一个虚拟的包裹 把不带的物品放在里面 则问题就转化为确 定每个物品放在哪个包裹里 如果直接设变 量为每个物品放在包裹的编号 则每个包裹 所含物品的总容量就很难写成变量的函数 为此我们设变量为第 i 个物品是否放在第个物品是否放在第j个 包裹中 个 包裹中 1 0 1 2 17 1 2 3 ij xij 约束 包裹容量限制 必带物品限制 选带物品限制 约束 包裹容量限制 必带物品限制 选带物品限制 17 1 1 2 3 iijj i c xrj 3 1 1 1 2 7 ij j xi 00 nn ijij ij c x 目标函数目标函数 未带物品购买费用最小未带物品购买费用最小 3 1 1 8 9 17 ij j xi 173 81 1 iij ij px 1 0 ij x 17 1 1 2 3 iijj i c xrj 3 1 1 1 2 7 ij j xi 3 1 1 8 2 17 ij j xi 1 0 1 2 17 1 2 3 ij xij 模型 模型 3 优化问题的数学模型及其分类优化问题的数学模型及其分类 min n x R f x 3 1 根据优化问题的不同特点分类根据优化问题的不同特点分类 无约束最优化问题 无约束最优化问题 n维欧氏空间 向量 向量变量实值函数 维欧氏空间 向量 向量变量实值函数 1 n fRR n R 12 n n xR xx xx 工程优化课件 穆学文 2010 98 约束最优化问题约束最优化问题 min 0 1 2 0 1 2 i j f x stgxim hxjl 其中均为向量其中均为向量 x 的实值连续 函数 有二阶连续偏导数 的实值连续 函数 有二阶连续偏导数 ij fgh 采用向量表示法即为 采用向量表示法即为 其中其中 这就是最优化问题的一般形式 又称非线性规划 这就是最优化问题的一般形式 又称非线性规划 min 0 0 f x stG x H x 目标函数 不等式约束 等式约束 12 12 m l G xgxgxgx H xhxhxhx 定义 称满足所有约束条件的向量定义 称满足所有约束条件的向量x为容许解或可 行解 容许点的集合称为容许集或可行集 在容许集中找一点 使目标函数在该点 取最小值 即满足 的过程即为最优化的求解过程 称为问题的最优解 称为最优值 称为最优点 为容许解或可 行解 容许点的集合称为容许集或可行集 在容许集中找一点 使目标函数在该点 取最小值 即满足 的过程即为最优化的求解过程 称为问题的最优解 称为最优值 称为最优点 x f x min 0 0f xf xstS xH x x f x xf x 最优化问题模型统一化 在上述最优化问题的一般式中只是取极小值 如果遇到极大化问题 只须将目标函数反号就可 以化为求极小的问题 最优化问题模型统一化 在上述最优化问题的一般式中只是取极小值 如果遇到极大化问题 只须将目标函数反号就可 以化为求极小的问题 f x f x f x f x f x 4 因此后面只研究最小 化问题 因此后面只研究最小 化问题 如果约束条件中有 小于等于 的 即 则转化为 另外 等式约束可 以由下面两个不等式来代替 因而最优化问题的一般形式又可写成 如果约束条件中有 小于等于 的 即 则转化为 另外 等式约束可 以由下面两个不等式来代替 因而最优化问题的一般形式又可写成 0 G x 0G x 0H x 0 0H xH x min 0 f x stG x 可行域记为可行域记为 0Dx G x 3 2 根据函数的类型分类根据函数的类型分类 线性规划 目标函数和约束函数皆为线性函数 线性规划 目标函数和约束函数皆为线性函数 二次规划二次规划 凸二次规划 非凸的二次规划凸二次规划 非凸的二次规划 目标函数为二次函数 约束函数为线性函数目标函数为二次函数 约束函数为线性函数 非线性规划 目标函数不是一次或二次函数 或者约束函数不 全是线性函数 非线性规划 目标函数不是一次或二次函数 或者约束函数不 全是线性函数 工程优化课件 穆学文 2010 99 对于最优化问题一般可作如下分类 对于最优化问题一般可作如下分类 n 线性问题 无约束问题一维问题 非线性问题 维问题静态问题 最优化问题 线性规划 约束问题 非线性规划 无约束 动态问题 约束 一 极小点概念 一 极小点概念 f 例如 图中一元函数例如 图中一元函数 f 定义在 区间 定义在 区间 a b 上上 为严格局部极 小点 为非严格局部极小点 为严格局部极 小点 为非严格局部极小点 a 为全局严格极小点 为全局严格极小点 严格局部极小点 局部极小点 非严格局部极小点 极小点 严格全局极小点 全局极小点 非严格全局极小点 1 x 1 x 2 x 2 x 4 最优解与极值点最优解与极值点 ab o 定义定义1 对满足不等式的点对满足不等式的点x的集合 称为的邻域 记为 的集合 称为的邻域 记为 0 0 xx 0 x 00 0N xxxx 定义定义2 设若使 设若使 1 均有 则称为 均有 则称为 f 的非严格局部极小点 的非严格局部极小点 2 且且 有 则称为 有 则称为 f 的严格局部极小点的严格局部极小点 1 n fDRR 0 xD xN xD f xf x xN xD f xf x x x xx 定义定义3 设若使 设若使 1 均有 则称为 均有 则称为f 在在 D上的非严格全局极小点 上的非严格全局极小点 2 有 则称为 有 则称为 f 在在 D 上的严格全局极小点上的严格全局极小点 xD xD f xf x xD xx x x f xf x 1 n fDRR 由定义可知有如下两个定理由定义可知有如下两个定理 定理定理1 最优化问题的任意全局极小点必为局部 极小值点 最优化问题的任意全局极小点必为局部 极小值点 定理定理2 若为定义在上 的连续函数 若为定义在上 的连续函数 则 则 1 以上问题的可行解的集合 以上问题的可行解的集合D为闭集 为闭集 2 以上问题的最优解的集合为闭集 以上问题的最优解的集合为闭集 1 2 i f x g x im n R min 0 1 2 i f x stgxim 对如下问题对如下问题 5 常用数学软件常用数学软件 Matlab Maple Mathematics Lingo 工程优化课件 穆学文 2010 910 Matlab 应用范围很广 工具箱不断在扩展应用范围很广 工具箱不断在扩展 Mathematic Maple 具有强大的符号计算功能 主要用于数学方面具有强大的符号计算功能 主要用于数学方面 Lingo 主要对优化问题 特别是整数规划问题 十分有效主要对优化问题 特别是整数规划问题 十分有效 西安电子科技大学 穆学文 20101 工程优化方法工程优化方法工程优化方法工程优化方法 硕士研究生课程硕士研究生课程硕士研究生课程硕士研究生课程 理学院数学系 穆学文理学院数学系 穆学文 E mail mxw1334 下载课件邮箱 下载课件邮箱 mxw 1334 密码 密码 654321 多元函数及其导数多元函数及其导数 等高线等高线 二元函数二元函数 多元函数的极值多元函数的极值 凸集 凸函数和凸规划凸集 凸函数和凸规划 重要的不等式重要的不等式 下降迭代算法及其收敛性下降迭代算法及其收敛性 第二章 基础知识第二章 基础知识 1 1 多元函数的可微性和梯度多元函数的可微性和梯度 1 多元函数及其导数多元函数及其导数 以后我们研究的最优化问题涉及的均是多元 函数 并要求它们的可微性 下面先给出定义 以后我们研究的最优化问题涉及的均是多元 函数 并要求它们的可微性 下面先给出定义 1 n f DRR 1 n f DRR n RnR 表示是定义在中区域 上的 元实值函数 表示是定义在中区域 上的 元实值函数 fDn 定义定义1 设设 若 使对 有 则称 若 使对 有 则称 f x 在处可微 在处可微 00 0 lim0 1 T p f xpf xl p p 00 0 lim0 1 T p f xpf xl p p 1 n f DRR 1 n f DRR n pR n pR 0 xD 0 xD n lR n lR 0 x0 x 若令若令 00 T fxpfxl p p 00 T fxpfxl p p 则则 f 在处可微时 有 即是无穷 小量 在处可微时 有 即是无穷 小量 0 x0 x 0 lim0 p 0 lim0 p 00 T f xpf xl pop 00 T f xpf xl pop 2 其中表示的高阶无穷小 与一 元函数可微性定义类似 即 其中表示的高阶无穷小 与一 元函数可微性定义类似 即 opp opp p p o t o t 0 lim0 t o t t 0 lim0 t o t t 西安电子科技大学 穆学文 20102 定理定理1 若在处可微 则在该点 处关于各变量的一阶偏导数存在 且 若在处可微 则在该点 处关于各变量的一阶偏导数存在 且 0 x 000 12 3 T n fxfxfx l xxx 000 12 3 T n fxfxfx l xxx f x f x 证明 令 依次取 证明 令 依次取 为任意无穷小变量 是单位向量 由在处可微 则 对 成立 即 两边除以并取的极限有 为任意无穷小变量 是单位向量 由在处可微 则 对 成立 即 两边除以并取的极限有 12 T n llll 12 T n llll 1 2 i i ppe in 1 2 i i ppe in i pip i e 0 x0 x ii pp e ii pp e 00i iiii fxp efxl pop 00i iiii fxp efxl pop 1 2 in 1 2 in i pip 0 i p 0 i p 000 0 lim i ii i P ii fxfxp efx l xp 000 0 lim i ii i P ii fxfxp efx l xp 1 2 in 1 2 in f f x定义定义2 以的以的 n 个偏导数为分量的向量称 为 个偏导数为分量的向量称 为f x 在在 x 处的梯度 处的梯度 12 4 T n f xf xf x f x xxx 12 4 T n f xf xf x f x xxx 记为 梯度也可称为函数 记为 梯度也可称为函数 f x 关于向量关于向量 x 的一阶导数 若 的一阶导数 若 f 在处可微在处可微 将 代入 得将 代入 得 0 x 000 5 T fxpfxfxpop 这与一元函数展开到两项的这与一元函数展开到两项的 Taylor 公式是相对应的 公式是相对应的 设设 f x 在定义域内有连续偏导数 即有 连续梯度 则梯度有以下两个重要性质 在定义域内有连续偏导数 即有 连续梯度 则梯度有以下两个重要性质 f x 1 2 梯度的性质 性质 梯度的性质 性质2 梯度方向是函数具有最大变化率的方向 性质 梯度方向是函数具有最大变化率的方向 性质1 函数在某点的梯度不为零 则必与过 该点的等值面的切平面垂直 函数在某点的梯度不为零 则必与过 该点的等值面的切平面垂直 性质性质1的证明的证明 过点的等值面方程为 设是过点同时又 完全在等值面 上的任一条光滑曲线 过点的等值面方程为 设是过点同时又 完全在等值面 上的任一条光滑曲线 L 的方 程 的方 程 为参数为参数 点对应的参数是 把此曲线 方程代入 点对应的参数是 把此曲线 方程代入 0 x 0 1200 6 n fx xxr rf x 0 x 1122 nn xxxxxx 0 x 0 120 n f xxxr 两边同时在 处关于两边同时在 处关于 求导数 根据复合函数微 分法有 求导数 根据复合函数微 分法有 0 0 f xf x 0 f x 0 t 两边同时在 处关于两边同时在 处关于 求导数 根据复合函数微 分法有 求导数 根据复合函数微 分法有 0 000 10200 12 0 n n fxfxfx xxx xxx 向量恰为曲线向量恰为曲线L在处 的切向量 有 在处 的切向量 有 010200 n txxx 0 x 00 0 T fxt 即函数即函数 f x 在处的梯度与过该点在等值面 上的任一条曲线 在处的梯度与过该点在等值面 上的任一条曲线L在此点的切线垂直 从而与过该 点的切平面垂直 从而性质一成立 在此点的切线垂直 从而与过该 点的切平面垂直 从而性质一成立 0 x 0 f x 西安电子科技大学 穆学文 20103 为说明第二条性质 先引进下面方向导数定义 定义 为说明第二条性质 先引进下面方向导数定义 定义3 设在点设在点x处可微 处可微 p为固定向量 为固定向量 e 为 向量 为 向量 p方向的单位向量 则称极限 为函数 方向的单位向量 则称极限 为函数 f x 在点处沿方向在点处沿方向 p 的方向导数 其中 为其记号 的方向导数 其中 为其记号 1 n fRR 000 0 lim t fxfxtefx pt 0 x 0 f x p 由定义及极限性质可知 由定义及极限性质可知 若 则若 则 f x 从出发在附近沿从出发在附近沿 p方向是下降的 则 方向是下降的 则 t 0 充分小时充分小时 即即 若 则若 则 f x 从出发在附近沿 方向 从出发在附近沿 方向 p 是上升的 是上升的 0 0 f x p 0 x 0 x 0 xxte 0 f xf x 0 0 f x p 00 0 f xtef x t 定理定理2 若在点处可微 则 其中 若在点处可微 则 其中 e 为为 p 方向上的单位向量 证明 利用方向导数定义并将 中的 方向上的单位向量 证明 利用方向导数定义并将 中的 p 换成换成 te 有 有 0 x 1 n fRR 0 0 T fx fxe p 000 T fxpfxfxpop 00 0 0 lim T T t f xt f xeo t f xe pt 推论推论 若 则若 则 p 是函数是函数 f x 在处的下降 方向 在处的下降 方向 若 则若 则 p 是函数是函数 f x 在处的上 升方向 证明 因为 在处的上 升方向 证明 因为 p te t 0 则 有 由前面证明即知 则 有 由前面证明即知 p 为下 降方向 同样可证明后者 为下 降方向 同样可证明后者 0 0 0 T fx fxe p 0 0 T fxp 0 0 T fxp 0 f x p 0 x 以上我们看到方向导数正负决定了函数升降 而升降速度的快慢由方向导数绝对值大小来决定 绝对值越大 升降速度越大 因此又将方向导数 称为 以上我们看到方向导数正负决定了函数升降 而升降速度的快慢由方向导数绝对值大小来决定 绝对值越大 升降速度越大 因此又将方向导数 称为f x 在处沿方向在处沿方向 p 的变化率的变化率 0 00 cos T f x f xef x p 向量内积 0 pfx pf x e tf x 由于由于 0 f x 为方向为方向 p 与的夹角 与的夹角 0 f x p 为使取最小值 为使取最小值 应取 即应取 即 0 180 则 可见 负梯度方向即为函数的最速下降法方向 梯度方向即为函数的最速上升方向 性质二得证 则 可见 负梯度方向即为函数的最速下降法方向 梯度方向即为函数的最速上升方向 性质二得证 西安电子科技大学 穆学文 20104 我们有结论 我们有结论 函数在与其梯度正交的方向上变化率为函数在与其梯度正交的方向上变化率为 0 函数在与其梯度成锐角的方向上是上升的 函数在与其梯度成锐角的方向上是上升的 函数在与其梯度成钝角的方向上是下降的 函数在与其梯度成钝角的方向上是下降的 0 x 0 f x 0 f x 上升方向 下降方向 变化率为 上升方向 下降方向 变化率为0方向方向 例例1 试求目标函数 在点处的最速下降方向 并求沿这个 方向移动一个单位长度后新点的目标函数值 试求目标函数 在点处的最速下降方向 并求沿这个 方向移动一个单位长度后新点的目标函数值 0 0 1 T x 22 121122 34fx xxx xx 解 由于 则函数在处的最速下降方向是 解 由于 则函数在处的最速下降方向是 1212 12 64 42 fxfx xxxx xx 0 0 1 T x 1 2 1 2 112 0 0 12 1 0 2 1 644 422 x x x x fx xxx pfx xxfx x 10 22 55 0 55 111 515 55 xxe 0 22 0 4 2 5 2 5 1 42 5 5 fx e fx 1 1 22 1122 26 34 2 5 5 x f xxx xx 这个方向上的单位向量是 新点是 这个方向上的单位向量是 新点是 1 0 2 3 2 4 2 T T T fxCfx fxb xfxb fxx xfxx Qfxx QxfxQx 常数则 则 则 对称矩阵 则 几个常用的梯度公式几个常用的梯度公式 1 3 Hesse矩阵矩阵 222 2 211 1 222 2 2 1 22 2 222 2 12 f xf xf x xxxx nx f xf xf x f xf x x xxx nx f xf xf x x xx x nnxn 多元函数的一阶导数即梯度 二阶导数即多元函数的一阶导数即梯度 二阶导数即Hesse阵阵 f x 西安电子科技大学 穆学文 20105 T f xb x 2 0n nf xbf x 1 2 T f xx x 2 f xxf xI 1 2 T f xx Qx 2 f xQxf xQ 下面几个下面几个Jacobi公式是今后常用到的 公式是今后常用到的 1 4 多元函数的多元函数的Taylor展开公式 设 展开公式 设 f x R Rn n R R 二阶可导 在 二阶可导 在x 的邻域内的邻域内 一阶Taylor展开式一阶Taylor展开式 f x f x f T x x x o x x 二阶Taylor展开式 二阶Taylor展开式 f x f x f T x x x 1 2 x x T 2f x x x o x x 2 一阶中值公式 对一阶中值公式 对x 0 1 0 1 使使 f x f x f x x x T x x Lagrange余项 对余项 对x 0 1 0 1 记记x x x x f x f x f T x x x 1 2 x x T 2f x x x 2 等高线等高线 二维最优化问题具有鲜明的几何解释 并且可 以象征性地把这种解释推广到 二维最优化问题具有鲜明的几何解释 并且可 以象征性地把这种解释推广到 n 维空间中去 因此 我们简要介绍一下图解法对