實(shí)驗(yàn)二：MATLAB編程單純形法求解

1、北京聯(lián)合大學(xué)實(shí)驗(yàn)報(bào)告項(xiàng)目名稱： 運(yùn)籌學(xué)專題實(shí)驗(yàn)報(bào)告 學(xué) 院： 自動(dòng)化 專 業(yè)： 物流工程 班 級(jí)： 1201B 學(xué) 號(hào)：2012100358081 姓 名： 管水城 成 績(jī)： 2015 年5月6日實(shí)驗(yàn)二：MATLAB編程單純形法求解一、實(shí)驗(yàn)?zāi)康模?1)使學(xué)生在程序設(shè)計(jì)方面得到進(jìn)一步的訓(xùn)練;，掌握Matlab (C或VB)語(yǔ)言進(jìn)行程序設(shè)計(jì)中一些常用方法。(2)使學(xué)生對(duì)線性規(guī)劃的單純形法有更深的理解.二、實(shí)驗(yàn)用儀器設(shè)備、器材或軟件環(huán)境 計(jì)算機(jī), Matlab R2006三、算法步驟、計(jì)算框圖、計(jì)算程序等本實(shí)驗(yàn)主要編寫如下線性規(guī)劃問(wèn)題的計(jì)算程序:其中初始可行基為松弛變量對(duì)應(yīng)的列組成.對(duì)于一般標(biāo)準(zhǔn)線性

2、規(guī)劃問(wèn)題:求解上述一般標(biāo)準(zhǔn)線性規(guī)劃的單純形算法（修正）步驟如下：對(duì)于一般的標(biāo)準(zhǔn)形式線性規(guī)劃問(wèn)題(求極小問(wèn)題),首先給定一個(gè)初始基本可行解。設(shè)初始基為B,然后執(zhí)行如下步驟： (1).解,求得，(2).計(jì)算單純形乘子w, ,得到,對(duì)于非基變量，計(jì)算判別數(shù),可直接計(jì)算令 ,R為非基變量集合若判別數(shù) ,則得到一個(gè)最優(yōu)基本可行解，運(yùn)算結(jié)束；否則，轉(zhuǎn)到下一步(3).解,得到；若,即的每個(gè)分量均非正數(shù)，則停止計(jì)算，問(wèn)題不存在有限最優(yōu)解，否則，進(jìn)行步驟(4).確定下標(biāo)r,使;、計(jì)算框圖為：開(kāi)始 初始可行基B 是 否 得到最優(yōu)是否 不存在有限確定下標(biāo)r,使得 圖13計(jì)算程序(Matlab)：A=input(&#

3、39;A=');b=input('b=');c=input('c=');format rat %可以讓結(jié)果用分?jǐn)?shù)輸出m,n=size(A);E=1:m;E=E' F=n-m+1:n;F=F'D=E,F; %創(chuàng)建一個(gè)一一映射，為了結(jié)果能夠標(biāo)準(zhǔn)輸出X=zeros(1,n); %初始化Xif(n<m) %判斷是否為標(biāo)準(zhǔn)型 fprintf('不符合要求需引入松弛變量') flag=0;else flag=1; B=A(:,n-m+1:n); %找基矩陣 cB=c(n-m+1:n); %基矩陣對(duì)應(yīng)目標(biāo)值的c while fla

4、g w=cB/B; %計(jì)算單純形乘子，cB/B=cB*inv(B),用cB/B的目的是，為了提高運(yùn)行速度。 panbieshu=w*A-c %計(jì)算判別數(shù),后面沒(méi)有加分號(hào)，就是為了計(jì)算后能夠顯示出來(lái)。 z,k=max(panbieshu); % k作為進(jìn)基變量下標(biāo) 。 fprintf('b''./(BA(:,%d)為',k); b'./(BA(:,k) if(z<0.000000001) flag=0; %所有判別數(shù)都小于0時(shí)達(dá)到最優(yōu)解。 fprintf(' 已找到最優(yōu)解!n'); xB=(Bb')' f=cB*xB&

5、#39; for i=1:n mark=0; for j=1:m if (D(j,2)=i) mark=1; X(i)=xB(D(j,1); %利用D找出xB與X之間的關(guān)系。 end end if mark=0 X(i)=0; %如果D中沒(méi)有X(i),則X(i)為非基變量，所以X(i)0。 end end fprintf('基向量為:'); X fprintf('目標(biāo)函數(shù)值為:') ; f else if(BA(:,k)<=0) % 如果BA(;,k)中的每一個(gè)分量都小于零。 flag=0; fprintf(' n 此問(wèn)題不存在最優(yōu)解!n'

6、); %若BA(:,k)的第k列均不大于0，則該問(wèn)題不存在最優(yōu)解。 else b1=Bb' temp=inf; for i=1:m if (A(i,k)>0) && (b1(i)/(A(i,k)+eps)<temp ) temp=b1(i)/A(i,k); %找退基變量 r=i; end end fprintf('x(%d)進(jìn)基，x(%d)退基n',k,D(r,2); %顯示進(jìn)基變量和退基變量 B(:,r)=A(:,k); cB(r)=c(k); %確定進(jìn)基退基變量后，相應(yīng)的基矩陣及新基對(duì)應(yīng)的目標(biāo)值的c也相應(yīng)改變 D(r,2)=k; %改變D

7、中的映射關(guān)系 end end endend程序保存為 danchunxin.m文件四數(shù)值實(shí)驗(yàn)及其結(jié)果： 打開(kāi)matlab軟件，點(diǎn)擊運(yùn)行danchunxin.m，出現(xiàn)命令符要求輸入相應(yīng)矩陣命令。1. 求解：輸入數(shù)據(jù)矩陣如下：A=9 4 1 0 0;4 5 0 1 0;3 10 0 0 1b=360 200 300c=-7 -12 0 0 0點(diǎn)擊運(yùn)行得如下圖：圖2由實(shí)驗(yàn)結(jié)果可知，該問(wèn)題的最優(yōu)解為：x1=100,x2=0,x3=540,x4=200,x5=0,最大值為700。2. 求解：輸入數(shù)據(jù)矩陣如下：A=-3 -2 -1 -6 -18 1 0;-1 -0.5 -0.2 -2 -0.5 0 1;0.5 1 0.2 2 0.8 0 0b=-700 -30 200c=2 7 4 9 5 0 0點(diǎn)擊運(yùn)行得如下圖：圖3由實(shí)驗(yàn)結(jié)果可知，該問(wèn)題的最優(yōu)解為：x1=15200/33,x2=0,x3=0,x4=0,x5=1250/33,x6=0,最小值為：1235/3。3. 求解：輸入數(shù)據(jù)矩陣如下：A=1 -2 1 1 0;4 -1 -2 0 1;-2 0 1 0 0b=11 -3 1c=3 -1 -1 0 0點(diǎn)擊運(yùn)行得如下圖：圖4由實(shí)驗(yàn)結(jié)果可知，該線性問(wèn)題不存在最優(yōu)解。五實(shí)驗(yàn)總結(jié) 通過(guò)該實(shí)驗(yàn)，加深了對(duì)線性規(guī)劃問(wèn)題的理解，并加深了將實(shí)際問(wèn)題進(jìn)行數(shù)學(xué)建模轉(zhuǎn)化為可利用MATLAB軟件處理的線性規(guī)劃