数学建模(美赛)数学规划.

线性规划整数规划目标规划非线性规划动态规划图论排队论数学规划模型线性规划目的内容2.掌握用数学软件包求解线性规划问题.1.了解线性规划的基本内容.2.用数学软件包MATLAB求解线性规划问题.1.两个引例.3.建模案例：投资的收益与风险.问题：任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件.假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表.问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？单位工件所需加工台时数单位工件的加工费用车床类型工件1工件2工件3工件1工件2工件3可用台时数甲0.41.11.013910800乙0.51.21.311128900引例解设在甲车床上加工工件1、2、3的数量分别为x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为x4、x5、x6,可建立以下线性规划模型：6543218121110913minxxxxxxz142536123456x400600500s.t.0.41.18000.51.21.39000,1,2,,6ixxxxxxxxxxxxi解答线性规划模型的一般形式11min,1,2,...,.s.t.0,1,2,...,.niiinikkikiucxaxbinxin目标函数和所有的约束条件都是设计变量的线性函数.min.s.tucxAxbvlbxvub矩阵形式：用MATLAB优化工具箱解线性规划minz=cXs.t.AXb1.模型：命令：x=linprog（c,A,b）2.模型：minz=cXs.t.AXbbeqXAeq命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=[]，b=[].bAX3.模型：minz=cXs.t.AXbbeqXAeqVLB≤X≤VUB命令：[1]x=linprog（c，A，b，Aeq,beq,VLB，VUB）[2]x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：[1]若没有等式约束:,则令Aeq=[],beq=[].[2]其中X0表示初始点beqXAeq4.命令：[x,fval]=linprog(…)返回最优解ｘ及ｘ处的目标函数值fval.解编写M文件xxgh1.m如下：c=[-0.4-0.28-0.32-0.72-0.64-0.6];A=[0.010.010.010.030.030.03;0.02000.0500;00.02000.050;000.03000.08];b=[850;700;100;900];Aeq=[];beq=[];vlb=[0;0;0;0;0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)例1max6543216.064.072.032.028.04.0xxxxxxz123456s.t.0.010.010.010.030.030.03850xxxxxx70005.002.041xx10005.002.052xx90008.003.063xx01,2,,6jxjToMATLAB(xxgh1)例2321436minxxxz123s.t.120xxx301x5002x203x解:编写M文件xxgh2.m如下：c=[634];A=[010];b=[50];Aeq=[111];beq=[120];vlb=[30,0,20];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh2)123min(634)xzxx32120030xxx123111120s.t.01050xxxs.t.Xz8121110913min9008003.12.15.000000011.14.0X500600400100100010010001001X，0654321xxxxxxX改写为：例3问题一的解答问题编写M文件xxgh3.m如下:f=[1391011128];A=[0.41.110000000.51.21.3];b=[800;900];Aeq=[100100010010001001];beq=[400600500];vlb=zeros(6,1);vub=[];[x,fval]=linprog(f,A,b,Aeq,beq,vlb,vub)ToMATLAB(xxgh3)结果:x=0.0000600.00000.0000400.00000.0000500.0000fval=1.3800e+004即在甲机床上加工600个工件2,在乙机床上加工400个工件1、500个工件3，可在满足条件的情况下使总加工费最小为13800.投资的收益和风险一、问题提出市场上有n种资产is（i=1,2，…，n）可以选择，现用数额为M的相当大的资金作一个时期的投资.这n种资产在这一时期内购买is的平均收益率为ir，风险损失率为iq，投资越分散，总的风险越小，总体风险可用投资的is中最大的一个风险来度量.购买is时要付交易费，(费率ip)，当购买额不超过给定值iu时，交易费按购买iu计算.另外，假定同期银行存款利率是0r，既无交易费又无风险.（0r=5%）已知n=4时相关数据如下：isir（%）iq（%）ip（%）iu（元）S1282.51103S2211.52198S3235.54.552S4252.66.540试给该公司设计一种投资组合方案，即用给定的资金M，有选择地购买若干种资产或存银行生息，使净收益尽可能大，使总体风险尽可能小.基本假设：1.投资数额M相当大,为了便于计算，假设M=1；2．投资越分散，总的风险越小；3．总体风险用投资项目is中最大的一个风险来度量；4．n种资产is之间是相互独立的；5．在投资的这一时期内,ri,pi,qi，r0为定值，不受意外因素影响；6．净收益和总体风险只受ri,pi,qi影响，不受其他因素干扰.二、基本假设和符号规定符号规定：Si：第i种投资项目，如股票，债券ri,pi,qi：分别为Si的平均收益率,交易费率，风险损失率ui：Si的交易定额0r：同期银行利率xi：投资项目Si的资金a：投资风险度Q：总体收益ΔQ：总体收益的增量三、模型的建立与分析1.总体风险用所投资的Si中最大的一个风险来衡量,即max{qixi|i=1，2,…,n}2．购买Si所付交易费是一个分段函数,即pixixiui交易费=piuixi≤ui而题目所给定的定值ui(单位:元)相对总投资M很小,piui更小,可以忽略不计,这样购买Si的净收益为(ri-pi)xi3．要使净收益尽可能大，总体风险尽可能小,这是一个多目标规划模型:目标函数maxniiiixpr0)(minmax{qixi}约束条件0(1)niiipx=Mxi≥0i=0,1,…,n4.模型简化：c．投资者在权衡资产风险和预期收益两方面时，希望选择一个令自己满意的投资组合.因此对风险、收益赋予权重s（0＜s≤1)，s称为投资偏好系数.模型3目标函数：mins{max{qixi}}-（1-s）niiiixpr0)(约束条件0(1)niiipx=M，xi≥0i=0,1,2，…，nb．若投资者希望总盈利至少达到水平k以上，在风险最小的情况下寻找相应的投资组合.模型2固定盈利水平，极小化风险目标函数：R=min{max{qixi}}约束条件：niiiixpr0)(≥k，Mxpii)1(，xi≥0i=0，1，…，na．在实际投资中，投资者承受风险的程度不一样，若给定风险一个界限a，使最大的一个风险qixi/M≤a，可找到相应的投资方案.这样把多目标规划变成一个目标的线性规划.模型1固定风险水平，优化收益目标函数：Q=max11)(niiiixpr约束条件：Mxqii≤aMxpii)1(，xi≥0i=0,1,…,n四、模型1的求解模型1为:minf=(-0.05,-0.27,-0.19,-0.185,-0.185)(x0x1x2x3x4)Tx0+1.01x1+1.02x2+1.045x3+1.065x4=10.025x1≤a0.015x2≤as.t.0.055x3≤a0.026x4≤axi≥0(i=0，1，…，4)由于a是任意给定的风险度，到底怎样给定没有一个准则，不同的投资者有不同的风险度.我们从a=0开始，以步长△a=0.001进行循环搜索，编制程序如下：a=0;while(1.1-a)1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);ax=x'Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')ToMATLAB（xxgh5）a=0.0030x=0.49490.12000.20000.05450.1154Q=0.1266a=0.0060x=00.24000.40000.10910.2212Q=0.2019a=0.0080x=0.00000.32000.53330.12710.0000Q=0.2112a=0.0100x=00.40000.584300Q=0.2190a=0.0200x=00.80000.188200Q=0.2518a=0.0400x=0.00000.99010.000000Q=0.2673计算结果：五、结果分析返回4.在a=0.006附近有一个转折点，在这一点左边，风险增加很少时，利润增长很快.在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是a*=0.6%，Q*=20%，所对应投资方案为:风险度收益x0x1x2x3x40.00600.201900.24000.40000.10910.22123.曲线上的任一点都表示该风险水平的最大可能收益和该收益要求的最小风险.对于不同风险的承受能力，选择该风险水平下的最优投资组合.2.当投资越分散时，投资者承担的风险越小，这与题意一致.即:冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资.1.风险大，收益也大.整数规划解设在甲车床上加工工件1、2、3的数量分别为整数x1、x2、x3，在乙车床上加工工件1、2、3的数量分别为整数x4、x5、x6,可建立以下整数线性规划模型：6543218121110913minxxxxxxz142536123456x400600500s.t.0.41.18000.51.21.39000,1,2,,6ixxxxxxxxxxxxi解答）为整数，，，（且621iix）为整数，，，（且521iix目标规划一、多目标规划及其解•多目标规划包含有三大要素：目标、方案和决策者•多目标规划中的方案即为决策变量，也称为多目标问题的解。备选方案即决策问题的可行解。在多目标决策中，有些问题的方案是有限的，有些问题的方案是无限的。方案有其特征或特性，称之为属性。例题某工厂在一个计划期内生产甲、乙两种产品，各产