实验序号:■实验名称问题背景描述:1数学实验报告日期:2012年6月1日主名熊兀武学号1101550120线性规划建模与求解线性规划可以用来解决资源分配问题,成本效益平衡问题。常用的方法有图解法和单纯形方法。掌握好线性规划问题求解方法非常重要。实验目的:1・掌握线性规划求解的方法,了解线性规划建模的核心思想与一般步骤。2・学会求解线性规划问题,掌握解题方法。3・学会使用matlab或lindo求解线性规划问题的基本方法和步骤。4・掌握用线性规划方法解决一些相关的实际问题。实验原理:单纯性方法的基本思路是:先找一个基本可行解,判断其是否为最优解,如果不是最优解,转到相邻的基本可行解,并使目标函数值不但增大,直到找到最优解或判断有无界解,无解为止。使用matlab可以解决一般线性规划求解问题。2实验所用软件及版本:Matlab7.0主要内容(要点):1.自学运筹学实验指导书第三章,掌握线性规划求解的软件技术。2.利用软件实现运筹学实验指导书第三章例题的求解计算。3.参照例题,总结求解过程的重难点,学会求解方法。4.利用所学,完成习题1.2和1.9。(习题来自《运筹学》第三版清华大学出版社)5.完成实验中的实际问题求解。3实验过程记录(含:基本步骤、主要程序清单及异常情况记录等):习题求解1.2将下列线性规划转化为标准型,并用程序求解。Minz=-3x+4x-2x+5x12344x-x+2x-x=-21234x+x+3x-x<14S..1234-2x+3x-x+2x>21234x,x,x>0V123解:转化为标准型如下:Minz=-3x+4x-2x+5x12344x-x+2x-x=-21234x+x+3x-x+s=14S.t.12341-2x+3x-x+2x一s=212342x,x,x,s,s>0V12312用matlab求解命令如下:f=[-3,4,-2,5,0,0];aeq=[4,-l,2,-4,0,0;l,l,2,-l,l,0;-2,3,-l,2,0,-l];beq=[-2,14,2]';lb=[O,O,O,-inf,O,O,];[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=1Minz=x1x+x16x+x12x+x23x+x34x+x45x+x56s.4实验过程记录(含:基本步骤、主要程序清单及异常情况记录等)(接上页))1.9司机和乘务人员区段上班问题解:设x人在第i班次开始上班(i=1,2,3,4,5,6)Z为所需司机和乘务人员总人数。+x+x+x+x+x23455>60>70>60>50>20>30x,x,xx,x,x>0123456求解命令:f=[l丄1丄1,1];a=[-l,O,O,O,O,-l;-l,-l,O,O,O,O;O,-l,-l,O,O,O;O,O,-l,-l,O,O;O,O,O,-l,-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=15实验过程记录(含:基本步骤、主要程序清单及异常情况记录等)(接上页))实验书中的实际问题求解:解:设a为0-1变量,表示第i根8M线材设b'为0-1变量,表示第i根12M线材X表示第i根8M线材截得的第j种长度的线材数目Y表示第i根12M线材截得的第j种长度的线材数目Z为浪费的线材总长度又由于150*(8+12)远大于所需线材总长度,故知所用两种线材每种不超过150根Minz=艺8*a+刃12*b一刃Yx+艺工yiii,ji,ji=1i=1i=1j=1i=1j=12x+3.6x+2.8x+1.85x+0.75x+0.55x=8*a1,11,21,31,41,51,616.2x+3.6x+2.8x+1.85x+0.75x+0.55x=8*a120.1120,2120,3120,4120,5120,6120s.t.6.2y+3.6y+2.8y+1.85y+0.75y+0.55y=8*b1.11,21,31,41,51,61