资源描述：
《线性规划的求解算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、线性规划的求解算法线性规划（linearprogramming）是运筹学中的一个重要分支，在现代工业、农业、商业、交通运输、国防军事及经济管理等诸多领域都有着广泛重要的应用。在数学系的竞赛数学建模中，也多次应用线性规划来建模从而解决实际问题。在这里介绍单纯性法和对偶单纯形法两种求解线性规划的方法。一、单纯形法算法主体思想标准线性规划简记如下：LP-maxLP-mins.t{s.t{这里只以LP-min为例。1、算法思想单纯形法是在已知一个可行基的前提下采用的解决线性规划的算法。步骤如下：（1）输入初始矩阵：，并化为典则形式。用R（i）记录单位矩阵I中元素1的位置。（2）求若t不存
2、在，则得到最优解；（i=1,2,...m）.其他9=0，停。否则，转到（3）。（3）求。若不存在，则LP-min无下届，所以无最优解，停；否则，求，转到（4）。（4），（j=1，2....n+1）,(i=0,1,2...m;is;j=1,2,....,n+1),,转到（2）.二、对偶单纯形法对偶单纯形法是在已知一个正则基的条件下的求解线性规划的方法。步骤如下:(1)输入初始矩阵：，并化为典则形式。用R（i）记录单位矩阵I中元素1的位置。(2)求若s不存在，则得到最优解；（i=1,2,...m）.其他=0，停。否则，转到（3）。(3)求。若不存在，则LP-min无下届，所以无最优解
3、，停；否则，求，转到（4）。9(4)，（j=1，2....n+1）,(i=0,1,2...m;is;j=1,2,....,n+1),,转到（2）.三、程序代码1、单纯形法。%求解标准型线性规划:maxc*x;s.t.A*x=b;x>=0%A1是标准系数矩阵及最后一列是资源向量，C是目标函数的系数向量%N是(初始的)基变量的下标%M=10000人工变量系数%本函数中的A是单纯形表，包括:最后一行是初始的检验数，最后一列是资源向量b%c1是基变量系数%输出变量sol是最优解%输出变量val是最优值，k是迭代次数%flag1的值代表有无最优解，0无界解，1无可行解，2无穷多解，3唯一最
4、优解function[sol,val,k,flag1]=ssimplex(A1,C,N)M=10000;[mA1,nA1]=size(A1);C1=[C,0];val=zeros(1,length(C));fori=1:length(N)c1(i)=C1(N(i));endfori=1:nA1a(i)=C1(i)-c1*A1(:,i);%计算初始检验数endA=[A1;a];%构造初始单纯形表[mA,nA]=size(A);k=0;%迭代次数flag=1;whileflagfori=1:(nA-1)ifA(mA,i)<=0flag=0;elseflag=1;9break;ende
5、ndifflag==0%已找到最优解val1=A(1:(mA-1),nA)';fori=1:length(N)if(val1(i)~=0&&abs(C(N(i)))==M)disp('无可行解');sol=inf;val=inf;flag3=0;flag1=1;break;elseflag3=1;endendifflag3iflength(find(A(mA,1:(nA-1))==0))>length(N)disp('存在无穷多最优解');flag1=2;elsedisp('存在最优解');flag1=3;endsol=c1*val1';endelseifflag==1forj=
6、1:(mA-1)ifA(j,i)<=0flag2=1;elseflag2=0;break;endendifflag==1&&flag2==1disp('此线性规划问题存在无界解');sol=inf;val=inf;flag1=0;flag=0;%跳出while循环break;endmaxq=max(A(mA,1:(nA-1)));[m,nb]=find(A(mA,:)==maxq);%确定入基变量的纵坐标9fors=1:(mA-1)ifA(s,nb)>0temp(s)=A(s,nA)/A(s,nb);elsetemp(s)=10000;endendk=k+1;mino=min(t
7、emp);[n,mb]=find(temp==mino);%确定入基变量的横坐标iflength(mb)>1mb=mb(1);endab=A(mb,nb);A2=A;fori=1:(mA-1)forj=1:nAifi==mbA(mb,j)=A2(mb,j)/ab;elseA(i,j)=A2(i,j)-A2(i,nb)*(A2(mb,j)/ab);endendendfori=1:length(N)ifi==mbN(i)=nb;endendfori=1:length(N)c1(i)=
