一類關(guān)于運輸問題的參數(shù)線性規(guī)劃最優(yōu)解的研究

摘要：論文利用文獻[1]中的改進的匈牙利算法，研究關(guān)于運輸問題的參數(shù)線性規(guī)劃的最優(yōu)解，并給出了相應(yīng)的思路，方法步驟及應(yīng)用舉例。

關(guān)鍵詞：改進；匈牙利算法；運輸問題；參數(shù)線性規(guī)劃；最優(yōu)解

中圖分類號：F253.9文獻標(biāo)識碼：A文章編號：1002-3100(2007)12-0033-04

Abstract: This paper is mainly studying of optimal solutions distribution area of one kind of parametric linear programming about transportation problem with developed Hungry algorithm used in reference document[1]， the thought， method， process， and example are also given.

Key words: improved; Hungry algorithm; transportation problem; parametric linear programming; optimal solution

0引言

在實際生活中，運輸問題中的物資供應(yīng)量，物資需求量都可能會發(fā)生波動，研究運輸問題的參數(shù)線性規(guī)劃很有實用意義。而如果用通常求解運輸問題的方法——表上作業(yè)法，首先我們須利用最小元素法或西北角法求出一組基本可行解，再檢驗此解是否最優(yōu)，否則要進行改進。這一過程比較麻煩，編程也過于繁瑣。若再含有參量，則又得重復(fù)此過程，工作量非常大。因此我們采用文獻[1]中的改進的匈牙利算法研究關(guān)于運輸問題的參數(shù)線性規(guī)劃，根據(jù)參量δ在不同區(qū)間改變，可以保留有用的數(shù)據(jù)，則相對就簡便很多了。

1改進的匈牙利算法

引理1設(shè)給定了n×n矩陣C，又設(shè)把C的某一行（或列）的所有元素都減去一個數(shù)d得到矩陣C'，則以C為價格矩陣的分配問題A和以C'為價格矩陣的分配問題A'等價的。

改進的匈牙利算法以最小運輸量為分配目標(biāo)，每次分配都為當(dāng)前已分配的最優(yōu)解。因此，當(dāng)完成所有運輸任務(wù)后，得到的是全局最優(yōu)解。由引理可知，在匈牙利算法中，可以使初始可行解對應(yīng)的目標(biāo)函數(shù)值顯著減小，使之更逼近最優(yōu)解，減少迭代次數(shù)，減少計算量。同時匈牙利算法解決的指派問題具有0-1整形和運輸問題的雙重特點。因此可以很方便地利用改進的匈牙利算法研究含參量時的最優(yōu)解。

2運輸問題的參數(shù)線性規(guī)劃

3算例分析

參考文獻：

[1] 胡運權(quán). 運籌學(xué)教程[M]. 北京：清華大學(xué)出版社，2003.

[2] 管梅谷，鄭漢鼎. 線性規(guī)劃[M]. 山東：山東大學(xué)科技出版社，1983.

[3] 張建中，許紹吉. 線性規(guī)劃[M]. 北京：科學(xué)出版社，1997.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”