数学规划模型

数学规划模型数学规划模型 （1）视频中提到的附件可在售后群的群文件中下载。 包括讲义、代码、优秀的作业、我视频中推荐的资料等。 （2）关注我的微信公众号数学建模学习交流，后台发送“软件”两个字，可获得常见的建模软件下载方法；发送“数据” 两个字，可获得建模数据的获取方法；发送“画图”两个字，可获得数学建模中常见的画图方法。另外，也可以看看公众号的历史 文章，里面发布的都是对大家有帮助的技巧。 （3）购买更多优质精选的数学建模资料，可关注我的微信公众号数学建模学习交流，在后台发送“买”这个字即可进入 店铺进行购买。 （4）视频价格不贵，但价值很高。单人购买观看只需要58 元，和另外两名队友一起购买人均仅需46 元，视频本身也是 下载到本地观看的，所以请大家不要侵犯知识产权，对视频或者资料进行二次销售。 数学规划模型 - 概述 u)什么是数学规划? 数学规划是运筹学的个分 , 其来研究:在给定的条件下(约束条件) , 如何按照某衡量指标(标函数)来寻求计划 、管理作 中的最优案 。 求标函数在定约束条件下的极值问题 。 例 : 数学考试卷中的线性规划题 12)数学规划的般形式 min(或者 max) Z=灬x: 决策变量(般有多个变量) 然9ilxko.it,2, ,m (不等式约剌 协标函数 6 subiectto(也可能有等式约束 ,整数约束或两者皆有) 不等式约束 ,等式约束整数约束 :约束条件 例如 min还以3Xzt4 3minz-xi-zx.xztzxi-4X.tn/z MGXZ-20X.tloxzx.tzxz-3XsE8os.t.at 叫 燚品 叫 烈管管 !空焱5。 2*+2E 3 X. , 从30 3720 , X270 Xi ,从EZ(x,不是整数) 13)数学规划的分类 线性规划( Lineupngramming) 如果标函数和和约束条件均是决策变量的线性表达式 ,那么此时的数学规划问题就 属于线性规划 。 1947年 , 美国数学家丹格(GB.Dantz.in)提出了 求解线性规划的单纯形法,奠定了这学科的基础 。 线性规划 (nonlinearpogramming) 当标函数和或者约束条件中有个是决策变量的线性表达式 ,那么此时的数学规划问题就属于线性规划 。 解决线性规划要线性规划困难得多 , 前没有通算法 , 多数算法都是在选定决策变量的初始值后 ,通过定的搜索法 寻求最优的决策变量 。 整数规划( integerpngramm.gl -线性整数规划 (在线性规划模型中,有决策变量限定为整数) 整数规划是类要求变量取整数值的数学规划 线性整数规划 前,所流的 求解整数规划 的算法往往只适于线性整数规划 , 所以本节学习的求解均针对线性整数规划 。 0-1规划 (otngrammng) : 整数规划的特例 , 整数变量的取值只能为0和1 。 code1.m 、线性规划问题的求解 u)Matlab中线性规划的标准型 minix (向量的内积 , (=( 别 ,川剡 , n是决策变量的个数) 不等式约束 n ns.t.f 是点 beq_等式约束注意:可能只对部分决策变量有约束。 lbEXEub.it上下界约束(也可以当成不等式约束) 练习题 :将下列线性规划问题转换为 Matlab 中的标准型 , 1有点类代线性代数中的线性程组的表示) mhZ= -5X , -4名-6 , 等 tinfst.li 蕊焱器, 、嚠 、 n.li剡 、嚰 了 . 性:1 . 收懰 3X.tn/zE3oIx,Xz,X3 0 minzoo4X.to/5XztQlX3to.l25X4sy: 焱毕点 囕懰!噬 器影 嚠 、 性沁 0114X4007X4E42 X.,Xz ,了,X40 beq =24 . 13: 阅 原来求maxztmihz maxzzx,3Xz-53 个 叫 悠器品 。 悾了 .嘇了 、哘別 、吠 onaoii.nl:1 X.+3加以12 X. ,Xz,X30 (z)Matlab求解线性规划的函数 x,fvd = linpnglc.A.b.Aeq.beq.lb.ub.nl 0表示给定Matlab迭代求解 的初始值(般不给) 上三个题的代码: f 不写的意味着 不存在上界 C.A.b.Aeg.beq.lb.us的意义和标准型中的意义致 10 x,fvdjtpwglc.lt ,b,以1 约束 苦不存在不等式约束 , 可 替代A和b 2 0x ,fvd =linpwglc.A.b.Aeg.beg.ly 先不存在等式约束 , 可 替代 Aeq和beq 30x ,fvd = linpwglc.lt/b,Aeg,beg,lb) 苦某个下界或上界 , 则设置lblik-inf.us们inffvak.fm/ 返回的表示最值处的 x取值 ;fvd表示最优解处时取得的最值 :厵 ,囖 !: 。翟諐 解或有穷多的解.li/- code2.m 三 、线性规划的典型例题 111例题1 :(产决策问题 。o 蟹,矗-_-在。鑾 注意教材中得到的答案: ns.max-nn 注意本题实质上应该是 个 整数规划 , 我们的件数不 应该出现数 , 我们在 后 部分再来 求解 。 code3.m 12)例题21投料问题)记地的坐标为(ai , bi) ,以 2-6 、 泥量为d, 记料场 的坐标为lxj ,物 ,j= 1,2 , 储量为20 从料场往地运送的泥为 xj吨 则minzi鞥xjxllaixiig 、 吨乘以千 ,笑: hnox.jp 0, i=1,2, ,6;1,2 记地的坐标为(ai , bi) ,以 2-6 、 泥量为di 决策变量 :Xijlil,2, ,6 ; j=1, 2)共12个 记料场 的坐标为lxj ,物 ,j= 1,2 , 储量为20 , Xz , 了 , 从料场往地运送的泥为 xj吨点 点点凔 则 以 为必州 2 - M叫的标准型|系数必为是已知的 。 (距离) st.ixij-di.FI, 2, , 6 育们 =di.it,2,6 6个约束 侪 们:20,州,2 XHXFd.Xztxs-dz.n.tt 加 dtx.jp O.FI, 2 , ,6;1,2 iijtzo.it,2=) 2个约束 X.txzt.li/6E2o.X7tXst.ntXizE20 (使 Ling 。这个软件求解会更便 ) 四线性规划问题的求解 n)Matlab 中线性规划的标准型 minfMAxeb.Aeqx-beqllinearconstraintsjs.tn/ClXk0,Ceqlx)=o(nonline arconsuy 注意可能只对部分决策变量有约束。 lbtxeb 中的标准型 。 练习题 :将下列线性规划问题转换为Mat maxfcxkxitxi-X.xz-zx.si min-fxk-xi-xitx.xztzx.tn/zs.t.1-lXH2tXz3o s.t.tl 从1) 2 -X2 Eo 线性不就约束 2 ,-3从+60 - 2X,t32 E6 线性不就约束 其中 :Aeq.beq.ceq.lb.us均为 A= -2,3 , b= 6 C=M -1)三灯 minfx) =+加 +8 minfxkx.tl/z4xit8Xi2-Xztxi,o xitxz-xito.xtxitxi-Eox.tk txiez。 | -X , 加2 +2=0 .Xztzxi-3=0 叫 :笖,恐 。 其中 A.b.Aeq.beq.us均为 以330 ( = -x . 2 + xz-xiix.txitxi-zojce.gex_x242 ;Xztzxj -3 15= o.0 , o maxfx) =x.xzx, mintxk-X.Xzxz.fi :發器器 州 启炎恐品佳产了 10Exz Ezo-_- 7 X_X-10 1性= 1 , -1 , ojbeqiox-xzi.io 20 15= 鼗 ub: (蒙特卡罗模拟的例) c . ceq 为 code4 (2) Matlab求解线性规划的函数 x, fvalIfminconlfun.XO.A.b.Aeq.beq ,lb.ub.nonlfun.optn ) 解释 : 线性规划中对于初始值0的选取常重要 , 因为线性规划的算法求解出来的是个局部最优解 。 (线性规划不存在这个问题 ) 如果要求 全局最优解!有两种思路 : 10给定不同的初始值 , 在找到个最优解 ; 2 0先蒙特卡罗 t 模拟 ,得到个蒙特卡罗解 , 然后将这个解作为初始值来求最优解 。 特有! Tion 选项可以给定求解的算法 , 共有四种: (内点法) 、 sa.pl序列次规划法) 、 actie.at(有法)以及trust-egion.ieflectie (信赖域反射算法) 。 不同的算法有其各的优缺点和适情况 , 我们可以改变求解的算法来看求解的结果是否变好了 。 如何改变求解的算法请参考代码演示 。 (数模赛中可以都尝试下,这可以体现出稳健性,也是你的优点) (1 fun 表示标函数 , 我们要编写个独的m件来存标函数: functionf = fun (x) 注 fun可以任意取名,例如你写成 qingfng520 也可以 , 只 f = _要符合Matlab命名规范 ,保存的m件也是这个名 。 end2 0f也可以任意取名 , 但返回的f和函数内部的f得完全致 ; 这的实际上是表示决策变量的量 ,其 列向取决于纫始值。 调函数: fminconCfun.n . )求解 。 nonlfun 表示线性部分的约束 , 我们同样得编写个独的m件任存线性约束条件 : functon c ,ceq = nonlfunlx) 注: 10 nonlfun同样可任意取名 ,别和上的fun (=线性不等式约束1 ; 相同即可 ,保存的m件也得是这个名字 。 -_- 线性不等式约束问 2 0C . 49 中可能有多个约束因此我们写成 g =线性等式约束 1; 列向量的 形式 ; 线性等式约束9;3 30若不存在线性不等式约束 , 则可以令 C= ; d 40调函数 fminconl-.nonlfun.options)求解。 注意要把下标改写为托号 , 例如fx, 2 +3名写成Matlab能识别的就应该为 :仁吃+3 *12) 若不存在某种约束 ,则可 替代 , 若后全为 且不指定 0阰使默认的求解法) ,则 也可以省略掉 。 注意因为涉及到多个m件 , 所以这 下我们就对上的三个例题进求解: IO.ly wde4是个件夹 。 code5 五、线性规划的典型例题 例题1 . 选址问题第问 : 记地的坐标为(ai , bi) ,以 2-6 、 泥量为di 记新料场 的坐标为lxj ,物 ,j= 1,2 , 储量为20 从料场往地运送的泥为 xj吨 则 min 点必州 2-fnfs.si 们 = , 以2, , 6 | 们 E20, jizx.jp 0, i=1,2, ,6;1,2 决策变量 :xijli.bz, ,6 ; j=1, 2) ,Xj, (州,2) X. , Xz , X 6 , X7 , X8 , _ , X12 , X13 ttttt d i 鉴鉴 t 记地的坐标为(ai ,bij.FI, 2 , 6 , 泥量为di Xn 21 1161 X1222 X62 名 记料场 的坐标为lxj ,物 ,j= 1,2 , 储量为20 12个系数tixitlbiyj 是未知的 。 (距离) 从料场往地运送的泥为 xj吨 商们 =di.it,2,6 6个约束 则m.nu,必,州 2 揵 ! 坳标准型 lnxu.weix-qst.jxij-di.FI , 2, , 6 截 上20 ,州,2 =)2 个约束 | 们 E20,j=1,2 hxtxz-tX6E20.xtxst.ntxnezox.jp O.FI, 2 , ,6;1,2 例题2.管理问题 躙 决策变量 :6架机调整的度 loi.it , 2 , , 6) 假设 : 标函数 : 100i l或者 2 0忽略机体积 、转向时间等 。 约束条件 : 10 计 dij以为七时刻时, i ,j两架机的距离 (i#) 是 。筌强鑾:鱮 于8公癴 。 刚进 次就调整到位 , 直到下个机进区域 code6 假设 i和j两架机的初始坐标为: (xi,别和必 ,则 若经过时间 诱的列时, 距离最近 , 此时它们的坐标为必 炒 乐。(吖 ,炒 例如。也5,则则必 炒 =( xitkasoitoi.yitutjsihloito.tl c.必爽 妗, yy-txjtlhosojtoj.yjtlgsihlgitoDcxi.ci )* a 则dij-dllyi-y.TT8 俐 ypixj-xittjlosoioj-coscoitoo.it/yj-yitv.tjIsml0jtoj)-Shl0i- 10012764 问题来了 ,tj 怎么求呢? 很简单,记函数 djltkyi-xitvtlslojtoj-coscoito.BY tlyj-yitvtEinlojtolgis.hlo.to)1 2 =批 ) 两种可能 Ofit)0 ,则t.jo 2 0先于0,后于0 , 则tj : 兠 三0 记秈=A 2 +B 2 (A.B是两个括号内容) 、 男记A1 . B , 是两个中托号内容 则 fitFZAVA.tzBVB.lA-lxj-xiltltAi.BE/yj-yi)ttB.) 当 0时, AA.tBB.to 即lxj-xilA.tvtAitcyj-yilB.tvtB, 2 o 此时 , ( VAitvB.yts-fj-yiiB.tn/j-xi)AJ 即t_ Y-Bitlxj-nhA.lu,。) , 则 _ 以利-15加- 8 , di 8 , di 8 , di8 , , 岭8 - 共有 :42- 13 - 14+5 = 15个 % 例1 c=-20,-10; intcon=1,2; % x1和x2限定为整数 A=5,4; 2,5; b=24;13; lb=zeros(2,1); x,fval=intlinprog(c,intcon,A,b,lb) fval = -fval % 例2 c=18,23,5; intcon=3; % x3限定为整数 A=107,500,0; 72,121,65; -107,-500,0; -72,-121,-65; b=50000;2250;-500;-2000; lb=zeros(3,1); x,fval=intlinprog(c,intcon,A,b,lb) % 例3 c=-3;-2;-1; intcon=3; % x3限定为整数 A=ones(1,3); b=7; Aeq=4 2 1; beq=12; lb=zeros(3,1); ub=+inf;+inf;1; %x(3)为0-1变量 x,fval=intlinprog(c,intcon,A,b,Aeq,beq,lb,ub) code7.m 六、整数规划 整数规划 线性整数规划-Matlab可进 求解 1线性的意思在线性规划的基础上 , 加决策变量取整数的条件) (特例 线性整数规划 特定算法 , 只能近似算法 , 如蒙特卡罗模拟 、 智能算法(后续会讲到) 0-1规划 : 特殊的整数规划 , Matlab中也只能求解线性01规划 , 对于线性0-1规划也只能近似求解 。 (数模赛中最常出现) u)Matlab线性整数规划求解 x,fvd = linpnglc.A.b.Aeq.beq.lb.ub.tl -7线性规划的函数 x,fvd = con.A.b.Aeq.beq.lb.us)线性整数规划的求解 注: 10 intlinpng不能指定初始值; 加了inton参数可以指定哪些决策变量是整数 。 例如 决策变量有三个 : , 从 , ; 若和x,是整数 , 则intwn =1,3 (2)Matlwb线性0-1规划求解 仍然使intlinpog函数 , 只不过在1姀哟上作章 。 例如 三个决策变量加 ,为中, X,和,是0 -1变量 , 后不限制 , 则 化汇1,3了 , 15- 钻 , ub诎灯 例 limaxztox.tloxzs.tn/5Xit4XzE242X.t5XzEl3Xi,Xz)O,X.,XzEZ 例2 : minZ=18X , 23Xz +5 st. | 500 107 X.t5ooxzE5oooozoooETZX.tk/Xzt65X3E225oXi,Xz,X33o 且从EZ 例 3.minZ-3X-zxz-Xz.SI0 code8.m code9.m 七、整数规划 的典型例题 (i)背包问题 nhtn.li 鑿 , iii.IO 则标函数max Pixi 约束条件 s.tl wixiE3oxic-lo.lt (2)指派问题 1 1 , 2 , , 5 五名队员 j= 1 ,2,3,4四种泳姿 = % ; 队员,参加第;种泳姿 紧靠意鸜 tij队员i参加 蠿 i 裂1 , 以2,3,4 , 5(每个只能选4种泳姿之) lnfsn 育 = 1 , 州,2,3 ,4 (每种泳姿有且仅有 1参加) 们 E10 , 1 1 本题和线性规划中的投料问题很类似 : Xn , Xn , _ X .4 , Xu, Xzz , -_- , X 24 , -_- , X 51, X 52 , -.-X54 标、 LX.Xz.is/4.X5X6-X8,-,X17.Xo,i-Xzo 单 下标 code10.m 131钢管切割问题 。 曼哈顿距离 code11 ,最最化模型 (l) 模型的般形式 - nnnrres 标去数 (z)典型例题 lrft nnir (可以取数哦 ! 否则枚举就可以了) 注:我们也可以定义其他的标函数 如 minilx-a.lt/y-biD 131模型的求解 x, fvalIfminconlfun.XO.A.b.Aeq.beq ,lb.ub.nonlfun.optn) 线性规划 区,fvdJ-fminimaxltnX0.A.b.Aeq.beq ,lb.ub.nonlfun.option) 最最化模型 标函告 _ 姍 -崔数向量表示 functionf-Funcxjhfetoslm.ly fu)= - f(2) -_- ! fmiend code12.m 九 ,多标规划模型 u)求解思路 若个规划问题中有多个标,例如企业在保证利润最时也要保证产时产的污染最少这种情况下我们可以对多标 函数进加权组合,使问题变为单标规划 , 然后再利之前学的知识进求解。 注意要先将多个标函数统为最化或最化问题后才可以进加权组合 2 0如果标函数的量纲不相同 ,则 需要对其进标准化 后再进加权 , 标准化的法般是标函数除以某个常量 , 该常量是这个标函数的某个取值 , 具体取何值可根据经验确定 30对多标函数进加权求和时 , 权重需要由该问题领域的专家给定 , 在实际建模 赛中, 若特殊说明,我们拎权重相同 。 以典型例题 。 每名护每天连续作个时，在每个班次安排多少名护可使总数最少? 课后习题 : 曹蟠 题2: 题3 : 题4 : (覆盖问题 腱 肠 homework1.m 每名护每天连续作个时，在每个班次安排多少名护可使总数最少? 习题参考答案