作業(yè)1—單純形法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上單純形法及MATLAB實(shí)現(xiàn)單純形法(simplex method)由美國(guó)數(shù)學(xué)家G.B.丹齊克于1947年首先提出來(lái),其基本思路:將模型的一般形式變成標(biāo)準(zhǔn)形式，再根據(jù)標(biāo)準(zhǔn)型模型，從可行域中找一個(gè)基本可行解，并判斷是否是最優(yōu)。如果是，獲得最優(yōu)解；如果不是，轉(zhuǎn)換到另一個(gè)基本可行解，當(dāng)目標(biāo)函數(shù)達(dá)到最大時(shí)，得到最優(yōu)解。1.單純形法的基本原理單純形方法的基本思想, 是從一個(gè)基本可行解出發(fā), 求一個(gè)使目標(biāo)函數(shù)值有所改善的基本可行解; 通過(guò)不斷改進(jìn)基本可行解, 力圖達(dá)到最優(yōu)基本可行解.對(duì)問(wèn)題 其中A是一個(gè)m×n矩陣, 且秩為m, 為n維行向量, 為n維列向量, 為m維非負(fù)列

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

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

4、, 得到新單純形表. 表的最后一行是判別數(shù)和函數(shù)目標(biāo)值. 4. 實(shí)驗(yàn)流程圖及其MATLAB實(shí)現(xiàn)1. 流程圖開始: 初始基本可行解B解, 求得, 令, 計(jì)算目標(biāo)函數(shù)值求單純形乘子, 解, 得到. 對(duì)于所有非基變量, 計(jì)算判別數(shù). 令YN解, 得到現(xiàn)行基本可行解是最優(yōu)解NY確定下標(biāo)r, 使x=賦以正的大值NYNmin=N問(wè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

5、維列向量% 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:N k; z=B(:,end);%右端 for j=1:n-1 t(j)=y*B(:,j)-C(j);%檢驗(yàn)數(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

6、)=z(p)/B(p,q); 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

7、(2) 數(shù)值算例:例 3.1.2 用單純形方法解下列問(wèn)題 引進(jìn)松弛變量x, x, 問(wèn)題標(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) 運(yùn)行結(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 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