数学模型与数学实验1第一章线性规划

1、当今社会现状：经济快速发展，资源急剧消耗，地球环境不堪重负解决关键：如何利用现有资源安排生产，以取得最大经济效益-数学规划。线性规划（Linear Programming, LP）是其中的重要分支。1947，G.B.Dantzig，单纯形法（Simplex Method）计算机快速求解例 1.1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000 元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各

2、几台，才能使总利润最大？产品甲产品甲产品乙产品乙机器资源（小时）机器资源（小时）机器A2110机器B118机器C017利润（元/件）40003000概括：在如下资源条件下，应生产甲、乙机床各几台，才能使总利润最大？数学模型：设该厂生产x1台甲机床和x2乙机床时总利润最大，则x1, x2应满足（目标函数） max z = 4000 x1 + 3000 x2 (subject to) s.t.2x1+x210 (约束条件)x1+x2 8x2 7x1,x20其中x1, x2称为决策变量。定义（线性规划问题）：在一组线性约束条件下，求一线性目标函数的最大（或最小）。单纯形法基本思想：线性规划问题的可行

3、域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。据此可以完成计算求解。LP问题标准形式可行解：满足约束条件的解可行域：所有可行解构成的集合最优解、较优解11max,1,2,. .0,1,2, .njjjni jjijjzc xa xb imstxjn目标函数约束条件12 ,Tnx xxxLP问题的Matlab形式(向量形式)求解命令格式x,fval=linprog(f,A,b,Aeq,beq,lb,ub,x0)注：更多内容可help linprog了解min,. .,Tzst.目标函数约束条件f xA xbAeq xbeqlbxub例1.2 求解LP问题解: 1)编

4、写m文件ex1_2.mf=2;3;-5; A=-2,5,-1;1,3,1; b=-10;12;Aeq=1,1,1; beq=7; lb=zeros(3,1);x=linprog(-f,A,b,Aeq,beq,lb);z=f*x; 2)执行ex1_2.m123123123123123max235,7,2510,. .312,0.zxxxxxxxxxstxxxx x x注意不同情形下的命令格式x,z=linprog(f,A,b,lb,ub,x0)x,z=linprog(f,Aeq,beq,lb,ub,x0)x,z=linprog(f,A,b,Aeq,beq,ub)例1.4 规划问题1121212,

5、22,1,1,min. .minmin,.,.,1,.iiiiiiTTTnnnTniiiiiiiiizxxxstzzuvsxuvxxxxxuvu uuvutsvtvv +A xbcucvuAuvbAAbvu,v0.u,v0.uvc例1.5 求解数学规划问题解：1)转化为Matlab标准形式 由1234123412341234min342. .31230.5zxxxxxxxxstxxxxxxxx +212341234,22,iiiiiiiiiiTTiixuvxuxxxxuvu u u uvv vvvuv且1,min.11.,111113 ,1,2,3,4,2, 1, 0.51123,min. .

6、niiiiTTTzc uvstzst Auvbu,v0.uAAbcuvcvu,v0.Acb2)编写m文件ex1_5.mA=1,-1,-1,1;1,-1,1,-3;1,-1,-2,3;b=-2;-1;-0.5;c=1,2,3,4;f=c;c; Amat=A,-A; lb=zeros(8,1);y=linprog(f,Amat,b,lb);z=f*y;x=y(1:4)-y(5:8);3)执行ex1_5.m例1.6 某商品有m个产地、n个销地，各产地的产量分别为a1,a2,am，各销地的需求量分别为b1,b2,bn。若该商品由i产地运到j销地的单位运价为cij，问应该如何调运才能使总运费最省？111

7、1,1,2,min. .,1,2, ,nijijmnmijijijjijiijxa imzc xstxbjnx0.改写为Matlab形式，由11221210010001001001000100,1,1,0111000nnmnmTmxcxcxcaaaxcAeqbeq且1200011100011102,211,min. .2200000000000011.1nmnTnTbbbzstAeqbeqAeqbeqxc xAeqbeqx求解程序transport.mfunction x,z=transport(a,b,c)%a is m*1,b is 1*n, c is m*nm,n=size(c);Aeq

8、1=;Aeq2=;for j=1:nAeq1=Aeq1,eye(m);endfor i=1:mtmat=zeros(n);tmat(i,:)=1;Aeq2=Aeq2,tmat;endAeq=Aeq1;Aeq2;beq1=a;beq2=b;beq=beq1;beq2;x,z=linprog(c(:),Aeq,beq,zeros(m*n,1);ex1_6.mclear;clc;m=4;n=5;a=rand(m,1);b=rand(1,n);c=rand(m,n);x,z=transport(a,b,c);例1.7 min maxmin,1,2, ,. .0?.min0,0,1,2, ,. .m x

9、0.a,iiiiixyiiiyiiiiiiixyvinstvvxyvyxvinstvxyxyv yxvvgap改写为Matlab形式，由121211211000100 , , ,0,0,1 ,01100010001, ,inf, inf,0,10101, 1,101121000100011000101100TTnnTTTTTnnnnx xxy yyv xyf =z = xylbAbA2100, 2,0nnb得11,min. .22.TstAbzf zAbzlb社会经济快速发展，各种理财产品层出不穷，投资行为变得越来越普及（财团、公司、boss、大妈？）。如何在当前复杂环境下对有限资本进行合理投

10、资？可用投资总额为M；市场上有n种资产si (i=1,2,n)可选，投资si时，收益率qi，风险损失率ri，交易费率为pi(购买额不超ui时按ui计算)；总体风险可用投资资产中最大的一个风险来度量；同期银行存款利率为q0(=5%)，无交易费无风险；给定n=4时数据，试设计投资方案使静收益尽可能大，总体风险尽可能小。n=4时数据siqi(%)ri(%)pi(%)uis1282.51103 s2211.52198 s3 235.54.5 52s4252.66.5 40a)符号规定si表示第i种投资项目,i=0,1,n, s0表示存入银行;qi,pi,ri表示si的收益率,交易费率,风险损失率,p0

11、=r0=0;ui表示si的交易定额,u0=0;xi表示投资项目si的资金;R表示总体风险;Q表示总体收益.b)基本假设投资数额M相当大;总体风险R用所投资项目si中的最大风险度量;si之间相互独立;在投资时期内,ri,pi,qi为定值,不受意外因素影响;收益Q和风险R不受其它因素干扰.a)总体风险R用所投资项目si中的最大风险度量，即R=max rixi, i=0,1,nb)投资si的交易费为pimaxxi,ui,i=0,1,2,n故投资si的净收益为Qi=qixi-pimaxxi,uic)要使净收益尽可能大，总体风险尽可能小，即max iQi和min R需要同时进行，此即多目标规划适当条件(

12、uiM)下可以考虑近似模型000000maxmax,max,min max.min max. . .1,1,0,0,1, .0,0,1, .nniiiiiiiiiinniiiiiinniiiiiiiiq xpx uqpxrxrxststpxMpxMxinxind)模型简化多目标规划的求解较复杂，一般可转化为单目标规划再进行求解。约束风险，优化收益(模型ex1_8a)；若投资者所能承受最高风险度为a，则00,0,1, ,max. .1,0,0,1, .nniiiiiiiiiiqpxstpxrxMiMinaxn约束收益，优化风险(模型ex1_8b)；若投资者要求的最低综合收益率为k，则000min

13、 max. .1,0,0,1, .,nniiiiiiiiniiirxstpqpxMxMkxin风险-收益平衡优化(模型ex1_8c)，即对风险和收益分别赋以权重s和1-s；000minmax. .1,0,0,1, .1nniiiiiiiniiiisrxqpxstpxMxinsa)模型可改写为Matlab形式编写m文件ex1_8a.mclear;clc;M=1e5;r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2;p=0,1,2,4.5,6.5*1e-2;u=0,103,198,52,40*1e-2; min. .1,0.TTMastMdiag r xp

14、qxpxxf=p-q;A=diag(r);Aeq=(1+p);beq=M;lb=zeros(5,1);aset=0:0.001:0.05;xset=;Qset=;for a=asetb=M*a;x,rQ=linprog(f,A,b,Aeq,beq,lb); xset=xset,x;Qset=Qset,rQ;endplot(aset,Qset,k*);xlabel(a);ylabel(Q);执行ex1_8a.m，绘图结果如下b)模型可改写为LP形式000min.,.1,0,0,1max0,0,1, , .niiiniiiiniiiiiivstpxMvrxrxixqpnMnxikv 进一步改写为M

15、atlab形式 11 1111,1min. .1,00,.,0TTnnTndiagMvstMk 010rypxyff y+ pyyqy编写m文件ex1_8b.mclear;clc;M=1e5;r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2;p=0,1,2,4.5,6.5*1e-2;u=0,103,198,52,40*1e-2;f=zeros(5,1);1;A=diag(r),-ones(5,1);p-q,0;Aeq=(1+p),0;beq=M;lb=zeros(5,1);kset=0.05:0.01:0.5;yset=;Rset=;rRset=;fo

16、r k=ksetb=zeros(5,1);-M*k;y,R=linprog(f,A,b,Aeq,beq,lb); yset=yset,y;Rset=Rset,R;rRset=rRset,max(r.*y(1:5);endfigure;hold on;plot(kset,Rset,k:);plot(kset,rRset,b.-);xlabel(k);ylabel(R);legend(ideal,real);执行ex1_8b.m，绘图结果如下c)模型三可改写为LP形式000max0min. .1,0,0,1,0,1,.,1,niiiiniiiiniiiiivrxrZvqpxstpxvssixxnn

17、Mi进一步改写为Matlab形式 1 11 1,1min. .,00.1,nnTTdiassvsMgZ =t 10ryxpqyf+ pf yyy编写m文件ex1_8c.mclear;clc;M=1e5;r=0,2.5,1.5,5.5,2.6*1e-2;q=5,28,21,23,25*1e-2;p=0,1,2,4.5,6.5*1e-2;u=0,103,198,52,40*1e-2;A=diag(r),-ones(5,1);b=zeros(5,1);Aeq=(1+p),0;beq=M;lb=zeros(5,1);sset=0:0.1:1;yset=;Zset=;rZset=;Qset=;Rset=;for s=ssetf=(1-s)*(p-q);s;y,Z=linprog(f,A,b,Aeq,beq,lb); yset=yset,y;Zset=Zs