实验报告——线性规划建模与求解

１数学实验报告实验序号：1日期：2012年6月1日班级水文1001姓名熊元武学号1101550120实验名称线性规划建模与求解问题背景描述：线性规划可以用来解决资源分配问题，成本效益平衡问题。常用的方法有图解法和单纯形方法。掌握好线性规划问题求解方法非常重要。实验目的：1．掌握线性规划求解的方法，了解线性规划建模的核心思想与一般步骤。2．学会求解线性规划问题，掌握解题方法。3．学会使用matlab或lindo求解线性规划问题的基本方法和步骤。4．掌握用线性规划方法解决一些相关的实际问题。实验原理：单纯性方法的基本思路是：先找一个基本可行解，判断其是否为最优解，如果不是最优解，转到相邻的基本可行解，并使目标函数值不但增大，直到找到最优解或判断有无界解，无解为止。使用matlab可以解决一般线性规划求解问题。２实验所用软件及版本：Matlab7.0主要内容（要点）：1.自学运筹学实验指导书第三章，掌握线性规划求解的软件技术。2.利用软件实现运筹学实验指导书第三章例题的求解计算。3.参照例题，总结求解过程的重难点，学会求解方法。4.利用所学，完成习题1.2和1.9。（习题来自《运筹学》第三版清华大学出版社）5.完成实验中的实际问题求解。３实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）：习题求解1.2将下列线性规划转化为标准型，并用程序求解。解：转化为标准型如下：用matlab求解命令如下：f=[-3,4,-2,5,0,0];aeq=[4,-1,2,-4,0,0;1,1,2,-1,1,0;-2,3,-1,2,0,-1];beq=[-2,14,2]’;lb=[0,0,0,-inf,0,0,];[x,fval,exitflag,output,lambda]=linprog(f,[],[],aeq,beq,lb);解得结果为：x=[0.0000,0.4000,0.0000,0.4000,14.0000,0.0000]’fval=3.6000exitflag=10x,x,x22xx-3x+2x-14x-3xx+x2-x-2xx-4x..5x+2x-4x+3x-=zMin3214321432143214321ts0,s,sx,x,x22xx-3x+2x-14sx-3xx+x2-x-2xx-4x..5x+2x-4x+3x-=zMin21321243211432143214321sts４实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页）：1.9司机和乘务人员区段上班问题解：设xi人在第i班次开始上班（i=1,2,3,4,5,6）Z为所需司机和乘务人员总人数。求解命令：f=[1,1,1,1,1,1];a=[-1,0,0,0,0,-1;-1,-1,0,0,0,0;0,-1,-1,0,0,0;0,0,-1,-1,0,0;0,0,0,-1,-1,0;0,0,0,0,-1,-1];b=[-60,-70,-60,-50,-20,-30]’;lb=zeros(6,1);[x,fval,exitflag,output,lambda]=linprog(f,a,b,[],[],lb);解得结果为：x=[41.9176,28.0824,35.0494,14.9506,9.8606,20.1394]fval=150.0000exitflag=10x,x,xx,x,x302050607060..x+xx+x=zMin654321655443322161554321xxxxxxxxxxxxtsxx５实验过程记录（含：基本步骤、主要程序清单及异常情况记录等）（接上页）：实验书中的实际问题求解：解：设ai为0-1变量，表示第i根8M线材设bi为0-1变量，表示第i根12M线材Xji,表示第i根8M线材截得的第j种长度的线材数目Yji,表示第i根12M线材截得的第j种长度的线材数目Z为浪费的线材总长度又由于150*(8+12)远大于所需线材总长度，故知所用两种线材每种不超过150根解不出变量1-0为,a0,y,x*855.075.085.18.26.3y2.6.........*855.075.085.18.26.3y2.6*855.075.085.18.26.3x2.6.........*855.075.085.18.26.3x2.6..*12a*8=zMiniji,ji,1206,1205,1204,1203,1202,1201,12016,15,14,13,12,11,11206,1205,1204,1203,1202,1201,12016,15,14,13,12,11,1120161,120161,12011201iiiijjiijjiiibbyyyyybyyyyyaxxxxxaxxxxxtsyxb６实验结果报告与实验总结：对于实验指导书中matlab使用的例题和方法已经基本掌握，《运筹学》书中例题与方法处于基本了解的程度，不能灵活运用，但书后习题全都能独立完成，已经有一定解题能力。且实验书中的实际运用题的简易版问题的解题方法也已经掌握，但此实验题仍很吃力。思考与深入：1.线性规划问题的建模与求解由完全不会到初窥门道比较容易，但对于复杂的实际问题来说，还是需要一定的灵活运用与变通。但解决实际问题才是最后目的。2．对于本实验中的实际运用题的思考：如果能制作一张8M和12M线材所能裁得的各种规定尺寸根数种类表，可能是一种解题方法，但12M线材所能裁得种类太多，实施起来复杂。教师评语：