實驗6最短路求解--的編程實現(xiàn)

1、實驗6 最短路問題的編程實現(xiàn)成績專業(yè)班級 數(shù)學121 學號 201212010131 姓名 覃紹強 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設(shè)計性實驗實驗?zāi)康模菏炀氉疃搪穯栴}的Dijkstra算法。實驗內(nèi)容：最短路問題的Dijkstra算法。實驗原理 最短路問題的Dijkstra算法：首先對圖中的所有節(jié)點賦予雙標號,即臨時標號和永久標號,然后按一定的策略,依次判斷并修改節(jié)點的臨時標號,知道最后將終點改為永久標號求出最短路徑。實驗步驟1 要求上機實驗前先編寫出程序代碼 2 編輯錄入程序3 調(diào)試程序并記錄調(diào)試過程中出現(xiàn)的問題及修改程序的過程4 經(jīng)反復(fù)調(diào)試后，運行程序并驗證程序運行是否正確。5

2、 記錄運行時的輸入和輸出。 預(yù)習編寫程序代碼：實驗報告：根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗總結(jié)：參考程序函數(shù)文件：dijkstra.mfunction min,path=dijkstra(w,start,terminal)n=size(w,1); label(start)=0; f(start)=start;%初始化for i=1:nif i=startlabel(i)=inf;endends(1)=start; u=start;while length(s)(label(u)+w(u,v)label(v)=(label(u)+w(u,v); f(v)=u;endendend %v1=

3、0; k=inf;for i=1:nins=0;for j=1:length(s)if i=s(j)ins=1;endendif ins=0 v=i;if klabel(v) k=label(v); v1=v;endendends(length(s)+1)=v1; u=v1;endmin=label(terminal); path(1)=terminal;i=1; while path(i)=startpath(i+1)=f(path(i); i=i+1 ;endpath(i)=start;L=length(path);path=path(L:-1:1); 求解下圖中的最短路求解過程：輸入輸出

4、： x = 0 2 1 8 Inf Inf Inf Inf Inf Inf Inf 2 0 Inf 6 1 Inf Inf Inf Inf Inf Inf 1 Inf 0 7 Inf Inf 9 Inf Inf Inf Inf 8 6 7 0 5 1 2 Inf Inf Inf Inf Inf 1 Inf 5 0 3 Inf 2 1 Inf Inf Inf Inf Inf 1 3 0 4 Inf 6 Inf Inf Inf Inf 9 2 Inf 4 0 Inf 3 1 Inf Inf Inf Inf Inf 2 Inf Inf 0 7 Inf Inf Inf Inf Inf Inf Inf

5、6 3 7 0 1 2 Inf Inf Inf Inf Inf Inf 1 Inf 1 0 1 Inf Inf Inf Inf Inf Inf Inf Inf 2 1 0 start=1; terminate=11; min,path=dijkstra(x,start,terminate)min = 6path =1 2 5 9 11結(jié)果分析：即最短路徑為：v1v2v5v9v11,最短距離為：16，手工計算的結(jié)果為：上述兩種結(jié)果一致?？偨Y(jié)：通過編程，將最短路的算法加深了印象，也熟悉了matlab編程，頗有收獲的一次實驗，給力！實驗7 最大流問題的編程實現(xiàn)成績專業(yè)班級 數(shù)學121 學號 2012

6、12010128 姓名 秦柯柯 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設(shè)計性實驗實驗?zāi)康模菏炀氉畲罅鲉栴}的求解算法。實驗內(nèi)容：最大流問題的求解算法。實驗原理：先給定初始可行流，然后找出可擴充路（增廣鏈），調(diào)整可擴充路上的流量，使可行流增大，不斷重復(fù)上述過程，直到不存在可擴充路為止。 實驗步驟1 要求上機實驗前先編寫出程序代碼 2 編輯錄入程序3 調(diào)試程序并記錄調(diào)試過程中出現(xiàn)的問題及修改程序的過程4 經(jīng)反復(fù)調(diào)試后，運行程序并驗證程序運行是否正確。5 記錄運行時的輸入和輸出。 預(yù)習編寫程序代碼：實驗報告：根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗總結(jié)：參考程序使用lingo求解model:

7、sets:point/v1,v2,v3,v4,v5/;route(point,point)/v1 v2,v1 v3,v2 v3,v2 v4,v4 v3,v3 v5,v4 v5/:transport,capacity;endsetsdata:capacity=3 2 1 2 0 4 2;enddatamax=z;z=sum(point(j)|in(route,index(point,v1),j):transport(1,j);for(point(i)|i#ne#index(point,v1)#and#i#ne#index(point,v5):sum(point(j)|in(route,i,j):

8、transport(i,j)=sum(point(j)|in(route,j,i):transport(j,i);for(route:transport=capacity);end運行結(jié)果：Global optimal solution found. Objective value: 5.000000 Total solver iterations: 0 Variable Value Reduced Cost Z 5.000000 0.000000 TRANSPORT( V1, V2) 3.000000 0.000000 TRANSPORT( V1, V3) 2.000000 0.000000

9、 TRANSPORT( V2, V3) 1.000000 0.000000 TRANSPORT( V2, V4) 2.000000 0.000000 TRANSPORT( V4, V3) 0.000000 0.000000 TRANSPORT( V3, V5) 3.000000 0.000000 TRANSPORT( V4, V5) 2.000000 0.000000 CAPACITY( V1, V2) 3.000000 0.000000 CAPACITY( V1, V3) 2.000000 0.000000 CAPACITY( V2, V3) 1.000000 0.000000 CAPACI

10、TY( V2, V4) 2.000000 0.000000 CAPACITY( V4, V3) 0.000000 0.000000 CAPACITY( V3, V5) 4.000000 0.000000 CAPACITY( V4, V5) 2.000000 0.000000 Row Slack or Surplus Dual Price 1 5.000000 1.000000 2 0.000000 1.000000 3 0.000000 -1.000000 4 0.000000 0.000000 5 0.000000 -1.000000 6 0.000000 0.000000 7 0.0000

11、00 1.000000 8 0.000000 1.000000 9 0.000000 0.000000 10 0.000000 1.000000 11 1.000000 0.000000 12 0.000000 1.000000實驗總結(jié)：最大流問題的基本思路是：先給出初始可行流，再找到可擴充路，不斷進行優(yōu)化，直至無法找到可擴充路為止。實驗8 排隊論與存儲論問題的編程實現(xiàn)成績專業(yè)班級 數(shù)學121 學號 201212010128 姓名 秦柯柯 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設(shè)計性實驗實驗?zāi)康模毫私夥蔷€性規(guī)劃的模型與求解算法。實驗內(nèi)容：實驗原理 按照存儲問題的基本模型類型，通過求解使

12、總費用最小的優(yōu)化問題，求出最優(yōu)訂購批量、生產(chǎn)批量、最大存儲量和最大缺貨量、訂貨周期、間隔等數(shù)量指標。實驗步驟1 要求上機實驗前先編寫出程序代碼 2 編輯錄入程序3 調(diào)試程序并記錄調(diào)試過程中出現(xiàn)的問題及修改程序的過程4 經(jīng)反復(fù)調(diào)試后，運行程序并驗證程序運行是否正確。5 記錄運行時的輸入和輸出。 預(yù)習編寫程序代碼：實驗報告：根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗總結(jié)：參考程序問題：某電氣公司的生產(chǎn)流水線需要某種零件，該零件需要靠訂貨得到。為此公司考慮到了如下費用結(jié)構(gòu)：1） 批量訂購的訂貨費12000元/次2） 每個零件的單位成本10元/件3） 每個零件的存儲費用0.3元/(件.月)4） 每個零

13、件的缺貨損失1.1 元/(件.月)Lingo求解：min=0.5*C_P*(Q-S)2/Q+C_D*D/Q+0.5*C_S*S2/Q;N=D/Q;gin(N);data:C_D=12000;D=96000;C_P=3.6;C_S=13.2;enddata運行結(jié)果：Local optimal solution found. Objective value: 81257.14 Extended solver steps: 3 Total solver iterations: 895 Variable Value Reduced Cost C_P 3.600000 0.000000 Q 32000.

14、00 0.000000 S 6857.143 0.000000 C_D 12000.00 0.000000 D 96000.00 0.000000 C_S 13.20000 0.000000 N 3.000000 -3085.704 Row Slack or Surplus Dual Price 1 81257.14 -1.000000 2 0.000000 -3085.704實驗9 排隊論問題的編程實現(xiàn)成績專業(yè)班級 數(shù)學121 學號 201212010128 姓名 秦柯柯 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設(shè)計性實驗實驗?zāi)康模毫私夥蔷€性規(guī)劃的模型與求解算法。實驗內(nèi)容：實驗原理 按

15、照排隊論的基本模型：M/M/1、M/M/c等會計算排隊系統(tǒng)的數(shù)量指標，包括隊長、排隊等待的隊長、逗留時間、等待時間、忙期、閑期及排隊系統(tǒng)的優(yōu)化。實驗步驟1 要求上機實驗前先編寫出程序代碼 2 編輯錄入程序3 調(diào)試程序并記錄調(diào)試過程中出現(xiàn)的問題及修改程序的過程4 經(jīng)反復(fù)調(diào)試后，運行程序并驗證程序運行是否正確。5 記錄運行時的輸入和輸出。 預(yù)習編寫程序代碼：實驗報告：根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗總結(jié)：參考程序程序文件：%* %初始化顧客源 %* %總仿真時間 Total_time = 10; %隊列最大長度 %到達率與服務(wù)率 lambda = 10; mu = 6; %平均到達時間與

16、平均服務(wù)時間 arr_mean = 1/lambda; ser_mean = 1/mu; arr_num = round(Total_time*lambda*2); events = ; %按負指數(shù)分布產(chǎn)生各顧客達到時間間隔 events(1,:) = exprnd(arr_mean,1,arr_num); %各顧客的到達時刻等于時間間隔的累積和 events(1,:) = cumsum(events(1,:); %按負指數(shù)分布產(chǎn)生各顧客服務(wù)時間 events(2,:) = exprnd(ser_mean,1,arr_num); %計算仿真顧客個數(shù)，即到達時刻在仿真時間內(nèi)的顧客數(shù) len_si

17、m = sum(events(1,:)Total_time break; else number = sum(events(4,member) events(1,i); %如果系統(tǒng)已滿，則系統(tǒng)拒絕第 i個顧客，其標志位置 0 if number = N+1 events(5,i) = 0; %如果系統(tǒng)為空，則第 i個顧客直接接受服務(wù) else if number = 0 %其等待時間為 02009.1516%PROGRAMLANGUAGEPROGRAMLANGUAGEevents(3,i) = 0; %其離開時刻等于到達時刻與服務(wù)時間之和 events(4,i) = events(1,i)+e

18、vents(2,i); %其標志位置 1 events(5,i) = 1; member = member,i; %如果系統(tǒng)有顧客正在接受服務(wù)，且系統(tǒng)等待隊列未滿，則 第 i個顧客進入系統(tǒng) else len_mem = length(member); %其等待時間等于隊列中前一個顧客的離開時刻減去其到 達時刻 events(3,i)=events(4,member(len_mem)-events(1,i); %其離開時刻等于隊列中前一個顧客的離開時刻加上其服 %務(wù)時間 events(4,i)=events(4,member(len_mem)+events(2,i); %標識位表示其進入系統(tǒng)后，

19、系統(tǒng)內(nèi)共有的顧客數(shù) events(5,i) = number+1; member = member,i; end end end end %仿真結(jié)束時，進入系統(tǒng)的總顧客數(shù) len_mem = length(member); %* %輸出結(jié)果 %* %繪制在仿真時間內(nèi)，進入系統(tǒng)的所有顧客的到達時刻和離 %開時刻曲線圖（stairs：繪制二維階梯圖） stairs(0 events(1,member),0:len_mem); hold on; stairs(0 events(4,member),0:len_mem,.-r); legend(到達時間 ,離開時間 ); %標簽hold off; gr

20、id on; %添加網(wǎng)格線%繪制在仿真時間內(nèi)，進入系統(tǒng)的所有顧客的停留時間和等 %待時間曲線圖（plot：繪制二維線性圖） figure; plot(1:len_mem,events(3,member),r-*,1: len_mem,events(2,member)+events(3,member),k-); legend(等待時間 ,停留時間 ); grid on;運行圖像：ans =2.0092e+003 實驗10 運籌學綜合應(yīng)用成績專業(yè)班級 數(shù)學121 學號 201212010128 姓名 秦柯柯 報告日期 .實驗類型：驗證性實驗 綜合性實驗 設(shè)計性實驗實驗?zāi)康模号囵B(yǎng)用運籌理論與方法解決

21、實際問題的能力。實驗內(nèi)容：自己發(fā)現(xiàn)生活、生產(chǎn)實際中的問題，建立其數(shù)學模型，進行求解，完成實驗報告；或針對過去數(shù)學建模問題的某一部分進行建模求解，寫出實驗報告。實驗原理 根據(jù)生活、生產(chǎn)實際中的問題特征，綜合運籌學所學理論與方法建立相應(yīng)的模型，設(shè)計求解算法，求出問題的解。實驗步驟1 要求上機實驗前先編建立模型、設(shè)計求解算法、寫出程序代碼 2 編輯錄入程序3 調(diào)試程序并記錄調(diào)試過程中出現(xiàn)的問題及修改程序的過程4 經(jīng)反復(fù)調(diào)試后，運行程序并驗證程序運行是否正確。5 記錄運行時的輸入和輸出。預(yù)習編寫程序代碼：實驗報告：根據(jù)實驗情況和結(jié)果撰寫并遞交實驗報告。實驗總結(jié)：參考程序問題：某公司有甲乙兩個工廠生產(chǎn)兩

22、種產(chǎn)品，這兩種產(chǎn)品要運到南北兩個地區(qū)出售。相關(guān)信息見表格，產(chǎn)品分別有兩個工廠中的兩個車間來完成。公司希望采取一些措施來提高經(jīng)濟效益，為此要弄清楚應(yīng)該關(guān)注哪些問題，是擴大銷量還是改善工廠的瓶頸問題？如果擴大銷量，首先擴大哪個市場以及首先擴大哪種產(chǎn)品？如果要增加工廠的有效工時，應(yīng)首先關(guān)注哪一家工廠的哪個車間？分析：這是一個線性規(guī)劃問題，重點在建模并用對偶理論進行分析。 產(chǎn)品收益=售價-銷售費用-單價生產(chǎn)成本-單價運費建模： 銷量限制：，工時限制：故可建立模型：s.t求解：下面用matlab求解：1） 建立函數(shù)文件：function sol,val,kk=ssimplex(A,N)%- 求解標準型線

23、性規(guī)劃:max c*x;s.t. A*x=b;x=0%- A:初始單純形表，（包括:第一行為c，最后一行是初始的檢驗數(shù)，最后一列是資源向量b）%- N：初始的基變量的下標%- sol：是最優(yōu)解%- val：是最優(yōu)值%- kk：是迭代次數(shù)mA,nA=size(A);kk=0; % 迭代次數(shù)flag=1;while flag kk=kk+1; if A(mA,:)0 & A(1:mA-1,i)temp temp=A(mA,i); inb=i; % 進基變量的下標 end end sita=zeros(1,mA-1); for i=1:mA-1 if A(i,inb)0 sita(i)=A(i,nA

24、)/A(i,inb); end end temp=inf; for i=1:mA-1 if sita(i)0&sita(i) temp=sita(i); outb=i; % 出基變量下標 end end % 以下更新N for i=1:mA-1 if i=outb N(i)=inb; end end % 以下進行轉(zhuǎn)軸運算 A(outb,:)=A(outb,:)/A(outb,inb); for i=1:mA if i=outb A(i,:)=A(i,:)-A(outb,:)*A(i,inb); end end end endend2） 輸入輸出：A= 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 9000; 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 7500