最优化方法及控制运用0

《最优化方法及控制运用0》由会员分享，可在线阅读，更多相关《最优化方法及控制运用0（109页珍藏版）》请在金锄头文库上搜索。

1、最优化方法及控制应用 主讲人 董密 信息科学与工程学院 参考书 1 实用最优化方法R Fleter著 游兆永等译天津科技翻译出版公司2 非线性规划数值方法袁亚湘上海科学技术出版社19953 非线性最优方法席少霖高等教育出版社4 工程优化的算法分析张可村西安交大出版社19895 最优化方法解文新 韩立兴等天津大学出版社20016 最优化方法施光燕 董加礼高等教育出版社2001 最优化方法及控制应用 最优化 在多种 有限种或无限种 决策中挑选最好决策的问题 最优化方法 也称做运筹学方法 是近几十年形成的 主要运用数学方法研究各种系统的优化途径及方案 为决策者提供科学决策的依据 最优方案 是达到最优

2、目标的方案 最优化理论 就是最优化方法的理论 数学意义 为了达到最优化目的所提出的各种求解方法 从数学意义上说 最优化方法是一种求极值的方法 即在一组约束为等式或不等式的条件下 使系统的目标函数达到极值 即最大值或最小值 从经济意义上说 是在一定的人力 物力和财力资源条件下 使经济效果达到最大 如产值 利润 或者在完成规定的生产或经济任务下 使投入的人力 物力和财力等资源为最少 发展简史 公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为1 618 称为黄金分割比 其倒数至今在优选法中仍得到广泛应用 在微积分出现以前 已有许多学者开始研究用数学方法解决最优化问题 最优化方法

3、真正形成为科学方法则在17世纪以后 工作步骤 提出最优化问题 收集有关数据和资料 建立最优化问题的数学模型 确定变量 列出目标函数和约束条件 分析模型 选择合适的最优化方法 求解 一般通过编制程序 用计算机求最优解 最优解的检验和实施 模型的基本要素 最优化模型包括 变量 约束条件和目标函数 变量 指最优化问题中待确定的某些量 变量可用x x1 x2 xn T表示 约束条件 指在求最优解时对变量的某些限制 包括技术上的约束 资源上的约束和时间上的约束等 约束条件可用gi x 0表示i 1 2 m m表示约束条件数 目标函数 最优化有一定的评价标准 目标函数就是这种标准的数学描述 一般可用f x

4、 来表示 即f x f x1 x2 xn 最优化方法 最优化问题的求解方法可分成解析法 直接法 数值计算法和其他方法 解析法 只适用于目标函数和约束条件有明显的解析表达式的情况 求解方法是 先求出最优的必要条件 得到一组方程或不等式 再求解这组方程或不等式 一般是用求导数的方法或变分法求出必要条件 通过必要条件将问题简化 因此也称间接法 直接法 当目标函数较为复杂或者不能用变量显函数描述时 无法用解析法求必要条件 可采用直接搜索的方法经过若干次迭代搜索到最优点 这种方法常常根据经验或通过试验得到所需结果 对于一维搜索 单变量极值问题 主要用消去法或多项式插值法 对于多维搜索问题 多变量极值问题

5、 主要应用爬山法 数值计算法 也是一种直接法 它以梯度法为基础 所以是一种解析与数值计算相结合的方法 其他方法 如网络最优化方法等 最优解的概念 最优化问题的解一般称为最优解 如果只考察约束集合中某一局部范围内的优劣情况 则解称为局部最优解 如果是考察整个约束集合中的情况 则解称为总体最优解 对于不同优化问题 最优解有不同的含意 因而还有专用的名称 例如 在对策论和数理经济模型中称为平衡解 在控制问题中称为最优控制或极值控制 在多目标决策问题中称为非劣解 又称帕雷托最优解或有效解 最优化方法的应用 最优化可分为最优设计 最优计划 最优管理和最优控制等四个方面 最优设计 世界各国工程技术界 尤其

6、是飞机 造船 机械 建筑等部门都已广泛应用最优化方法于设计中 从各种设计参数的优选到最佳结构形状的选取等 结合有限元方法已使许多设计优化问题得到解决 最优计划 现代国民经济或部门经济的计划 直至企业的发展规划和年度生产计划 尤其是农业规划 种植计划 能源规划和其他资源 环境和生态规划的制订 都已开始应用最优化方法 一个重要的发展趋势是帮助领导部门进行各种优化决策 最优管理 一般在日常生产计划的制订 调度和运行中都可应用最优化方法 随着管理信息系统和决策支持系统的建立和使用 使最优管理得到迅速的发展 最优控制 主要用于对各种控制系统的优化 例如 导弹系统的最优控制 能保证用最少燃料完成飞行任务

7、用最短时间达到目标 再如飞机 船舶 电力系统等的最优控制 化工 冶金等工厂的最佳工况的控制 一 组合最优化TSP 即旅行商问题 假设有n个城市 一个推销员要在这n个城市推销产品 要求经过每个城市且仅有一次 如何选择这条路径 使路径最短 二 动态规划管道铺设 有n个城市铺设管道 要求管道到达每个城市 并且使总的费用最低 经典极值问题 包括 无约束极值问题 约束条件下的极值问题 1 无约束极值问题的数学模型 2 约束条件下极值问题的数学模型 其中 极大值问题可以转化为极小值问题来进行求解 如求 可以转化为 1 无约束极值问题的求解 例1 求函数y 2x3 3x2 12x 14在区间 3 4 上的最

8、大值与最小值 解 令f x y 2x3 3x2 12x 14f x 6x2 6x 12 6 x 2 x 1 解方程f x 0 得到x1 2 x2 1 又由于f 3 23 f 2 34 f 1 7 f 4 142 综上得 函数f x 在x 4取得在 3 4 上得最大值f 4 142 在x 1处取得在 3 4 上取得最小值f 1 7 有约束最优化最优化方法分类 一 线性最优化 目标函数和约束条件都是线性的则称为线性最优化 非线性最优化 目标函数和约束条件如果含有非线性的 则称为非线性最优化 二 静态最优化 如果可能的方案与时间无关 则是静态最优化问题 动态最优化 如果可能的方案与时间有关 则是动态

9、最优化问题 有约束最优化问题的数学建模 有约束最优化模型一般具有以下形式 或 其中f x 为目标函数 省略号表示约束式子 可以是等式约束 也可以是不等式约束 根据目标函数 约束条件的特点将最优化方法包含的主要内容大致如下划分 线性规划整数规划非线性规划动态规划多目标规划对策论 最优化方法主要内容 两个引例 问题一 某工厂在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及A B两种原材料的消耗 如下表所示 该工厂每生产一件产品I可获利2元 每生产一件产品II可获利3元 问应如何安排计划使该工厂获利最多 解 该工厂生产产品Ix1件 生产产品IIx2件 我们可建立如下数学模型 s

10、 t 问题二 某厂每日8小时的产量不低于1800件 为了进行质量控制 计划聘请两种不同水平的检验员 一级检验员的标准为 速度25件 小时 正确率98 计时工资4元 小时 二级检验员的标准为 速度15件 小时 正确率95 计时工资3元 小时 检验员每错检一次 工厂要损失2元 为使总检验费用最省 该工厂应聘一级 二级检验员各几名 解设需要一级和二级检验员的人数分别为x1 x2人 则应付检验员的工资为 因检验员错检而造成的损失为 故目标函数为 约束条件为 运用最优化方法解决最优化问题的一般方法步骤如下 前期分析 分析问题 找出要解决的目标 约束条件 并确立最优化的目标 定义变量 建立最优化问题的数学

11、模型 列出目标函数和约束条件 针对建立的模型 选择合适的求解方法或数学软件 编写程序 利用计算机求解 对结果进行分析 讨论诸如 结果的合理性 正确性 算法的收敛性 模型的适用性和通用性 算法效率与误差等 线性规划 某豆腐店用黄豆制作两种不同口感的豆腐出售 制作口感较鲜嫩的豆腐每千克需要0 3千克一级黄豆及0 5千克二级黄豆 售价10元 制作口感较厚实的豆腐每千克需要0 4千克一级黄豆及0 2千克二级黄豆 售价5元 现小店购入9千克一级黄豆和8千克二级黄豆 问 应如何安排制作计划才能获得最大收益 一 问题前期分析该问题是在不超出制作两种不同口感豆腐所需黄豆总量条件下合理安排制作计划 使得售出各种

12、豆腐能获得最大收益 二 模型假设1 假设制作的豆腐能全部售出 2 假设豆腐售价无波动 变量假设 设计划制作口感鲜嫩和厚实的豆腐各x1千克和x2千克 可获得收益R元 目标函数 获得的总收益最大 总收益可表示为 受一级黄豆数量限制 受二级黄豆数量限制 综上分析 得到该问题的线性规划模型 s t 用Matlab编程求解程序如下 X FVAL EXITFLAG OUTPUT LINPROG f A b f 105 A 0 30 4 0 50 2 B 9 8 X FVAL EXITFLAG OUTPUT LINPROG f A b X 10 000015 0000FVAL 175 0000 用YALMI

13、P编程求解程序如下 x sdpvar 1 2 C 105 a 0 30 4 0 50 2 b 98 f C x F set 0 x inf F F set a x b solvesdp F f double f double x ans 175ans 1015 线性规划 设某工厂有甲 乙 丙 丁四个车间 生产A B C D E F六种产品 根据机床性能和以前的生产情况 得知每单位产品所需车间的工作小时数 每个车间在一个季度工作小时的上限以及单位产品的利润 如下表所示 例如 生产一个单位的A产品 需要甲 乙 丙三个车间分别工作1小时 2小时和4小时 问 每种产品各应该每季度生产多少 才能使这个工

14、厂每季度生产利润达到最大 这是一个典型的最优化问题 属线性规划 假设 产品合格且能及时销售出去 工作无等待情况等变量说明 xj 第j种产品的生产量 j 1 2 6 aij 第i车间生产单位第j种产品所需工作小时数 i 1 2 3 4 j 1 2 6 bi 第i车间的最大工作上限cj 第j种产品的单位利润则 cjxj为第j种产品的利润总额 aijxj表示第i车间生产第j种产品所花时间总数 于是 我们可建立如下数学模型 s t 计算结果 运输问题 要从甲城调出蔬菜2000吨 从乙城调出蔬菜2500吨 从丙地调出3000吨 分别供应A地2000吨 B地2300吨 C地1800吨 D地1400吨 已知

15、每吨运费如下表 问 如何调拨才能使运费最省 可以建立如下模型 s t 整数规划 最优化问题中的所有变量均为整数时 这类问题称为整数规划问题 如果线性规划中的所有变量均为整数时 称这类问题为线性整数规划问题 整数规划可分为线性整数规划和非线性整数规划 以及混合整数规划等 如果决策变量的取值要么为0 要么为1 则这样的规划问题称为0 1规划 例1某钢厂两个炼钢炉同时各用一种方法炼钢 第一种炼法每炉用a小时 第二种用b小时 包括清炉时间 假定这两种炼法 每炉出钢都是k公斤 而炼1公斤钢的平均燃料费第一法为m元 第二法为n元 若要求在c小时内炼钢公斤数不少于d 试列出燃料费最省的两种方法的分配方案的数

16、学模型 设用第一种炼法炼钢x1炉 第二种炼钢x2炉 s t 引例2 资源分配问题 某个中型的百货商场要求售货人员每周工作5天 连续休息2天 工资200元 周 已知对售货人员的需求经过统计分析如下表 问如何安排可使配备销售人员的总费用最少 非线性规划 非线性规划问题的一般数学模型 其中 为目标函数 为约束函数 这些函数中至少有一个是非线性函数 应用实例 供应与选址 某公司有6个建筑工地要开工 每个工地的位置 用平面坐标系a b表示 距离单位 km 及水泥日用量d t 由下表给出 目前有两个临时料场位于A 5 1 B 2 7 日储量各有20t 假设从料场到工地之间均有直线道路相连 1 试制定每天的供应计划 即从A B两料场分别向各工地运送多少水泥 可使总的吨千米数最小 2 为了进一步减少吨千米数 打算舍弃两个临时料场 改建两个新的 日储量各为20t 问应建在何处 节省的吨千米数有多大 一 建立模型 记工地的位置为 ai bi 水泥日用量为di i 1 6 料场位置为 xj yj 日储量为ej j 1 2 料场j向工地i的运送量为Xij 当用临时料场时决策变量为 Xij 当不用临时料场时决策