最优化方法_理工大学内部课件概要.ppt

（4）旅行售货问题 有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。 其它优化 目标规划(多目标规划) 动态规划 对策论、决策论 模糊优化 随机规划 随机规划： 报童的诀窍 问题 报童售报： a (零售价) b(购进价) c(退回价) 售出一份赚 a-b；退回一份赔 b-c 每天购进多少份可使收入最大？ 每天需求量是随机的 优化问题的目标函数应是长期的日平均收入 每天收入是随机的 建模 设每天购进 n 份，日平均收入为 G(n) 调查需求量的随机规律——每天需求量为 r 的概率 f(r), r=0,1,2… 准备 求 n 使 G(n) 最大 已知售出一份赚 a-b；退回一份赔 b-c 一般地，对于最优化问题（1.1）的求解，是指 在可行域内找一点，使得目标函数在该点取得极小 值，即 这样的 称为问题（1.1）的最优点，也称极 小点，而相应的目标函数值　　 称为最优值； 合起来，称为最优解，但习惯上，把　 本身称为最优解． 优化问题的求解 满足所有约束的点（解）称为可行点．可行点的集合称为可行域． 优化问题的求解方法（最优化方法）： （１）图解法 （２）函数极值法：　目标函数求导数 （3 ）数值解法， 　　　初始值x0，迭代的方法，有哪些信誉好的足球投注网站最优解 以下为例： 线性规划模型(LP) １、图解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 约束条件 目标函数 Z=0 Z=2400 Z=3600 z=c (常数) ~等值线 c 在B(20,30)点得到最优解 LINDO 6.1 ２、Lindo软件求解 但是，图解法和函数极值法都存在一定的局限性！ （1）图解法，适合于2维情况，更高维的就难以表达； （2）函数极值法，通常高等数学中的求极值问题的变量个数一般不超过三个；当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决． 呼唤新的求解方法！~直到上世纪50年代最优化理论建立以及电子计算机的迅速发展才为求解各种最优化问题提供了雄厚的基础和有效手段。 最优化问题的迭代解法（数值解法）！ 最优化方法 2013.2 : 1 何为优化问题? 2 优化问题如何描述? (即如何进行数学建模?) 3 如何求解? 1.1 问题提出 现实世界中普遍存在着优化问题 最优化问题 如：（1）电影院的座位设计问题 （2）组合投资问题 （3）背包问题/贪婪问题 （4）旅行售货问题 优 化 问 题 （1）电影院的座位设计问题 优 化 问 题 （2）组合投资问题 （3）背包问题(贪婪问题) 一个小偷打劫一个保险箱，发现柜子里有3类不同大小与价值的物品，但小偷只有一个容积为20的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。 （4）旅行售货问题 有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。 在所有可行的方案中选出最合理的，达到规定要求最优目标方案的实际问题称之为最优化问题。 最优化问题的提出 其它的最优化问题： 田忌赛马 本课程名为：运筹与优化 更合适 优化问题的数学描述，包括： （１）优化的目标 追求的目的，路程最短，花费最少… （２）寻求的决策 众多可选的方案中寻找一个使目标达到最优的决策 （３）限制条件 方案需满足特定的规则约束，如背包容量有限 优化问题的一般表述（优化问题的数学模型）： X表示决策变量，X=(x1,x2,…xn)’ Max f(X) ( 或 Min )目标函数 S.T g(X)=0 约束条件 X∈D 优化问题的数学描述，包括： 优化的目标——目标函数 寻求的决策——决策变量 限制条件 ——约束不等式 1.2 优化问题分类 根据处理思想方法的不同，分为数学规划、组合优化、图论与网络流、动态规划… 根据决策变量取值情况不同，分为连续型和离散型。 数学规划 线性规划 (Linear Programming)