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

最优化方法2013.2:1何为优化问题?2优化问题如何描述?(即如何进行数学建模?)3如何求解?1.1问题提出•现实世界中普遍存在着优化问题最优化问题如：（1）电影院的座位设计问题（2）组合投资问题（3）背包问题/贪婪问题（4）旅行售货问题优化问题（1）电影院的座位设计问题优化问题（2）组合投资问题（3）背包问题(贪婪问题)一个小偷打劫一个保险箱，发现柜子里有3类不同大小与价值的物品，但小偷只有一个容积为20的背包来装东西，背包问题就是要找出一个小偷选择所偷物品的组合，以使偷走的物品总价值最大。（4）旅行售货问题有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。在所有可行的方案中选出最合理的，达到规定要求最优目标方案的实际问题称之为最优化问题。最优化问题的提出其它的最优化问题：田忌赛马本课程名为：运筹与优化更合适优化问题的数学描述，包括：（１）优化的目标追求的目的，路程最短，花费最少…（２）寻求的决策众多可选的方案中寻找一个使目标达到最优的决策（３）限制条件方案需满足特定的规则约束，如背包容量有限优化问题的一般表述（优化问题的数学模型）：X表示决策变量，X=(x1,x2,…xn)’Maxf(X)(或Min)目标函数S.Tg(X)=0约束条件X∈D优化问题的数学描述，包括：优化的目标——目标函数寻求的决策——决策变量限制条件——约束不等式1.2优化问题分类根据处理思想方法的不同，分为数学规划、组合优化、图论与网络流、动态规划…根据决策变量取值情况不同，分为连续型和离散型。数学规划线性规划(LinearProgramming)非线性规划(Non-LinearProgramming)运输问题一般线性规划整数规划（IntegerProgramming）无约束非线性规划约束非线性规划问题：一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。例1加工奶制品的生产计划试为该厂制定一个生产计划，使每天获利最大.1桶牛奶3公斤A112小时8小时4公斤A2或获利24元/公斤获利16元/公斤50桶牛奶时间480小时至多加工100公斤A1制订生产计划，使每天获利最大每天：问题分析：生产计划是什么?每天的牛奶：安排多少生产A1，多少生产A2?有决策变量（生产计划），有目标，肯定就是一个优化问题！考虑建立优化模型~决策变量模型建立：设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2目标函数设每天获利为z元。x1桶牛奶可生产3x1公斤A1，获利24*3x1;x2桶牛奶可生产4x2公斤A2，获利16*4x2;故z=72x1+64x2约束条件原料供应生产A1、A2的原料（牛奶）总量不超过每天的供应50桶，即x1+x2≤50劳动时间生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时，即12x1+8x2≤480设备能力A1的产量不得超过设备甲每天的加工能力100小时，即3x1≤100非负约束x1、x2均不能为负值，即x1≥0，x2≥0216472xxzMax综上所述可得如下优化模型：1212112501284803100,0xxxxstxxx线性规划模型(LP)目标函数和约束条件都是线性的，这种优化模型称为是线性规划（linearprogramming,LP）模型。整数线性规划模型的实例例1某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表5－1：货物体积每箱（米3）重量每箱（百斤）利润每箱（百元）甲乙54252010托运限制2413问两种货物各托运多少箱，可使获得的利润为最大？解：设托运甲、乙两种货物x1，x2箱，用数学式可表示为：如果丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5,组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例：游泳队员的选拔问题甲乙丙丁戊蝶泳1’06”857”21’18”1’10”1’07”4仰泳1’15”61’06”1’07”81’14”21’11”蛙泳1’27”1’06”41’24”61’09”61’23”8自由泳58”653”59”457”21’02”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。目标函数若选择队员i参加泳姿j的比赛，记xij=1,否则记xij=00-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.4每种泳姿有且只有1人非线性规划：使用临时料场的情形使用两个临时料场A(5,1)，B(2,7).求从料场j向工地i的运送量为Xij，在各工地用量必须满足和各料场运送量不超过日储量的条件下，改建两个新料场，要同时确定料场的位置(xj,yj)和运送量Xij，在同样条件下使总吨千米数最小。组合优化（CombinatorialOptimization）组合最优化问题是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。例：旅行商问题（TSP,travelingsalemanproblem）一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij,如何选择一条道路使得商人每个城市走一遍后回到起点且所走路径最短。图论与网络流最短路问题最小生成树问题最大流问题匹配问题最小费用流问题（4）旅行售货问题有一个推销员，要到各个城市去推销产品，他希望能找到一个最短的旅遊途径，访问每一个城市，而且每个城市只拜訪一次，然后回到最初出发的城市。其它优化目标规划(多目标规划)动态规划对策论、决策论模糊优化随机规划随机规划：报童的诀窍问题报童售报：a(零售价)b(购进价)c(退回价)售出一份赚a-b；退回一份赔b-c每天购进多少份可使收入最大？每天需求量是随机的优化问题的目标函数应是长期的日平均收入每天收入是随机的建模•设每天购进n份，日平均收入为G(n)调查需求量的随机规律——每天需求量为r的概率f(r),r=0,1,2…准备nrnrrnfbarfrncbrbanG01)()()()])(()[()(求n使G(n)最大•已知售出一份赚a-b；退回一份赔b-c•一般地，对于最优化问题（1.1）的求解，是指在可行域内找一点，使得目标函数在该点取得极小值，即•这样的称为问题（1.1）的最优点，也称极小点，而相应的目标函数值称为最优值；合起来，称为最优解，但习惯上，把本身称为最优解．优化问题的求解满足所有约束的点（解）称为可行点．可行点的集合称为可行域．优化问题的求解方法（最优化方法）：（１）图解法（２）函数极值法：目标函数求导数（3）数值解法，初始值x0，迭代的方法，搜索最优解216472xxzMax以下为例：1212112501284803100,0xxxxstxxx线性规划模型(LP)１、图解法x1x20ABCDl1l2l3l4l55021xx48081221xx10031x0,21xx约束条件50:211xxl480812:212xxl1003:13xl0:,0:2514xlxl216472xxzMax目标函数Z=0Z=2400Z=3600z=c(常数)~等值线c在B(20,30)点得到最优解LINDO6.1２、Lindo软件求解但是，图解法和函数极值法都存在一定的局限性！（1）图解法，适合于2维情况，更高维的就难以表达；（2）函数极值法，通常高等数学中的求极值问题的变量个数一般不超过三个；当限制条件出现不等式，无论变量数多少，按经典极值方法求解根本无法解决．呼唤新的求解方法！~直到上世纪50年代最优化理论建立以及电子计算机的迅速发展才为求解各种最优化问题提供了雄厚的基础和有效手段。最优化问题的迭代解法（数值解法）！