实验2+单纯形法求解线性规划.doc

:?验证性实验?综合性实验?设计性实验实验目的:进一步熟练掌握单纯形法求解线性规划。实验内容:单纯形法求解线性规划4个(题目自选)实验原理首先要找到一个初始基本可行解,求出对应的检验数,判断其是否是最优解,如果是就停止计算;否则,就进行迭代找到另一个能使得目标函数值更优的基本可行解,然后再判断其是否是最优解,如此反复进行下去,直到找到最优解或者判断线性规划问题无解为止(线性规划解有四种情形,唯一最优解,无穷多个最解,无界解,无可行解)。实验步骤1要求上机实验前先编写出程序代码2编辑录入程序3调试程序并记录调试过程中出现的问题及修改程序的过程4经反复调试后,运行程序并验证程序运行是否正确。5记录运行时的输入和输出。预习编写程序代码:实验报告:根据实验情况和结果撰写并递交实验报告。实验总结::[xx,b,fm,sgma,AA,flg]=myprgmh(m1,m,n,A,b,c)%单纯形法求解性规划函数。默认标准型人工变量在最前、剩余变量在后构成基本量;%m1人工变量的个数;m基变量的个数;n所有变量的个数;%A约束方程的系数矩阵;%b约束方程右端列向量;输出b基变量的值;%c目标函数的系数。cb基变量的系数%输出xx为基变量的下标;%fm输出目标函数的值;%flg表示解得四种情况;B0=A(:,1:m);%B0初始可行基矩阵(单位矩阵);cb=c(:,1:m);xx=1:m;%xx变量的下标;sgma=c-(cb*B0)*A;%sgma检验数;h=-1;sta=ones(m,1);fori=1:nifsgma(i)>0h=1;endendvv=0;whileh>0[msg,mk]=max(sgma);fori=1:mifA(i,mk)>0sta(i)=b(i)/A(i,mk);elsesta(i)=10000;endend[mst,mr]=min(sta);ifmst==10000flg='unboundedsolution';fm=inf;xx=[];b=[];h=-1;vv=1;AA=[];elsezy=A(mr,mk)fori=1:mifi==mrforj=1:nA(i,j)=A(i,j)/zy;endb(i)=b(i)/zy;elseendendfori=1:mifi~=mramk=A(i,mk);b(i)=b(i)-amk*b(mr);forj=1:nA(i,j)=A(i,j)-amk*A(mr,j);endelseendA;B1=A(:,1:m);%B1新基的逆矩阵;cb(mr)=c(mk);xx(mr)=mk;sgma=c-cb*A;h=-1;fori=1:nifsgma(i)>0h=1;endendendcbbfm=sum(cb*b);if(h==-1)&(vv~=1)vv=0;fori=1:mifxx(i)<=m1vv=vv+2;endendifvv>=2;flg='nofeasibel';xx=[];fm=[];b=[];vv=1;AA=[];endifvv~=1AA=A;ss=size(find(sgma))ww=ss(2)ifww==n-mflg='Thereisonlyonesolution';elseflg='Therearemanysolutions';:单纯形法求解线性规划一:(唯一最优解)=[1,0,0,1,2;0,1,0,4,0;0,0,1,0,4]b=[8;16;12]c=[0,0,0,2,3]m1=0m=3n=:[xx,b,fm,sgma,AA,flg]=myprgmh(m1,m,n,A,b,c)输出结果:xx=435b=442fm=14sgma=--=--=Thereisonlyonesolution单纯形法求解线性规划二:(无穷多个解)=[1,0,0,-2,3,-1,0,2,-2,-1;0,1,0,-4,1,-2,0,1,-1,0;0,0,1,1,1,3,0,-1,1,0]b=[2,2,14]'c=[-1000,-1000,0,3,-4,2,0,,-5,5,0]m1=2m=3n=:[xx,b,fm,sgma,AA,flg]=myprgmh(m1,m,n,A,b,c)输出结果:xx=5109b==-2sgma=+003*--