1、1 / 15 工廠原料運輸問題課程設計報告 一、課程設計的目的 運籌與最優化方法 是信息與計算科學專業的一門重要的專業課程， 是一 門綜合應用課程。 主要內容包括： 線性規劃、整數規劃、動態規劃、非線性規劃、 庫存論、排隊論、博奕論、圖與網絡分析的基本概念、方法和模型等，以及有廣 泛應用前景的運籌學問題的啟發式算法。 運籌學與最優化方法中的運輸問題是一種應用廣泛的網絡最優化模型， 該模型的主要目的是為物資調運，車輛調度選擇最經濟的運輸路線。 運籌學與最優化方法 運輸問題課程設計的目的是為了適應信息管理與信 息系統培養目標的要求， 使我們學習掌握如何應用運籌學中的數量方法與模型來 分析通過計算機

2、來實現研究現代企業生產與技術管理以及經營管理決策問題。 課 程設計使我們能成熟的理解和應用運籌學模型， 使我們認識運籌學在生產與技術 管理和經營管理決策中的作用， 領會其基本思想和分析與解決問題的思路。 為我 們以后畢業參加工作單位的策略策劃打下堅實的基礎。 二、課程設計地點 ： 第三實驗樓 4 樓， 運籌學實驗室 三、課程設計時間 ： 第十八周，第十九周 四、課程設計原理與過程 (一)運輸問題的內容及其解決方法 運輸問題是一種應用廣泛的網絡最優化模型，該模型的主要目的是為物資 調運、車輛高度選擇最經濟的運輸路線。有些問題，如 m臺機床加工零件問題、 工廠合理布局問題， 雖要求與提法不同， 經

3、適當變化也可以使用本模型求得最付 佳方案。 運輸問題的一般提法： 某種物資有m個產地Ai，產量是ai (i = 1,2,m),有m個銷售地Bi，銷量(需 求量)是 bj(j=1,2, ，m)。 若從 Ai 運到 Bi 單位運價為 dij(i=1,2, ,m;j=1,2,m),又假設產銷平衡,即 mn ai bj i1 j 1 問如何安排運輸可使總運費最小？ 若用xij (i=1,2,m;j=1,2,n)表示由A運到B的運輸量，則平衡運輸 問題可寫出以下線性規劃模型： mn min Z dij xij i1j1 約束條件n 2 / 15 Xjj a (i 1,2., m) j i m Xij b

4、j (j 1,2.,n) i 1 xij 0(i 1,2.,m; j 1,2,.,n) 具體問題如下： 三個工廠B1, B, 它們需要同一種原料，數量分別是 72噸、102噸、 41噸，另外有三座倉庫 A、A、A可以供應上述原料56噸、82噸、77噸，由于 工廠和倉庫位置不同，單位運價不同，具體數據如表 1。應如何安排運輸方案， 才能使總運費最??？ 表1 B R B3 產量 A 4 8 8 56 A 16 24 16 82 A 8 16 24 77 銷量 72 102 41 215 解決方法用表上作業法，具體原理和方法如下： 觀察運輸問題的線性規劃模型可知：它有 m*n具變量，（m+n）個約束

5、方程, 其系數矩陣為0-1矩陣，且有大量的零，通常稱為稀疏矩陣，形如: X11X12 X 1nX21X22 X 2n X mXm2 X mn 1 1 1 m行 1 1 1 1 1 1 1 1 1 1 1 1 n行 1 1 1 易知此矩陣的任何一個m+n階子方陣對應的行列式等于零，所以系數矩陣的 秩w m+n-1，并可證明運輸問題的約束方程組系數矩陣的秩為 m+n-1. 由此可知運輸問題只有m+n-1個獨立的約束方程，即其基本可行解中基變量 個數為m+n-1，其余均為非基變量。 由于運輸問題的以上特征，可用更簡便的方法進行計算，即表上作業法。 表上作業法原理同于單純形法，首先給出一個初始的調運方

6、案（實際上是初 始基本可行解），求出各非基變量的檢驗數去判定當前解是否為最優解，若不是 則進行方案調整（即從一個基本可行解轉換成另一個基本可行解），再判定是否為 最優解，重復以上步驟，直到獲得最優解為止。這些步驟在表上進行十分方便。 操作過程在表上進行，具體的表如下： 表23 / 15 B1 B2 B3 產量 A1 4 X 11 8 X 12 8 X 13 56 A2 16 X 21 24 X 22 16 X 23 82 A3 8 X 31 16 X 32 24 X 33 77 銷量 72 102 41 215 初始調運方案如下表: 表3 B1 B2 B3 產量 A1 4 56 8 x 8 x

7、 56 A2 16 x 24 41 16 41 82 A3 8 16 16 61 24 x 77 銷量 72 102 41 215 上表中“x”表示非基變量 最優解的判定如下表 B1 B2 B3 產量 Ui A1 4 56 8 CD 8 56 0 A2 16 24 41 16 41 82 12 A3 8 16 16 61 24 77 4 銷量 72 102 41 215 vj 4 12 4 上表中帶圈的數字所表示的是非基變量。 若令入j =dj -（u i+vj（d j為非基變量所在的空格處的運費），稱入j為空格檢 驗數?？梢宰C明入j就是單純形法中的檢驗數。所以用判定最優解的原則也同于 單純形

8、法中的判定定理。當入j 0時，即可得到最優解，若入j 0,則返回上 級操作。直到得到最優解。 （二） 運輸問題課程設計源程序代碼 / #include stdafx.h #include #include #include #include using namespace std; 4 / 15 #define a(j) (* (C+(M-1)*N+j) / 銷量數組 #define b(i) (* (C+i*N+N-1) / 產量數組 #define c(i,j) (* (C+i*N+j) / 運價數組 #define x(i,j) (* (X+i*(N-1)+j) / 運量數組 const

9、 double BIG_NUM = 1.0E15; / 任意大數 / ( = J BIG_NUM : 運量為 0 ) #define s(i,j) (*(S+i*(N-1)+j) / 檢驗數數組 Sij */ #define u(i) (*(U+i) / 位勢數組 Ui #define v(i) (*(V+i) / 位勢數組 Vi #define cpi(k) (CP+k)-i) / 閉回路點 i 標 #define cpj(k) (CP+k)-j) / 閉回路點 j 標 #define cpf(k) (CP+k)-f) / 閉回路點 f 標 /* f = 0: j+; f = 1: i-;

10、f = 2: j-; f = 3: i+; */ void TP(int M,int N,double *C,double *X); int main() int M, N, i, double* C; / double* X; / double z; ifstream infile; char fn80; double sum; cout.setf(ios_base:left,ios_base:adjustfield); cout.setf(ios_base:fixed,ios_base:floatfield); cout.precision(3); coutfn; infile.open(

11、fn); if (!infile) coutMN; j; 存儲運價 , 產量及銷量 存儲運量分配方案 5 / 15 M+; N+; X=new doublesizeof(double)*(M-1)*(N-1); C=new doublesizeof(double)*M*N; / 把運價 , 供應量和需求量的數據讀入到數組 c( i, j ) for(i=0;iM;+i) for(j=0;jz; c(i,j)=z; infile.close(); coutn= 數據文件 =n; for(i=0;iM;+i) for(j=0;jN;+j) coutsetw(10)c(i,j); coutendl;

12、 system(pause); TP(M,N,C,X); / 輸出產銷分配方案 coutn= 最優解 =n; sum=0; for(i=0;iM-1;+i) for(j=0;j=BIG_NUM) coutsetw(10)*; else coutsetw(10)x(i,j); sum+=(x(i,j)*c(i,j); coutendl; /coutnntThe min Cost is: %-10.4fn, sum); coutnnt 最高產量 :setw(10)sumendl; / 我們現在是在求 max， free(X); free(C); system(pause); return 0; / 記錄閉回路點結構 max=-min 6 / 15 struct PATH int i,j,f; ; void TP(int M,int N,double* C,double* X) double *U, *V , *S; int MN1,m,n; struct PATH* CP; int k,i,j,l,k1,l1,ip; double Cmin,sum; int I0,J0,Im