運輸論法

運輸論法

運輸論法,主要研究從一些貨源地到另一些目的地的最優運輸方法的問題。經過適當修改後,並可用來解決一些與運輸毫無關係的問題,如向機器分派任務的問題等。

基本介紹

  • 中文名:運輸論法
  • 外文名:Transport theory
  • 拼音:Yùn shū lùn fǎ
  • 適用:運輸問題
  • 套用領域:生產計畫、任務分配等
  • 學科:運籌學
基本內容,適用範圍,求解過程,舉例,

基本內容

運輸問題:人們在從事生產活動中,不可避免地要進行物資調運工作。如某時期內將生產基地的煤、鋼鐵、糧食等各類物資,分別運到需要這些物資的地區,根據各地的生產量和需要量及各地之間的運輸費用,如何制定一個運輸方案,使總的運輸費用最小。這樣的問題稱為運輸問題。

適用範圍

有些問題表面上與運輸問題沒有多大關係,也可以建立與運輸問題形式相同的數學模型。現已發現的運輸型問題有以下6類:①一般運輸問題,又稱希契科克運輸問題,簡稱H問題。②網路運輸問題,又稱圖上運輸問題,簡稱T問題。③最大流量問題,簡稱F問題。④最短路徑問題,簡稱S問題。⑤任務分配問題,又稱指派問題,簡稱A問題。⑥生產計畫問題,又稱日程計畫問題,簡稱CPS問題。如把產地稱為源(發點),銷地稱為匯(收點),則任務分配問題、生產計畫問題等運輸型問題的模型也可以歸納成類似上述形式。

求解過程

表上作業法的基本思想是:先設法給出一個初始方案,然後根據確定的判別準則對初始方案進行檢查、調整、改進,直至求出最優方案。表上作業法是求解運輸問題的一種簡化方法,實質是單純形法。具體步驟如下:
1.找初始基可行解。即在 (m
n) 產銷平衡表上給出m+n -1個數字格,不能構成閉迴路,且行和等於產量,列和等於銷售量;
2.求非基變數檢驗數。在表上求出空格的檢驗數,判別是否達到最優解。如果達到最優解,則停止計算,否則轉入下一步;
3.確定換入變數和換出變數,找出新的基可行解,在表上用閉迴路法進行調整。
4.重複2、3步,直到求得最優解為止。
確定初始基可行解
① 方法一:最小元素法
基本思想:就近供應。即從單位運價表中最小的運價開始確定產銷關係,依次類推,直到給出初始方案為止。兩種特殊情況:1.多個元素同時最小,任選一個作基變數。2.對於最小元素,發現該元素所在行的剩餘產量等於該元素所在列的剩餘銷售量。這時在產銷平衡表相應的位置填上一個數,而在單位運價表中就要同時划去一行和一列。為了使調運方案中有數字的格仍為(m + n –1)個,需要在同時划去的行或列的任一空格位置添上一個“0”,這個“0”表示該變數是基變數,只不過它取值為0,即此時的調運方案是一個退化的基可行解。
②方法二:伏格爾法
一產地的產品,假如不能按最小運費就近供應,就考慮次小運費。這就有一個差額,差額越大,說明不能按最小運費調運時,運費增加就越多。因此,對於差額最大處,就優先採用最小運費調運。
③方法三:西北角法
西北角法的基本思想是給運輸表中左上角的變數分配運輸量以確定產銷關係。
最優解的判別
目標函式是要求最小化,所以當所有的非基變數檢驗數全都大於等於 0 時為最優解。求空格檢驗數。
①方法一:閉迴路法
這種方法需要對每一個空格尋找一條閉迴路,並根據閉迴路求出每個空格的檢驗數。當運輸問題中m和n較大時,計算檢驗數的工作量很大。
② 方法二:位勢法
先對初始調運方案求出位勢,然後求各空格的檢驗數。當所有的檢驗數均為非負時,就得到最優方案。如果出現負的檢驗數,則從檢驗數為負的空格出發,作閉迴路,重新計算檢驗數,作進一步調整。用位勢法求檢驗數就是對偶問題的表上作業法。
基可行解改進——閉迴路調整法
若有兩個或兩個以上的檢驗數為負時,一般選擇其中最小的負檢驗數,以它對應的空格為調入格。即以它對應的非基變數為換入變數。
產銷平衡的運輸問題必定存在最優解。至於有唯一最優解還是無窮多個最優解,主要看非基變數(即空格處)的檢驗數是否有為0的。若有,則存在無窮多個最優解;否則,只有唯一最優解。

舉例

例1.有四項工作指派給甲、乙兩人完成,每人完成兩項工作。兩人完成各項工作的時間(小時)見表1,怎樣安排工作使總時間最少。
表1
A
B
C
D
15
20
9
10
12
16
10
12
解:設
(i=1,2;j=1,2,3,4)為第i人完成第j項工作的狀態。其中
=0時,表示安排第i人完成第j項工作;
=1時,表示不安排第i人完成第j項工作。
數學模型如下:
0或1(i=1,2;j=1,2,3,4)。
利用運輸論法,把該任務分配問題轉化為運輸問題,寫出其平衡運輸表如表2。
表2
A
B
C
D
產量
15
20
9
10
2
12
16
10
12
2
1
1
1
1
用運輸單純形法求解得到最優表,如表3。
表3
A
B
C
D
產量
0
0
1
1
2
1
1
0
0
2
1
1
1
1
最優的工作分配是:甲完成工作C和D,乙完成工作A和B,總時間Z=47(小時)。

相關詞條

熱門詞條

聯絡我們