運籌單純型算法

1、 運籌學實驗報告 題目：用單純形法求解線性規(guī)劃問題姓 名 王賽賽 學 號 2012436138 年級專業(yè) 12數(shù)電類2 指導教師 蘇珂 2013年11月15日一、 實驗目的：運用MATLAB科學計算軟件完成單純型算法求解線性規(guī)劃問題。二、 實驗內(nèi)容：編寫一個MATLAB的函數(shù)文件：matrix.m，用于求解標準型的線性規(guī)劃問題： Ax=bmin f=c*x subject to x01.函數(shù)調(diào)用基本形式：x,minf,optmatrx,flag=matrix(A,c,b)2.參數(shù)介紹： Ax=bA：線性規(guī)劃問題的約束 中各變量的系數(shù)組成的矩陣，是一個m×n的矩陣。 x0c：線性規(guī)劃問

2、題的目標函數(shù)f= c*x中各變量的系數(shù)變量，是一個n維的行向量。 Ax=bb：線性規(guī)劃問題的約束 中的常數(shù)向量，是一個mn維德列向量。 x0X：輸出線性規(guī)劃問題的最優(yōu)解，當線性規(guī)劃問題沒有可行解或者有可行解但沒有優(yōu)解X=。minf：輸出線性規(guī)劃問題的最優(yōu)解，當線性規(guī)劃問題沒有可行解minf，當線性規(guī)劃問題有可行解但沒有最優(yōu)解時minf=-inf。optmartx:輸出最優(yōu)解對應的單純型表，當線性規(guī)劃問題沒有可行解或者有可行解但沒有最優(yōu)解時optmartx=。flag：相性規(guī)劃問題的求解結(jié)果標志值，當線性規(guī)劃問題有最優(yōu)解時flag=1，當線性規(guī)劃問題有可行解但沒有最優(yōu)解時flag=0，當線性規(guī)劃

3、問題沒有可行解時flag=-1.三、 MATLAB函數(shù)linprog的使用Function x,fval,exitflag,output,lambda=linprog(f,A,B,Aeq,Beq,lb,ub,x0,options)這個函數(shù)的功能是解決線性規(guī)劃問題，它可以有變化的函數(shù)傳遞個數(shù)，函數(shù)內(nèi)部根據(jù)傳值的多少進行不同的功能操作。一、函數(shù)的傳值1、X = LINPROG(f,A,b) 試圖解決線性問題：求出f*x的最小值，且fx服從A*x<=b,其中x為自變量2、X = LINPROG(f,A,b,Aeq,beq）解決滿足添加約束等式：Aeq*x = beq的上述問題3、X = LIN

4、PROG(f,A,b,Aeq,beq,LB,UB)在以上的條件加下，與此同時定義了自變量的上下線，LB <= X <= UB，其中X為問題中的自變量。如果問題中沒有上下線（即沒有UB和LB），則用空矩陣來代替。如果問題中沒有下線，則LB(i)=-Inf；如果沒有上線，則UB(i)=Inf。4、X = LINPROG(f,A,b,Aeq,beq,x0),在以上條件下，設置起點x0。這一項是唯一可用的有效集算法。默認的內(nèi)點算法將忽略任何非空的起點。5.X = LINPROG（F，A，B，AEQ，BEQ，LB，UB X0，OPTIONS），最大限度地減少使用默認的值在股權(quán)結(jié)構(gòu)。二、函數(shù)的

5、返回值1、X,FVAL = LINPROG(f,A,b)，返回值FVAL是目標函數(shù)的最優(yōu)解，X是相應于最優(yōu)解的為指數(shù)的向量2、X,FVAL,EXITFLAG = LINPROG(f,A,b)，前兩個與上述相同，最后一個EXITFLAG返回z值描述退出函數(shù)的不同情況，其中，可能返回的EXITFLAG的值及其對應的情況如下：1LINPROG收斂于結(jié)果X。0達到最大迭代次數(shù)-2找不到可行解-3問題無界-4當執(zhí)行算法的時候出現(xiàn)不確定解-5原問題及其對偶問題都無可行解-7搜索方向的數(shù)量級過??；沒有辦法進行更加深入的搜索。問題條件有錯或者變量有錯誤。 3、X,FVAL,EXITFLAG,OUTPUT =

6、LINPROG(f,A,b)，前面與上相同，最后返回一個OUIPUI的結(jié)構(gòu)，此結(jié)構(gòu)是帶有從OUOPUT中得到的iterations的數(shù)值的最大值。參數(shù)Iterations是OUIPUI中約束問題的最大值。參數(shù)Constrviolation是一個在OUIPUI算法中使用的算法。Algorithm是在OUIPUI中共軛梯度的iterations的值。4、X,FVAL,EXITFLAG,OUTPUT,LAMBDA = LINPROG(f,A,b)，前面與上相同，最后返回拉格朗日乘法算子LAMBDA，在這個解中：LAMBDA.ineqlin代表先行不等式A，LAMBDA.eqlin代表線性等式Aeq，

7、LAMBDA.lower代表LB，LAMBDA.upper代表UB。四、 matrix函數(shù)%兩階段算法求解線性規(guī)劃問題 %子函數(shù)function使用格式；%function輸出參數(shù)列表=函數(shù)名(輸入?yún)?shù)列表)%函數(shù)體 %輸入?yún)?shù)列表中的c，A，b的含義%c 目標函數(shù)中的系數(shù)向量%A 約束中的系數(shù)矩陣%b 約束中的常數(shù)向量 %輸出參數(shù)列表中的 x,minf,optmatrx,flag的含義：%x 最優(yōu)解%minf 最優(yōu)值%optmatrx 最優(yōu)值對應的單純形表%flag 線性規(guī)劃求解結(jié)果的標志值 functionx,minf,optmatrx,flag=linpa(A,b,c)A=input(&

8、#39;請輸入約束中的系數(shù)矩陣 A=') b=input('請輸入約束中的常數(shù)向量 b=') %b為單列矩陣c=input('請輸入目標函數(shù)中的系數(shù)向量 c=') %c為單行矩陣，注意目標函數(shù)中的系數(shù)向量c=-c%判斷c是否為單行矩陣，b是否為單列矩陣%i,j=size(c)%如果輸入的c為單列矩陣if j=1 c=c' disp('輸入的目標函數(shù)系數(shù)向量c為單位矩陣，已將其轉(zhuǎn)化為單行矩陣') fprintf('nc =n') disp(c)endi,j=size(b)%如果輸入的b為單行矩陣if i=1 b=b&

9、#39; disp('輸入的約束中的常數(shù)向量b為單行矩陣，已將其轉(zhuǎn)化為單列矩陣') fprintf('nb =n') disp(b)end %將c=-c處理c=-c%size()用于獲取數(shù)組的行數(shù)和列數(shù) m,n=size(A); %第一個輸出變量m用于存儲數(shù)組的行數(shù)，第二個輸出變量用于存儲數(shù)組的列數(shù)m1=m; %保存下原來的行數(shù)s=eye(m); %建立大小行數(shù)m的單位矩陣，eye（）用于獲取單位矩陣A=A s;A=A b;g1=zeros(1,n);x=ones(1,m);g1=g1 -x;g=0;g1=g1 g; %人工變量的檢驗向量s1=n+m+1; %目

10、前列數(shù)之和s2=zeros(1,m+1);c=c s2;A1=zeros(m,1);for i1=1:m A1(i1,1)=i1+n;%基變量的數(shù)值存儲區(qū)endfor i=1:m g1(1,:)= g1(1,:)+A(i,:); end %*第一階段* decide=find(g1(1,1:m+n)>0); % 尋找g1中大于零的數(shù)值列數(shù)存于dicide數(shù)組中while isempty(decide) %當存在大于零的值時 i=decide(1); %當列數(shù)賦給itext=find(A(1:m,i)>0); %text存放該列中所有數(shù)值大于零的行數(shù) if isempty(text)

11、 %當沒有大于零的數(shù)值時無解 flag=0; break; end min=inf; for i1=1:m %當該列存在大于零的數(shù)值時 if A(i1,i)>0&A(i1,s1)/A(i1,i)<min %尋找比值最小的 min=A(i1,s1)/A(i1,i); x1=i1; %將比值最小的行數(shù)賦給x1 end end A(x1,:)=A(x1,:)/A(x1,i); %單位化 c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:); g1(1,:)=g1(1,:)+(-1*g1(1,i)*A(x1,:); for i1=1:m if i1=x1 A(i1,:)

12、=A(i1,:)+(-1*A(i1,i)*A(x1,:);%進行換基迭代 end end A1(x1,1)=i; %將列數(shù)既對應的非基變量轉(zhuǎn)換為基變量 decide=find(g1(1,1:m+n)>0); %再進行查找end %* if g1(1,s1)>0 %此時對應的為無解情況 flag=-1;end %*判斷人工變量* if g1(1,s1)=0 g1(1,:)=; for i6=1:m A(:,n+1)=; end for i6=1:m c(n+1)=; end decide=find(A1(1:m,1)>n); %查找是否有人工變量 if isempty(deci

13、de) %存在人工變量 while isempty(decide) x1=decide(1); %存放的是人工變量的行數(shù) text=find(A(x1,1:n)=0); %該行的所有元素都不為零的列坐標 if isempty(text) %都為零，則該行為多余的行，刪除 decide(1)=; A1(x1,:)=; A(x1,:)=; m=m-1; else i=text(1); %i保存的是列數(shù) A(x1,:)=A(x1,:)/A(x1,i); A1(x1,1)=i; c(1,:)=c(1,:)+(-1*c(1,i)*A(x1,:); for i1=1:m if i1=x1 A(i1,:)=

14、A(i1,:)+(-1*A(i1,i)*A(x1,:); end end decide(1)=; text(1)=; end end end %*第二階段* decide=find(c(1,1:n)>0); %查找檢驗向量是否存在大于零的數(shù)，將列數(shù)保存 while isempty(decide) i=decide(1); %將列數(shù)賦給i text=find(A(:,i)>0); %保存大于零的項的行數(shù) if isempty(text) %為空的時候，則無解 disp('有可行解但沒有最優(yōu)解') flag=0 c=c;A; optmatrx=c; x=zeros(n,

15、1); for o=1:n for o1=1:m if o=A1(o1,1) x(o,1)=A(o1,n+1); end end end minf=-inf optmatrx x return; end min=inf; for i1=1:m if A(i1,i)>0&A(i1,n+1)/A(i1,i)<min min=A(i1,n+1)/A(i1,i); x1=i1; %保存最小項的行數(shù) end end A(x1,:)=A(x1,:)/A(x1,i); %單位化 j=c(1,i); for j1=1:n+1 c(1,j1)=c(1,j1)+A(x1,j1)*(-1)*j;

16、 %換基迭代 end for i1=1:m if i1=x1 A(i1,:)=A(i1,:)+(-1*A(x1,:)*A(i1,i); end end A1(x1,1)=i; decide=find(c(1,1:n)>0); end %*結(jié)果賦值結(jié)算*%* c=c;A;optmatrx=c;x=zeros(n,1); for o=1:n for o1=1:m if o=A1(o1,1) x(o,1)=A(o1,n+1); end endendminf=c(1,n+1);flag=1 ;end switch flag case 1 %有可行解 disp('輸出最優(yōu)解對應的單純形表&

17、#39;) optmatrx disp('輸出最優(yōu)解') x disp('輸出線性規(guī)劃問題的最優(yōu)值 ') minf case 0 %有可行解但沒有最優(yōu)值 disp('輸出可行解對應的單純形表 ') optmatrx disp('輸出可行解 ') x disp('輸出線性規(guī)劃問題的最優(yōu)值 ') minf case -1 %沒有可行解 disp('沒有可行解â') disp('輸出最優(yōu)解對應的單純形表 ') optmatrx= disp('輸出最優(yōu)解 ') x=

18、 disp('輸出線性規(guī)劃問題的最優(yōu)值 ') minf=-inf end五、例題求解 例題1（有最優(yōu)解）題目：min z=4x1 + 3x3 s.t. 1/2x1 + x2 + 1/2x3 2/3x4= 2 3/2x1 + 1/2x3 = 3 3x1 - 6x2 + 4x4 = 0 xj 0, j = 1,4輸入及函數(shù)的調(diào)用：測試結(jié)果：經(jīng)過測試當線性規(guī)劃問題存在最優(yōu)解時，程序運行沒有問題。例題2（有可行解但無最優(yōu)解）題目：min z=-2x1 - 5x2 s.t. -1x1 + x3 = 4 x2 + x4 = 3 -x1 + 2x2 + x5 = 8 xj 0, j = 1,

19、5輸入及函數(shù)的調(diào)用：測試結(jié)果：經(jīng)過測試當線性規(guī)劃問題有可行解但無最優(yōu)解時，程序運行沒有問題。例題3（沒有可行解）題目： min z=2x1 + 2x2 s.t. -1x1 + x2 - x3 = 1 -x1 - x2 - x4 =2 xj 0, j = 1,4輸入及函數(shù)的調(diào)用：測試結(jié)果：經(jīng)過測試當線性規(guī)劃問題沒有可行解時，程序運行沒有問題。 >> linpa請輸入約束中的系數(shù)矩陣 A=1 0 0 0 0 1 -1 0 0 0 0 0;1 1 0 0 0 0 0 -1 0 0 0 0;0 1 1 0 0 0 0 0 -1 0 0 0;0 0 1 1 0 0 0 0 0 -1 0 0;0 0 0 1 1 0 0 0 0 0 -1 0;0 0 0 0 1 1 0 0 0 0 0 -1A = Columns 1 through 11 1 0 0 0 0 1 -1 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 1 1 0 0 0 0 0 -1 0 0 0 0 1 1 0 0 0 0 0 Column 12 0 0 0 0 0 -1請輸入