中圖分類號(hào):F502 文獻(xiàn)標(biāo)識(shí):A 文章編號(hào):1009-4202(2010)10-286-02

摘 要 運(yùn)輸問題是運(yùn)籌學(xué)的經(jīng)典問題,而表上作業(yè)法是運(yùn)輸問題中的重要算法,具有廣泛的應(yīng)用.本文對(duì)運(yùn)輸問題表上作業(yè)法進(jìn)行了一些必要的探討,利用閉回路的唯一性,給出了一種新的閉回路構(gòu)建方法,簡化了求解運(yùn)輸問題最優(yōu)解的過程。

關(guān)鍵詞 運(yùn)輸問題 運(yùn)籌學(xué) 表上作業(yè)法 閉回路

一、引言

運(yùn)輸問題的數(shù)學(xué)模型為:

設(shè)某產(chǎn)品有 個(gè)產(chǎn)地 和 個(gè)銷地 .在產(chǎn)地 的產(chǎn)量為 ,在銷地 的銷量為 ,從 到 運(yùn)送一個(gè)單位貨物的運(yùn)費(fèi)為 .假設(shè)產(chǎn)銷平衡,即 ,試確定一個(gè)調(diào)運(yùn)方案,使總運(yùn)費(fèi)最小。

假設(shè)產(chǎn)地 供給銷地 的貨物量為 ,上述問題可用以下數(shù)學(xué)模型表示:

的前 行對(duì)應(yīng) 個(gè)產(chǎn)地,后 行對(duì)應(yīng) 個(gè)銷地。 的增廣矩陣記作 。由于產(chǎn)銷不平衡運(yùn)輸問題均可轉(zhuǎn)化為產(chǎn)銷平衡運(yùn)輸問題,因此本文僅研究產(chǎn)銷平衡運(yùn)輸問題。

二、運(yùn)輸問題的基本性質(zhì)

定理1:銷平衡的運(yùn)輸問題必存在有限最優(yōu)解。

定理2:運(yùn)輸問題的系數(shù)矩陣 和增廣矩陣 的秩均為 。

定理3:運(yùn)輸問題中, 的任何方子矩陣的行列式為-1,0或1。

三、表上作業(yè)法求解運(yùn)輸問題

運(yùn)輸問題是線性規(guī)劃問題的特殊情形,其約束條件具有特殊結(jié)構(gòu),除了可用一般的單純形方法求解外,還可用簡單有效的表上作業(yè)法求解.表上作業(yè)法就是一種求解運(yùn)輸問題的有效的迭代法.按照迭代法的基本思想,表上作業(yè)法的步驟可歸納如下:

(1)確定初始基本可行解,得到 個(gè)基變量。

求解初始基本可行解的方法很多,最常見的是西北角法,最小元素法和差額法。一般情況,差額法確定的基本可行解質(zhì)量最好,最接近最優(yōu)解。

(2)判定是否最優(yōu)。用位勢法判別可行解是否為最優(yōu)解,如果所有判別數(shù)非正,說明得到最優(yōu)解,否則轉(zhuǎn)入(3)。

(3)若是最優(yōu),則問題得解;若不是最優(yōu),則按閉回路法對(duì)運(yùn)輸方案進(jìn)行調(diào)整。

a.從具有最大的判別數(shù)的空格作為閉回路的第一格.

b.第二格的確定。找出基向量,找基向量中與第一格中同在的行(列)的元素,作為第二格。

c.第k格的確定。在基向量中尋找,與第k-1格同在一列(行)的元素,若存在,則選擇其一作為第k格,令k=k+1,轉(zhuǎn)入第d步;否則令k=k-1,轉(zhuǎn)入第d步。

d.找與第k-1格同在一行(列)的元素,判斷是否與第k格在同一列(行),若在同一列(行),則得到閉回路;否則轉(zhuǎn)入第c步。

四、實(shí)例

給定運(yùn)輸問題如表1,其中 為產(chǎn)地, 為產(chǎn)量, 為銷地, 為銷量,每個(gè)方格右上角數(shù)字為費(fèi)用系數(shù) ,試確定一個(gè)運(yùn)輸方案,使總運(yùn)輸費(fèi)用最小。

解:首先用差額法求初始基本可行解,計(jì)算結(jié)果如表2,其基變量為( )=(0,10,1,11,4,5)目標(biāo)函數(shù)值為f=148。

五、總結(jié)

運(yùn)輸問題是運(yùn)籌學(xué)的經(jīng)典問題,而表上作業(yè)法是運(yùn)輸問題中的重要算法,具有廣泛的應(yīng)用.本文主要提出了閉回路構(gòu)建的新算法,改進(jìn)了之前的算法涉及到每個(gè)格,降低了構(gòu)建閉回路的計(jì)算時(shí)間。

參考文獻(xiàn):

[1]陳寶林.最優(yōu)化理論與算法.清華大學(xué)出版社.2005.

[2]錢頌迪.運(yùn)籌學(xué).清華大學(xué)出版社.北京.1990.

[3]韓偉一.運(yùn)輸問題表上作業(yè)法的一點(diǎn)駐記.運(yùn)籌與管理.2009.18(4):7-9.

總結(jié)

以上是生活随笔為你收集整理的C语言表上作业法运输问题,论运输问题表上作业法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。