單純形法的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)康募耙?:1. 了解單純形算法的原理及其 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 cxs.t. Ax b,x 0.其中 A 是一個(gè) mn 矩陣,

2、 且秩為 m, c為 n 維行向量 , x為 n 維列向量 , b為 m 維 非負(fù)列向量 . 符號“”表示右端的表達(dá)式是左端的定義式 , 即目標(biāo)函數(shù) f 的具體形式就是 cx. 記A (p1, p2 ,., pn)令 A=(B,N), B 為基矩陣 , N 為非基矩陣 , 設(shè)(0) B bx0是基本可行解 , 在 x(0) 處的目標(biāo)函數(shù)值cx(0)(cB,cN) 0cBB -1b ,其中 cB 是 c 中與基變量對應(yīng)的分量組成的 m 維行向量 ; cN 是 c 中與非基變量對應(yīng)的分量組 成的 n-m 維行向量 .現(xiàn)由基本可行解 x（0） 出發(fā)求解一個(gè)改進(jìn)的基本可行解 .xB設(shè) x B 是任一可

3、行解 , 則由 Ax b 得到xNxB B-1b B-1NxN ,在點(diǎn) x 處的目標(biāo)函數(shù)值xBf cx （cB,cN ）f0（zj cj ）xj ,xNj R其中 R 是非基變量下標(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 mj aRxz j-cj .若

4、zk -ck 0, 則對于所有非基變量 zj -cj 0, 對應(yīng)基變量的判別數(shù)總是為零 , 因此 停止計(jì)算 , 現(xiàn)行基本可行解是最優(yōu)解 . 否則 , 進(jìn)行下一步 .（3）解 Byk pk , 得到 yk B 1pk, 若 yk 0, 即 yk 的每個(gè)分量均非正數(shù) , 則停止計(jì)算 問題不存在有限最優(yōu)解 . 否則進(jìn)行步驟（ 4 ）（4 ）確定下標(biāo) r, 使brbixk =minyik 0yrkyikxB r為離基變量 , xk 為進(jìn)基變量 . 用 pk替換 pBr, 得到新的基矩陣 B, 返回步驟（ 1）3. 單純形方法表格形式表 3.1.1fxBxN右 端xB0Im-1B-1NB-1bf10-1

5、cBB N -cNcBB -1b表 3.1.2 （ 3.1.1 略去左端列后的詳表）xB1xBrxBmxjxkxB1100y1jy1kb1xBr010yrjyrkbrxBm001ymjymkbmf000zj -cjzk -ckcBb假設(shè) b B-1b 0, 由上表得 xB b,xN 0.-1 若cBB-1N -cN 0 , 則現(xiàn)行基本可行解是最優(yōu)解 .-1若 cBB-1N -cN 0 , 則 用 主 元 消 去 法 求 改 進(jìn) 的 基 本 可 行 解 . 先 根 據(jù)bbzk -ck mj aRxz j - cj選擇主列 , 再根據(jù) brmin bi yik 0 找主行 , 主元為 yrk ,

6、然后yrkyik進(jìn)行主元消去 , 得到新單純形表 . 表的最后一行是判別數(shù)和函數(shù)目標(biāo)值四實(shí)驗(yàn)流程圖及其 MATLAB 實(shí)現(xiàn) :1. 流程圖 :初始基本可行解 B1解 BxB b, 求得 xB B 1b b, 令 xN 0, 計(jì)算目標(biāo)函數(shù)值 f cBxB求單純形乘子 w, 解wB cB , 得到 w cBB 1. 對于所有非基變量, 計(jì)算判別數(shù) zj-cj wjpj cj. 令 zk -ck mj aRxz j-cjyk0brbi確定下標(biāo) r, 使 x k = r min iyrkyikyik0b賦 i 以正的大值 N yikxBr 為 r離基變量 , xk為進(jìn)基變量 . 用 pk替換 pBr,

7、 得到新的基矩陣 B(1) 程序源代碼 :function x,f=DCmin(c,A,b,AR,y0,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=y0;x=zeros(1,length(c);for k=1:Nk;z=B(:,end); % 右端for j=1:n-1t(j)=y*B(:,j)-C(j); % 檢驗(yàn)數(shù)puNUOA)X so yss唳

8、團(tuán)ww0 - )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)8c)83)0宜Mu-Elldrooq 一pupu _(b-d)8、(d)zd) so zH(d)0v(b-d)8 七ILLLUdOJ %1R州畀娯滬 % 眾BKX% pgM exelubaJLld-e %忌州畀娯滬MHH SINA上pu(2) 數(shù)值算例 :例 3.1.2 用單純形方法解下列問題min x1 -2x2 x3s.t. x1 x 2 -2x3 x

9、4 10， 2x1-x2 4x3 8， -x1 2x2 -x3 4， x j 0， j 1，2，3，4.引進(jìn)松弛變量 x 5 , x 6 , 問題標(biāo)準(zhǔn)化 :minx1 -2x 2 x 3s.t.x1x 2-2x3 x410，2x1-x 2 4x3 x58，-x12x2 -x3x64.xj0，j 1，2，3，4，5，6.(i) 輸出命令 : c=1 -2 1;A=1 1 -2 1;2 -1 4 0;-1 2 -4 0;b=10;8;4;AR=0 0;1 0;0 1;y0=0 0 0;d=0 0 0; x,f=DCmin(c,A,b,AR,y0,d)(ii) 運(yùn)行結(jié)果 :11-2102-1401-

10、12-400k =1t =-12-100f =0B =1.5000001.500002.0000-0.50001.0000-2.0000B =0 100 81 41.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.000012.00000-1.5000-1.7500五總結(jié) :在單純形法求解