matlab建模与求解详解

《matlab建模与求解详解》由会员分享，可在线阅读，更多相关《matlab建模与求解详解（49页珍藏版）》请在金锄头文库上搜索。

1、MATLAB建模与求解,彭扬,1. 生产计划问题,一、线性规划模型,max f= 5x1 +2x2,求最大利润,三种材料量的限制,生产量非负,线性规划模型,2. 运输问题,解：设A1,A2调运到三个粮站的大米分别为x1， x2， x3， x4， x5， x6吨。,题设量可总到下表：,结合存量限制和需量限制得数学模型：,m个产地A1,Am联合供应n个销地B1,Bn,各产 地至各销地单位运价(单位:元/吨)为cij，问如何调运使 总运费最少?,一般运输问题,总运价,产量限制,需量限制,运量非负,假设产销平衡:,在很多实际问题中,解题思想和运输问题同出一辙, 也就是说我们可以用运输模型解决其他问题.

2、,设有n件工作B1, B2, Bn,分派给n人A1, A2, An去 做,每人只做一件工作且每件工作只派一个人去做,设Ai 完成Bj的工时为cij,问应如何分派才能完成全部工作的 总工时最少.,每件工作只派1人,每个人只派做1件,变量xi只取0和1,故建立 的模型也称0-1规划.,3. 分派问题,4.选址问题,现要做100套钢架,用长为2.9m、2.1m和1.5m的元 钢各一根,已知原料长7.4m,问如何下料,使用的原材料 最省?,分析:,下料方式：,最省：,1.所用刚架根数最少；,2.余料最少,5.下料问题,不同方法截得每种根长的总数至少100,例3,4中的此例的变量xi只取正整数, 故建立

3、的模型也称整数规划. 0-1规划是整数规划的特殊情形.,某公司生产某产品,最大生产能力为100单位,每单位 存储费2元,预定的销售量与单位成本如下:,求一生产计划,使 1)满足需求; 2)不超过生产能力; 3)成本(生产成本与存储费之和)最低.,6. 生产批量问题,解:假定1月初无库存,4月底卖完,当月生产的不库 存,库存量无限制.,第j+1个月的库存量,第j+1个月的库存费,共3个月的库存费,到本月总生产量大于等于销售量,4个月总生产量等于总销售量,4个月总生产成本,线性规划模型,本问题的3个模型为整数规划模型.,线性规划模型特点,决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素非

4、负； 约束条件：线性等式或不等式； 目标函数：Z=(x1 xn) 线性式，求Z极大或极小；,21,一般形式,目标函数,约束条件,矩阵形式,满足约束条件的变量的值称为可行解，,可行解的集合称为可行域。,使目标函数达到最大（小）值的可行解称为最优解，,相应的目标函数的值称为最优值。,线性规划问题的性质:,比例性 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比. 可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关. 连续性 每个决策变量的取值都是连续的.,应 用,市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“

5、生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题,线性规划模型,财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用),求解线性规划的Matlab解法 1. Matlab解线性规划的标准形式 x,fval = linprog(c,A1,b1,A2,b2) x,fval = linprog(c,A1,b1,A2,b2,lb,ub) x,fval = linprog(c,A1,b1,A2,b2,lb,ub,x0) 没有的加例如x=0;则l

6、b=0,ub用代替,求解线性规划问题 编写Matlab程序如下： c=2;3;1; a=-1,-4,-2;-3,-2,-0; b=-8;-6; x,y=linprog(c,a,b,zeros(3,1),案例 一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天

7、获利最大，并进一步讨论以下3个附加问题： 1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？,线性规划综合举例：生产计划问题,2 该问题的模型为:,3、编写MATLAB程序为: f=-72,-64; A=1,1;12,8;3,0; b=50;480;100; lb=zeros(2,1); x,fval=linprog(f,A,b,lb,); disp(x); disp(fval);,4、结果为: x = 20.0000

8、 30.0000 fval = -3.3600e+003 这个线性规划的最优解为x1=20，x2=30，最优值为z=3360，即用20桶牛奶生产A1, 30桶牛奶生产A2，可获最大利润3360元。,5、灵敏度分析: 为了分析一桶牛奶35元是否可以购买进行投资,可以在约束条件50改为51,重新求最大利润,如果利润在原来的基础上提高超过35,那么可以作这个投资。 牛奶供应量这个约束条件放宽一桶以后,结果为: x = 18.0000 33.0000 fval = -3.4080e+003 由结果可以看出增加一桶牛奶的供应量增加的利润为3408-3360=48元35元 因此可以作这方面的投资.进一步考

9、虑,以35元一桶的牛奶扩大供应再生产,在现有资源的限制下规模可以扩大到什么程度.,6、灵敏度分析: 为了分析付给临时工人的工资最多是每小时几元？,可以将工时约束条件480改为481(相当于聘用临时工增加一个工时),重新求最大利润, 利润在原来的基础上提高一定的数值,付给临时工人的工资理论上应不超过这个数值。 约束条件480改为481以后,结果为: x = 20.2500 29.7500 fval = -3.3620e+003 由结果可以看出增加一个工时增加的利润为3362-3360=2元 因此付给临时工人的工资理论上应不超过2元/小时.进一步考虑,是否付给临时工人的工资一定不超过2元/小时,条

10、件对利润的影响是综合的相互的,工时的限制会限制规模的扩张,从而影响利润的增长,因此,这种固定其他约束,改变一个约束来分析该约束对利润的影响是有一定局限性,7、灵敏度分析: 目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单地回答。通过改变目标函数系数值求解,观察解的变化,得到系数值允许的变化范围：x1的系数为（64，96）；x2的系数为（48，72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题3）：若每公斤A1的获利增加

11、到30元，则x1系数变为303=90，在允许范围内，所以不应改变生产计划，但最优值变为9020+6430=3720。 由于市场需求变化，每公斤A1的获利增加到32元(A2获利不变)，或者每公斤A2的获利增加到18元(A1获利不变),则都应该改变生产计划,很容易定出新的生产计划.,2.整数规划,定义 规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数

12、规划。 3o 变量只能取0或1时，称之为0-1整数规划。,（i）分枝定界法可求纯或混合整数线性规划。 （ii）割平面法可求纯或混合整数线性规划。 （iii）隐枚举法求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。 （iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。 （v）蒙特卡洛法求解各种类型规划(随机取样法),特殊的整数规划 指派问题（又称分配问题Assignment Problem） 拟分配 人去干 项工作，每人干且仅干一项工作，若分配第 人去干第 项工作，需花费 单位时间，问应如何分配工作才能使工人花费的总时间最少？,求解下列指派问题，已知指派矩阵为,编写Matlab程序如

13、下： c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 5；8 4 2 3 5;9 10 6 9 10; c=c(:); a=zeros(10,25); for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1; end b=ones(10,1); x,y=linprog(c,a,b,zeros(25,1),ones(25,1),2019/5/24,40,优化问题三要素：决策变量decision bariable；目标函数objective function；约束条件constraints,优化问题的一般形式,等约束equality const

14、raint,不等约束inequality constraint,一般优化问题概述,要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件,特点,一般优化问题概述,可行解feasible solution（满足约束）与可行域feasible region（可行解的集合） 最优解optimal solution（取到最小minimum大值maximum的可行解,对应最优值optimal value）,局部最优解或相对最优解local/relative optimizer,全局或整体最优解global optimizaer,优化模型的基本类型,无约束优化 u

15、nconstrained optimization,约束优化 constrained optimization,特殊：等式（不等式）方程组 system of equations(inequations),一般优化问题概述,约束优化constrained optimization的简单分类,数学规划mathematical programming 或连续优化continuous optmization,线性规划(LP) 目标和约束均为线性函数 Linear programming 非线性规划(NLP) 目标或约束中存在非线性函数 Nonlinear programming 二次规划(QP) 目

16、标为二次函数、约束为线性 Quadratic programming,一般优化问题概述,整数规划(IP) 决策变量(全部或部分)为整数 Integer programming 整数线性规划(ILP)，整数非线性规划(INLP) 纯整数规划(PIP), 混合整数规划(MIP) Pure (mixed) Integer programming 一般整数规划，0-1（整数）规划 Zero-one programming,离散优化discrete optimization 或组合优化combinatorial optimization,一般优化问题概述,Matlab优化工具箱简介,1.MATLAB求解优化问题的主要函数,2. 优化函数的输入变量,使用优化函数或优化工具箱中其它优化函数时, 输入变量见下表:,3. 优化函数的输出变量下表:,大作业,要求： 1）从给定主题选择一