實驗二：MATLAB編程單純形法求解

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

2、規(guī)劃問題:求解上述一般標(biāo)準(zhǔn)線性規(guī)劃的單純形算法（修正）步驟如下：對于一般的標(biāo)準(zhǔn)形式線性規(guī)劃問題(求極小問題),首先給定一個初始基本可行解。設(shè)初始基為B,然后執(zhí)行如下步驟： (1).解,求得，(2).計算單純形乘子w, ,得到,對于非基變量，計算判別數(shù),可直接計算令 ,R為非基變量集合若判別數(shù) ,則得到一個最優(yōu)基本可行解，運算結(jié)束；否則，轉(zhuǎn)到下一步(3).解,得到；若,即的每個分量均非正數(shù)，則停止計算，問題不存在有限最優(yōu)解，否則，進行步驟(4).確定下標(biāo)r,使;、計算框圖為：開始 初始可行基B 是 否 得到最優(yōu)是否 不存在有限確定下標(biāo)r,使得 圖13計算程序(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)建一個一一映射，為了結(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); %基矩陣對應(yīng)目標(biāo)值的c while fla

4、g w=cB/B; %計算單純形乘子，cB/B=cB*inv(B),用cB/B的目的是，為了提高運行速度。 panbieshu=w*A-c %計算判別數(shù),后面沒有加分號，就是為了計算后能夠顯示出來。 z,k=max(panbieshu); % k作為進基變量下標(biāo) 。 fprintf('b''./(BA(:,%d)為',k); b'./(BA(:,k) if(z<0.000000001) flag=0; %所有判別數(shù)都小于0時達到最優(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中沒有X(i),則X(i)為非基變量，所以X(i)0。 end end fprintf('基向量為:'); X fprintf('目標(biāo)函數(shù)值為:') ; f else if(BA(:,k)<=0) % 如果BA(;,k)中的每一個分量都小于零。 flag=0; fprintf(' n 此問題不存在最優(yōu)解!n'

6、); %若BA(:,k)的第k列均不大于0，則該問題不存在最優(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)進基，x(%d)退基n',k,D(r,2); %顯示進基變量和退基變量 B(:,r)=A(:,k); cB(r)=c(k); %確定進基退基變量后，相應(yīng)的基矩陣及新基對應(yīng)的目標(biāo)值的c也相應(yīng)改變 D(r,2)=k; %改變D

7、中的映射關(guān)系 end end endend程序保存為 danchunxin.m文件四數(shù)值實驗及其結(jié)果： 打開matlab軟件，點擊運行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點擊運行得如下圖：圖2由實驗結(jié)果可知，該問題的最優(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點擊運行得如下圖：圖3由實驗結(jié)果可知，該問題的最優(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點擊運行得如下圖：圖4由實驗結(jié)果可知，該線性問題不存在最優(yōu)解。五實驗總結(jié) 通過該實驗，加深了對線性規(guī)劃問題的理解，并加深了將實際問題進行數(shù)學(xué)建模轉(zhuǎn)化為可利用MATLAB軟件處理的線性規(guī)劃