数学实验报告——利用MALTAB进行线性规划.docx

实验六 线性规划一、债券投资问题描述给定可供购进的证券以及其信用等级、到期年限、收益。市政证券的收益可以免税，其他证券的收益需按50%的税率纳税。此外还有以下限制：(1) 政府及代办机构的证券总共至少要购进400万元；(2) 所购证券的平均信用等级不超过1.4；(3) 所购证券的平均到期年限不超过5年。1、若经理有1000万元资金，应如何进行投资？2、如果能以2.75%的利率借到不超过100万元资金，该经理应如何操作？3、在1000万元资金情况下，若证券A的税前收益增加为4.5%，投资应够改变？若证券C的税前收益减少为4.8%，投资应否改变？简要分析本题是一个比较简单的线性规划+扰动分析问题，对所谓问题进行建模，可以得到线性规划如下：设分别购入A、B、C、D、E五种证券a、b、c、d、e万元。于是对第1问有b+c+d4002a+2b+c+d+5e1.4(a+b+c+d+e)9a+15b+4c+3d+2e5(a+b+c+d+e)a+b+c+d+e100a,b,c,d,e0maxf=4.3%a+5.4%50%b+5%50%c+4.4%50%d+4.5%e对第2问，增设a1,b1,c1,d1,e1分别表示用借来的资金购买证券的金额，于是规划变为b+c+d+b1+c1+d14002a+a1+2b+b1+c+c1+d+d1+5(e+e1)1.4(a+b+c+d+e+a1+b1+c1+d1+e1)9(a+a1)+15(b+b1)+4(c+c1)+3(d+d1)+2(e+e1)5(a+b+c+d+e+a1+b1+c1+d1+e1)a+b+c+d+e1000a1+b1+c1+d1+e1100a,b,c,d,e,a1,b1,c1,d1,e10maxf=4.3%a+a1+5.4%50%b+b1+5%50%c+c1+4.4%50%d+d1+4.5%(e+e1)-2.75%(a1+b1+c1+d1+e1)对第三问，仅需将第一问中的规划做一点修改即可。方法与公式线性规划方法：(1)内点算法opt1=optimset(largescale,on);x,f,exitflag,output,lag= linprog(c,A,b,opt1);(2)有效集方法opt2=optimset(largescale,off);x,f,exitflag,output,lag= linprog(c,A,b,opt2);(3)单纯形算法 opt3=optimset(largescale,off,simplex,on);x,f,exitflag,output,lag= linprog(c,A,b,opt3);结果与分析1、第一问：最优解最优目标值平均迭代次数平均使用时间内点218.1818188.45E-09736.3636362.29E-0845.4545455-29.8363636352 60.01020192有效集218.181818-8.81E-16736.363636045.4545455-29.8363636364 50.004822365单纯形218.1818180736.363636045.4545455-29.8363636364 40.009097038使用三种方法进行计算，得到结果对比如下：结果为：应购买A种证券218.18万元、B种证券0元、C种证券736.36万元、D种证券0元、E种证券45.45万元；最终得到的收益约为29.8364万元。通过对比可以发现以下几点结论：(1)三种算法所得的计算结果基本一致，各种算法计算得到的目标值仅在小数点后第10位才有所区别；(2)三种算法得到的最优解略有区别，其中内点算法没有得出第2、4项为0的结论（虽然已很接近），这也许只是因为计算精度的问题，但也有可能是算法本身的原因；(3)迭代次数上，内点算法有效集算法单纯性算法。但是值得注意的是，这里的问题仅仅是一个n=5的小规模规划的例子，不能以此得出“大规模算法比中、小规模算法需要更多次迭代“的结论；(4)使用时间上，这里对三种算法分别进行了100次调用，计算得到平均使用时间。从表格可以看出使用时间上内点算法单纯性算法有效集算法。当然，这个结论在未进行进一步的实验前也不能推广2、第二问继续采用三种算法，计算结果如下：最优解内点229.11.74E-07739.39968.11E-0631.52 1.09E+011.73E-077.06E+015.39E-0618.478886有效集240-5.32E-15710050-1.36E-14-6.71E-161000-8.52E-15单纯形24007100500010000将所得的最优解根据债券类型进行合并，即计算a+a1,b+b1,c+c1,d+d1,e+e1，记录如下：最优解最优目标值平均迭代次数平均使用时间内点240.00 0.00 810.00 0.00 50.00 -30.0699999606 70.011674有效集240.00 0.00 810.00 0.00 50.00 -30.0700000000 100.008759单纯形240.00 0.00 810.00 0.00 50.00 -30.0700000000 50.010294结果为：应购买A种证券240万元、B种证券0元、C种证券810万元、D种证券0元、E种证券50万元；最终得到的收益约为30.07万元。观察表格可以发现一个有意思的现象，即通过内点算法计算得到的结果与使用有效集或单纯形算法得到的结果，虽然最终结论一样，但是在如何分配使用已有资金和贷款资金上并不相同。产生这种现象是因为该线性规划存在不止一个最优解，即目标函数的最大值对应的不是一个点。本次实验的结果出现了两个最优解，这意味着最优解至少是一条线。其实从实际意义上也很好理解，题目中已有资金和贷款资金唯一的区别就是贷款资金需要交利息，而这一点在规划方程组中仅体现在目标函数中，也就是说它们在其它约束上是没有区别的，即a与a1相同，b与b1相同等等。这样也就不难理解实验过程中出现了不止一个最优解的现象。通过对比还可以得到以下几点结论：(1)本例中迭代次数上有效集算法内点算法单纯性算法；(2)使用时间上内点算法单纯性算法有效集算法；(3)有效集算法得到的最优解与单纯形算法得到的最优解仍略有区别，其中有效集算法没有得出第2、4项为0的结论（虽然已很接近），猜测这是算法本身的原因。3、第三问前面已经对三种算法进行了对比和分析，本小问不再继续采用三种算法，仅选用最经典的单纯形算法。改变规划进行计算：A证券税前收益增加结果如下：最优解最优目标值迭代次数218.18180736.3636045.45455-30.272727274 可以看出投资方案不应改变。但是由于个别证券收益有所提升，所以最优目标值有所“提高”。C证券税前收益减少最优解最优目标值迭代次数3360064816-29.4243 可以看出，投资方案有所改变，而且投资组合也出现了改变，说明基解发生了变化。由于个别证券收益有所下降，所以最优目标值“下降”理所当然。4、总结(1)单纯形、有效集、内点算法都能简单有效地解决线性规划基本问题。对于小规模线性规划而言，有效集算法效率更高，单纯性算法结果更为可靠。(2)理论上，通过分析单纯形表格法求解过程的最终表格，可以得到严格的敏感性分析结论，但是由于本题计算较为繁琐，我没有使用表格法进行计算。观察Lagrange乘子可以在敏感性分析上得出一些基本的结论，但是无法解决目标函数变化的情况。程序清单1、第一问clear;clc;c=-4.3e-2 2.7e-2 2.5e-2 2.2e-2 4.5e-2;A=0 -1 -1 -1 0;0.6 0.6 -0.4 -0.4 3.6;4 10 -1 -2 -3;1 1 1 1 1;b=-400,0,0,1000;v1=0 0 0 0 0;opt1=optimset(largescale,on);tic;for i = 1:100 x1,f1,exitflag1,output1,lag1= linprog(c,A,b,v1,opt1);endtime1 = toc;time1 = time1/100;opt2=optimset(largescale,off);i=0;tic;for i = 1:100 x2,f2,exitflag2,output2,lag2= linprog(c,A,b,v1,opt2);endtime2 = toc;time2 = time2/100;opt3=optimset(largescale,off,simplex,on);i=0;tic;for i = 1:100 x3,f3,exitflag3,output3,lag3= linprog(c,A,b,v1,opt3);endtime3 = toc;time3 = time3/100;2、第二问的线性规划c=-4.3e-2 2.7e-2 2.5e-2 2.2e-2 4.5e-2 4.3e-2-2.75e-2 2.7e-2-2.75e-2 2.5e-2-2.75e-2 2.2e-2-2.75e-2 4.5e-2-2.75e-2;A=0 -1 -1 -1 0 0 -1 -1 -1 0; 0.6 0.6 -0.4 -0.4 3.6 0.6 0.6 -0.4 -0.4 3.6; 4 10 -1 -2 -3 4 10 -1 -2 -3; 1 1 1 1 1 0 0 0 0 0; 0 0 0 0 0 1 1 1 1 1;b=-400,0,0,1000,100;v1=0 0 0 0 0 0 0 0 0 0;3、第三问的线性规划 (1)A改变clear;clc;c=-4.5e-2 2.7e-2 2.5e-2 2.2e-2 4.5e-2;A=0 -1 -1 -1 0;0.6 0.6 -0.4 -0.4 3.6;4 10 -1 -2 -3;1 1 1 1 1;b=-400,0,0,1000;v1=0 0 0 0 0;opt3=optimset(largescale,off,simplex,on);x3,f3,exitflag3,output3,lag3= linprog(c,A,b,v1,opt3);(2)C改变clear;clc;c=-4.3e-2 2.7e-2 2.4e-2 2.2e-2 4.5e-2;A=0 -1 -1 -1 0;0.6 0.6 -0.4 -0.4 3.6;4 10 -1 -2 -3;1 1 1 1 1;b=-400,0,0,1000;v1=0 0 0 0 0;opt3=optimset(largescale,off,simplex,on);x3,f3,exitflag3,output3,lag3= linprog(c,A,b,v1,opt3);二、牧马问题描述给定养马所需的最低营养需求、各种饲料中各种营养的含量以及各种饲料的价格，确定如何以最低的成本满足最低的营养需求。简要分析这仍旧是一个比较简单的线性规划问题。假设分别购买干草、燕麦片、饲料块、高蛋白浓缩料a,b,c,d个单位。由题意有：0.5a+b+2c+6d402a+4b+0.5c+d205a+2b+c+2.5d45a,b,c,d0minf=1.8a+3.5b+0.4c+d解此线性规划即可。为继续第一题的探究，仍旧使用三种算法进行解题。最后作为探究，通过lagrange乘子做出大致的敏感性分析，并写出其对偶问题并求解。方法与公式线性规划方法：(1)内点算法opt1=optimset(largescale,on);x,f,exitflag,output,lag= linprog(c,A,b,opt1);(2)有效集方法opt2=optimset(largescale,off);x,f,exitflag,output,lag= linprog(c,A,b,opt2);(3)单纯形算法 opt3=optimset(largescale,off,simplex,on);x,f,exitflag,output,lag= linprog(c,A,b,opt3);结果与分析1、解题通过计算，得到如下结果最优解最优目标值平均迭代次数平均使用时间内点51.42E-13201.66E-1217 100.013959495有效集5020017 50.00425513单纯形5020017 20.008455142结果为：应购买干草5捆，饲料块20块。总价格为17美元。简要对比分析如下：(1)平均迭代次数上， 内点算法有效集算法单纯性算法。(2)平均时间上，内点算法单纯性算法有效集算法。(3)最优解中，内点算法仍旧没有计算得出0。2、敏感性分析单纯性算法的Lagrange乘子如下：从ineqlin可以看出，第一项约束不是有效约束。通过计算可以发现，当最优解取5, 0, 20, 0时，蛋白质含量为45磅，超过了需求，证实这不是有效约束。这说明，当各种饲料的蛋白质含量在某一范围内变化时，最优解以及目标函数值并不会变化。3、对偶问题及其解0.5x+2y+5z1.8x+4y+2z3.52x+0.5y+z0.46x+y+2.5z1x,y,z0maxf=40x+20y+45z实验结果如下（这里仅选用单纯形法）：最优解最优目标值（-f）迭代次数00.40.2-174 可以看到，最优目标值为17，与原问题最优解一致。这就是线性规划中的强对偶定理。由于问题比较难以理解，这里没有得出有关其现实意义的结论。4、总结 这道题比较简单，计算过程中没有太多问题。第一部分有关三种算法的对比与第一道题得到的结果一致。有关敏感性分析也与之前的想法一致。线性规划对偶问题是很值得研究的方向。程序清单1、原问题clear;clc;c=1.8 3.5 0.4 1;A=-0.5 1 2 6;2 4 0.5 1;5 2 1 2.5;b=-40,20,45;v1=0 0 0 0;opt1=optimset(largescale,on);tic;for i = 1:100 x1,f1,exitflag1,output1,lag1= linprog(c,A,b,v1,opt1);endtime1 = toc;time1 = time1/100;opt2=optimset(largescale,off);