運(yùn)輸問(wèn)題用檢驗(yàn)數(shù)判別最優(yōu)解的注記

毛圓潔

(無(wú)錫科技職業(yè)學(xué)院文化創(chuàng)意學(xué)院,江蘇無(wú)錫 214028)

運(yùn)輸問(wèn)題用檢驗(yàn)數(shù)判別最優(yōu)解的注記

毛圓潔

(無(wú)錫科技職業(yè)學(xué)院文化創(chuàng)意學(xué)院,江蘇無(wú)錫 214028)

求解運(yùn)輸問(wèn)題的表上作業(yè)法中一般用檢驗(yàn)數(shù)判別可行解是否為最優(yōu)解,但此方法并不適用于判別非基本最優(yōu)解和部分基本最優(yōu)解.

運(yùn)輸問(wèn)題;基本最優(yōu)解;基本可行解;檢驗(yàn)數(shù)

運(yùn)輸問(wèn)題是在實(shí)際應(yīng)用中常見(jiàn)的一類(lèi)線性規(guī)劃問(wèn)題,通?？梢杂帽砩献鳂I(yè)法來(lái)求解運(yùn)輸問(wèn)題的最優(yōu)解.求解過(guò)程中,在求得運(yùn)輸問(wèn)題的可行解后,通常利用閉回路法或位勢(shì)法來(lái)計(jì)算非基變量的檢驗(yàn)數(shù),以判別可行解是否為最優(yōu)解.

運(yùn)輸問(wèn)題可以用以下數(shù)學(xué)模型描述

有關(guān)于運(yùn)輸問(wèn)題如何用檢驗(yàn)數(shù)判別最優(yōu)解的如下定理.

定理 1若模型 TP的一個(gè)可行解滿足:對(duì)每一非基變量xij(無(wú)運(yùn)量格),都有檢驗(yàn)數(shù)λij=cij-(ui+vj)≥0,則該可行解為最優(yōu)解.

定理證明參見(jiàn)文獻(xiàn)[1],其中ui和vj分別為行、列位勢(shì).由定理 1可知,在運(yùn)輸問(wèn)題中,如果通過(guò)計(jì)算得非基變量的檢驗(yàn)數(shù)均非負(fù),則已求得最優(yōu)解.那么,用檢驗(yàn)數(shù)來(lái)判別運(yùn)輸問(wèn)題的可行解是否為最優(yōu)解的方法一定萬(wàn)無(wú)一失嗎?

1 檢驗(yàn)數(shù)不能判別非基本最優(yōu)解

圖 1 例1運(yùn)輸問(wèn)題的一個(gè)可行解

在運(yùn)輸問(wèn)題中,若某個(gè)基本可行解為最優(yōu)解,則稱(chēng)之為基本最優(yōu)解,其余的最優(yōu)解被稱(chēng)為非基本最優(yōu)解[2].

例 1判斷圖 1中給出的可行解是否為此運(yùn)輸問(wèn)題的最優(yōu)解.

此時(shí),求以上運(yùn)輸問(wèn)題非基變量的檢驗(yàn)數(shù)出現(xiàn)了困難,無(wú)論是閉回路法或位勢(shì)法都無(wú)法求出所有非基變量的檢驗(yàn)數(shù),因?yàn)楸砀裰写嬖诜腔兞空也坏介]回路,或是行列位勢(shì)無(wú)法全部求出,其他求檢驗(yàn)數(shù)的方法亦然.然而,用表上作業(yè)法容易求得此運(yùn)輸問(wèn)題的最少運(yùn)費(fèi)為 45,表 1中給出的可行解的總運(yùn)費(fèi)也為 45,說(shuō)明表 1中給出的可行解確為此運(yùn)輸問(wèn)題的最優(yōu)解,而造成無(wú)法用檢驗(yàn)數(shù)判別其是否為最優(yōu)解的原因是此可行解為非基本最優(yōu)解[3].

在運(yùn)輸問(wèn)題中,m+n-1個(gè)變量構(gòu)成基本可行解的基變量的充分必要條件是它們不包含閉回路.而在此例中,(A2,B2)、(A2,B3)、(A3,B2)和(A3,B3)4個(gè)變量構(gòu)成一個(gè)閉回路,所以此可行解并非基本可行解,因而也不是基本最優(yōu)解.

既然檢驗(yàn)數(shù)不能用來(lái)判別非基本最優(yōu)解,那么,是否所有的基本最優(yōu)解都能用檢驗(yàn)數(shù)來(lái)判別?

2 檢驗(yàn)數(shù)不能判別所有的基本最優(yōu)解

例 2求表 1所示的運(yùn)輸問(wèn)題的最優(yōu)解.

用伏格爾法求此運(yùn)輸問(wèn)題的初始可行解,得到一個(gè)退化的基本可行解,為了使基變量個(gè)數(shù)為m+n-1個(gè),添加一個(gè)“0”元,考慮到基本可行解的基變量之間不能形成閉回路,可以將“0”元添加在(A1,B1)處,如圖 2[4].

表1 產(chǎn)銷(xiāo)平衡運(yùn)輸表

圖2 例2運(yùn)輸問(wèn)題的一個(gè)可行解

圖3 例2運(yùn)輸問(wèn)題的另一可行解

此時(shí),通過(guò)計(jì)算非基變量的檢驗(yàn)數(shù),可以得到非基變量(A1,B4)處的檢驗(yàn)數(shù)為σ14=-1,由定理 1,圖 2中的基本可行解并非最優(yōu)解.考慮用閉回路法對(duì)此基本可行解進(jìn)行改進(jìn),在圖 2中找到(A1,B4)的閉回路,調(diào)整量θ取閉回路偶數(shù)頂點(diǎn)上調(diào)運(yùn)量的最小值,即θ=min[0,4]=0,于是基變量為(A1,B1)換出基的變量,然后在閉回路奇數(shù)頂點(diǎn)運(yùn)輸量的值均加上調(diào)整量θ=0,非基變量(A1,B4)為換入基的變量,于是得改進(jìn)后的基本可行解,見(jiàn)圖 3.

計(jì)算圖 3中各非基變量的檢驗(yàn)數(shù),分別為σ11=1,σ13=1,σ22=5,σ23=4,σ31=3,σ32=6,所有非基變量的檢驗(yàn)數(shù)均非負(fù),由定理 1,可知圖 3中的基本可行解即為此運(yùn)輸問(wèn)題的最優(yōu)解,也是基本最優(yōu)解[5].

觀察比較圖 2和圖 3中的兩個(gè)基本可行解,除 0基元的位置不同外,兩個(gè)可行解無(wú)其他區(qū)別,總運(yùn)費(fèi)的取值也應(yīng)該一致.若圖 3中的基本可行解是基本最優(yōu)解,那么圖 2中的基本可行解也應(yīng)為基本最優(yōu)解.而檢驗(yàn)數(shù)判別卻給出了不同的結(jié)論,可見(jiàn)檢驗(yàn)數(shù)不適用于所有的基本最優(yōu)解的判別.

3 結(jié)論

在運(yùn)輸問(wèn)題中,用檢驗(yàn)數(shù)來(lái)判別最優(yōu)解并非萬(wàn)無(wú)一失,面對(duì)非基本最優(yōu)解,檢驗(yàn)數(shù)判別可能束手無(wú)策,而檢驗(yàn)數(shù)均非負(fù)也僅是判別基本最優(yōu)解的充分而非必要條件,此均為定理 1中未提及的部分.由于運(yùn)輸問(wèn)題是一類(lèi)特殊的線性規(guī)劃問(wèn)題,以上結(jié)論亦可在線性規(guī)劃中進(jìn)行推廣.

[1] 俞玉森.數(shù)學(xué)規(guī)劃的原理和方法[M].武漢:華中理工大學(xué)出版社,1985.

[2] 黃桐城.運(yùn)籌學(xué)基礎(chǔ)教程[M].上海:上海人民出版社,2007.

[3] 胡運(yùn)權(quán).運(yùn)籌學(xué)教程[M].北京:清華大學(xué)出版社,1998.

[4] 唐文廣,吳振奎,王全文,等.運(yùn)輸問(wèn)題的退化解及表解中 0元的添加[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2009(1):160-165.

[5] 吳振奎,王全文,劉振航.線性規(guī)劃問(wèn)題通解表示的注記[J].運(yùn)籌與管理,2004,13(1):63-67.

A Note on Using Test Number D istinguishing Opt imal Solution in Transportation Problems

MAO Yuan-jie

(College of Culture and Creativity,W uxi Professional College of Science and Technology,W uxi214028,China)

In the table-working method of transportation problems,test number is generally used to distinguish whether the feasible solution is the optimal solution,but thismethod isn’t suitable for distinguishing non-basic optimal solution and partial basic optimal solution.

transportation problems;basic optimal solution;basic feasible solution;test number

O221.1

A

1007-0834(2010)04-0009-02

10.3969/j.issn.1007-0834.2010.04.004

2010-09-06

毛圓潔(1983—),女,江蘇無(wú)錫人,無(wú)錫科技職業(yè)學(xué)院文化創(chuàng)意學(xué)院教師.