最优化方法课件.ppt

1、最优化方法:1 何为优化问题何为优化问题?2 优化问题如何描述优化问题如何描述? (即如何进行数学建模即如何进行数学建模?)3 如何求解如何求解?1.1 问题提出问题提出 现实世界中普遍存在着优化问题现实世界中普遍存在着优化问题最优化问题如：（1）电影院的座位设计问题 （2）组合投资问题 （3）背包问题/贪婪问题 （4）旅行售货问题优优 化化 问问 题题（1）电影院的座位设计问题优优 化化 问问 题题（2）组合投资问题（3）背包问题(贪婪问题) 一个小偷打劫一个保险箱，发现柜子里有3类不同大小与价值的物品，但小偷只有一个容积为20的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以

2、使偷走的物品总价值最大。 （4）旅行售货问题 有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。 在所有可行的方案中选出最合理的，达到规定要求最优目标方案的实际问题称之为最优化问题。 最优化问题的提出最优化问题的提出其它的最优化问题：田忌赛马本课程名为：运筹与优化 更合适优化问题的数学描述优化问题的数学描述，包括：（）优化的目标追求的目的，路程最短，花费最少（）寻求的决策众多可选的方案中寻找一个使目标达到最优的决策（）限制条件方案需满足特定的规则约束，如背包容量有限优化问题的一般表述（优化问题的数学模型）：X表

3、示决策变量，X=(x1,x2,xn) Max f(X) ( 或 Min )目标函数 S.T g(X)=0 约束条件 XD优化问题的数学描述，包括： 优化的目标目标函数 寻求的决策决策变量 限制条件 约束不等式 1.2 优化问题分类 根据处理思想方法的不同，分为数学规划、组合优化、图论与网络流、动态规划 根据决策变量取值情况不同，分为连续型和离散型。数学规划线性规划(Linear Programming)非线性规划(Non-Linear Programming)运输问题一般线性规划整数规划（Integer Programming）无约束非线性规划约束非线性规划问题：问题：一奶制品加工厂用牛奶生产

4、一奶制品加工厂用牛奶生产A1、A2两种奶制两种奶制品，品，1桶牛奶可以在设备甲上用桶牛奶可以在设备甲上用12小时加工成小时加工成3公斤公斤A1，或者在设备乙上用，或者在设备乙上用8小时加工成小时加工成4公斤公斤A2。根据。根据市场需求，生产的市场需求，生产的A1、A2能全部售出，且每公斤能全部售出，且每公斤A1获利获利24元，每公斤元，每公斤A2获利获利16元。现在加工厂每天能元。现在加工厂每天能得到得到50桶牛奶的供应，每天正式工人总的劳动时间桶牛奶的供应，每天正式工人总的劳动时间为为480小时，并且设备甲每天至多能加工小时，并且设备甲每天至多能加工100公斤公斤A1，设备乙的加工能力没有限

5、制。设备乙的加工能力没有限制。例例1 加工奶制品的生产计划加工奶制品的生产计划 试为该厂试为该厂制定一个生产计划制定一个生产计划，使每天获利最大使每天获利最大.1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶桶牛奶 时间时间480小时小时 至多加工至多加工100公斤公斤A1 制订生产计划，使每天获利最大制订生产计划，使每天获利最大 每天：每天：问题分析：问题分析：生产计划是什么生产计划是什么? 每天的牛奶：安排多少生产每天的牛奶：安排多少生产A1，多少生产，多少生产A2 ? 有决策变量（生产计划），有目标，肯定就是一个优化问题！考虑建立优化模

6、型决策变量决策变量 模型建立：模型建立：设每天用x1桶牛奶生产A1 ，用x2桶牛奶生产A2目标函数目标函数 设每天获利为z元。 x1桶牛奶可生产3x1公斤A1，获利24*3x1; x2桶牛奶可生产4x2公斤A2，获利16*4x2; 故z=72x1+64x2约束条件约束条件原料供应原料供应 生产A1、A2的原料（牛奶）总量不超过每天的供应50桶，即 x1+x250劳动时间劳动时间 生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时，即 12x1+8x2480设备能力设备能力 A1的产量不得超过设备甲每天的加工能力100小时，即 3x1100非负约束非负约束 x1、x2均不能为负值

7、，即x10，x20216472xxzMax综上所述可得如下综上所述可得如下优化模型优化模型：1212112501284803100,0 xxxxstxx x线性线性规划规划模型模型(LP) 目标函数和约束条件都是线性的，这种优化模型称为是线性规划（linear programming,LP）模型。整数线性规划模型的实例例1 某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表51： 货物体积每箱（米3）重量每箱（百斤）利润每箱（百元） 甲 乙 5 4 2 5 20 10托运限制 24 13问两种货物各托运多少箱，可使获得的利润为最大？解：设托运甲、乙两种货物x1，x2

8、箱，用数学式可表示为：1212121220105424:25130MaxZxxxxSTxxxx，且为整数如果丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例：游泳队员的选拔问题 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xi

9、j=0 0-1规划模型 cij(秒)队员i 第j 种泳姿的百米成绩约束条件每人最多入选泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.44151jiijijxcZMin每种泳姿有且只有1人 5, 1, 141ixjij4, 1, 151jxiij非线性规划：使用临时料场的情形 使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下， 改建两个新料场，要同时确定料

10、场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。组合优化（Combinatorial Optimization） 组合最优化组合最优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。 例：旅行商问题（TSP,traveling saleman problem） 一个商人欲到 n 个城市推销商品，每两个城市 i 和 j 之间的距离为 d ij ,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。图论与网络流最短路问题最小生成树问题最大流问题匹配问题最小费用流问题（4）旅行售货问题 有一个推销员，要到各个城市去推销产品，他希望能找到一个最短

11、的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。 其它优化目标规划(多目标规划)动态规划对策论、决策论模糊优化随机规划随机规划： 报童的诀窍报童的诀窍问问题题报童售报：报童售报： a (零售价零售价) b(购进价购进价) c(退回价退回价)售出一份赚售出一份赚 a-b；退回一份赔；退回一份赔 b-c 每天购进多少份可使收入最大？每天购进多少份可使收入最大？每天需求量是随机的每天需求量是随机的优化问题的目标函数应是长期的日平均收入优化问题的目标函数应是长期的日平均收入每天收入是随机的每天收入是随机的建建模模 设每天购进设每天购进 n 份，份，日平均收入为日平均收入为

12、G(n)调查需求量的随机规律调查需求量的随机规律每天每天需求量为需求量为 r 的概率的概率 f(r), r=0,1,2准准备备)()(rncbrnrbarnr赔退回赚售出nbannr)( 赚售出nrnrrnfbarfrncbrbanG01)()()()()()(求求 n 使使 G(n) 最大最大 已知售出一份赚已知售出一份赚 a-b；退回一份赔；退回一份赔 b-c 一般地，对于最优化问题（一般地，对于最优化问题（1.11.1）的求解，是指）的求解，是指在可行域内找一点，使得目标函数在该点取得极小在可行域内找一点，使得目标函数在该点取得极小值，即值，即 这样的这样的 称为问题（称为问题（1.11

13、.1）的）的最优点，也称，也称极极小点，而相应的目标函数值小点，而相应的目标函数值 称为称为最优值； 合起来，称为合起来，称为最优解，但习，但习惯上，把惯上，把 本身称为本身称为最优解*()min()()0. .()0f Xf XG Xs tH X，*()f X*(,()Xf X*X*X优化问题的求解满足所有约束的点（解）称为可行点可行点的集合称为可行域可行域优化问题的求解方法（优化问题的求解方法（最优化方法最优化方法）：）：（）图解法（）图解法（）函数极值法：目标函数求导数（）函数极值法：目标函数求导数（3 ）数值解法，）数值解法，初始值初始值x0，迭代的方法，搜索最优解，迭代的方法，搜索最

14、优解216472xxzMax以下为例：以下为例：1212112501284803100,0 xxxxstxx x线性线性规划规划模型模型(LP)、图解法、图解法 x1x20ABCDl1l2l3l4l55021 xx48081221 xx10031x0,21xx约约束束条条件件50:211 xxl480812:212 xxl1003:13xl0:, 0:2514xlxl216472xxzMax目标函数目标函数 Z=0Z=2400Z=3600z=c (常数常数) 等值线等值线c在在B(20,30)点得到最优解点得到最优解LINDO 6.1 、LindoLindo软件求解软件求解 但是，图解法和函数极值法都存在一定的局限性！ （1）图解法图解法，适合于2维情况，更高维的就难以表达； （2）函数极值法函数极值法，通常高等数学中的求极值问题的变量个数一般不超过三个；当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决 呼唤新的求解方法！呼唤新的求解方法！直到上世纪50年代最优化理论建立以及电子计算机的迅速发展才为求解各种最优化问题提供了雄厚的基础和有效手段。 最优化问题的迭代解法（数值解法）！最优化问题的迭代解法（数值解法）！