單純形法的matlab實現(xiàn)極小化問題

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

2、表示右端的表達(dá)式是左端的定義式, 即目標(biāo)函數(shù)的具體形式就是.記令=(B,N), B為基矩陣, N為非基矩陣, 設(shè)是基本可行解, 在處的目標(biāo)函數(shù)值,其中是中與基變量對應(yīng)的分量組成的m維行向量; 是中與非基變量對應(yīng)的分量組成的n-m維行向量. 現(xiàn)由基本可行解出發(fā)求解一個改進(jìn)的基本可行解. 設(shè)是任一可行解, 則由得到, 在點處的目標(biāo)函數(shù)值, 其中R是非基變量下標(biāo)集, . 2. 單純形方法計算步驟: 首先給定一個初始基本可行解, 設(shè)初始基為B, 然后執(zhí)行下列主要步驟: （1） 解, 求得, 令, 計算目標(biāo)函數(shù)值. （2） 求單純形乘子, 解, 得到. 對于所有非基變量, 計算判別數(shù). 令. 若, 則對

3、于所有非基變量, 對應(yīng)基變量的判別數(shù)總是為零, 因此停止計算, 現(xiàn)行基本可行解是最優(yōu)解. 否則, 進(jìn)行下一步. （3） 解, 得到, 若, 即的每個分量均非正數(shù), 則停止計算, 問題不存在有限最優(yōu)解. 否則進(jìn)行步驟（4）. （4） 確定下標(biāo)r, 使x=, 為離基變量, 為進(jìn)基變量. 用替換, 得到新的基矩陣B, 返回步驟（1）. 3. 單純形方法表格形式: 右端010表 3.1.2（3.1.1略去左端列后的詳表） 假設(shè), 由上表得. 若, 則現(xiàn)行基本可行解是最優(yōu)解. 若, 則用主元消去法求改進(jìn)的基本可行解. 先根據(jù)選擇主列, 再根據(jù)找主行, 主元為, 然后進(jìn)行主元消去, 得到新單純形表. 表的

4、最后一行是判別數(shù)和函數(shù)目標(biāo)值. 四實驗流程圖及其MATLAB實現(xiàn): 1. 流程圖開始: 初始基本可行解B解, 求得, 令, 計算目標(biāo)函數(shù)值求單純形乘子, 解, 得到. 對于所有非基變量, 計算判別數(shù). 令YN解, 得到現(xiàn)行基本可行解是最優(yōu)解NY確定下標(biāo)r, 使x=賦以正的大值NYNmin=N問題不存在有限最優(yōu)解為離基變量, 為進(jìn)基變量. 用替換, 得到新的基矩陣B2. 代碼及數(shù)值算例: (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: 松弛變

5、量系數(shù)矩陣% y0: 基矩陣初始向量% d: 補充向量（非目標(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:N k; z=B(:,end);%右端 for j=1:n-1 t(j)=y*B(:,j)-C(j);%檢驗數(shù) end t; f=y*z; %=選取主元=% %-選取主列-% alpha,q=max(t); q; W(k)=q;%x下標(biāo)矩陣 %-% %-選取主元-% for p=1:m if B(p,q)<=0 r(p)=N; else r(p)=z(p)/B(p,q)

6、; end end beta,p=min(r); p; y(p)=C(q); %-% %=% B(p,:)=B(p,:)/B(p,q); for i=1:m if i=p B(i,:)=B(i,:)-B(p,:)*B(i,q); end end if max(t)<=0 break; end B;end%+%Z=B(:,end);if length(x(W)=length(Z) x=char(' NONE');f=char(' NONE');disp(' 不存在有限最優(yōu)解');else x(W)=Z'end(2) 數(shù)值算例:例 3.

7、1.2 用單純形方法解下列問題 引進(jìn)松弛變量x, x, 問題標(biāo)準(zhǔn)化: (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) 運行結(jié)果: B = 1 1 -2 1 0 0 10 2 -1 4 0 1 0 8 -1 2 -4 0 0 1 4k = 1t = -1 2 -1 0 0 0f = 0B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 1.5000

8、 0 2.0000 0 1.0000 0.5000 10.0000 -0.5000 1.0000 -2.0000 0 0 0.5000 2.0000k = 2t = 0 0 3 0 0 -1f = -4B = 1.5000 0 0 1.0000 0 -0.5000 8.0000 0.7500 0 1.0000 0 0.5000 0.2500 5.0000 1.0000 1.0000 0 0 1.0000 1.0000 12.0000k = 3t = -2.2500 0 0 0 -1.5000 -1.7500f = -19x = 0 12 5f = -19五總結(jié): 在單純形法求解過程中, 每一個基