運(yùn)籌學(xué)與最優(yōu)化MATLAB編程課程報(bào)告

1、基于MATLAB編程語言采用大M法求 解線性規(guī)劃問題線性規(guī)劃單純形法 大M法 MATLAB編程語言1引言伴隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，最優(yōu)化理論與方法取得了巨大的 進(jìn)步，并日益受到重視，而解決實(shí)際最優(yōu)化問題的軟件也得到了飛速 發(fā)展，其中MATLAB這個(gè)強(qiáng)大的計(jì)算平臺(tái)，既可以利用MATLAB優(yōu)化工 具箱(OptimizationToolbox)中的函數(shù)，又可以通過對算法編程實(shí) 現(xiàn)相應(yīng)的最優(yōu)化計(jì)算，是目前最流行的計(jì)算軟件之一。摘要本程序是采用運(yùn)籌學(xué)中的求解線性規(guī)劃的大M法來解現(xiàn)實(shí)問題， 并采用MATLAB編程語言。本文通過投資問題的實(shí)例分析了投資項(xiàng) 日和各項(xiàng)目收益率確定的情況下，并結(jié)合公司實(shí)際，如何

2、合理的分配 利用，最終確定使得該公司收益最大的投資方案。說明了線性規(guī)劃在 現(xiàn)代企業(yè)投資管理中的應(yīng)用，對企業(yè)的投資管理決策提供了支持。但 是本程序只實(shí)現(xiàn)了線性規(guī)劃的部分功能，所以有待進(jìn)一步完善。算法說明3.1算法原理單純形法的基本思路是將可行域中某個(gè)基可行解轉(zhuǎn)換到一個(gè)新 的可行解，同時(shí)使得目標(biāo)函數(shù)值有所改進(jìn)。而大M法則是通過將人 工變量加入到原約束方程組中作為虛擬變量，并使得這些虛擬變量從基變量中被置換出來。為此只需假定人工變量在日標(biāo)函數(shù)中的系數(shù)為M（M0,是個(gè)充分大的數(shù)），這樣，對于求極大值問題，只要在基本可行解中，還有人工變量是基變量，且取值不為0，則日標(biāo)函數(shù)就不可能達(dá)到最大值；對于極小值問

3、題而言，人工變量在日標(biāo)函數(shù)中的系數(shù)取+M，這種方法稱為大M法。3.2算法步驟用大M法求解下列線性規(guī)劃問題minf=cxs.t.=的步驟如下:r Ax=b=01.首先將線性規(guī)劃問題minf=cx，s.t.=轉(zhuǎn)化為如下問題:Minf=cx+MeTy,s.t.=r Ax=0Ax+y=02.確定初始基變量矩陣B，求解方程令xN=0計(jì)算f=cBxB其中xB、xN分別代表基變量和非基變量的值，cB 表示基變量在日標(biāo)函數(shù)中的系數(shù)；求解方程wB=CB,對于所有非基變量計(jì)算判別數(shù)Z.-C.wP.-C.，其中 Pj為非基變量在約束系數(shù)距震中相對應(yīng)的列，令Zk-Ck=max（Z.-C.）, 如果Zk-Ck0，將目標(biāo)

4、函數(shù)改寫為如式2），就可按原單純形法的步驟進(jìn)行迭代。6.2本程序設(shè)計(jì)缺點(diǎn)本程序設(shè)計(jì)時(shí)只涉及了求極小值的方法，所以在求解極大值問題 時(shí)需要先將模型轉(zhuǎn)化為求最小值的模型；而且在用大M法求解線性 規(guī)劃時(shí)也需先把一般形式化為標(biāo)準(zhǔn)形式；在計(jì)算時(shí)要給M賦予一個(gè) 適當(dāng)?shù)亩ㄖ担ㄌ貏e是在編程時(shí)），但究竟應(yīng)該取多大，事先無法估計(jì)， 過大的話容易引起計(jì)算誤差。6.3算法需改進(jìn)之處應(yīng)該設(shè)計(jì)一種既能求解極大值又能求解極小值的算法，而不需來回轉(zhuǎn) 換，本程序的設(shè)計(jì)也未考慮當(dāng)原問題無界時(shí)這種情況，所以有待進(jìn)一 止土 步兀善。6.4算法對比效果算法改進(jìn)后，會(huì)使得本程序設(shè)計(jì)的功能更強(qiáng)大，更完善，大大簡化繁 瑣的轉(zhuǎn)換過程。7.總結(jié)

5、與心得體會(huì)通過對本次課程報(bào)告的編寫，大大加強(qiáng)了自己的實(shí)踐動(dòng)手能力與 MATLAB編程能力，實(shí)現(xiàn)了理論與實(shí)際的緊密結(jié)合，同時(shí)也提高了 自己解決實(shí)際問題的能力，為以后的編程打下了基礎(chǔ)。由于接觸MATLAB編程語言的時(shí)間還比較短，所以對它掌握的 還不是特別的熟練，以至于在算法的編程實(shí)現(xiàn)過程中會(huì)出現(xiàn)種種問 題。本次最大的收獲就是學(xué)會(huì)了 MATLAB的基本操作及基本編程，遇到問題首先要自己認(rèn)真思考，提高自己的思維創(chuàng)新能力，需要更加 的努力才能真正的把MATLAB學(xué)好，學(xué)會(huì)理論聯(lián)系實(shí)際。參考文獻(xiàn)運(yùn)籌學(xué)的原理和方法(第二版)/鄧成梁 主編.一武漢：華中科技大學(xué)出版社，2002年1月MATLAB語言高級(jí)編程/

6、張德豐等編著，一北京：機(jī)械工業(yè)出版社，2010年1月精通MATLAB最優(yōu)化計(jì)算/龔純，王正林編著，一北京：電子工業(yè) 出版社，2009年4月附件(程序代碼)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;if c=0vr二find(c=0,1, last);rgv二inv(A(

7、:,(nVia-n+1):nVia)*b;if rgv=0 x=zeros(1,vr);minf=0;elsedisp(the best answer do not exist!);x=nan;minf=nan;return;endendfor i=1:nViaif (isempty(find(basevector=xx(i),1)% 獲取非基變量下標(biāo) nobase(m)=i;m=m+1;elseendend bCon=1;M=0;while bConnB=A(:,nobase);%非基變量矩陣ncb=c(nobase);%非基變量系數(shù)B=A(:,basevector);% 基變量矩陣cb=c

8、(basevector);% 基變量系數(shù)xb=inv(B)*b;f=cb*xb;w=cb*inv(B);for i=1:length(nobase)% 判別sigma二w*nB(:,i)-ncb(i);endmaxs,ind=max(sigma);%ind 為進(jìn)基變量下標(biāo)if maxs=0minf=cb*xb;vr二find(c=0,1, last);for i=1:vrele=find(basevector=i,1);if(isempty(ele)x(i)=0;elsex(i)=xb(ele);endendbCon=0;elsey=inv(B)*A(:,nobase(ind);if y0bz=xb(j)/y(j);if bzminbminb=bz;chagB=j;endendtmp二basevector(chagB);%更新基矩陣和非基矩陣 basevector(ch