純形法：simplemth

《純形法：simplemth》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、單純形法函數(shù)：SimpleMthd用單純形算法解如下線性規(guī)劃問題的步驟如下：（1）確定初始基變量矩陣；求解方程；（2）令，計(jì)算；其中和分別代表基變量和非基變量的值，表示基變量在目標(biāo)函數(shù)中的系數(shù)；（3）求解方程，對(duì)于所有非基變量計(jì)數(shù)判別數(shù)，其中為非基變量在約束系數(shù)矩陣中相對(duì)應(yīng)的列，令，如果，則停止計(jì)算，輸出最優(yōu)解，否則轉(zhuǎn)步驟4；（4）求解方程，若的每個(gè)分量均大于0，則問題不存在最優(yōu)解，否則轉(zhuǎn)步驟5；（5）令，其中，用代替，得到新的基變量矩陣再轉(zhuǎn)步驟2計(jì)算。調(diào)用格式：其中，：約束矩陣；：目標(biāo)函數(shù)系數(shù)向量；：約束右端向量；：初始向量，basic；：目標(biāo)函數(shù)取最小值時(shí)自由變量值

2、；：目標(biāo)函數(shù)的最小值；單純形法函數(shù)的MATLAB程序代碼如下：function[x,minf]=SimpleMthd(A,c,b,baseVector)%約束矩陣：A;%目標(biāo)函數(shù)系數(shù)向量:c;%約束右端向量:b;%初始基向量：baseVector;%目標(biāo)函數(shù)取最小值時(shí)的自變量值:x;%目標(biāo)函數(shù)最小值:minf;sz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia;nobase=zeros(1,1);m=1;fori=1:nViaif(isempty(find(baseVector==xx(i),1)))nobase(m)=i;m=m+1;els

3、e;endendbCon=1;M=0;whilebConnB=A(:,nobase);%非基變量矩陣ncb=c(nobase);%非基變量系數(shù)B=A(:,baseVector);%基變量矩陣cb=c(baseVector);%基變量系數(shù)xb=inv(B)*b;f=cb*xb;w=cb*inv(B);fori=1:length(nobase)sigma(i)=w*nB(:,i)-ncb(i);end[maxs,ind]=max(sigma);%ind為進(jìn)基變量下標(biāo)ifmaxs<=0%最大值小于零，輸出最優(yōu)解minf=cb*xb;vr=find(c~=0,1,'last')

4、;forl=1:vrele=find(baseVector==l,1);if(isempty(ele))x(l)=0;elsex(l)=xb(ele);endendbCon=0;elsey=inv(B)*A(:,nobase(ind));ify<=0%不存在最優(yōu)解disp('不存在最優(yōu)解！');x=NaN;minf=NaN;return;else%尋找出基變量minb=inf;chagB=0;forj=1:length(y)ify(j)>0bz=xb(j)/y(j);ifbz

5、gB);%更新基矩陣和非基矩陣baseVector(chagB)=nobase(ind);noase(ind)=tmp;endendM=M+1;if(M==1000000)%迭代步數(shù)限制disp('找不到最優(yōu)解');x=NaN;minf=NaN;return;endend當(dāng)目標(biāo)函數(shù)的自變量系數(shù)全都大于0時(shí)，一定要小心。為解決這個(gè)問題，可以在代碼中加入如下語句：ifc>=0vr=find(c~=0,1,'last');rgv=inv(A(:,(nVia-n+1):nVia))*b;ifrgv>=0elsedisp('不存在最優(yōu)解！');x=NaN;minf=NaN;ret

6、urn;endend因此完整的單純形的MATLAB程序如下：function[x,minf]=CmpSimpleMthd(A,c,b,baseVector)%約束矩陣：A;%目標(biāo)函數(shù)系數(shù)向量:c;%約束右端向量:b;%初始基向量：baseVector;%目標(biāo)函數(shù)取最小值時(shí)的自變量值:x;%目標(biāo)函數(shù)最小值:minf;sz=size(A);nVia=sz(2);n=sz(1);xx=1:nVia;nobase=zeros(1,1);m=1;ifc>=0vr=find(c~=0,1,'last');rgv=inv(A(:,(nVia-n+1):nVia))*b;ifrgv>=

7、0elsedisp('不存在最優(yōu)解！');x=NaN;minf=NaN;return;endendfori=1:nViaif(isempty(find(baseVector==xx(i),1)))nobase(m)=i;m=m+1;else;endendbCon=1;M=0;whilebConnB=A(:,nobase);%非基變量矩陣ncb=c(nobase);%非基變量系數(shù)B=A(:,baseVector);%基變量矩陣cb=c(baseVector);%基變量系數(shù)xb=inv(B)*b;f=cb*xb;w=cb*inv(B);for