桂林電子科技大學
運籌學實驗報告
實驗六動態規劃輔導員意見：
電腦科學與工程學院資訊管理與資訊系統專業
12003401班第實驗小組
作者黃桂學號 1200340119
同作者輔導員
實驗日期 2014 年 12 月 22 日成績簽名
(1) 掌握動態規劃原理和數學建模方法；
(2) 掌握用動態規劃、整數規劃等來求解最短路徑問題、小規模的貨郎擔問題；
(3) 掌握用軟體來實現動態規劃應用求解方法。
用動態規劃、整數規劃方法來求解小規模的貨郎擔問題等np難度問題。
利用動態規劃來求解多段圖最短路徑問題。對如下圖所示的乙個3段圖，圖上的數字代表該段路徑的成本。現要求求出一條從起點1到匯點7的最短路徑，並計算出最短路徑成本。
答：在lingo輸入以下**：
model:
data:
n=7;
enddata
sets:
cities/1..n/: f; !7個城市;
roads(cities,cities)/
1,2 1,3 1,4
2,5 2,6
3,5 3,6
4,65,76,7/: d, p;
endsets
data:
d=1 4 6
7 6
1 5
821;enddata
f(n)=0;
@for(cities(i) | i #lt# n:f(i)=@min(roads(i,j): d(i,j)+f(j));
);!顯然，如果p(i,j)=1,則點i到點n的最短路徑的第一步是i --> j，否則就不是。
由此，我們就可方便的確定出最短路徑，p表示的就是路徑，為1是被選擇的;
@for(roads(i,j):p(i,j)=@if(f(i) #eq# d(i,j)+f(j),1,0)
);end點選solve得到以下執行結果為：
根據以上執行結果知，最短路徑為：1,3,5,7
提法一：有乙個推銷員，從城市1出發，要遍訪城市2，3，…，n各一次，最後返回城市1。已知從城市i到j的旅費為cij，問他應按怎樣的次序訪問這些城市，使得總旅費最少？
提法二：有乙個賣貨郎，從城鎮1出發，要遍訪城鎮2，3，…，n各一次，最後返回城鎮1。已知從城鎮i到j的距離為dij，問他應按怎樣的次序訪問這些城鎮，使得總路程最短？
用動態規劃求解以下貨郎擔問題。已知4個城市間距離如下表所示，求從v1出發，經其餘城市一次且僅一次最後返回v1的最短路徑與距離。
答：在lingo輸入以下**：
!貨郎擔問題;
model:
sets:
city / 1.. 4/: u;
link( city, city):
dist, ! 距離矩陣;
x;!最後求解的結果矩陣;
endsets
n = @size( city);
data: !距離矩陣，它並不需要是對稱的;
dist = 0 6 7 9
8 0 9 7
5 8 0 8
6 5 5 0; !要解決的問題的資料;
enddata
!目標函式;
min = @sum( link: dist * x);
@for( city( k):
!進入城市k;
@sum( city( i)| i #ne# k: x( i, k)) = 1;
!離開城市k;
@sum( city( j)| j #ne# k: x( k, j)) = 1;
);!保證不出現子圈;
@for(city(i)|i #gt# 1:
@for( city( j)| j#gt#1 #and# i #ne# j:
u(i)-u(j)+n*x(i,j)<=n-1);
);!限制u的範圍以加速模型的求解，保證所加限制並不排除掉tsp問題的最優解;
@for(city(i) | i #gt# 1: u(i)<=n-2 );
!定義x為0\1變數;
@for( link: @bin( x));
end點選solve得到以下介面為：
最短路徑為1，2，4，3
運籌學實驗一
運籌學上機實驗報告 姓名學號年級專業 2012級資訊管理與資訊系統 指導老師曹萍 實驗一線性規劃問題建模和求解 實驗目的 本實驗目的在於幫助我們學習如何運用excel對複雜的實際系統進行描述與建模，並用計算機求解，訓練學生的建模能力。實驗要求 用spreadsheet方法如何建立運籌學模型，並進一步...
運籌學實驗報告
實驗目的 了解及掌握運籌學一些常用軟體，如excel，winqsb 實驗步驟 1用excel求解數學規劃 例 求max 2x1 x2 x3 4x1 2x2 2x2 4 2x1 4x2 20 4x1 8x2 2x3 4 步驟 1 輸入模型資料 2 在e3單元格輸入公式 sumproduct b 2 d...
運籌學實驗報告
數學與計算科學學院 實驗報告 實驗專案名稱 lingo matlab關於線性問題的求解 所屬課程名稱運籌學 實驗型別綜合 實驗日期2014年10月12日 班級統計1201班 學號201247100126 姓名楊賽波 附錄1 源程式 附錄2 實驗報告填寫說明 1 實驗專案名稱 要求與實驗教學大綱一致....