工程优化数学实验线性规划.pdf

数学实验Experiments in Mathematics西安交通大学数学学院 美国空军为了保证士兵的营养，规定每餐的食品中,要保证一定的营养成份，例如蛋白质、脂肪、维生 素等等，都有定量的规定。当然这些营养成份可以 由各种不同的食物来提供，例如牛奶提供蛋白质和 维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生 素，等等。由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定 各种食品的数量，使得既能满足营养成份的需要，又可以降低成本？现代管理问题虽然千变万化，但大致上总是要利用 有限的资源，去追求最大的利润或最小的成本，如 何解决这些问题？解决问题的方法：线性规划2在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促 进战争的胜利，起了关键的作用。甚至有这样 的说法：因为使用炸药，第一次世界大战可说 是化学的战争；因为使用原子弹，第二次 世界大战可说是物理的战争；因为使用线 性规划，波斯湾战争可称为数学的战争。在历史上，没有哪种数学方法，可以像线性规 划那样，直接为人类创造如此巨额的财富，并 对历史的进程发生如此直接的影响。3最优化问题及其求解 线性规划 最优化问题简介及Matlab求解 规划举例参看：实验8,实验94一、线性规划1、引例例1、生产计划问题：某企业生产A,B两种产品，成本和利润指标如下:煤 劳动日 仓库A B1 23 20 2备用资源306024利润 4050问：A,B各生产多少，可获最大利润?5解:设产品A,B的产量分别为变量修，与，则:max Z=40/+50 x2xx+2x2 30,t 3xr+2x2 60,|2x224,0；煤 劳动日 仓库A B1 23 20 2备用资源-3o6024利润 40 50 6例2、（资源配置问题）有一批长度为7.4m的钢筋若干根。现有5中下料方 案，分别作成2.9m,2.1m,L5m的钢筋架子各100 根。每种下料方案及剩余料头如下表所示：2.9m2.1m1.5m 合计I II III IV V1 2 6 1 0-0 0 2 2 13 12 0 37.4 7.3-6oTi7.2 7.1 6.60.2 0.3 0.8问：如何下料使得剩余料头最少?7解：设按第i种方案下料的原材料为西根，则:minZ=0.1x2+0.2x3+0.3x4+0.8x5xx+2x2+x4=10 0,I 2x3+2x4+x5=10 0,3Xi+x2+2x3+3%5=10 0,.N0(i=l5),且为整数;I II III IV V9m 1 2 6 1 02.I m 0 0 2 2 11.5m 3 1 2 0 37.4 7.3 7.2 7.1 6.660.1 0.2 0.3 0.88例3、（运输问题）某棉纺厂的原棉需从仓库运送到各车间。各车间原 棉需求量，单位产品从各仓库运往各车间的运输费 以及各仓库的库存容量如下袤所列：2 31 32 44 2库存容量503010需求40 15 35问：如何安排运输任务使得总运费最小?9解：设均为i仓库运到/车间的原棉数量(i=123;J=123)。则minZ=2xn+x12+3x13+2x21+2x22+4x2+3x31+4x32+2x33f%11+工12+工13 V 50,工21+”22+”23 30,%31+32+33 0,i=1,2,3;/=1,2,3;t/10例4、现有10万元，可连续投资于4个项目。各项目 投资时间和本利情况如下：项目A：从第1年 到第4年每年初要投资，次年末回收本利L 15倍。项目B：第3年初投资，到第5年末回收本利L 25倍,最大投资4万元。项目C:第2年初投资，到第5年末回收本利1.40倍,最大投资3万元。项目D：每年初投资，每年末回收本利1.11倍。求：如何分配投资资金使得5年末总资本最大?11解：设/虱i=1,234,5;k=A,B,C,D）表示第i年初投 资第A项目的资金数。7份 项4A1 2 3 4 5BCDX1A*X2A X3A X4AX3BX2CX1D X2D X3D X4D X5D12xik(i=1,2,.,5;k=A,B,C,D)为第i年初投女项目的 资金数.则：maxZ=1.15x4A+1.40 x2C+1.25x3B+1.11x5D(x1A+x1D=10%2a+2c+2D=LU%1DX2C 3X3A+x3B+x3D=1.15 x1A+1.11 x2D%3B4%4a+%4D=L15 x2A+1.11 x3Dx5D=1.15 x3A+1.11 x4D xik ，i=12,5;k=A,B,C,D;13以上问题的特点：1.在人力、财力、资源给定条件下，如何 合理安排任务，使得效益最高.2.某项任务确定后，如何安排人力、财力、物力，使之最省.即以上问题都是在一定条件下，求线性函 数的最大值或最小值问题。这类问题称为线，性规划LP(Lin ear Programmin g)问题。142、线性规划问题的一般形式C/2+。12%2+,+（-，）b,。22*2+（一，）2,或加11+/w22l*+mrtn（一，）%0（j=l.n）;min（或max）z=fT xs.t.Ax）b x.0（/=12/）153、线性规划问题的求解方法二元线性规划问题的图解法线性规划问题的理论解法线性规划问题的M ATLAB软件解法164、求解线性规划的MATLAB命令x=linprog(f,A,b):求解 min z=f，x,A-x bx=linprog(f9 A,b,Aeq,beq):求解：min z=fx,A-x b,Aeq-x=beq;x=linprog(f,A,b,Aeq,beq,lb,ub):指定lb xub;若没有不等式约束，可用替代A和b,若没有等式约束,可用替代Aeq和beq,若某个Xj下无界或上无界,可设定inf或inf;用羽Fval代替上述命令行中的x,可得最优解处的函 数值FvaL17例 1、min Z=-40 xx-50 x2x1+2x2 30,4 3x1+2x2 W 60,、2x224,解：程序如下c=-40,-50;a=1,2;3,2;0,2;b=30;60;24;x=linprog(c,a,b)|x z=c*x=linprog(c,a,b)18例2:min Z=4巧+3x2xt+x2 5,-6 Xj 10,-lx2 4;解：%I p2.m%c=4,3;a=1,1；b=5;vl b=-6;-1 ;%lower bound of vec t or x%vub=1 0;4;%upper bound of vec t or x%X,Z=l i nprog(c,a,b,vl b,vub)19例3:min Z=-xt+2x2-3x3Fxr+x2+x30；解:%I p3.m%c=-1,2,-3;a=U,1；-1,1,-1；b=7；-2;vlb=0；0；0；%lower bound of vec t or x%V u b=；%upper bound of vec t or x%x=l i npr og(c,a,b,vl b,vub)z=c*x20例4:+x7=40,/+x2+x3x4+x5+x6=15,=35,50,30,*V 7+8+9 0,i=172,9;1/21解：%I p4.m%0=2,1,3,2,2,4,3,4,2;b=40;15;35;beq=50;30;10;a(2,:)=0,1,0,0,1,0,0,1,0 1；a(3,:)=0,0,1,0,0,1,0,0,11；aeq(1,：)=1,1,1,0,0,0,0,0,0;aeq(2,:)=0,0,0,1,1,1,0,0,0;aeq(3,:)=0,0,0,0,0,0,1,1,1;vl b=zer OS(9,1)；%lower bound of vec t or x%V u b=；%upper bound of vec t or x%x,Z=l i npr og(c,a,b,aeq,beq,vl b,vub)225、求解整数线性规划问题:min z=fx,r A-X 利用分支定界法编写,需要将程序拷贝在当 前目录下才可调用L lbxub9且为整数指令：x,fm=I nt ProgFZ(f,A,b,Aeq,beq,lb,ub)例如：%zhengshu1.mf=2；1；-3;A=1 1 2;2 2-1;b=5；1；minz=2xt+x2-3x3 xr+x2+2x3 5s.t 2xr+2x2-x3 1N 0且为整数x,fm=lnt ProgFZ(f,A,b,0;0;0,inf;inf;inf)23二、最优化问题简介及求解最优化技术是一门较新的学科分支。它是在本世 纪五十年代初在电子计算机广泛应用的推动下才 得到迅速发展，并成为一门直到目前仍然十分活 跃的新兴学科。最优化所研究的问题是在众多的 可行方案中怎样选择最合理的一种以达到最优目 标。将达到最优目标的方案称为最优方案或最优决策,搜寻最优方案的方法称为最优化方法，关于最优 化方法的数学理论称为最优化理论。24另外也可用学术味更浓的名称：“运筹学”。由于最优化问题背景十分广泛，涉及的知识 不尽相同，学科分枝很多，因此这个学科名 下到底包含哪些分枝，其说法也不一致。比较公认的是：“规划论”（包括线性和非 线性规划、整数规划、动态规划、多目标规 划和随机规划等），“组合最优化”，“对 策论”及“最优控制”等等。251、最优化问题的数学表述:求目标函数F(X)在约束条件x c D下的最小值或最大值问题。26 2720 0 9B眼科病床的合理安排20 0 8B高等教育学费探讨20 0 7A乘公交，看奥运20 0 6A.的资源配置问题20 0 5BDVD在线租赁20 0 4D公务员招聘工作中录用方案一多目标规划20 0 4A奥运会临时超市网点设计问题20 0 3B露天矿生产的车辆安排问题20 0 2B彩票中的数学2001C基金使用的最优策略一线性规划2001B公交车优化调度20 0 0 B钢管订购和运输问题一二次规划2、数学建模竞赛中的优化问题：3、最优化问题的一般形式无约束最优化问题X目标函数min/(xxeRn约束最优化问题最优解；最优值84、最优化问题分类分类1:J无约束最优化I约束最优化分类2：线性规划I非线性规划线性规划：目标函数与约束函数均为线性函数；非线性规划：目标函数与约束函数中至少有一个 是变量解勺非线性函数；295、求解无约束最优化问题的mat lab指令 求一元函数fun在区间(x1,x2)上的最小值 X=fmin bnd(fun,x1,x2)或x,fval=fmin bn d(fun Kl,X2)求多元无约束函数fun的最小值 x,fval=fminun c(fun,xO)xO 为初值 x,fval=fmin searc h(fun9xO)注意：fminunc不是解决平方相加函数优化问 题的最好方法30函数I sqnonlin专门解决非线性最小二乘问题:叫 n|/(x)l；=叫 n(/i(x)2+/(%)2)调用格式：x=lsqnonlin(fun,xO)x=lsqnonlin(fun5xOJ b,ub)x=lsqnonlin(fun9xOJ b9ub9opt ions)31线性最小二乘问题I sqlin函数：用于解决线性最小二乘问题：minCr-引；x 2Ax bs.t.Aeqx=beq lb x 1x2+x5=1 xr+x2l张李王赵田周 大尢小小小小卷鼎123456身名193191187186180185色置 中锋 中锋 前卫 前卫 后卫 后卫(0-1)规 划“2+%6 4I 1x4+x6 1 2、明 0,1 3、J4、至少补充一名后卫队员大李或小田中间只能入选一名最多补充一名中锋如果大李或小赵入选，小周就不能取选例2经典指派问题n个员工分配做n项工作，已知第i个员工做第j项工作的 成本为Sj,i=l,，n;j=l,，n。分配方案。解设X ij=1 第i员工分配做第j项工作0 否则 n nMinz=ZZcijxij i=l j=lnE=lEI求解0-1规划的Matab指令问题：min/TxAx b s.t.0 =1,2,/45模型转化方法一:固定风险水平，优化收益在实际投资中，投资者承受风险的程度不 一样，若给定风险一个界限a,使最大的一 个风险名芭./M0 a,可找到相应的投资方案。nmax ZG-Pi)巧i=0分芭 Man模型一线性规划模型 0/=1246模型转化方法二:固定盈利水平，极小化风险 若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合。minmax(.x.)n-Pig N Ki=o 模型二s.t t(l+Pi)Xi=M线性规划模型 1=0 x.0/=12 147模型转化-方法3线性加权投资者在权衡资产风险和预期收益两 方面时，希望选择一个令自己满意的 投资组合。因此对风险、收益赋予权 重s(0 s 0/=12/48模型一的求解将具体数据代入,模型一如下：minf=(-0.05,-0.27,-0.19,-0.185,-0.185)(x0 Xi X2 X3 X4)T r xo+l.Olxi+1.02x2+1.045x3+1.065x4=1s.t.0.025x1 Wa0.015x2 Wa 0.055x3 Wa0.026x4 lc=-0.05-0.27-0.19-0.185-0.185;Aeq=l 1.01 1.02 1.045 1.065;beq=l;A=0 0.025 0 0 0;0 0 0.015 0 0;0 0 0 0.055 0;0 0 0 0 0.026;b=a;a;a;a;vlb=0,0509090;vub=;x5val=linprog(c9A9b5Aeq5beq,vlb5vub);a x=x Q=-val plot(a,Q/.f),axis(0 0.1 0 0.5),hold on a=a+0.001;endxlabel(a),ylabel(Q)50计算结果:a=0.0030a=0.0060a=0.0080 a=0.0100 a=0.0200 a=0.0400 x=0.4949x=0 x=0.0000 x=0 x=0 x=0.00000.12000.24000.32000.40000.80000.99010.20000.40000.53330.58430.18820.00000.05450.10910.12710000.11540.22120.0000000Q=0.1266Q=0.2019Q=0.2112Q=0.2190Q=0.2518Q=0.26730.50.450.40.350.3o 0.250.20.150.10.0 5-00 0.01 0.02 0.0 3 0.0 4 0.05 0.06 0.07 0.08 0.09 0.151模型一结果分析1.风险大，收益也大。2.当投资越分散时，投资者承担的风险越 小，这与题意一致。即：冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。3.曲线上的任一点都表示该风险水平的最 大可能收益和该收益要求的最小风险。对于不同风险的承受能力，选择该风险 水平下的最优投资组合。524.在a=0.006附近有一个转折点，在这一点左边,风险增加很少时，利润增长很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说,应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%,Q*=20%,此时风险度为0.0060收益为0.20 19,所对应投资方案为：0 0.2400 0.4000 0.1091 0.221253实验作业实验8：练习2、练习3、练习4、练习5实验9：练习2、练习3、练习4、练习5要求：2人一组；至少选择6个题，写出数学模型，程序、结果 以及结果分析。所选题目应涵盖：整数规划，规划，线性规划54数学实验报告要求1.实验问题2.问题分析:包括解决问题的理论依据，建立 的数学模型以及求解问题的思路和方法。3.程序设计流程图。4.结果分析和结论。5,总结和体会。55