運輸問題的多重最優(yōu)解

運輸問題的多重最優(yōu)解簡介：運輸問題存在于各行各業(yè)中，水利水電工程建設(shè)也不例外。作為線性規(guī)劃問題的一個特例，運輸問題的求解無論是在理論上還是在計算技術(shù)上，都已經(jīng)相當(dāng)成熟。本文對運輸問題的最優(yōu)解作了較為深入的探究，特別對多重最優(yōu)解的存在定理作了進一步證明和推論，最后給出了計算實例。關(guān)鍵字：運輸問題最優(yōu)解線性規(guī)劃方案1問題的提出運輸問題是線性規(guī)劃的一個特例，可以用求解線性規(guī)劃的一般方法一一單純形法求解。然而運輸問題有它自身的特殊結(jié)構(gòu)系數(shù)矩陣，其獨特的求解方法較單純形法更為簡單實用，這就是表上作業(yè)法。目前以表上作業(yè)法編制的計算機程序已廣泛地得到應(yīng)用，但遺憾的是已見之于公開發(fā)表的文獻書籍(見參考文獻)上的程序卻對運輸問題的多重最優(yōu)解顯得無能為力，甚至不予提及。而在實踐中往往會遇到這樣的問題:所給題目在求出了最佳調(diào)運方案之后還存不存在其它最佳調(diào)運方案(即問題的多重最優(yōu)解)?如果存在，又如何判斷有多少種最佳調(diào)運方案?怎樣很快求得這些最佳調(diào)運方案?另一方面，如果原題目存在多重最優(yōu)解，我們僅在得到了一個最佳調(diào)運方案后就不再予以追究了，那么就有可能漏掉調(diào)運更為合理可行的真正名符其實的最佳調(diào)運方案。因此，當(dāng)原題目多重最優(yōu)解存在時，我們應(yīng)盡可能地多求幾組出來供決策者選擇。同樣地，如果實際情況發(fā)生了變化，原最佳調(diào)運方案在車輛安排，管理運營等方面有困難時，希望對原方案進行調(diào)整，那么有多個最佳調(diào)運方案進行比較，其效果就不言而喻了。以上問題本文作了一些探討，認為得到了滿意的回答。2運輸問題多重最優(yōu)解的存在定理我們知道用表上作業(yè)法求解運輸問題時，在初始調(diào)運方案得到后需進行最優(yōu)性檢驗，通常采用位勢法求各非基變量的檢驗數(shù)。當(dāng)所有非基變量的檢驗數(shù)均大于等于零時，所得到的調(diào)運方案就是該題目的最佳調(diào)運方案。如果這些檢驗數(shù)中出現(xiàn)零，則該方案就可能不是唯一的最佳調(diào)運方案。這是因為以檢驗數(shù)為零的空格作為閉回路的起點，以基變量為轉(zhuǎn)角點畫出閉回路重新迸行迭代調(diào)整，其結(jié)果將得到另一新方案，并且這樣的迭代不會使目標(biāo)函數(shù)值發(fā)生變化，那么這個與原最佳調(diào)運方案具有相同目標(biāo)函數(shù)的新方案也是最佳調(diào)運方案。同理，如果原題目存在多個非基變量檢驗數(shù)為零的空格，分別以各空格為進入變量，重復(fù)以上迭代過程，即可得到多個最佳調(diào)運方案。此外，以檢驗數(shù)為零的空格作為進入變量，其調(diào)入的具體數(shù)量也可以是不同的，只要滿足約束條件即可，換句話說，進人變量的數(shù)量不是唯一的，可在該量所涉及的范圍之內(nèi)變化，從而可得到更多的最佳調(diào)運方案。以上分析可歸結(jié)為如下定理:定理1給定的運輸問題，其最佳調(diào)運方案非唯一性的條件是:1)在已獲得的最佳調(diào)運方案中存在有非基變量檢驗數(shù)為零的空格；2）以此檢驗數(shù)為零的空格為一頂點的閉回路上需要減少運輸量的頂點的不能為零。定理l的存在是顯而易見的，證明從略。定理2設(shè)存在有個檢驗數(shù)為零的空格滿足定理1，那么該運輸問題至少存在個最佳調(diào)運方案。式中為最佳調(diào)運方案的最少個數(shù)，(1，2，…,)為在個空格中任取個空格作為進入變量的組合數(shù)。證明當(dāng)所給運輸問題已經(jīng)獲得了最佳調(diào)運方案，其調(diào)運表中存在有個滿足定理1的零檢驗空格，在此個空格中任取1個作為進入變量進行迭代，可得到一個新的最佳調(diào)運方案，其取法有種，即新的最佳調(diào)運方案有個。又分別在個空格中任取2個作為進人變量進行迭代，可得到個最佳調(diào)運方案。以此類推，可得到個新的最佳調(diào)運方案，加上最先得到的一個方案，則總調(diào)運方案的個數(shù)到此為止有：個。

證畢需要說明的是定理2所給出的個方案中，并不存在同解方案。這是因為在以上證明推導(dǎo)中采用的是組合數(shù)相加法，每一種組合都是獨立存在的。換言之，凡嚴格滿足定理1條件的運輸問題，這個方案就不存在相同方案。推論當(dāng)以零檢驗數(shù)空格作為進入變量進行迭代以尋求其它最佳調(diào)運方案時，設(shè)退出變量的數(shù)值為A，如果在區(qū)間(0，A)中任意選擇退出變量的具體數(shù)量，則最佳調(diào)運方案的個數(shù)將急劇增加，遠遠超過定理2中給出的最少個數(shù)。推論是不難證明的。我們知道，在以檢驗數(shù)為零的空格作為進入變量進行迭代時，其進入變量的數(shù)量就是退出變量的全部數(shù)量，迭代后退出變量即在調(diào)運方案表中完全消失。如果我們?nèi)匀槐Ａ敉顺鲎兞康囊徊糠謹?shù)量，即退出變量以部分退出的形式進行，進人變且的數(shù)量與退出變量退出那部分數(shù)量相同，以此進行迭代，這同樣對目標(biāo)函數(shù)值毫無影響。如此得到的新的最佳調(diào)運方案將不在定理2所給出的方案個數(shù)之內(nèi)。還需要說明的是，作這種調(diào)整是在按定理2求得的任何一個最佳調(diào)運方案的基礎(chǔ)上進行的，并不需要在此基礎(chǔ)上繼續(xù)進行“表上作業(yè)”，因而違背了非零變量的個數(shù)不大于獨立約束方程組的個數(shù)和基變量所對應(yīng)的約束方程組的系數(shù)列向量線性無關(guān)[5]這兩個對表上作業(yè)法的原則要求。這是完全許可的。3求多重最優(yōu)解程序(1)在現(xiàn)有的運輸問題求解程序中根據(jù)定理1和定理2的原理增加設(shè)置多重最優(yōu)解的判斷程序段，以數(shù)組形式記存零檢驗數(shù)在最佳調(diào)運方案表中的位置，為下一步直接在已獲得的最優(yōu)解的基礎(chǔ)上進行迭代以尋求其它最優(yōu)解作淮備。(2)在得到最佳調(diào)運方案后，如果存在其它最優(yōu)解的可能，則輸出整個最佳調(diào)運方案表以及非基變量檢驗數(shù)表格，以便計算者直觀分析判斷多重最優(yōu)解的分布情況及其可調(diào)性。(3)可直接在以上輸出表格上進行特殊的表上作業(yè)，運算簡單易行，可用手算，僅在以零檢驗數(shù)為頂點的閉回路的轉(zhuǎn)角點上作相應(yīng)的加減法即可得到新的調(diào)運方案，并不需要再計算各非基變量的檢驗數(shù)就知道該方案一定是最佳調(diào)運方案。(4)第3步也可編制成計算機程序，可采用人機對話形式，輸入任意一個零檢驗數(shù)空格的行、列數(shù)，即可求得該空格作為進人變量迭代后的新方案。也可以把程序設(shè)計成按所有零檢驗數(shù)空格的不同組合方式進行迭代，并輸出全部最佳調(diào)運方案，方案個數(shù)為定理2中的。(5)在獲得了以上多重最優(yōu)解之后，若計算分析者或決策者還希望進一步調(diào)整，可以某一最佳調(diào)運方案為基準(zhǔn)，結(jié)合最佳調(diào)運方案檢驗數(shù)表，按推論中的原則進行。4計算實例今以文獻[1]P.111中的數(shù)據(jù)表(本文表1)為例演算于下(此例為3個煤炭產(chǎn)地的產(chǎn)量和13個銷地的需求量的運輸問題)。(1)按程序設(shè)計要求的數(shù)據(jù)資料輸入格式和順序輸入表1。(2)輸入產(chǎn)地個數(shù)M(單價矩陣的行數(shù))=3，需求地個數(shù)N(單價短陣的列數(shù))=13。(3)運算。輸出最佳調(diào)運方案(表2中的方案1)，同時顯示存在多重最優(yōu)解，輸出該題目最佳調(diào)運表中零檢驗數(shù)空格所在的位置。此例有5個零檢驗數(shù)空格(表2方案1中的(0))。(4)從表2方案1看出，這5個檢驗數(shù)為零的空格均滿足定理1的條件。以(2，7)空格為頂點的閉回路是(2，7)→(2，8)→(3，8)→(3，7)→(2，7)。其它各零檢驗數(shù)空格為起點的閉回路均有兩個頂點是(1，2)、(2，2)，另兩個頂點分別為各空格所在列的第一行和該零檢驗數(shù)空格本身。(5)求解其它最佳調(diào)運方案。分別以表2方案1第2行的3、4、5、6空格進行任意組合作為進人變量，即可得到表2中的方案2一16，其方案個數(shù)滿足在4個事件中任取1～4個事件的組合數(shù)15，與方案l相加共為16個方案(即表2中方案1～16)。今再以(2，7)空格作為進入變量分別與前16個方案相組合(例如與方案1組給得到方案17)即可得到32個方案，滿足定理2所給的最少方案個數(shù)=1+5+10+10+5+1=32。(6)按推論原則，以方案4為基礎(chǔ)，僅僅使退出變量x(1，5)不全退出，例如退出一半，則得方案18。以此類推可得到若干個新方案。而在前述的32個基本方案中除了方案1之外，每一個方案都可作這樣的謂整，詞整后的方案又可進行不同形式的組合。所有這些調(diào)運方案都具有相同的目標(biāo)函數(shù)，都屬于最優(yōu)解之列，其方案個數(shù)將多達成千上萬，以致于筆者目前尚還不能對這些方案個數(shù)作出準(zhǔn)確計算。有興趣者可自行演算驗證之。5結(jié)語實踐證明，有相當(dāng)一部分運輸問題存在多重最佳調(diào)運方案。這些方案的存在判別與求解，依本文所述是很簡單且易于掌握運用的。無論是分析者還浪決策者，細讀本文，必有所悟。（本文原載：《系統(tǒng)工程理論與實踐》1991年第3期，中國系統(tǒng)工程學(xué)會會刊）參考文獻[1]朱廷昌、胡喜忠著:《企業(yè)管理常用方法的程序設(shè)計》，電子工業(yè)出版社，1987年9月。[2]孫鐘秀主綿:《計算機與計劃管理》，南京大學(xué)出版社，1987年8月。[3]萬耀青等編:《最優(yōu)化計算法常用程序匯編》，工人出版