最优化概念及其分类(工程油画中的数学方法).pdf

工程优化课件 穆学文2008 8 221 工程优化设计中的数学方法工程优化设计中的数学方法工程优化设计中的数学方法工程优化设计中的数学方法 硕士研究生课程硕士研究生课程硕士研究生课程硕士研究生课程 理学院数学系 穆学文理学院数学系 穆学文 E mail mxw1334 2009 4 15西安电子科技大学 穆学文2 教材及其参考书目教材及其参考书目教材及其参考书目教材及其参考书目 计划学时数 计划学时数 46学时 教材 学时 教材 1 最优化计算方法最优化计算方法 陈开周 西安电子科技大学出版社 陈开周 西安电子科技大学出版社 1985 2 最优化理论与算法最优化理论与算法 陈宝林陈宝林 清华大学出版社 清华大学出版社 2003 主要参考书目 主要参考书目 1 最优化理论与方法最优化理论与方法 袁亚湘袁亚湘 孙文渝孙文渝 科学出版社 科学出版社 1997 2 最优化方法最优化方法 唐焕文唐焕文 秦学志秦学志 大连理工大学出版社 大连理工大学出版社 1985 3 非线性规划数值方法非线性规划数值方法 袁亚湘 上海科学技术出版社 袁亚湘 上海科学技术出版社 1993 2009 4 15西安电子科技大学 穆学文3 考核方法考核方法考核方法考核方法 期末考试成绩作为总成绩期末考试成绩作为总成绩 课件下载地址 邮箱 课件下载地址 邮箱 mxw 1334 密码 密码 654321 2009 4 15西安电子科技大学 穆学文4 背景知识背景知识 基本概念及其应用基本概念及其应用 最优化问题举例最优化问题举例 优化问题的数学模型及其分类优化问题的数学模型及其分类 最优解与极值点最优解与极值点 常用的数学软件常用的数学软件 第一章 基础知识第一章 基础知识 1背景知识背景知识 运筹学理论的一部分运筹学理论的一部分 最早起源于中国古代最早起源于中国古代 公元前公元前6世纪孙武所著的 孙子兵法 世纪孙武所著的 孙子兵法 孙膑孙膑 斗马术斗马术 田忌与齐王赛马 博弈论 田忌与齐王赛马 博弈论 运筹帷幄之中 决胜千里之外运筹帷幄之中 决胜千里之外 这千古名句也 可以说是对张良运筹思想的赞颂和褒奖 这千古名句也 可以说是对张良运筹思想的赞颂和褒奖 国外起源与发展国外起源与发展 1738年年 D Bernoulli首次提出了效用的概念 并以此作 为决策的标准 首次提出了效用的概念 并以此作 为决策的标准 2009 4 15西安电子科技大学 穆学文6 1896年 年 V Pareto首次从数学角度提出多目标优化问 题 引进了 首次从数学角度提出多目标优化问 题 引进了Pareto最优的概念 最优的概念 丹麦电话工程师丹麦电话工程师A K Erlang开展了关于电话局中继线数 目的话务理论的研究 开展了关于电话局中继线数 目的话务理论的研究 1909年发表了他将概率论应用于 电话话务理论的研究论文 年发表了他将概率论应用于 电话话务理论的研究论文 概率论与电话会话概率论与电话会话 开排 队论研究的先河 开排 队论研究的先河 1935 38年 英国为了正确地运用新研制的雷达系统来对 付德国飞机的空袭 在皇家空军中组织了一批科学家 进行新战术试验和战术效率评价的研究 并取得了满意 的效果 他们把自己从事的这种工作命名为 年 英国为了正确地运用新研制的雷达系统来对 付德国飞机的空袭 在皇家空军中组织了一批科学家 进行新战术试验和战术效率评价的研究 并取得了满意 的效果 他们把自己从事的这种工作命名为 Operational Research 运筹学 或直译为作战研究运筹学 或直译为作战研究 1939年 苏联的 年 苏联的 总结了他 对生产组织的研究 写了 生产组织与计划中的数学方 法 一书 是线性规划应用于工业生产问题的经典著作 总结了他 对生产组织的研究 写了 生产组织与计划中的数学方 法 一书 是线性规划应用于工业生产问题的经典著作 背景知识 续 背景知识 续 工程优化课件 穆学文2008 8 222 2009 4 15西安电子科技大学 穆学文7 1947年年 G B Dantzig提出了单纯形方法后 线性规划便 迅速形成为一个独立的分支 并逐级发展起来 提出了单纯形方法后 线性规划便 迅速形成为一个独立的分支 并逐级发展起来 英国运筹学会英国运筹学会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条 件 标志着非线性规划理论的初步形成 条 件 标志着非线性规划理论的初步形成 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文8 1952年年5月美国运筹学会成立 并创刊 月美国运筹学会成立 并创刊 Operations Research 1953年年 R Bellman提出动态规划的名称 并阐述了最优 化原理 提出动态规划的名称 并阐述了最优 化原理 1954年 年 D R Dantzig等研究旅行推销员问题时提出了分 解的思想 成为整数规划中两大方法 等研究旅行推销员问题时提出了分 解的思想 成为整数规划中两大方法 割平面法与分枝 定界法的萌芽 割平面法与分枝 定界法的萌芽 1955年年 G Dantzig首先考虑出现随机变量的线性规划问 题 这是最早提出的随机规划中的有补偿二阶段问题 首先考虑出现随机变量的线性规划问 题 这是最早提出的随机规划中的有补偿二阶段问题 1956年年 L R Ford Jr 与与 D R Fulkerson提出并解决了网络 最大流问题 加强了图论与线性规划的联系 促进了优 化理论的研究 提出并解决了网络 最大流问题 加强了图论与线性规划的联系 促进了优 化理论的研究 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文9 1959年年1月月1日 国际运筹学会联合会日 国际运筹学会联合会 1FORS 正式宣告 成立 当时的联合会只包括英 美 法三个国家的运筹 学会 首任 正式宣告 成立 当时的联合会只包括英 美 法三个国家的运筹 学会 首任 1959 61年 主席 当时称为秘书 到年 主席 当时称为秘书 到1968 年第四届时才改称主席 为英国的年第四届时才改称主席 为英国的Charles Goodeve 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文10 运筹学理论在中国的研究与发展运筹学理论在中国的研究与发展 1957年 经中国科学院力学研究所所长钱学森的倡导 在该所成立了由许国志领导的国内第一个运筹学研究组 年 经中国科学院力学研究所所长钱学森的倡导 在该所成立了由许国志领导的国内第一个运筹学研究组 后成室后成室 刘源张 周华章 桂湘云等是该组最早的一 批研究人员 从此在我国开始了现代运筹学的研究 当 年秋季 又有大学毕业生顾基发 董泽清 徐映波 陈 锡康 郭绍僖 李秉全等分配进入该组 刘源张 周华章 桂湘云等是该组最早的一 批研究人员 从此在我国开始了现代运筹学的研究 当 年秋季 又有大学毕业生顾基发 董泽清 徐映波 陈 锡康 郭绍僖 李秉全等分配进入该组 1958年 中国科学院数学研究所所长华罗庚率领广大研 究人员 包括吴文俊 越民义 万哲先 王元等在内 也开展了运筹学应用课题的研究 并影响和带动了全国 范围内各部门 各高校的运筹学应用和推广工作 运输 和农业等部门的 年 中国科学院数学研究所所长华罗庚率领广大研 究人员 包括吴文俊 越民义 万哲先 王元等在内 也开展了运筹学应用课题的研究 并影响和带动了全国 范围内各部门 各高校的运筹学应用和推广工作 运输 和农业等部门的 图上作业法图上作业法 打麦场设计打麦场设计 中国 邮递员问题 中国 邮递员问题 是典型的成果 是典型的成果 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文11 1959年年2月 山东大学在数学系中设置了国内最早的一 个运筹学专门化 由谢力同与郑汉鼎执教 自当年暑假 开始 每年都有运筹学方向的学生毕业 为我国运筹学 事业的发展作出了重要贡献 月 山东大学在数学系中设置了国内最早的一 个运筹学专门化 由谢力同与郑汉鼎执教 自当年暑假 开始 每年都有运筹学方向的学生毕业 为我国运筹学 事业的发展作出了重要贡献 1959年 中国科学院数学研究所成立了运筹学研究室 研究人员都由所内其它室组调入 孙克定任研究室主 任 该室最早的一批研究人员有排队论组的越民义 吴 方 徐光煇 韩继业 对策论组的吴文俊 江加禾 施 闺芳 数学规划组的朱永津 应玫茜 马仲蕃 凌开诚 等 与此同时 全国范围内很多高校也有大批教师转入 运筹学领域 年 中国科学院数学研究所成立了运筹学研究室 研究人员都由所内其它室组调入 孙克定任研究室主 任 该室最早的一批研究人员有排队论组的越民义 吴 方 徐光煇 韩继业 对策论组的吴文俊 江加禾 施 闺芳 数学规划组的朱永津 应玫茜 马仲蕃 凌开诚 等 与此同时 全国范围内很多高校也有大批教师转入 运筹学领域 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文12 1965年起 华罗庚和他的小分队在全国工业部门开始普 及推广统筹法的群众运动 在此后的二十年中 为普及 推广双法 统筹法与从 年起 华罗庚和他的小分队在全国工业部门开始普 及推广统筹法的群众运动 在此后的二十年中 为普及 推广双法 统筹法与从1970年开始普及推广的优选 法 他们走访了全国 年开始普及推广的优选 法 他们走访了全国23个省市中几百个城市的几千个 工厂 并向数百万人开设讲座开展工作 取得了巨大的 社会效益和经济效益 个省市中几百个城市的几千个 工厂 并向数百万人开设讲座开展工作 取得了巨大的 社会效益和经济效益 1965年华罗庚 统筹方法平话及其补充 一书由中国工 业出版社出版 年华罗庚 统筹方法平话及其补充 一书由中国工 业出版社出版 1970年起 华罗庚和他的小分队开始在全国范围内普及 推广优选法的群众运动 从此 统筹与优选双法变得家 喻户晓 双法的普及推广也取得了极为可观的社会 经 济效益 年起 华罗庚和他的小分队开始在全国范围内普及 推广优选法的群众运动 从此 统筹与优选双法变得家 喻户晓 双法的普及推广也取得了极为可观的社会 经 济效益 1971年华罗庚 优选法平话及其补充 一书由国防工业 出版社出版 年华罗庚 优选法平话及其补充 一书由国防工业 出版社出版 背景知识 续 背景知识 续 工程优化课件 穆学文2008 8 223 2009 4 15西安电子科技大学 穆学文13 1980年年4月月22 26日在山东济南 召开了中国数学会运筹 学会成立暨第一届代表大会 中国运筹学倡导者之一 中国科学院副院长华罗庚主持了会议 有来自各地科研 机构 高等院校 军事部门 工交企业等有关单位的 日在山东济南 召开了中国数学会运筹 学会成立暨第一届代表大会 中国运筹学倡导者之一 中国科学院副院长华罗庚主持了会议 有来自各地科研 机构 高等院校 军事部门 工交企业等有关单位的82 名代表出席 华罗庚在大会开幕式与闭幕式上均发表了 讲话 回顾了他在全国范围普及推广 名代表出席 华罗庚在大会开幕式与闭幕式上均发表了 讲话 回顾了他在全国范围普及推广 双法双法 的经验和成 果 勉励大家以克敌攻坚的进取精神积极开展运筹学研 究 会议作了 的经验和成 果 勉励大家以克敌攻坚的进取精神积极开展运筹学研 究 会议作了12个专题学术报告和个人成果的几十个分 组报告 中国数学会理事长华罗庚被推选兼任运筹学会 理事长 越民义 许国志 余潜修为副理事长 桂湘云 为秘书长 推选常务理事 个专题学术报告和个人成果的几十个分 组报告 中国数学会理事长华罗庚被推选兼任运筹学会 理事长 越民义 许国志 余潜修为副理事长 桂湘云 为秘书长 推选常务理事11名 理事名 理事42名 会议决定学 会挂靠在中科院应用数学所 名 会议决定学 会挂靠在中科院应用数学所 背景知识 续 背景知识 续 2009 4 15西安电子科技大学 穆学文14 2基本概念及其应用基本概念及其应用 最优化技术是一门较新的学科分支 它是在本 世纪五十年代初在电子计算机广泛应用的推动下才 得到迅速发展 并成为一门直到目前仍然十分活跃 的新兴学科 最优化技术是一门较新的学科分支 它是在本 世纪五十年代初在电子计算机广泛应用的推动下才 得到迅速发展 并成为一门直到目前仍然十分活跃 的新兴学科 最优化所研究的问题是在众多的可行 方案中怎样选择最合理的一种以达到最优目标 最优化所研究的问题是在众多的可行 方案中怎样选择最合理的一种以达到最优目标 将达到最优目标的方案称为将达到最优目标的方案称为最优方案最优方案或或最优决 策 最优决 策 搜寻最优方案的方法称为 搜寻最优方案的方法称为最优化方法最优化方法 关于最 优化方法的数学理论称为 关于最 优化方法的数学理论称为最优化理论最优化理论 2009 4 15西安电子科技大学 穆学文15 最优化问题至少有两要素 一是可能的 方案 二是要追求的目标 后者是前者的函 数 如果第一要素与时间无关就称为 最优化问题至少有两要素 一是可能的 方案 二是要追求的目标 后者是前者的函 数 如果第一要素与时间无关就称为静态最 优化问题 静态最 优化问题 否则称为 否则称为动态最优化问题动态最优化问题 本科程专门讲授静态最优化问题 本科程专门讲授静态最优化问题 最优化技术应用范围十分广泛 在我们日常 生活中 在工农业生产 社会经济 国防 航空 航天工业中处处可见其用途 如结构最优设计 电子器件最优设计 光学仪器最优设计 化工工 程最优设计 标腔最优配方 运输方案 机器最 优配备 油田开发 水库调度 饲料最优配方 食品结构优化等等 最优化技术应用范围十分广泛 在我们日常 生活中 在工农业生产 社会经济 国防 航空 航天工业中处处可见其用途 如结构最优设计 电子器件最优设计 光学仪器最优设计 化工工 程最优设计 标腔最优配方 运输方案 机器最 优配备 油田开发 水库调度 饲料最优配方 食品结构优化等等 2009 4 15西安电子科技大学 穆学文17 最优化技术工作被分成两个方面 一是最优化技术工作被分成两个方面 一是由实 际生产或科技问题形成最优化的数学模型 由实 际生产或科技问题形成最优化的数学模型 二是二是 对所形成的数学问题进行数学加工和求解 对所形成的数学问题进行数学加工和求解 对于 第二方面的工作 目前已有一些较系统成熟的资 料 但对于第一方面工作即如何由实际问题抽象 出数学模型 目前很少有系统的资料 而这一工 作在应用最优化技术解决实际问题时是十分关键 的基础 没有这一工作 最优化技术将成为无水 之源 难以健康发展 对于 第二方面的工作 目前已有一些较系统成熟的资 料 但对于第一方面工作即如何由实际问题抽象 出数学模型 目前很少有系统的资料 而这一工 作在应用最优化技术解决实际问题时是十分关键 的基础 没有这一工作 最优化技术将成为无水 之源 难以健康发展 2009 4 15西安电子科技大学 穆学文18 因此 我们在学习本科程时要尽可能了解 如何由实际问题形成最优化的数学模型 为 了便于大家今后在处理实际问题时建立最优化 数学模型 下面我们先把有关数学模型的一些 事项作一些说明 因此 我们在学习本科程时要尽可能了解 如何由实际问题形成最优化的数学模型 为 了便于大家今后在处理实际问题时建立最优化 数学模型 下面我们先把有关数学模型的一些 事项作一些说明 数学模型数学模型 对现实事物或问题的数学抽象或描述对现实事物或问题的数学抽象或描述 工程优化课件 穆学文2008 8 224 2009 4 15西安电子科技大学 穆学文19 建立数学模型时要尽可能简单 而且要能 完整地描述所研究的系统 但要注意到过于简 单的数学模型所得到的结果可能不符合实际情 况 而过于详细复杂的模型又给分析计算带来 困难 因此 具体建立怎样的数学模型需要丰 富的经验和熟练的技巧 即使在建立了问题的 数学模型之后 通常也必须对模型进行必要的 数学简化以便于分析 计算 建立数学模型时要尽可能简单 而且要能 完整地描述所研究的系统 但要注意到过于简 单的数学模型所得到的结果可能不符合实际情 况 而过于详细复杂的模型又给分析计算带来 困难 因此 具体建立怎样的数学模型需要丰 富的经验和熟练的技巧 即使在建立了问题的 数学模型之后 通常也必须对模型进行必要的 数学简化以便于分析 计算 建立最优化问题数学模型的三要素 建立最优化问题数学模型的三要素 1 决策变量和参数 决策变量和参数 决策变量是由数学模型 的解确定的未知数 参数表示系统的控制变量 有 确定性的也有随机性的 决策变量是由数学模型 的解确定的未知数 参数表示系统的控制变量 有 确定性的也有随机性的 2 约束或限制条件 约束或限制条件 由于现实系统的客观物 质条件限制 模型必须包括把决策变量限制在它们 可行值之内的约束条件 而这通常是用约束的数学 函数形式来表示的 由于现实系统的客观物 质条件限制 模型必须包括把决策变量限制在它们 可行值之内的约束条件 而这通常是用约束的数学 函数形式来表示的 一般的模型简化工作包括以下几类 一般的模型简化工作包括以下几类 1 将离散变量转化为连续变量 将离散变量转化为连续变量 2 将非线性函数线性化 将非线性函数线性化 3 删除一些非主要约束条件 删除一些非主要约束条件 3 目标函数 目标函数 这是作为系统决策变量的 一个数学函数来衡量系统的效率 即系统追 求的目标 这是作为系统决策变量的 一个数学函数来衡量系统的效率 即系统追 求的目标 2 最优化问题举例最优化问题举例 最优化在运输 自动控制 机械设计 采 矿冶金 经济管理等科学技术各领域中有广泛 应用 下面举几个实例 最优化在运输 自动控制 机械设计 采 矿冶金 经济管理等科学技术各领域中有广泛 应用 下面举几个实例 例例1 把半径为把半径为1的实心金属球熔化后 铸成一个 实心圆柱体 问圆柱体取什么尺寸才能使它的表 面积最小 的实心金属球熔化后 铸成一个 实心圆柱体 问圆柱体取什么尺寸才能使它的表 面积最小 2009 4 15西安电子科技大学 穆学文23 解解 1 决定圆柱体表面积大小有两个决策变量 圆柱体底面半径 决定圆柱体表面积大小有两个决策变量 圆柱体底面半径 r 高 高 h 2 问题的约束条件是所铸圆柱体重量与球重 相等 即 问题的约束条件是所铸圆柱体重量与球重 相等 即 23 4 3 rhR 0 1R 为金属比重 即即 2 4 0 3 r h 问题追求的目标是圆柱体表面积最小 即问题追求的目标是圆柱体表面积最小 即 2 22rhr 2 2 min22 4 0 3 rhr str s t Subject to 固定固定 minimize min 则得原问题的数学模型 则得原问题的数学模型 工程优化课件 穆学文2008 8 225 2009 4 15西安电子科技大学 穆学文25 利用在高等数学中所学的利用在高等数学中所学的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 1exp a ya xa a a 1234 aaaa5 a 1 12 2 mm x yx yxy 2009 4 15西安电子科技大学 穆学文27 将测量点沿垂线方向到曲线的距离的平方和作 为这种 将测量点沿垂线方向到曲线的距离的平方和作 为这种 偏差偏差 的度量的度量 即即 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 2009 4 15西安电子科技大学 穆学文29 例例3 旅游售货员问题 旅游售货员问题 旅游线路安排旅游线路安排 预定景点走且只走一次 路上时间最短 预定景点走且只走一次 路上时间最短 配送线路配送线路 货郎担问题货郎担问题 送货地到达一次 总路程最短 送货地到达一次 总路程最短 旅行团从出发要遍游城市 已知从到的旅费为 问应如何安排行 程使总费用最小 旅行团从出发要遍游城市 已知从到的旅费为 问应如何安排行 程使总费用最小 0 v 12 n v vv j v i v ij c 模型 模型 模型 模型 变量变量 是否从是否从 i 第个城市到第第个城市到第 j 个城市个城市 约束约束 每个城市只能到达一次 离开一次每个城市只能到达一次 离开一次 1 0 ij x 00 1 1 2 1 1 2 nn ijij ji xinxjn 工程优化课件 穆学文2008 8 226 目标目标 总费用最小总费用最小 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 2009 4 15西安电子科技大学 穆学文32 例例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 2009 4 15西安电子科技大学 穆学文35 例例例例5 5 背包问题 背包问题 背包问题 背包问题 邮递包裹 把形状可变的包裹用尽量少的车辆运走 邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品 旅行背包 容量一定的背包里装尽可能的多的物品 装箱问题装箱问题 2009 4 15西安电子科技大学 穆学文36 某人出国留学打点行李 现有三个旅行 包 容积大小分别为 某人出国留学打点行李 现有三个旅行 包 容积大小分别为1000毫升 毫升 1500毫升和毫升和 2000毫升 根据需要列出需带物品清单 其 中一些物品是必带物品共有 毫升 根据需要列出需带物品清单 其 中一些物品是必带物品共有7件 其体积大 小分别为 件 其体积大 小分别为400 300 150 250 450 760 190 单位毫升 尚有 单位毫升 尚有10件可带可不带物 品 如果不带将在目的地购买 通过网络查 询可以得知其在目的地的价格 单位美元 这些物品的容量及价格分别见下表 试给出 一个合理的安排方案把物品放在三个旅行包 里 件可带可不带物 品 如果不带将在目的地购买 通过网络查 询可以得知其在目的地的价格 单位美元 这些物品的容量及价格分别见下表 试给出 一个合理的安排方案把物品放在三个旅行包 里 工程优化课件 穆学文2008 8 227 2009 4 15西安电子科技大学 穆学文37 物品物品12345678910 体积体积200350500430320120700420250100 价格价格1545100705075200902030 2009 4 15西安电子科技大学 穆学文38 问题分析 问题分析 变量变量 对每个物品要确定是否带同时要确定 放在哪个包裹里 如果增加一个虚拟的包裹 把不带的物品放在里面 则问题就转化为确 定每个物品放在哪个包裹里 如果直接设变 量为每个物品放在包裹的编号 则每个包裹 所含物品的总容量就很难写成变量的函数 为此我们设变量为第 对每个物品要确定是否带同时要确定 放在哪个包裹里 如果增加一个虚拟的包裹 把不带的物品放在里面 则问题就转化为确 定每个物品放在哪个包裹里 如果直接设变 量为每个物品放在包裹的编号 则每个包裹 所含物品的总容量就很难写成变量的函数 为此我们设变量为第 i 个物品是否放在第个物品是否放在第j个 包裹中 个 包裹中 1 0 1 2 17 1 2 3 ij xij 2009 4 15西安电子科技大学 穆学文39 约束 包裹容量限制 必带物品限制 选带物品限制 约束 包裹容量限制 必带物品限制 选带物品限制 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 2009 4 15西安电子科技大学 穆学文40 目标函数目标函数 未带物品购买费用最小未带物品购买费用最小 3 1 1 8 9 17 ij j xi 173 81 1 iij ij px 2009 4 15西安电子科技大学 穆学文41 173 81 min 1 iij ij px 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 工程优化课件 穆学文2008 8 228 2009 4 15西安电子科技大学 穆学文43 约束最优化问题约束最优化问题 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 2009 4 15西安电子科技大学 穆学文46 最优化问题模型统一化 最优化问题模型统一化 在上述最优化问题的一般式中只是取极小值 如果遇到极大化问题 只须将目标函数反号就可 以化为求极小的问题 在上述最优化问题的一般式中只是取极小值 如果遇到极大化问题 只须将目标函数反号就可 以化为求极小的问题 f x xf xf xf xf 4 因此后面只研究最小 化问题 因此后面只研究最小 化问题 如果约束条件中有 小于等于 的 即 则转化为 另外 等式约束可 以由下面两个不等式来代替 因而最优化问题的一般形式又可写成 如果约束条件中有 小于等于 的 即 则转化为 另外 等式约束可 以由下面两个不等式来代替 因而最优化问题的一般形式又可写成 0 G x 0G x 0H x 0 0H xH x min 0 f x stG x 可行域记为可行域记为 0Dx G x 2009 4 15西安电子科技大学 穆学文48 3 2 根据函数的类型分类根据函数的类型分类 线