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

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

2、化问题基本理论目前常用的方法：序列二次规划算法、内点法软件：matlab的fmincon4.1.4变分优化模型定义：设 为函数类，若有法则，使在该法则之下，对 中的每一个元素都可以确定一个相应的数与之对应，则称该法则为 上的一个泛函，记为 ，而函数类 称为泛函 的定义域.对比： 函数极值 和 泛函极值固定端点的简单泛函极值问题其中Euler方程即泛函极值问题：附加条件附加条件1 构造Lagrange函数附加条件2构造Lagrange函数变分不等式求 使得其中可以推得，这等价于4.2 微积分优化方法应用4.2.1 等周长问题问题: 等周长的矩形，什么情况下面积最大？设矩形的周长为 ，短边为 ，面

3、积为等周长的矩形中，正方形面积最大 4.2.2 碳排放生产控制问题一个企业生产某产品，收益与生产量成正比，比例系数为 。同时，生产过程产生碳排放，排放的多少与生产量成正比，比例系数 。如果碳排放超过许可，企业将面临高额罚款或者缩小生产规模以控制碳排放在许可范围内或者投资减排，投资费用与减排量的平方成正比，其比例系数为。制定最优的减排方案使得碳排放在许可范围内，并且收益最大，开销最小。4.2.2 碳排放生产控制问题模型假设 企业的生产量为 ，企业的纯收益 与生产量成正比，生产排碳量 也与生产量成正比设减排量为 ，企业采取减排措施，消费资金 与减排量的平方成正比，即企业的排放量必须控制在 范围内，

4、即4.2.2 碳排放生产控制问题总收益最佳产量4.2.2 碳排放生产控制问题解读最优点 ,碳排投资是必要的，扣除碳排费用，在碳排上限的限制下，企业可以获得更大的收益最优生产量 与 有反比关系，企业增进生产技术，减少生产中碳排率可以有进一步扩大生产的空间，使得企业获益更大最优生产量 与 有反比关系，企业增进碳排技术，减少减排消耗率可以有进一步扩大生产的空间，使得企业获益更大最优生产量 与 有正比关系，生产收益率始终是重要的4.2.2 碳排放生产控制问题推广对模型参数进行检验改进减排费用函数， 比如二次函数对参数进行敏感性分析减排量的随机性购买碳排放权利4.3 线性规划模型罗马建设问题 建罗马要耗

5、人工与资金的比例是3小时:4两黄金； 限制是每天人工1000小时，黄金800两。假定每天投入人工和资金分别为 ；目标函数是每天完成的工作4.3 线性规划模型生产规划问题 一个工厂投资生产产品 A，B；每生产100吨产品A需要资金200万元，需要场地200平方米，可以获利300万元；投资生产产品B时，每生产100米产品B需要资金300万元，需要场地100平方米，可以获利200万元；可用资金1400万元，场地900平方米。该如何分配产品A，B的生产可使获利最大？又是多少？ 4.3 线性规划模型证券投资问题 某银行经理计划用一笔资金进行有价证券投资，可以购进的证券以及其信用等级、到期年限、收益如下表

6、所示。按照规定，市政证券的收益可以免税，其他证券的收益需要按50%的税率纳税。政府及代办机构的证券总共至少要购进400万元；所购证券的平均信用等级不超过1.4(信用等级数字越小，信用程度越高)；所购证券的平均到期年限不超过5年。若经理有1000万元资金，他应该如何操作投资才能收益最大？如果能够以2.75%的利率借到不超过100万元资金，该经理应如何操作？4.3 线性规划模型证券名称证券种类信用等级到期年限到期税前收益(%)A市政294.3B代办机构2155.4C政府145.0D政府134.4E市政524.5规划问题的一般形式及定义目标约束决策变量线性 和 非线性整数规划线性规划问题的解工厂生产

7、问题线性规划问题的解证券投资问题f = - 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,fv,flag,output,lambda = 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.002

8、75, fprintf(Loan and invest more!);end营养配餐问题一家食品公司按照特定的需求特定需求提供营养餐。每份配餐要求达到的最低营养标准为：热量2860卡，蛋白质80克，铁15毫克，烟酸20毫克，维生素A达到20000单位。该食品公司应该如何配餐才能使套餐满足营养标准的情况下价格最低？食材单价(元/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

9、毫克为一个单位，配餐包含牛肉、面包、胡萝卜、鸡蛋、鱼各 个单位.f = 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) / 10000; x,fv,flag = linprog(f,-A,-b,lb)篮球队选拔一个篮球教练挑选5名篮球队员组成篮球队上

10、场阵容，目前有7名候选队员。教练如何在下面的条件下挑选队员，使得篮球队总体投篮命中率最高？平均身高不低于1.82米；平均弹跳高度不低于0.90米；平均百米成绩不低于12秒；平均体重不低于94公斤；场上需要有前锋、中锋、后卫各2,1,2名; 队员M2和M6都是新进队的球员, 配合不是很默契, 最好不要同时上场。篮球队选拔队员身高(米)弹跳高度(米)命中率(%)百米成绩(秒)体重(公斤)位置M11.860.9559.611.7104中锋、前锋M21.820.9762.212.194前锋M31.790.9159.411.993中锋、后卫M41.780.8960.311.087后卫M51.910.84

11、58.712.8105前锋M61.940.8160.112.7103中锋、前锋M71.761.0264.311.386中锋、后卫记第 名队员的入选变量为 ， 表示第 名队员的入选与不入选。记第 名队员的身高为 ，弹跳高度为 ，命中率为 ，百米成绩为 ，体重为 。整数规划的分支定界算法分支定界法的两个策略：分支(取整)定界(最优值、可行性)护士值班问题某医院需要重新安排护士值夜班，每个护士连续值5个夜班，休息两天，周而复始。据统计，每天晚上(周一到周日)需要值班的护士人别最少为18，16，15，16，19，14，12人。如何安排值夜班的护士，可使得值夜班护士人数达到最少？设从周 ( 代表周一到周

12、日)开始值班的护士人数为 护士值班问题warning off; vb = 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

13、is : %6.0fn,sum(x); 规划问题的LINGO解法生产规划问题Model:!product problem;max = 3*x+2*y;2*x + y = 9;2*x + 3*y =require(i);end规划问题的LINGO解法护士值班问题model:!每天需值班护士和每天开始值班的护士数量; sets: 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#

14、 j#GT#I-5): START(j) = NEED(i); ); for(days: gin(start); data: need = 18,16,15,16,19,14,12; enddataend4.4.1 非线性规划：工地运输某建筑公司有6个建筑工地，每个工地的位置(用平面坐标 表示，单位：千米)及水泥日用量 (单位：吨)由下表给出。目前有两个临时料场位于 ，日储量各有20吨，假设各料场到各工地之间均有直线道路相连，且假设运费与运输量及运输里程成正比。工地编号123456工地位置 1.258.750.55.7537.25工地位置 1.250.754.7556.57.25水泥需求量 3

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

16、3,3,3,3,3,3)假设任一球队的6个不同水平等可能出现。你会选择哪支球队?Efron骰子4.4.2 奇怪的骰子: 其它例子8163574923个骰子互胜的概率是5/9互胜的概率最大能达到多少呢？4.4.2 奇怪的骰子-最大概率规划模型假设我们有 个骰子，每个骰子有 个面，第 个骰子的第 个面点数为 ，掷出该点的概率为 , 其中， , . dfj=1j=2j=3j=4i=114710i=225811i=3369123个骰子每个4面的点数设置4.4.2 奇怪的骰子-最大概率规划模型不同的骰子数目及面数互胜概率fd=3d=4d=5d=6d=7d=8d=9d=10d=11d=1220.61800

17、.66670.69200.70710.71690.72360.72840.73210.73480.737030.61800.66670.69200.70710.71690.72360.72840.73210.73480.737040.61800.66670.69200.70710.71690.72360.72840.73210.73480.737050.61800.66670.69200.70710.71690.72360.72840.73210.73480.73704.4.3 关灯游戏问题一个n行n列的灯阵，每个灯都带着一个奇怪的开关：按下开关时，不仅本来位置上的灯会改变状态由亮变灭或者由灭

18、变亮，它上下左右相邻的灯，如果有的话，也会同时改变状态。4.4.3 关灯游戏问题性质1：灯阵从一个最初的状态变成任何一种状态，这个最终状态只和每个开关按下的次数有关，而与这个开关按下的次序无关。按下开关(2,1),(3,1),(2,1)和按下开关(3,1), (2,1),(2,1)是可以把灯阵从相同的初始状态变成相同的最终状态。性质2：每个灯的最终状态只和它的初始状态及它本身及上下左右相邻的开关所按下总次数的奇偶性相关。每个开关至多按一次。4.4.3 关灯游戏问题第 行第 列的开关按下的次数为 是一个0-1变量。如果(1,1)灯改变了状态，则 是一个奇数: (2，2)灯规划问题4.4.3 关灯

19、游戏问题如果不要求次数最少：2阶的例子4.4.4 零件生产正品优化问题一种产品由零件A，B组成零件A与零件B的参数 是独立的均匀分布的随机变量产品的参数 的目标值是1当产品参数值的偏差 小于 =0.01时是正品偏差大于 而小于 =0.02时是次品偏差大于 时是废品正品的市场单价 元，次品的市场单价是 元，不计加工费的各种成本折算后每件产品成本为 元。标定值 ，相对精度 ，最大偏差 ；每个零件的加工费用与相对加工精度成反比，系数是常数C每月的原材料量是固定的，当C=0.833292时，求最佳标定值及加工精度，使得平均利润最大，求其时的正品率和次品率当C为什么值时，该产品的平均利润为零？4.4.4

20、 零件生产正品优化问题设零件A的标定值为 ，若加工精度为 ，则零件参数 是区间 上的均匀分布。同样有零件B分布方式。正品率、次品率和废品率4.4.4 零件生产正品优化问题 售价期望值 - 成本记要求利润平均值为0相当于：求根问题割线法(二分法)最大平均利润为1694.5，该值可于 ， ， 处得到；而此时 ， ， 。当 时，最大平均利润为零。4.4.5 网络流问题要从点1出发，运送10吨货物A和10吨货物B到点16如何设计运输方案运费最省?道路路口运量上限(吨)长度(公里)道路路口运量上限(吨)长度(公里)11,2113131,312422,5510143,76435,1044157,13344

21、3,463162,46454,658174,88566,1144188,146477,843195,63488,956206,93499,1264219,15241013,14322210,11331114,15832311,12641215,161042412,161244.4.5 网络流问题第2条边连接节点2,54.4.5 网络流问题4.4.6 应急设施配置问题问题描述 里奥兰翘(Rio Rancho)镇至今还没有自己的应急设施，1986年该镇得到了建立两个应急设施的拨款，每个设施都有救护站、消防队和警所。应急事件的次数北边L形障碍, 南边有浅水塘的公园应急车辆驶过南北向的街道平均要花费1

22、5秒; 应急车辆通过东西向的街道平均花费20秒现在需要确定这两个应急设施的位置，使得总响应时间最小。假定需求集中在每个街区的中心，而应急设施位于街角处。4.4.6 应急设施配置问题模型假设 两个应急设施的功能完全相同有应急事件出现，只需从最近地点派出假设应急事件频度很低，不出现从一个处理现场奔赴另一个的情景4.4.6 应急设施配置问题街区中心坐标从位置 到街区中心的时间若应急设施设在响应时间为最小化按照频度加权的总响应时间4.4.6 应急设施配置问题应急事件可以发生在任一点管辖范围的分割: 垂直平分线作为界限应急设施的位置: 重心4.4.6 应急设施配置问题算法(应急设施的放置)给定需要放置的

23、应急设施数目 ; 设定 个随机的应急设施位置 , ; 迭代指标 ; 循环如下操作 以 为应急设施点， 划分出每个应急设施点的辖区 求出每个辖区的重心 令 , 直到 4.4.6 应急设施配置问题算法(应急设施的辖区)给定某个应急设施点 ，记其他应急设施点离它最近者为 记 ,进行如下循环：循环如下操作 对所有不为 的点 ， 1找出所有 的垂直平分线与 的垂直 平分线的交点； 2 找出这些交点离 线段中点(逆时针方向)最近 者，记下其对应的 3 直到4.4.6 应急设施配置问题4.5 变分优化: 等周问题黛朵用牛皮圈地，她很聪明地以海岸为一边，用牛皮条圈了一个半圆，如果牛皮条长L用变分方法来计算一下

24、她圈出来的最大面积。设固定点为坐标原点，海岸线为x轴，海岸线上假定离原点为a, 牛皮条形状为y(x)，可导有y(0)=0，y(a)=0。4.5 变分优化: 等周问题Euler-Lagrange方程模型求解圆定解4.5 变分优化: 磨刀不误砍柴工固定时间0到T砍柴的速度为 ，特点：磨刀时为0，砍柴时是时间 的下降函数，如 c是刀磨钝的速度磨完刀后回到最快速度 。简化问题，假定时间0到T内只磨一次刀什么时候磨刀? 假设磨刀时间为 . 磨刀间隔 固定。4.5 变分优化: 磨刀不误砍柴工砍柴量可得磨刀的砍柴量不磨刀砍柴量可得磨刀时间满足4.5.2 路径变分优化:直线条条道路通罗马,哪一条最近?站在坐标

25、原点(0,0)，设罗马的坐标为 ,连线函数是 .容许函数集合建模其中可得4.5.2 路径变分优化:绕山山:距离AB 最短路线满足最短路线4.5.2 路径变分优化:绕山一般性解法: 允许函数集合求等价于 寻找4.5.2 路径变分优化:航渡在去罗马的路上有海峡要航渡最近的路径可以理解成用时最短的路设海路所耗的时间时陆路的3倍如何横渡? 水流常数 航渡曲线 登陆点 目的地4.5.2 路径变分优化:航渡 变分优化应用4.5.2 路径变分优化:球面模型半径为1的球面，起点(0,1,0),终点方位角 ，仰角路线因此4.5.3 生产安排优化甲和乙签订合同，在规定时间里向乙提供定额商品不能提前或滞后，总费用最低原材料成本(常数),等待生产期间有储存费用生产费用生产基本费用(固定值)生产速度费用(生产率的函数,和生产率成正比)储存费用(产品交付前的储存费用，正比于产量)碳排费用(生产产品要消耗减排费用，正比于产量平方)4.5.3 生产安排优化合同生效时间为 ，产品交付日为 ，合同规定的产品量为 ，时间 时的成品数为 ，该时的生产率为 ，假定原材料随买随用，原材料储存费用为0原材料成本费和生产基本费为常数，合并记为生产费用 ， 与 成正比 费用：生产 存储 碳排放 4.5.3 生产安排优化总费用Euler方程解具体例子 4.6. 优化计算方法：遗传算法遗传算法(Genetic Algorith