單純形法的matlab實(shí)現(xiàn)

1、實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目:單純形法的matlab實(shí)現(xiàn)學(xué)生:學(xué) 號:實(shí)驗(yàn)時(shí)間:2013-4-15一. 實(shí)驗(yàn)名稱：單純形法的MATLAB實(shí)現(xiàn)二. 實(shí)驗(yàn)?zāi)康募耙螅?. 了解單純形算法的原理及其matlab實(shí)現(xiàn).2. 運(yùn)用MATLAB 編輯單純形法程序解決線性規(guī)劃的極小化問題，求出最優(yōu)解及目標(biāo)函數(shù)值三. 實(shí)驗(yàn)容：1. 單純形方法原理：單純形方法的基本思想，是從一個(gè)基本可行解出發(fā)，求一個(gè)使目標(biāo)函數(shù)值有所改善的基本可行解；通過不斷改進(jìn)基本可行解，力圖達(dá)到最優(yōu)基本可行解.對問題min f def exs.t. Ax b,x 0.其中A是一個(gè)m x n矩陣，且秩為m, e為n維行向量，x為n維列向量，b為m維 非負(fù)

2、列向量.符號“”表示右端的表達(dá)式是左端的定義式 ，即目標(biāo)函數(shù)f的具體形式就是ex. 記A （Pi，P2，.，Pn）令A(yù)=（B，N），B為基矩陣，N為非基矩陣，設(shè)（o） B 1bx0是基本可行解，在x（0）處的目標(biāo)函數(shù)值cx(0)(cb,Cn) B°bCbB-%,其中cB是c中與基變量對應(yīng)的分量組成的m維行向量；cn是c中與非基變量對應(yīng)的分量組成的n-m維行向量.現(xiàn)由基本可行解 x（0）出發(fā)求解一個(gè)改進(jìn)的基本可行解.Xb設(shè)X是任一可行解，則由Ax b得到XnXb B-1b B-1NXn ,在點(diǎn)x處的目標(biāo)函數(shù)值Xbf CX （Cb,Cn）fo（Zj Cj）Xj ,Xnj R其中R是非基變

3、量下標(biāo)集，Zj CBB-1Pj.2. 單純形方法計(jì)算步驟：首先給定一個(gè)初始基本可行解，設(shè)初始基為B,然后執(zhí)行下列主要步驟：（1 ）解BXb b,求得Xb B 1b b,令Xn 0,計(jì)算目標(biāo)函數(shù)值f CbXb .（2）求單純形乘子 W,解wB Cb ,得到w CbB 1 .對于所有非基變量，計(jì)算判別數(shù)Zj-Cj WjPj Cj.令Zk-Ck max"®.若Zk-Ck 0,則對于所有非基變量 Zj-Cj 0,對應(yīng)基變量的判別數(shù)總是為零，因此停止計(jì)算，現(xiàn)行基本可行解是最優(yōu)解.否則，進(jìn)行下一步.（3）解Byk pk，得到y(tǒng)k B 1pk,若yk 0,即yk的每個(gè)分量均非正數(shù)，則停止

4、計(jì)算,問題不存在有限最優(yōu)解.否則進(jìn)行步驟（4）（4 ）確定下標(biāo)r,使brdXk =min yik 0yrkyikXBr為離基變量，Xk為進(jìn)基變量用Pk替換PBr，得到新的基矩陣B,返回步驟（1 ）3. 單純形方法表格形式表 fXBXN右 端Xb0Im-1B NB-1bf10r-1CbB N - CnCbB-%表3.1.2（ 略去左端列后的詳表）XB1XBrXBmXjxkXB1100y1j%kbiXBr010YrjyrkbrXBm001ymjymkbmf000Zj-CjZk -CkCBb假設(shè)b B-1b 0,由上表得Xb b,XN 0.1若CbB- N -Cn 0 ,則現(xiàn)行基本可行解是最優(yōu)解.1

5、若CbB- N-Cn 0 ,則用主元消去法求改進(jìn)的基本可行解.先根據(jù)bbZk-CkmaRxZj-Cj選擇主列，再根據(jù)一Jmin 亠yik 0找主行，主元為yk,然后yrkyik進(jìn)行主元消去，得到新單純形表.表的最后一行是判別數(shù)和函數(shù)目標(biāo)值四. 實(shí)驗(yàn)流程圖及其 MATLAB實(shí)現(xiàn):1.流程圖:初始基本可行解B1 一解BXb b,求得Xb B b b,令Xn 0 ,計(jì)算目標(biāo)函數(shù)值f CbXb求單純形乘子 w,解wB cB ,得到w CbB 1.對于所有非基變量，計(jì)算判別數(shù) Zj-Cj WjPj Cj .令 Zk - Ck maRXZj_Cjyk 01rbb確定下標(biāo)r,使xk=min yrkyikyi

6、k0b賦一-以正的大值NyikxB為rJ離基變量,Xk為進(jìn)基變量用Pk替換PBr，得到新的基矩陣Bc/ rx -rrt f 也 J /古曲（1）程序源代碼:fun ctio nx,f=DCmi n(c,A,b,AR,yO,d)% x:最優(yōu)解% f:目標(biāo)函數(shù)最優(yōu)值% c:目標(biāo)函數(shù)系數(shù)向量% A:系數(shù)矩陣% b: m維列向量% AR:松弛變量系數(shù)矩陣% y0:基矩陣初始向量% d:補(bǔ)充向量(非目標(biāo)系數(shù)向量 ，為一零向量)N=10000;B=A,AR,b;m, n=size(B);C=c,d;y=y°x=zeros(1,le ngth(c);for k=1:Nk;z=B(:,e nd);

7、% 右端for j=1:n-1t(j)=y*B(:,j)-C(j);% 檢驗(yàn)數(shù)puNUOA)X so yss唳團(tuán)ww>0 - )ds_p mlljnon -)eLPJL M 山NON -)elpux (Z)£6U帀(M)X)£6U一七_(dá)(pue.?)8HZ %+% pu m puL >!3qOHVexTOE t pu puEPH-OJ 令 d)8、(CL)8''c£)83)0宜>Mu-Elldrooq 一pupu _(b-d)8、(d)z''d) so zH(d)0"v(b-d)8 七ILLLUdOJ %

8、1R州畀娯滬 % >眾BKX% pgM exelu''baJLld-e %忌州畀娯滬MHH SINA上pu(2)數(shù)值算例:例用單純形方法解下列問題min Xi -2x2 x3s.t. Xi X2-2X3 X410,2xi -X2 4x38,-Xi 2X2-X34,Xj 0, j 1,2,3,4.引進(jìn)松弛變量X 5 , X 6 ,問題標(biāo)準(zhǔn)化：minX1 -2x2 X3s.t.X1X2-2X3 X410,2x1-X2 4x3X58,-X12X2 -X3X64.Xj0, j123,4,5,6.(i)輸出命令:>> c=1 -2 1;A=1 1 -2 1;2 -1 4

9、 0;-1 2 -4 0;b=10;8;4;AR=0 0;1 0;0 1；y0=0 0 0;d=00 0;>> x,f=DCmi n(c,A,b,AR,y0,d)(ii)運(yùn)行結(jié)果:11-2102-1401-12-400k =1t =-12-100f =0B =1.5000001.500002.0000-0.50001.0000-2.0000b =01008141.00000-0.50008.000001.00000.500010.0000000.50002.0000t =0030 0f =-4B =1.5000000.750001.00001.00001.00000k =3t =-2.250000f =-19x =0125f =-192-11.00000-0.50008.000000.50000.25005.000001.00001.