数学建模-第四章-优化模型课件.pptx

1、第四章 优化模型优化问题的要素优化问题的要素优化目标控制变量(决策变量)限制条件(约束条件)历史上的优化问题历史上的优化问题古希腊的等周问题牛顿、莱布尼茨的实函数极值问题黄金分割比例在优选法中的使用4.1 4.1 优化优化模型的基本理论模型的基本理论有优化目标的问题优化模型确定优化目标、控制变量、限制条件控制变量是否连续控制变量是否函数目标和限制条件是否线性微积分优化方法变分法线性规划非线性规划是否是是否否4.1.14.1.1微积分优化方法微积分优化方法可微函数驻点、边界点极值，最值4.1.2.4.1.2.线性规划和整数规划模型线性规划和整数规划模型 软件 Excel、LINGO、LINDO，

2、Matlab 一般形式 解法 线性规划：图解、算法 整数规划：(隐式)枚举、分支定界1 122max ,nnzc xc xc x11 11221121 1222221 122,s.t.,nnnnmmmnnma xa xa xba xa xa xba xaxaxb0,1,2,0,1,2,.jixjnbim 4.1.3.4.1.3.非线性规划模型非线性规划模型 非线性最优化问题 基本理论 目前常用的方法：序列二次规划算法、内点法 软件：matlab的fmincon4.1.44.1.4变分优化模型变分优化模型定义：设 为函数类，若有法则，使在该法则之下，对 中的每一个元素都可以确定一个相应的数与之对

3、应，则称该法则为 上的一个泛函，记为 ，而函数类 称为泛函 的定义域.对比：函数极值 和 泛函极值MMM()J y xMJ固定端点的简单泛函极值问题固定端点的简单泛函极值问题101min ()(,)dxxJ y xF x y yx其中1001101()|(),(),yy xy xyy xy yC x xMEuler方程d0dyyFFx即0yxyyyyyFFF yF y泛函极值问题：附加条件泛函极值问题：附加条件 附加条件1 构造Lagrange函数 附加条件2 构造Lagrange函数10,(),()dxxG x y xy xxL*(,)(,)(,)Fx y yF x y yG x y y,(

4、),()0G x y xy x10*()(,)()(,)dxxJy xF x y yx G x y yx变分不等式变分不等式求 使得其中可以推得，这等价于*2()gyx M120inf()inf|()|dggyyJy xy xxMM1010011()|(),(),(),()()gf xf xC x xf xyf xyf xg xM1010011(),(),()g xC x xg xyg xy01()()0,()0()()()0 ()()0 u xg xuxu xg xuxu xu x4.2 4.2 微积分优化方法应用微积分优化方法应用4.2.1 4.2.1 等周长问题等周长问题问题:等周长的矩

5、形，什么情况下面积最大？设矩形的周长为 ，短边为，面积为等周长的矩形中，正方形面积最大 2LxA()Ax Lx2224LLAx 4.2.2 4.2.2 碳排放生产控制问题碳排放生产控制问题 一个企业生产某产品，收益与生产量成正比，比例系数为 。同时，生产过程产生碳排放，排放的多少与生产量成正比，比例系数 。如果碳排放超过许可，企业将面临高额罚款 或者缩小生产规模以控制碳排放在许可范围内 或者投资减排，投资费用与减排量的平方成正比，其比例系数为。制定最优的减排方案使得碳排放在许可范围内，并且收益最大，开销最小。4.2.2 4.2.2 碳排放生产控制问题碳排放生产控制问题模型假设模型假设 企业的生

6、产量为 ，企业的纯收益 与生产量成正比，生产排碳量 也与生产量成正比设减排量为 ，企业采取减排措施，消费资金 与减排量的平方成正比，即企业的排放量必须控制在 范围内，即xPC,PxcCxyB2ByQCyQ4.2.2 4.2.2 碳排放生产控制问题碳排放生产控制问题 总收益 最佳产量22max()APPBxcyxcxQ *222Qx4.2.2 4.2.2 碳排放生产控制问题碳排放生产控制问题 解读 最优点 ,碳排投资是必要的，扣除碳排费用，在碳排上限的限制下，企业可以获得更大的收益 最优生产量 与 有反比关系，企业增进生产技术，减少生产中碳排率可以有进一步扩大生产的空间，使得企业获益更大 最优生

7、产量 与 有反比关系，企业增进碳排技术，减少减排消耗率可以有进一步扩大生产的空间，使得企业获益更大 最优生产量 与 有正比关系，生产收益率始终是重要的*/xQ*x*x*x4.2.2 4.2.2 碳排放生产控制问题碳排放生产控制问题 推广 对模型参数进行检验 改进减排费用函数，比如二次函数 对参数进行敏感性分析 减排量的随机性 购买碳排放权利4.3 4.3 线性规划模型线性规划模型 罗马建设问题罗马建设问题 建罗马要耗人工与资金的比例是3小时:4两黄金；限制是每天人工1000小时，黄金800两。假定每天投入人工和资金分别为 ；目标函数是每天完成的工作,x yGmax34Gxy01000,0800

8、 xy4.3 4.3 线性规划模型线性规划模型 生产规划问题生产规划问题 一个工厂投资生产产品 A，B；每生产100吨产品A需要资金200万元，需要场地200平方米，可以获利300万元；投资生产产品B时，每生产100米产品B需要资金300万元，需要场地100平方米，可以获利200万元；可用资金1400万元，场地900平方米。该如何分配产品A，B的生产可使获利最大？又是多少？max32.29()2314(),0,zxystxyxyx yx y场地资金为整数4.3 4.3 线性规划模型线性规划模型 证券投资问题证券投资问题 某银行经理计划用一笔资金进行有价证券投资，可以购进的证券以及其信用等级、到

9、期年限、收益如下表所示。按照规定，市政证券的收益可以免税，其他证券的收益需要按50%的税率纳税。政府及代办机构的证券总共至少要购进400万元；所购证券的平均信用等级不超过1.4(信用等级数字越小，信用程度越高)；所购证券的平均到期年限不超过5年。若经理有1000万元资金，他应该如何操作投资才能收益最大？如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？4.3 4.3 线性规划模型线性规划模型证券名称证券名称证券种类证券种类信用等级信用等级到期年限到期年限到期税前收益到期税前收益(%)A市政294.3B代办机构2155.4C政府145.0D政府134.4E市政524.50,)

10、(5234159)(4.1522104s.t.045.0022.0025.0027.0043.0zmax54321543215432154321543215432143254321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx规划问题的一般形式及定义规划问题的一般形式及定义 目标 约束 决策变量 线性 和 非线性 整数规划12min/max()subject to()0,1,2,()0,1,2,(,),ijnnf xc ximh xjpxx xxR线性线性规划规划问题问题的解的解max32.29()2314(),0场地资金zxystxyxyx y(3.25,2.5

11、)工厂生产问题线性线性规划规划问题问题的解的解证券投资问题0,)(5234159)(4.1522104s.t.045.0022.0025.0027.0043.0zmax54321543215432154321543215432143254321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxf=-0.043 0.027 0.025 0.022 0.045;A=-0 1 1 1 0 oness(1,5)2 2 1 1 5-1.4*ones(1,5)9 15 4 3 2-5*ones(1,5);b=-4 10 0 0;lb=zeros(1,5);x,f v,f l a

12、g,o u t p u t,l a m b d a =linprog(f,A,b,lb)fv=-fvx,fv,flag,output,lambda=linprog(f,A,b,lb,options)lambda.ineqlin(2)if lambda.ineqlin(2)0.00275,fprintf(Loan and invest more!);end营养配餐问题营养配餐问题 一家食品公司按照特定的需求特定需求提供营养餐。每份配餐要求达到的最低营养标准为：热量2860卡，蛋白质80克，铁15毫克，烟酸20毫克，维生素A达到20000单位。该食品公司应该如何配餐才能使套餐满足营养标准的情况下价

13、格最低？食材食材单价单价(元元/50g)热量热量蛋白质蛋白质(克克)铁铁(毫克毫克)烟酸烟酸(毫克毫克)维生素维生素A牛肉牛肉2.030926.03.14.1 面包面包0.32760.60.60.9 胡萝卜胡萝卜0.1428.50.60.412000鸡蛋鸡蛋0.316212.82.70.31140鱼鱼1.818226.20.810.5 营养配餐问题营养配餐问题设食材每50毫克为一个单位，配餐包含牛肉、面包、胡萝卜、鸡蛋、鱼各 个单位.0,20000114012000205.103.04.09.01.4158.07.26.06.01.3802.268.125.86.026286018216242

14、276309s.t.8.13.01.03.00.2min54321435432154321543215432154321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxz12345,x x x x xf=2.0 0.3 0.1 0.3 1.8;A=309 276 42 162 182 26 0.6 8.5 12.8 26.2 3.1 0.6 0.6 2.7 0.8 4.1 0.9 0.4 0.3 10.5 0 0 12000 1140 0;b=2860 80 15 20 20000;lb=zeros(5,1);A(5,:)=A(5,:)/10000;b(5)=b(5)/1000

15、0;x,fv,flag=linprog(f,-A,-b,lb)篮球队选拔篮球队选拔 一个篮球教练挑选5名篮球队员组成篮球队上场阵容，目前有7名候选队员。教练如何在下面的条件下挑选队员，使得篮球队总体投篮命中率最高？平均身高不低于1.82米；平均弹跳高度不低于0.90米；平均百米成绩不低于12秒；平均体重不低于94公斤；场上需要有前锋、中锋、后卫各2,1,2名;队员M2和M6都是新进队的球员,配合不是很默契,最好不要同时上场。篮球队选拔篮球队选拔队员队员身高身高(米米)弹跳高度弹跳高度(米米)命中率命中率(%)百米成绩百米成绩(秒秒)体重体重(公斤公斤)位置位置M11.860.9559.611.

16、7104中锋、前锋M21.820.9762.212.194前锋M31.790.9159.411.993中锋、后卫M41.780.8960.311.087后卫M51.910.8458.712.8105前锋M61.940.8160.112.7103中锋、前锋M71.761.0264.311.386中锋、后卫iix7,2,1i0,1ixiiihiHisitiw记第 名队员的入选变量为 ，表示第 名队员的入选与不入选。记第 名队员的身高为 ，弹跳高度为 ，命中率为 ，百米成绩为 ，体重为 。7,2,1,1,0)5(5)M6M2,(1)2(2)1(1)2(2)(945)(125)(90.05)(82.1

17、5s.t.)(max716274373165217171717171ixxxxxxxxxxxxxxxwxtxHxhxsiiiiiiiiiiiiiiiiii名队员挑选不同时上个后卫个中锋个前锋体重百米成绩弹跳高度身高命中率整数规划的分支定界算法整数规划的分支定界算法.,143292s.t.23max为正整数yxyxyxyxz)5.2,25.3(B为正整数和为正整数yxxyxyxyxzyxxyxyxyxz,25.3143292s.t.23max,25.3143292s.t.23max)1,4()38,3(分支定界法的两个策略：1.分支(取整)2.定界(最优值、可行性)护士值班问题护士值班问题 某医

18、院需要重新安排护士值夜班，每个护士连续值5个夜班，休息两天，周而复始。据统计，每天晚上(周一到周日)需要值班的护士人别最少为18，16，15，16，19，14，12人。如何安排值夜班的护士，可使得值夜班护士人数达到最少？设从周 (代表周一到周日)开始值班的护士人数为i7,2,1iix 护士值班问题护士值班问题为非负整数7654321765436543254321743217632176521765417654321,12 14 19 16 15 16 18 s.t.minxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxwarning off;v

19、b=input(number of nurses each day);A =toeplitz(1 1 1 1 1 0 0,1 0 0 1 1 1 1);x,optv=bnb(ones(7,1),-A,-vb,zeros(7,1);clc;fprintf(n your original data:n);fprintf(%6.0f,vb);fprintf(n we need so many nurses each day:n);fprintf(%6.0f,x);fprintf(nTotal number is:%6.0fn,sum(x);规划问题的规划问题的LINGOLINGO解解法法 生产规划问

20、题max32.29()2314(),0,zxystxyxyx yx y场地资金为整数Model:!product problem;max=3*x+2*y;2*x+y=9;2*x+3*y=require(i);end 规划问题的规划问题的LINGOLINGO解解法法护士值班问题为非负整数7654321765436543254321743217632176521765417654321,12 14 19 16 15 16 18 s.t.minxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxmodel:!每天需值班护士和每天开始值班的护士数量;set

21、s:days/mon,tue,wed,thu,fri,sat,sun/:need,start;endsets min=sum(days:start);for(days(i):sum(days(j)|(j#GT#i+2)#OR#(j#LE#I#AND#j#GT#I-5):START(j)=NEED(i););for(days:gin(start);data:need=18,16,15,16,19,14,12;enddataend4.4.14.4.1 非线性规划：工地运输非线性规划：工地运输某建筑公司有某建筑公司有6个建筑工地，每个工地的个建筑工地，每个工地的位置位置(用平面坐标用平面坐标 表表示

22、示，单位：，单位：千米千米)及及水泥日水泥日用量用量 (单位单位：吨吨)由由下表给出。目前有下表给出。目前有两个临时料场两个临时料场位于位于 ，日储量各有日储量各有20吨，假设各料场到各工吨，假设各料场到各工地之间均有直线道路相连，且假设运费与运输量及运输里程成正地之间均有直线道路相连，且假设运费与运输量及运输里程成正比比。),(iibaid)7,2(),1,5(21LL工地编号工地编号123456工地位置工地位置 1.258.750.55.7537.25工地位置工地位置 1.250.754.7556.57.25水泥需求量水泥需求量 3547611iaibid4.4.14.4.1 非线性规划：

23、工地运输非线性规划：工地运输(1)请制定每天的供应计划，即从请制定每天的供应计划，即从 两个料场出发分别应向各个工地两个料场出发分别应向各个工地运送多少吨水泥，可以使得总运费最小运送多少吨水泥，可以使得总运费最小?(2)为了进一步降低总运费，该建筑公司打算舍弃原有的两个临时为了进一步降低总运费，该建筑公司打算舍弃原有的两个临时料场，改建新址但保持日储量不变，请建立数学模型，给出合理料场，改建新址但保持日储量不变，请建立数学模型，给出合理的选址方案的选址方案?假设料场 位置为 ，它向工地 运输水泥 吨，记每运输1吨水泥1千米的费用为1个单位，则总费用最小的规划问题可表示为:j),(jjqpiij

24、x)(0)(2,1 ,20)(6,2,1,s.t.)()()(min6121216122自然约束日存储量日需求量总运费ijiijjiijjiijijijxjxidxbqapxz4.4.14.4.1 非线性规划：工地运输非线性规划：工地运输变量的重新规划、解的可视化6543216212612111100000100000010000010000001000001000000100000100000010000010000001000001ddddddxxxxx20201111110000000000001111116212612111xxxxx02468100123456780246810012

25、345678save 46.0246 ton*km4.4.2 4.4.2 奇怪的骰子奇怪的骰子四支球队，他们可能发挥出的水平A(6,6,2,2,2,2),B(5,5,5,1,1,1),C(4,4,4,4,0,0),D(3,3,3,3,3,3)假设任一球队的6个不同水平等可能出现。你会选择哪支球队?.32)DC(P)CB(P)BA(P)AD(PEfron骰子4.4.2 4.4.2 奇怪的奇怪的骰子骰子:其它例子其它例子8163574923个骰子互胜的概率是5/9互胜的概率最大能达到多少呢？4.4.2 4.4.2 奇怪的奇怪的骰子骰子-最大概率规划模型最大概率规划模型 假设我们有 个骰子，每个骰子

26、有 个面，第 个骰子的第 个面点数为 ，掷出该点的概率为 ,其中，,.dfijidj)1(),(jipdi 1fj 1df j=1 j=2 j=3 j=4i=114710i=225811i=3369123个骰子每个个骰子每个4面的点数设置面的点数设置4.4.2 4.4.2 奇怪的骰子奇怪的骰子-最大概率规划模型最大概率规划模型不同不同的骰子数目及面数互胜概率的骰子数目及面数互胜概率fjdijipdijippkdpjpdipkipjippfjfjjkfjjk,2,1,2,1 ,0),(,2,1 ,1),(,),(),1(,2,1 ,),1(),(s.t.max111111fd=3d=4d=5d=

27、6d=7d=8 d=9d=10d=11d=1220.61800.66670.69200.70710.71690.7236 0.72840.73210.73480.737030.61800.66670.69200.70710.71690.7236 0.72840.73210.73480.737040.61800.66670.69200.70710.71690.7236 0.72840.73210.73480.737050.61800.66670.69200.70710.71690.7236 0.72840.73210.73480.73704.4.3 4.4.3 关灯游戏问题关灯游戏问题 一个n行

28、n列的灯阵，每个灯都带着一个奇怪的开关：按下开关时，不仅本来位置上的灯会改变状态由亮变灭或者由灭变亮，它上下左右相邻的灯，如果有的话，也会同时改变状态。4.4.3 4.4.3 关灯游戏问题关灯游戏问题 性质性质1：灯阵从一个最初的状态变成任何一种状态，这个最终状态只和每个开关按下的次数有关，而与这个开关按下的次序无关。按下开关(2,1),(3,1),(2,1)和按下开关(3,1),(2,1),(2,1)是可以把灯阵从相同的初始状态变成相同的最终状态。性质性质2：每个灯的最终状态只和它的初始状态及它本身及上下左右相邻的开关所按下总次数的奇偶性相关。每个开关至多按一次。4.4.3 4.4.3 关灯

29、游戏问题关灯游戏问题第 行第 列的开关按下的次数为 是一个0-1变量。如果(1,1)灯改变了状态，则 是一个奇数:(2，2)灯规划问题ij1,0ijx211211xxx1211211211mxxx12223223222112mxxxxx2,1,01,0,2,1,12s.t.min1|,ijijjlikijkljiijmxnjimxx4.4.3 4.4.3 关灯游戏问题关灯游戏问题 如果不要求次数最少：2阶的例子1 1 1 1 222112222111221211211211xxxxxxxxxxxx1 0 0 1 22211222122221211211xxxxxxxxxx1 0 0 1 212

30、2212212211211xxxxxxxx1 1 0 1 22212212211211xxxxxxx122211211xxxx4.4.4 4.4.4 零件生产零件生产正品优化问题正品优化问题l一种产品由零件A，B组成l零件A与零件B的参数 是独立的均匀分布的随机变量l产品的参数 的目标值是1l 当产品参数值的偏差 小于 =0.01时是正品l 偏差大于 而小于 =0.02时是次品l 偏差大于 时是废品l 正品的市场单价 元，次品的市场单价是 元，不计加工费的各种成本折算后每件产品成本为 元。l标定值 ，相对精度 ，最大偏差 ；l每个零件的加工费用与相对加工精度成反比，系数是常数Cl每月的原材料量

31、是固定的，当C=0.833292时，求最佳标定值及加工精度，使得平均利润最大，求其时的正品率和次品率l当C为什么值时，该产品的平均利润为零？0,YXXYYXfZ),(1Z1r1r2r2r4000P13000P22000P300,0XY10 k00,kXkY4.4.4 4.4.4 零件生产正品优化问题零件生产正品优化问题 设零件A的标定值为，若加工精度为，则零件参数 是区间 上的均匀分布。同样有零件B分布方式。正品率、次品率和废品率0 xkX,0000kxxkxx2211|1|2|1|1|1|0dd1 ,dd1 ,dd1rZrZrrZyxSpyxSpyxSp0000dd410020kyykyyb

32、axyyxkp000000000000d ddd410022kyykyyfkxxkyykyykxxexyxyyxkp)./)1(,min(),/)1(,max(100100yrkxxbyrkxxa),/)1(,min(,max(20000yrkxxkxxe)./)1(,max(,min(20000yrkxxkxxf4.4.4 4.4.4 零件生产正品优化问题零件生产正品优化问题 售价期望值-成本记要求利润平均值为0相当于：求根问题割线法(二分法)最大平均利润为1694.5，该值可于 ，处得到；而此时 ，。当 时，最大平均利润为零。)/22000(30004000 max10kcpp)/2200

33、0(30004000);,(1000kcppCkyxF);,(max)(00,00CkyxFCGkyx9740.00 x0267.10y0060.0k%22.970p%7788.21p02p5055.9C4.4.54.4.5 网络流网络流问题问题 要从点1出发，运送10吨货物A和10吨货物B到点16 如何设计运输方案运费最省?道路道路路口路口运量运量上限上限(吨吨)长度长度(公里公里)道路道路路口路口运量运量上限上限(吨吨)长度长度(公里公里)11,2113131,312422,5510143,76435,1044157,133443,463162,46454,658174,88566,114

34、4188,146477,843195,63488,956206,93499,1264219,15241013,14322210,11331114,15832311,12641215,161042412,16124dx3costA xdB231cost 4.4.54.4.5 网络流网络流问题问题100000000000100000000000000100000000110000000000000000100000011000000000000000000100001000000000110000000000000100000000011000000000000000100000001000000

35、000000000000100000110000000000110000000000000110000000011000000000000000110000001000000000011000000000000110000000001000000000000000110000000011000000000011000000000000011000000001000000000001000000000000011000000000001000000000001E第2条边连接节点2,54.4.54.4.5 网络流问题网络流问题4.9363.10371.10240.937311.10240.1742

36、33.87752.08280.975913.98440.364593.63540.651933.34311.39213.60791.65373.95550.534511.47046.52961.47046.87932.23495.0646.89631.18644.81360.534511.47043.83372.16636.73530.264725.99515.2565e-0110.763080.611311.11210.349750.764471.10240.174231.4673.80963.12077.7651 0,024,1,s.t.313min2412yxsEysExiwyxydxd

37、iiiiiiii4.4.6 4.4.6 应急设施配置问题应急设施配置问题 问题描述问题描述 里奥兰翘(Rio Rancho)镇至今还没有自己的应急设施，1986年该镇得到了建立两个应急设施的拨款，每个设施都有救护站、消防队和警所。应急事件的次数 北边L形障碍,南边有浅水塘的公园 应急车辆驶过南北向的街道平均要花费15秒;应急车辆通过东西向的街道平均花费20秒 现在需要确定这两个应急设施的位置，使得总响应时间最小。假定需求集中在每个街区的中心，而应急设施位于街角处。4.4.6 4.4.6 应急设施配置问题应急设施配置问题 模型模型假设假设 两个应急设施的功能完全相同 有应急事件出现，只需从最近地

38、点派出 假设应急事件频度很低，不出现从一个处理现场奔赴另一个的情景4.4.6 4.4.6 应急设施配置问题应急设施配置问题 街区中心坐标 从位置 到街区中心的时间 若应急设施设在 响应时间为 最小化按照频度加权的总响应时间)5.0,5.0(ji),(YX)5.0|5.0(|20)5.0|5.0(|15),(jYiXjiYXt),(),(2211YXYX),(),(min(),(22112211jiYXtjiYXtjiYXYXRijijjiYXYXRpT),(22114.4.6 4.4.6 应急设施配置问题应急设施配置问题 应急事件可以发生在任一点 管辖范围的分割:垂直平分线作为界限 应急设施的

39、位置:重心4.4.6 4.4.6 应急设施配置问题应急设施配置问题算法算法(应急设施的放置)给定需要放置的应急设施数目;设定 个随机的应急设施位置 ,;迭代指标 ;循环循环如下操作 以 为应急设施点，划分出每个应急设施点的辖区 求出每个辖区的重心 令 ,直到直到 NN),(00kkYXNk,2,10i1 ii),(11ikikYX),(11ikikVU)(111ikikikikXUXX)(111ikikikikYVYY|)|,(|max11ikikikikkYYXX4.4.6 4.4.6 应急设施配置问题应急设施配置问题算法算法(应急设施的辖区)给定某个应急设施点 ，记其他应急设施点离它最近者

40、为 记 ,进行如下循环：循环如下操作 对所有不为 的点 ，1找出所有 的垂直平分线与 的垂直 平分线的交点；2 找出这些交点离 线段中点(逆时针方向)最近 者，记下其对应的 3 直到),(00YX),(11YX1p),(),(00ppYXYX),(kkYX),(),(00ppYXYX),(),(00kkYXYX),(),(00ppYXYXkk*1k4.4.6 4.4.6 应急设施配置问题应急设施配置问题4.5 4.5 变分变分优化优化:等周问题等周问题 黛朵用牛皮圈地，她很聪明地以海岸为一边，用牛皮条圈了一个半圆，如果牛皮条长L 用变分方法来计算一下她圈出来的最大面积。设固定点为坐标原点，海岸

41、线为x轴，海岸线上假定离原点为a,牛皮条形状为y(x)，可导 有y(0)=0，y(a)=0。0max().ay x dx201+()ayx dxL，1()|(0,),(0)0,()0,y x yCayy a4.5 4.5 变分优化变分优化:等周问题等周问题 Euler-Lagrange方程 模型求解 圆 定解0max().ay x dx201+()ayx dxL，1()|(0,),(0)0,()0,y x yCayy a210,1dydxy22112221=1xCyxCyxCy或，22212+.xCyC12=,0,.22aaCC22=.2LLa，最大面积4.5 4.5 变分优化变分优化:磨刀不

42、误砍柴工磨刀不误砍柴工 固定时间0到T 砍柴的速度为 ，特点：磨刀时为0，砍柴时是时间 的下降函数，如 c是刀磨钝的速度 磨完刀后回到最快速度。简化问题，假定时间0到T内只磨一次刀 什么时候磨刀?假设磨刀时间为 .磨刀间隔 固定。()x tt0()ctx tx e0 x00(,)(0,)t tdTd4.5 4.5 变分优化变分优化:磨刀不误砍柴工磨刀不误砍柴工0max()TGx t dt00000()00,if(0,),()0,if ,if(,),ctc t tdx ettx ttt tdx ettd T00000()()000000()dd=(1)(1)tTc t tdctc T tdctt

43、dxxG tx etx eteecc砍柴量00()00()()0 ctc T tdG tx ee可得0*2Tdt磨刀的砍柴量()0202(*)(1)c T dxG tec不磨刀砍柴量0()(1)cTxG Tec可得磨刀时间满足0(*)()G tG T21+0ln2cTedTTc4.5.2 4.5.2 路径变分路径变分优化优化:直线直线 条条道路通罗马,哪一条最近?站在坐标原点(0,0)，设罗马的坐标为 ,连线函数是 .容许函数集合(1,)a()yf x()(0)0,(1)f xffa 连续可微，并且 建模120min 1+()dDfxx()*()()f xfxx其中(0)(1)0120()1+

44、(*()()Dfxxdx112220030,1*()()*()()*()()()1+*()1+*()1+*()xfxxfxxfxxDdxdxfxfxfx可得*()0fx 4.5.2 4.5.2 路径变分优化路径变分优化:绕绕山山 山:距离AB 最短路线满足 最短路线(),yh x(0)(1)0,hh()0.h x2122222121122(,)()1()(1)()xxd x xxhxhx dxxhx211112211222222222()()1()0,()1()()1()0,(1)()xh x h xhxxhxxh x h xhxxhx 121212()()(),()1h xh xh xh x

45、xx 11112222(),(0,),()(),(,),(),(,1).1当当当h xxxxxf xh xxx xh xxxxx4.5.2 4.5.2 路径变分优化路径变分优化:绕山绕山一般性解法:允许函数集合求等价于 寻找1()|()0,1,(0)0,(1)1,()(),f xf xCfff xg x1M=1*20()inf1()dyJ yxyxyM1()0,1f xC()()0,()0,()()()0,(0)0,(1)1.f xg xfxf xg xfxff4.5.2 4.5.2 路径变分优化路径变分优化:航渡航渡 在去罗马的路上有海峡要航渡 最近的路径可以理解成用时最短的路 设海路所耗的

46、时间时陆路的3倍 如何横渡?水流常数 航渡曲线 登陆点 目的地(0,0)Ac()f x(1,)a(2,1)4.5.2 4.5.2 路径变分优化路径变分优化:航渡航渡 1220min 31+()1(2(1)Dfxcdxf变分优化()0fx 122031+()1(2)Dacdxa22d23 1+()0d1(2)Daacaa应用2,c2.847a4.5.2 4.5.2 路径变分优化路径变分优化:球面模型球面模型半径为1的球面，起点(0,1,0),终点方位角 ，仰角路线2(,1,0)aat()f t(),(),()sin()sin,sin()cos,cos(),0,arcsin fffxtytztf

47、ttf ttf ttaarcsin2220arcsin222222220arcsin220()()()cos()sincos()cossin()cos()sin()()sin()()afffaaDxtytzt dtf ttf ttf tf tf tft dtf tft dt()0ft(0)(arcsin)/2ffa因此()/2f t4.5.3 4.5.3 生产安排优化生产安排优化 甲和乙签订合同，在规定时间里向乙提供定额商品 不能提前或滞后，总费用最低 原材料成本(常数),等待生产期间有储存费用 生产费用 生产基本费用(固定值)生产速度费用(生产率的函数,和生产率成正比)储存费用(产品交付前的

48、储存费用，正比于产量)碳排费用(生产产品要消耗减排费用，正比于产量平方)4.5.3 4.5.3 生产安排优化生产安排优化 合同生效时间为 ，产品交付日为 ，合同规定的产品量为，时间 时的成品数为 ，该时的生产率为 ，假定原材料随买随用，原材料储存费用为0 原材料成本费和生产基本费为常数，合并记为 生产费用 ，与 成正比 费用：生产 存储 碳排放 0ttTQt()x t()ux t(0)0,().xx TQc()f u()f uu(),(0)0,f uuf2()()()2F tf x tx t()(),G tx t2()(),2K tx t4.5.3 4.5.3 生产安排优化生产安排优化总费用E

49、uler方程解具体例子 0220()()()()()().22TTZF tG tK t dtcx tx tx tdtc22d0,dxxt/12(),ttx tC eC e /12/(1)(1),.tttttteQeQCCeeee 1,1,1,ln2,4TQ()321.ttx tee4.6.4.6.优化计算方法：遗传算法优化计算方法：遗传算法 遗传算法(Genetic Algorithm)模拟达尔文进化论的自然选择、遗传和变异现象 编码 对应 染色体(基因型)一定数量的近似解 对应 种群 算法产生新的近似解 对应 遗传/变异 保留较优解(适应度函数)对应 优胜劣汰 近似解集合的更新 对应 种群代

50、际更替4.6.4.6.优化计算方法：优化计算方法：TSPTSP 旅行售货商问题，TSP问题(Travelling Salesman Problem)给定 个城市的坐标 ，寻找旅行售货商的一个旅行计划即需要找到1到 的一个排列 ，使得旅行售货商的总行程最短：N),(iiyxNi,2,1NN,21Niiiiiyxyxd1),(),(min114.6.4.6.优化计算方法：遗传算法优化计算方法：遗传算法 TSP问题编码)6,2,7,5,1,4,3(2)7,3,6,5,2,4,1(1PP(1,4,1,5,7,2,6)简单交叉交叉后按序排列(3,2,1,5,7,4,6)变异(3,2,1,7,5,4,6)