版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
運(yùn)輸問(wèn)題的多重最優(yōu)解簡(jiǎn)介:運(yùn)輸問(wèn)題存在于各行各業(yè)中,水利水電工程建設(shè)也不例外。作為線性規(guī)劃問(wèn)題的一個(gè)特例,運(yùn)輸問(wèn)題的求解無(wú)論是在理論上還是在計(jì)算技術(shù)上,都已經(jīng)相當(dāng)成熟。本文對(duì)運(yùn)輸問(wèn)題的最優(yōu)解作了較為深入的探究,特別對(duì)多重最優(yōu)解的存在定理作了進(jìn)一步證明和推論,最后給出了計(jì)算實(shí)例。關(guān)鍵字:運(yùn)輸問(wèn)題最優(yōu)解線性規(guī)劃方案1問(wèn)題的提出運(yùn)輸問(wèn)題是線性規(guī)劃的一個(gè)特例,可以用求解線性規(guī)劃的一般方法一一單純形法求解。然而運(yùn)輸問(wèn)題有它自身的特殊結(jié)構(gòu)系數(shù)矩陣,其獨(dú)特的求解方法較單純形法更為簡(jiǎn)單實(shí)用,這就是表上作業(yè)法。目前以表上作業(yè)法編制的計(jì)算機(jī)程序已廣泛地得到應(yīng)用,但遺憾的是已見(jiàn)之于公開(kāi)發(fā)表的文獻(xiàn)書(shū)籍(見(jiàn)參考文獻(xiàn))上的程序卻對(duì)運(yùn)輸問(wèn)題的多重最優(yōu)解顯得無(wú)能為力,甚至不予提及。而在實(shí)踐中往往會(huì)遇到這樣的問(wèn)題:所給題目在求出了最佳調(diào)運(yùn)方案之后還存不存在其它最佳調(diào)運(yùn)方案(即問(wèn)題的多重最優(yōu)解)?如果存在,又如何判斷有多少種最佳調(diào)運(yùn)方案?怎樣很快求得這些最佳調(diào)運(yùn)方案?另一方面,如果原題目存在多重最優(yōu)解,我們僅在得到了一個(gè)最佳調(diào)運(yùn)方案后就不再予以追究了,那么就有可能漏掉調(diào)運(yùn)更為合理可行的真正名符其實(shí)的最佳調(diào)運(yùn)方案。因此,當(dāng)原題目多重最優(yōu)解存在時(shí),我們應(yīng)盡可能地多求幾組出來(lái)供決策者選擇。同樣地,如果實(shí)際情況發(fā)生了變化,原最佳調(diào)運(yùn)方案在車輛安排,管理運(yùn)營(yíng)等方面有困難時(shí),希望對(duì)原方案進(jìn)行調(diào)整,那么有多個(gè)最佳調(diào)運(yùn)方案進(jìn)行比較,其效果就不言而喻了。以上問(wèn)題本文作了一些探討,認(rèn)為得到了滿意的回答。2運(yùn)輸問(wèn)題多重最優(yōu)解的存在定理我們知道用表上作業(yè)法求解運(yùn)輸問(wèn)題時(shí),在初始調(diào)運(yùn)方案得到后需進(jìn)行最優(yōu)性檢驗(yàn),通常采用位勢(shì)法求各非基變量的檢驗(yàn)數(shù)。當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于等于零時(shí),所得到的調(diào)運(yùn)方案就是該題目的最佳調(diào)運(yùn)方案。如果這些檢驗(yàn)數(shù)中出現(xiàn)零,則該方案就可能不是唯一的最佳調(diào)運(yùn)方案。這是因?yàn)橐詸z驗(yàn)數(shù)為零的空格作為閉回路的起點(diǎn),以基變量為轉(zhuǎn)角點(diǎn)畫(huà)出閉回路重新迸行迭代調(diào)整,其結(jié)果將得到另一新方案,并且這樣的迭代不會(huì)使目標(biāo)函數(shù)值發(fā)生變化,那么這個(gè)與原最佳調(diào)運(yùn)方案具有相同目標(biāo)函數(shù)的新方案也是最佳調(diào)運(yùn)方案。同理,如果原題目存在多個(gè)非基變量檢驗(yàn)數(shù)為零的空格,分別以各空格為進(jìn)入變量,重復(fù)以上迭代過(guò)程,即可得到多個(gè)最佳調(diào)運(yùn)方案。此外,以檢驗(yàn)數(shù)為零的空格作為進(jìn)入變量,其調(diào)入的具體數(shù)量也可以是不同的,只要滿足約束條件即可,換句話說(shuō),進(jìn)人變量的數(shù)量不是唯一的,可在該量所涉及的范圍之內(nèi)變化,從而可得到更多的最佳調(diào)運(yùn)方案。以上分析可歸結(jié)為如下定理:定理1給定的運(yùn)輸問(wèn)題,其最佳調(diào)運(yùn)方案非唯一性的條件是:1)在已獲得的最佳調(diào)運(yùn)方案中存在有非基變量檢驗(yàn)數(shù)為零的空格;2)以此檢驗(yàn)數(shù)為零的空格為一頂點(diǎn)的閉回路上需要減少運(yùn)輸量的頂點(diǎn)的不能為零。定理l的存在是顯而易見(jiàn)的,證明從略。定理2設(shè)存在有個(gè)檢驗(yàn)數(shù)為零的空格滿足定理1,那么該運(yùn)輸問(wèn)題至少存在個(gè)最佳調(diào)運(yùn)方案。式中為最佳調(diào)運(yùn)方案的最少個(gè)數(shù),(1,2,…,)為在個(gè)空格中任取個(gè)空格作為進(jìn)入變量的組合數(shù)。證明當(dāng)所給運(yùn)輸問(wèn)題已經(jīng)獲得了最佳調(diào)運(yùn)方案,其調(diào)運(yùn)表中存在有個(gè)滿足定理1的零檢驗(yàn)空格,在此個(gè)空格中任取1個(gè)作為進(jìn)入變量進(jìn)行迭代,可得到一個(gè)新的最佳調(diào)運(yùn)方案,其取法有種,即新的最佳調(diào)運(yùn)方案有個(gè)。又分別在個(gè)空格中任取2個(gè)作為進(jìn)人變量進(jìn)行迭代,可得到個(gè)最佳調(diào)運(yùn)方案。以此類推,可得到個(gè)新的最佳調(diào)運(yùn)方案,加上最先得到的一個(gè)方案,則總調(diào)運(yùn)方案的個(gè)數(shù)到此為止有:個(gè)。
證畢需要說(shuō)明的是定理2所給出的個(gè)方案中,并不存在同解方案。這是因?yàn)樵谝陨献C明推導(dǎo)中采用的是組合數(shù)相加法,每一種組合都是獨(dú)立存在的。換言之,凡嚴(yán)格滿足定理1條件的運(yùn)輸問(wèn)題,這個(gè)方案就不存在相同方案。推論當(dāng)以零檢驗(yàn)數(shù)空格作為進(jìn)入變量進(jìn)行迭代以尋求其它最佳調(diào)運(yùn)方案時(shí),設(shè)退出變量的數(shù)值為A,如果在區(qū)間(0,A)中任意選擇退出變量的具體數(shù)量,則最佳調(diào)運(yùn)方案的個(gè)數(shù)將急劇增加,遠(yuǎn)遠(yuǎn)超過(guò)定理2中給出的最少個(gè)數(shù)。推論是不難證明的。我們知道,在以檢驗(yàn)數(shù)為零的空格作為進(jìn)入變量進(jìn)行迭代時(shí),其進(jìn)入變量的數(shù)量就是退出變量的全部數(shù)量,迭代后退出變量即在調(diào)運(yùn)方案表中完全消失。如果我們?nèi)匀槐A敉顺鲎兞康囊徊糠謹(jǐn)?shù)量,即退出變量以部分退出的形式進(jìn)行,進(jìn)人變且的數(shù)量與退出變量退出那部分?jǐn)?shù)量相同,以此進(jìn)行迭代,這同樣對(duì)目標(biāo)函數(shù)值毫無(wú)影響。如此得到的新的最佳調(diào)運(yùn)方案將不在定理2所給出的方案?jìng)€(gè)數(shù)之內(nèi)。還需要說(shuō)明的是,作這種調(diào)整是在按定理2求得的任何一個(gè)最佳調(diào)運(yùn)方案的基礎(chǔ)上進(jìn)行的,并不需要在此基礎(chǔ)上繼續(xù)進(jìn)行“表上作業(yè)”,因而違背了非零變量的個(gè)數(shù)不大于獨(dú)立約束方程組的個(gè)數(shù)和基變量所對(duì)應(yīng)的約束方程組的系數(shù)列向量線性無(wú)關(guān)[5]這兩個(gè)對(duì)表上作業(yè)法的原則要求。這是完全許可的。3求多重最優(yōu)解程序(1)在現(xiàn)有的運(yùn)輸問(wèn)題求解程序中根據(jù)定理1和定理2的原理增加設(shè)置多重最優(yōu)解的判斷程序段,以數(shù)組形式記存零檢驗(yàn)數(shù)在最佳調(diào)運(yùn)方案表中的位置,為下一步直接在已獲得的最優(yōu)解的基礎(chǔ)上進(jìn)行迭代以尋求其它最優(yōu)解作淮備。(2)在得到最佳調(diào)運(yùn)方案后,如果存在其它最優(yōu)解的可能,則輸出整個(gè)最佳調(diào)運(yùn)方案表以及非基變量檢驗(yàn)數(shù)表格,以便計(jì)算者直觀分析判斷多重最優(yōu)解的分布情況及其可調(diào)性。(3)可直接在以上輸出表格上進(jìn)行特殊的表上作業(yè),運(yùn)算簡(jiǎn)單易行,可用手算,僅在以零檢驗(yàn)數(shù)為頂點(diǎn)的閉回路的轉(zhuǎn)角點(diǎn)上作相應(yīng)的加減法即可得到新的調(diào)運(yùn)方案,并不需要再計(jì)算各非基變量的檢驗(yàn)數(shù)就知道該方案一定是最佳調(diào)運(yùn)方案。(4)第3步也可編制成計(jì)算機(jī)程序,可采用人機(jī)對(duì)話形式,輸入任意一個(gè)零檢驗(yàn)數(shù)空格的行、列數(shù),即可求得該空格作為進(jìn)人變量迭代后的新方案。也可以把程序設(shè)計(jì)成按所有零檢驗(yàn)數(shù)空格的不同組合方式進(jìn)行迭代,并輸出全部最佳調(diào)運(yùn)方案,方案?jìng)€(gè)數(shù)為定理2中的。(5)在獲得了以上多重最優(yōu)解之后,若計(jì)算分析者或決策者還希望進(jìn)一步調(diào)整,可以某一最佳調(diào)運(yùn)方案為基準(zhǔn),結(jié)合最佳調(diào)運(yùn)方案檢驗(yàn)數(shù)表,按推論中的原則進(jìn)行。4計(jì)算實(shí)例今以文獻(xiàn)[1]P.111中的數(shù)據(jù)表(本文表1)為例演算于下(此例為3個(gè)煤炭產(chǎn)地的產(chǎn)量和13個(gè)銷地的需求量的運(yùn)輸問(wèn)題)。(1)按程序設(shè)計(jì)要求的數(shù)據(jù)資料輸入格式和順序輸入表1。(2)輸入產(chǎn)地個(gè)數(shù)M(單價(jià)矩陣的行數(shù))=3,需求地個(gè)數(shù)N(單價(jià)短陣的列數(shù))=13。(3)運(yùn)算。輸出最佳調(diào)運(yùn)方案(表2中的方案1),同時(shí)顯示存在多重最優(yōu)解,輸出該題目最佳調(diào)運(yùn)表中零檢驗(yàn)數(shù)空格所在的位置。此例有5個(gè)零檢驗(yàn)數(shù)空格(表2方案1中的(0))。(4)從表2方案1看出,這5個(gè)檢驗(yàn)數(shù)為零的空格均滿足定理1的條件。以(2,7)空格為頂點(diǎn)的閉回路是(2,7)→(2,8)→(3,8)→(3,7)→(2,7)。其它各零檢驗(yàn)數(shù)空格為起點(diǎn)的閉回路均有兩個(gè)頂點(diǎn)是(1,2)、(2,2),另兩個(gè)頂點(diǎn)分別為各空格所在列的第一行和該零檢驗(yàn)數(shù)空格本身。(5)求解其它最佳調(diào)運(yùn)方案。分別以表2方案1第2行的3、4、5、6空格進(jìn)行任意組合作為進(jìn)人變量,即可得到表2中的方案2一16,其方案?jìng)€(gè)數(shù)滿足在4個(gè)事件中任取1~4個(gè)事件的組合數(shù)15,與方案l相加共為16個(gè)方案(即表2中方案1~16)。今再以(2,7)空格作為進(jìn)入變量分別與前16個(gè)方案相組合(例如與方案1組給得到方案17)即可得到32個(gè)方案,滿足定理2所給的最少方案?jìng)€(gè)數(shù)=1+5+10+10+5+1=32。(6)按推論原則,以方案4為基礎(chǔ),僅僅使退出變量x(1,5)不全退出,例如退出一半,則得方案18。以此類推可得到若干個(gè)新方案。而在前述的32個(gè)基本方案中除了方案1之外,每一個(gè)方案都可作這樣的謂整,詞整后的方案又可進(jìn)行不同形式的組合。所有這些調(diào)運(yùn)方案都具有相同的目標(biāo)函數(shù),都屬于最優(yōu)解之列,其方案?jìng)€(gè)數(shù)將多達(dá)成千上萬(wàn),以致于筆者目前尚還不能對(duì)這些方案?jìng)€(gè)數(shù)作出準(zhǔn)確計(jì)算。有興趣者可自行演算驗(yàn)證之。5結(jié)語(yǔ)實(shí)踐證明,有相當(dāng)一部分運(yùn)輸問(wèn)題存在多重最佳調(diào)運(yùn)方案。這些方案的存在判別與求解,依本文所述是很簡(jiǎn)單且易于掌握運(yùn)用的。無(wú)論是分析者還浪決策者,細(xì)讀本文,必有所悟。(本文原載:《系統(tǒng)工程理論與實(shí)踐》1991年第3期,中國(guó)系統(tǒng)工程學(xué)會(huì)會(huì)刊)參考文獻(xiàn)[1]朱廷昌、胡喜忠著:《企業(yè)管理常用方法的程序設(shè)計(jì)》,電子工業(yè)出版社,1987年9月。[2]孫鐘秀主綿:《計(jì)算機(jī)與計(jì)劃管理》,南京大學(xué)出版社,1987年8月。[3]萬(wàn)耀青等編:《最優(yōu)化計(jì)算法常用程序匯編》,工人出版
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年貨物運(yùn)輸合同規(guī)定運(yùn)輸方式與責(zé)任
- 2025年度歷史建筑保護(hù)拆墻工程合作協(xié)議4篇
- 2024豬場(chǎng)租賃承包合同
- 2024節(jié)能減排協(xié)議書(shū)
- 《中樞性高熱患者的護(hù)理與治療》課件
- 2025年度新媒體運(yùn)營(yíng)與公關(guān)合作服務(wù)合同范本4篇
- 2024年05月云南廣發(fā)銀行昆明分行招考筆試歷年參考題庫(kù)附帶答案詳解
- 2025年度大數(shù)據(jù)分析服務(wù)合同樣本8篇
- 2025變頻器代理商銷售合同:市場(chǎng)拓展與品牌推廣合作3篇
- 二零二五年度高端酒店集團(tuán)食材供應(yīng)與服務(wù)合同3篇
- 常見(jiàn)老年慢性病防治與護(hù)理課件整理
- 履約情況證明(共6篇)
- 云南省迪慶藏族自治州各縣區(qū)鄉(xiāng)鎮(zhèn)行政村村莊村名居民村民委員會(huì)明細(xì)
- 設(shè)備機(jī)房出入登記表
- 六年級(jí)語(yǔ)文-文言文閱讀訓(xùn)練題50篇-含答案
- 醫(yī)用冰箱溫度登記表
- 零售學(xué)(第二版)第01章零售導(dǎo)論
- 大學(xué)植物生理學(xué)經(jīng)典05植物光合作用
- 口袋妖怪白金光圖文攻略2周目
- 光伏發(fā)電站集中監(jiān)控系統(tǒng)通信及數(shù)據(jù)標(biāo)準(zhǔn)
- 三年級(jí)下冊(cè)生字組詞(帶拼音)
評(píng)論
0/150
提交評(píng)論