MATLAB建模与求解

1、MATLAB建模与求解建模与求解 彭扬?,./2, 5, 321可使利润最大可使利润最大问如何安排计划问如何安排计划吨吨万元万元的利润分别为的利润分别为且且下表下表原材料（单位：吨）如原材料（单位：吨）如每吨所需原材料及现有每吨所需原材料及现有，两种产品，已知生产两种产品，已知生产，生产生产和和，料料某工厂计划用三种原材某工厂计划用三种原材 AAA1. 生产计划问题生产计划问题一、线性规划模型 2x1 + x2 8 s.t . x1 3 x2 4 x1，x2 0 max f= 5x1 +2x2,:21吨吨两两种种产产品品分分别别为为设设生生产产解解xx 求最大利润求最大利润三种材料量的限制三种

2、材料量的限制生产量非负生产量非负线性规划模型。问如何调运使运费最低问如何调运使运费最低如下如下公里公里单位单位距离距离两个粮库到三个粮站的两个粮库到三个粮站的吨吨大米分别为大米分别为三个粮站至少需要三个粮站至少需要吨吨吨吨为为两个粮库现存大米分别两个粮库现存大米分别调运大米调运大米向三个粮站向三个粮站有两个粮库有两个粮库,):(,5 , 4 , 2,8 ,4, 32121BBBAA2. 运输问题运输问题解：解：设设A A1,1,A A2 2调运到三个粮站的大米分别为调运到三个粮站的大米分别为x x1 1，x x2 2， x x3 3， x x4 4， x x5 5， x x6 6吨。吨。题设量

3、可总到下表：题设量可总到下表：结合存量限制和需量限制得数学模型结合存量限制和需量限制得数学模型：65432124123082412minxxxxxxf 0,54284.654321635241654321xxxxxxxxxxxxxxxxxxts m个产地个产地A1,Am联合供应联合供应n个销地个销地B1,Bn,各产各产地至各销地单位运价地至各销地单位运价(单位单位:元元/吨吨)为为cij，问如何调运使，问如何调运使总运费最少总运费最少?一般运输问题一般运输问题.:ijjixBA的的运运输输量量为为到到销销地地设设从从产产地地解解 njmixnjbxmiaxtsxcfijjmiijinjijmi

4、njijij,.,1;,.,10,.,1,.,1,.min1111总运价总运价产量限制产量限制需量限制需量限制运量非负运量非负 njmixnjbxmiaxtsxcfijjmiijinjijminjijij,.,1;,.,10,.,1,.,1,.min1111假设假设产销平衡产销平衡: 在很多实际问题中在很多实际问题中,解题思想和运输问题同出一辙解题思想和运输问题同出一辙,也就是说我们可以用运输模型解决其他问题也就是说我们可以用运输模型解决其他问题. njjmiiba11 设有设有n件工作件工作B1, B2, Bn,分派给分派给n人人A1, A2, An去去做做,每人只做一件工作且每件工作只派一

5、个人去做每人只做一件工作且每件工作只派一个人去做,设设Ai完成完成Bj的工时为的工时为cij,问应如何分派才能完成全部工作的问应如何分派才能完成全部工作的总工时最少总工时最少. 否则否则去做去做分派给分派给工作工作设设解解01:ijijABx ninjijijxcf11min ）（或或）（）（njixnixnjxtsijnjijniij,.,2 , 1,10,.,2 , 11,.,2 , 11.11每件工作只派每件工作只派1人人每个人只派做每个人只派做1件件变量变量xi只取只取0和和1,故建立故建立的模型也称的模型也称0-1规划规划.3. 分派问题分派问题?,1,2:),(),(),(),()

6、,(),(),(:7, 7654321的年利润最大的年利润最大问如何选择地址使公司问如何选择地址使公司元元总投资不超过总投资不超过元元每年可获利每年可获利元元投资投资若选若选个个汉口汉阳至少汉口汉阳至少个个武昌至多武昌至多并规定并规定汉商汉商二十一世纪二十一世纪行街行街步步武广武广司门口司门口亚贸亚贸中商中商个地址个地址有有拟议中拟议中汉阳建立专卖店汉阳建立专卖店汉口汉口某公司拟定在在武昌某公司拟定在在武昌bcbAAAAAAAAiii 否则否则选择选择解解, 0, 1:iiAx 71maxiiixcf 7,.,2 , 110112.765432171ixxxxxxxxbxbtsiiii或或4.

7、选址问题选址问题 现要做现要做100套钢架套钢架,用长为用长为2.9m、2.1m和和1.5m的元的元钢各一根钢各一根,已知原料长已知原料长7.4m,问如何下料问如何下料,使用的原材料使用的原材料最省最省?分析分析:下料方式：下料方式：最省：最省：1.所用刚架根数最少；所用刚架根数最少；2.余料最少余料最少5.下料问题下料问题原料截成所需原料截成所需长度的根数长度的根数下料方法下料方法所所需需根根长长2.9m211100002.1m021032101.5m10130234剩余料头剩余料头0.10.30.901.10.20.81.4:, 为为则问题的线性规划模型则问题的线性规划模型根数根数种办法下

8、料的原材料的种办法下料的原材料的表示按第表示按第设设ixi876543214 . 18 . 02 . 01 . 109 . 03 . 01 . 0minxxxxxxxxf 取整取整jjxjxxxxxxxxxxxxxxxxts;8 , 7 , 6 , 5 , 4 , 3 , 2 , 1, 0100432310023321002.876431765324321不同方不同方法截得法截得每种根每种根长的总长的总数至少数至少100例例3,4中的此例的变量中的此例的变量xi只取正整数只取正整数,故建立的模型也称故建立的模型也称整数规划整数规划.0-1规划是整数规划的特殊情形规划是整数规划的特殊情形. 某公

9、司生产某产品某公司生产某产品,最大生产能力为最大生产能力为100单位单位,每单位每单位存储费存储费2元元,预定的销售量与单位成本如下预定的销售量与单位成本如下:月份月份单位成本单位成本(元元) 销售量销售量1234 70 60 72 70 80 120 76 60求一生产计划求一生产计划,使使 1)满足需求满足需求; 2)不超过生产能力不超过生产能力;3)成本成本(生产成本与存储费之和生产成本与存储费之和)最低最低.6. 生产批量问题生产批量问题 1 je 解解:假定假定1月初无库存月初无库存,4月底卖完月底卖完,当月生产的不库当月生产的不库存存,库存量无限制库存量无限制.为单位成本，为存储费

10、，为销售量，月产量，为第：设模型iiiicedix jiijiidx11 31j 41jjjxc fmin第j+1个月的库存量第j+1个月的库存费共共3个月的库存费个月的库存费 4 ,23, 110003 , 2 , 1.414111ixdxjdxtsiiiiijijiii且为正整数且为正整数到本月总生产量到本月总生产量大于等于销售量大于等于销售量4个月总生产量等个月总生产量等于总销售量于总销售量4个月总个月总生产成本生产成本.iiiiisicedix月初的库存量为月初的库存量为为单位成本，设第为单位成本，设第为存储费，为存储费，为销售量，为销售量，月产量，月产量，为第为第：设：设模型模型 4

11、141miniiiiiisexcf.ts 1is, iiidxs 4 , 3 , 2 , 1 i0051 ss4321043211000，且为整数且为整数，且为整数，且为整数， isixii.,月的销售量表示的第之和存储费月卖出时的生产成本与月生产的产品在第第表示月卖出的数量月生产的产品在第表示第设化为运输问题解法jdjicjixjijij月份月份单位成本单位成本(元元) 销售量销售量1234 70 60 72 70 80 120 76 6076827676-80-7472-747270生产月100100100100产量6041207060销量4321321需求月费用费用cij线性规划模型且为

12、整数且为整数0100.min41,411 ijijijjijijjjiijijxxdxtsxcf4 , 3 , 2 , 1 j4 , 3 , 2 , 1 i4 , 3 , 2 , 1, ji本问题的本问题的3个模型为整数规划模型个模型为整数规划模型.线性规划模型特点 决策变量：向量(x1 xn)T ,决策人要考虑和控制的因素非负； 约束条件：线性等式或不等式； 目标函数：Z=(x1 xn) 线性式，求Z极大或极小；21一般形式一般形式 0,.minmax21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxc

13、f目标函数目标函数约约束束条条件件 矩阵形式为：矩阵形式为：记记,),(212121TnTnnmijnbbbbxxxxaAcccc 0.minxbAxtscxfL称为约束矩阵。称为约束矩阵。的每一分量的每一分量指指Axxxj, 00 矩阵形式矩阵形式满足约束条件的变量的值称为满足约束条件的变量的值称为可行解可行解，可行解的集合称为可行解的集合称为可行域可行域。使目标函数达到最大（小）值的可行解使目标函数达到最大（小）值的可行解称为称为最优解最优解，相应的目标函数的值称为相应的目标函数的值称为最优值最优值。线性规划问题的性质: 比例性比例性 每个决策变量对目标函数以及右端项每个决策变量对目标函数

14、以及右端项的贡献与该决策变量的取值成正比的贡献与该决策变量的取值成正比. 可加性可加性 每个决策变量对目标函数以及右端项的每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关贡献与其他决策变量的取值无关. 连续性连续性 每个决策变量的取值都是连续的每个决策变量的取值都是连续的.应 用 市场营销市场营销(广告预算和媒介选择，竞争性定价，广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划新产品开发，制定销售计划) 生产计划制定生产计划制定(合理下料，配料，合理下料，配料，“生产计划、生产计划、库存、劳力综合库存、劳力综合”) 库存管理库存管理(合理物资库存量，停车场大小，设合理物资

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

16、b,ub) x,fval = linprog(c,A1,b1,A2,b2,lb,ub,x0) 没有的加例如x=0;则lb=0,ub用代替ubxlbbxAbxAtsxcxfT2211.)(min求解线性规划问题 编写Matlab程序如下：c=2;3;1;a=-1,-4,-2;-3,-2,-0;b=-8;-6;x,y=linprog(c,a,b,zeros(3,1)32132 minxxxz0,62382432121321xxxxxxxx案例案例 一奶制品加工厂用牛奶生产A1,A2两种奶制品，1桶牛奶可以在甲车间用12小时加工成3公斤A1，或者在乙车间用8小时加工成4公斤A2。根据市场需求，生产的

17、A1,A2全部能售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间480小时，并且甲车间每天至多能加工100公斤A1，乙车间的加工能力没有限制。试为该厂制订一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题： 1）若用35元可以买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？ 2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？ 3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？线性规划综合举例：生产计划问题线性规划综合举例：生产计划问题2 该问题的模型为:max=7

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

19、此付给临时工人的工资理论上应不超过2元/小时.进一步考虑,是否付给临时工人的工资一定不超过2元/小时,条件对利润的影响是综合的相互的,工时的限制会限制规模的扩张,从而影响利润的增长,因此,这种固定其他约束,改变一个约束来分析该约束对利润的影响是有一定局限性7、灵敏度分析:目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？这个问题不能简单地回答。通过改变目标函数系数值求解,观察解的变化,得到系数值允许的变化范围：x1的系数为（64，96）；x2的系数为（48，72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最

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

21、数规划 1o 变量全限制为整数时，称纯（完全）整数规划。 2o 变量部分限制为整数的，称混合整数规划。 3o 变量只能取0或1时，称之为0-1整数规划。 （i）分枝定界法可求纯或混合整数线性规划。 （ii）割平面法可求纯或混合整数线性规划。 （iii）隐枚举法求解“0-1”整数规划： 过滤隐枚举法； 分枝隐枚举法。 （iv）匈牙利法解决指派问题（“0-1”规划特殊情形）。 （v）蒙特卡洛法求解各种类型规划(随机取样法) 特殊的整数规划 指派问题（又称分配问题Assignment Problem） 拟分配 人去干 项工作，每人干且仅干一项工作，若分配第 人去干第 项工作，需花费 单位时间，问应如

22、何分配工作才能使工人花费的总时间最少？nnijijcninjijijxc11min n,1,2,ji, 1 0,2,1,1,2,1,111或ijniijnjijxnjxnixij 求解下列指派问题，已知指派矩阵为 1096109532485724679278310283编写Matlab程序如下：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;endb=ones(10,1);x,y=linprog

23、(c,a,b,zeros(25,1),ones(25,1) 2022-6-2740优化问题三要素：优化问题三要素：决策变量决策变量decision bariable；目标目标函数函数objective function；约束条件约束条件constraints约约束束条条件件决策变量决策变量优化问题的一般形式优化问题的一般形式njiDxljxgmixhtsxfopt,.,1,0)(,.,1,0)(.)(目标函数目标函数等约束等约束equality constraint不等约束不等约束inequality constraint一般优化问题概述 要解决的问题的目标可以用数值指标反要解决的问题的目标可

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

25、al optimizaer优化模型的基本类型优化模型的基本类型无约束优化无约束优化unconstrained optimization约束优化约束优化constrained optimization特殊：等式（不等式）方程组特殊：等式（不等式）方程组 system of equations(inequations)一般优化问题概述约束优化约束优化constrained optimization的简单分类的简单分类数学规划数学规划mathematical programming或连续优化或连续优化continuous optmization 线性规划线性规划(LP) 目标和约束均为线性函数目标和

26、约束均为线性函数 Linear programming 非线性规划非线性规划(NLP) 目标或约束中存在非线性函数目标或约束中存在非线性函数 Nonlinear programming 二次规划二次规划(QP) 目标为二次函数、约束为线性目标为二次函数、约束为线性 Quadratic programming一般优化问题概述整数规划整数规划(IP) 决策变量决策变量(全部或部分全部或部分)为整数为整数Integer programming 整数整数线性线性规划规划(ILP)，整数，整数非线性非线性规划规划(INLP) 纯整数规划纯整数规划(PIP), 混合整数规划混合整数规划(MIP) Pure (mixed) Integer programming 一般整数规划，一般整数规划，0-1（整数）规划（整数）规划Zero-one programming离散优化离散优化discrete optimization或组合优化或组合优化combinatorial optimization一般优化问题概述MatlabMatlab优化工具箱简介优化工具箱简介1.MATL