關(guān)于運籌學(xué)中幾個問題的新議

劉滿鳳 徐野 溫倩

[摘 要]運籌學(xué)是一門研究如何最優(yōu)安排的學(xué)科。筆者提出了運籌學(xué)中幾個問題的新議。一是用數(shù)學(xué)的語言來描述幸福就是“收入>付出”，而運籌學(xué)就是不斷追求幸福的過程;二是二階段法或大M法中的尋找初始可行基可用更為簡便的方法來實現(xiàn)，即對標(biāo)準(zhǔn)型的增廣矩陣實施初等行變換可獲得線性規(guī)劃問題的初始可行基，這樣做使計算量大大減少;三是在求解平衡運輸問題的表上作業(yè)法中，可對單位費用矩陣某行或某列減去一個常數(shù)，最優(yōu)解不變，這樣可大大減少計算量。

[關(guān)鍵詞]運籌學(xué);幸福不等式;二階段法;運輸問題

[中圖分類號] O22 [文獻標(biāo)識碼] A [文章編號] 2095-3437（2021）05-0092-04

一、運籌學(xué)中蘊含的幸福不等式“收入>付出”

幸福是人的一種主觀感受，當(dāng)你問100個人：“幸福是什么？”你將得到100種答案。有的人會說“只要有錢就是幸?！保钟械娜苏f“只要有一份體面又掙錢的工作就是幸?！?，還有的人說“只要和愛的人在一起就是幸?！薄Ｓ械目梢詮男睦韺W(xué)角度去解釋幸福，有的可以從哲學(xué)角度去解釋幸福，還有的可以從生理學(xué)角度去解釋幸福，等等。那么從數(shù)學(xué)角度去解釋幸福是什么呢？數(shù)學(xué)似乎與幸福離得太遠，數(shù)學(xué)看起來沒有溫度，而幸?？偸亲屓烁杏X暖暖的，但是數(shù)學(xué)卻能歸納出幸福的一般規(guī)律，即幸福不等式“收入>付出”，而這正是運籌學(xué)的真諦。

運籌學(xué)是一門研究如何最優(yōu)安排的學(xué)科，國外把它稱作Operations Research，即“運作研究”。而我國把它譯作“運籌學(xué)”，源于史記“運籌于帷幄之中，決勝于千里之外”，取“運籌”二字，體現(xiàn)運心籌謀、策略取勝。運籌學(xué)的真諦就是“收入>付出”，它總是研究如何用最小的成本取得最大的收益。如在企業(yè)生產(chǎn)計劃問題中，它研究如何運用最小的成本（資源）獲得最大的產(chǎn)出（利潤、收益等）;或為了獲得一定的產(chǎn)出，如何使資源使用最少。在投資問題中，它研究在風(fēng)險承受范圍內(nèi)如何使投資收益最大;或在一定的投資收益水平之上，如何使投資風(fēng)險最小。在網(wǎng)絡(luò)運輸問題中，它研究如何用最小的成本滿足客戶的需求。在分派問題中，它研究如何分配工作可以使效率最高或完成任務(wù)的費用最小，等?？傊痪湓?，運籌學(xué)就是研究如何用最少的成本獲得最多收入的過程，而只要“收入>付出”，在任何問題中，在任何事情上，人們均能感覺到滿足和幸福。如在投資中，投資者如果能夠?qū)崿F(xiàn)“收入>付出”， 他就會感覺到滿足;哪怕是收入只比付出大一點點，他也會感覺到一點點的滿足;而如果“收入>>付出”即收入遠遠大于付出，則他會感覺到非常的滿足。在工作中，如果一個人的“收入>付出”，此時的收入可以是金錢、榮譽、晉升機會、成就感、獲得感等，付出可以是時間、勞動、感情等，他也會感覺到滿足，由此而覺得幸福。因此，運籌學(xué)就是一個不斷追求幸福的過程，是如何實現(xiàn)“收入>付出”的過程。

二、用初等行變換確定初始可行基的方法

我們都知道，在運籌學(xué)的線性規(guī)劃問題的求解中，如果某個線性規(guī)劃問題沒有初始可行基，則需要用二階段法或大M法進行求解。而二階段法和大M法的計算量相對來說都是比較大的。因此，本文提出一種針對線性規(guī)劃問題沒有初始可行基解，但是計算量又比二階段法和大M法小得多的一種確定初始可行基解的方法，即用初等行變換確定線性規(guī)劃問題的初始可行基。本文通過幾個典型的例題進行分析，從而可從中略見一斑。

例題1：求解下列線性規(guī)劃問題

[maxz=-4x1-3x3s.t.12x1-x2-12x3≥2-32x1? ? ? +14x3=3x1，x2，x3≥0]

分析：在二階段法中，其實增加人工變量構(gòu)造輔助問題只是解決一個問題，即通過輔助問題尋找初始可行基，而這個問題我們認為，完全可以通過對標(biāo)準(zhǔn)型的增廣矩陣實施初等行變換得到。在此例中，標(biāo)準(zhǔn)型的增廣矩陣為[A=12-1-12-12-3201403]，對增廣矩陣施行初等行變換，

[A=12-1-12-12-3201403→015121-310-160-2]，由此看到，已經(jīng)得到一個單位矩陣[B=[P2，P1]=1001]，但此基是一個不可行基，因為常數(shù)列[b]為負。而且得到第一個方程約束為[x2+512x3+x4=-3]，由于[x2，x3，x4≥0]，因此這個等式是不可能成立的，即是一個矛盾的等式，所以得到原線性規(guī)劃問題無可行解。由此看到，通過對標(biāo)準(zhǔn)型的約束方程增廣矩陣施行初等行變換，能夠很方便地找到線性規(guī)劃問題的基，避免了二階段法或大M法中的復(fù)雜計算。我們再來看一個例子。

例題2：求解下列線性規(guī)劃問題? ? [maxz=-4x1-3x3s.t.12x1+x2+12x3≥232x1? ? ? ? +34x3=3x1，x2，x3≥0]

分析：我們可以用標(biāo)準(zhǔn)型的增廣矩陣施行初等行變換，求出原問題的初始可行基，這樣可以大大減少計算量。原問題的標(biāo)準(zhǔn)型的增廣矩陣為：

[A=12112-123203403]

對上述增廣矩陣施行初等行變換，得到：

[A=12112-123203403→0114-11101202]，同樣得到基[B=[P2，P1]]，

這樣得到兩個約束方程為[? ? x2+14x3-x4=1x1? ? ?+12x3? ? ? ? =2]，

將原目標(biāo)函數(shù)用非基變量表示[maxz=-4x1-3x3=-8-x3]，列出初始單純形表（見表1）。

因此，可以非常簡便地得到原問題的最優(yōu)解[x1=2，x2=0，x3=0，maxz=-8]。我們再來看一個例子。

例題3：求解下列線性規(guī)劃問題：[maxz=-4x1-3x3s.t.12x1+x2+12x3-23x4=232x1? ? ? ? -12x3? ? ? ? ? =33x1-6x2? ? ? ? ? ?+4x4=0x1，x2，x3，x4≥0]

分析：我們通過對標(biāo)準(zhǔn)型約束方程的增廣矩陣施行初等行變換非常方便地進行求解。該問題的標(biāo)準(zhǔn)型約束方程的增廣矩陣為：

[A=12112-232320-12033-6040→? ]

[12112-232-3010-6603012→]

[210-235-3010-610002][→010-2310010010002]

同樣得到原問題的初始可行基[B=[P2，P3，P1]]，原約束方程化為：[? ? x2? ? ? -23x4=1? ? ? ? ?x3? ? ? ? ? ?=0x1? ? ? ? ? ? ? ? ? ? =2]

將原問題的目標(biāo)函數(shù)用非基變量表示[maxz=-4x1-3x3=-8]，列出單純形表（見表2）。

表2已為最優(yōu)表，最優(yōu)解為[x1=2，x2=1，x3=0，x4=0，maxz=-8]。

總結(jié)：以上三個例題概括了用二階段法求解無初始可行基的線性規(guī)劃問題的所有類型，求解輔助問題時，（1）在最優(yōu)表中人工變量仍然無法出基，且目標(biāo)函數(shù)不等于0，表明原線性規(guī)劃問題無可行解;（2）在最優(yōu)表中，人工變量全部出基，得到原問題的一個初始可行基;（3）在最優(yōu)表中，人工變量沒有全部出基，但是輔助問題的目標(biāo)函數(shù)值為0，通過強行選擇人工變量出基，也得到原問題的一個初始可行基。后面兩種情況均可以繼續(xù)進入第二階段，求解原問題。從這三個例題中可以看到，用二階段法求原問題的初始可行基解一般計算量都較大，而用標(biāo)準(zhǔn)型約束方程的增廣矩陣施行初等行變換求原問題基的方法計算量則小得多，因而不失為一種較好的求解方法。

三、求解平衡運輸問題的一種簡化方法

運輸問題的基本模型如下：[minz=i=1mj=1ncijxijs.t.j=1nxij=ai，? （i=1，2，...，m）i=1mxij=bj，? ?（j=1，2，...，n）xij≥0]

求解運輸問題一般運用表上作業(yè)法，計算機求解時也可直接使用單純形法。無論是運用表上作業(yè)法還是單純形法，當(dāng)費用矩陣[C=cijm×n]中的單位費用[cij]數(shù)值較大時，都不便于計算。為了解決這個難題，我們可以仿照指派問題中的匈牙利法，從費用矩陣[C=cijm×n]中每一行減去其最小值，每一列減去其最小值，得到變換后的費用矩陣[B=bijm×n]，兩個費用矩陣[C=cijm×n]和[B=bijm×n]，其對應(yīng)的運輸問題最優(yōu)解不變。

性質(zhì)1：對于平衡運輸問題，從費用矩陣[C=cijm×n]中某行減去一個常數(shù)[t]，某列減去一個常數(shù)[d]后得到費用矩陣[B=bijm×n]，那么，這種變化并不會引起最優(yōu)解的改變。

證明如下：

模型（1）[minz=i=1mj=1ncijxijs.t.j=1nxij=ai，? （i=1，2，...，m）i=1mxij=bj，? ?（j=1，2，...，n）xij≥0]

模型（2）[minw=i=1mj=1nbijxijs.t.j=1nxij=ai，? （i=1，2，...，m）i=1mxij=bj，? ?（j=1，2，...，n）xij≥0]

設(shè)[bij=cij-ti-dj]，即由原運輸問題費用矩陣中第[i]行減去一個常數(shù)項[ti]，第[j]列減去一個常數(shù)項[dj]得到。

[minw=i=1mj=1nbijxij=i=1mj=1n（cij-ti-dj）xij]

[? ? ? ? ? ? ? ? ? ? ?=i=1mj=1ncijxij-i=1mj=1ntixij-i=1mj=1ndjxij]

[? ? ? ? ? ? ? ? ? ? ?=i=1mj=1ncijxij-i=1mtij=1nxij-j=1ndji=1mxij][? ? ? ? ? ? ? ? ? ? ?=minz-i=1mtiai-j=1ndjbj]

由于[i=1mtiai]和[j=1ndjbj]均為常數(shù)，所以模型（1）和模型（2）具有相同的最優(yōu)解。

由此性質(zhì)，在求解運輸問題時，可適當(dāng)?shù)貙M用矩陣進行簡化，然后再運用表上作業(yè)法進行計算，則可以大大減少計算量。下面以一個例子加以說明。

例題4：用表上作業(yè)法求以下運輸問題的最優(yōu)解（見表3）。

解：由于運輸問題的單位費用表中的單位費用數(shù)值較大，因此，求解起來很不方便，我們先對費用矩陣進行化簡，每一行減去該行的最小值，每列再減去該列的最小值，用最小元素法得到初始方案，圓圈內(nèi)的數(shù)字表示運量（見表4）。

最優(yōu)性檢驗，計算各空格（非基變量）的檢驗數(shù)。

[σ13=190-0+0-142+0-0=48]，[σ14=106-142+0-0=-36]

已經(jīng)有一個空格檢驗數(shù)為負，說明當(dāng)前的初始解不是最優(yōu)解，需要進入調(diào)整，用閉回路法進行調(diào)整（見表5）。

再次進行最優(yōu)性檢驗，計算各空格（非基變量）的檢驗數(shù)。

[σ11=0-106+142-0=36]，[σ13=190-106+0-0=84]，

[σ22=15-0+106-142=-21]

說明表5對應(yīng)的方案仍不是最優(yōu)方案，需要再一次用閉回路法進行調(diào)整，調(diào)整后的方案如下（見表6）。

再次進行最優(yōu)性檢驗，計算各空格（非基變量）的檢驗數(shù)。

[σ11=0-0+15-0=15]，[σ13=190-106+0-0=84]，

[σ23=338-15+0-106+0-0=217]，

[σ24=142-15+0-106=21]

[σ31=607-0+106-0+15-0=728]，

[σ32=245-0+106-0=351]

表6中所有空格的檢驗數(shù)均大于等于0，說明表19對應(yīng)的運輸方案為最優(yōu)方案。最優(yōu)調(diào)運方案為A→甲20個單位;A→丁55個單位;B→甲80個單位;B→乙45個單位;C→丙70個單位;C→丁30個單位。最小運費計算時將運量表與原始費用表相對應(yīng)，最小運輸費用為：

[minz=513×20+867×55+352×80+416×45+388×70+685×30=152535]

[ 參 考 文 獻 ]

[1] 陳儀坤.運籌學(xué)[M].上海：同濟大學(xué)出版社，1989.

[2] 劉滿鳳，陶長琪，柳鍵，等.運籌學(xué)教程[M].北京：清華大學(xué)出版社，2010.

[3] 于晉臣，邢育紅，孟艷雙，等.數(shù)學(xué)建模思想有效融入運籌學(xué)教學(xué)的研究[J].教育現(xiàn)代化，2019（51）：42-43.

[4] 曹陽.研究性教學(xué)方法在交通類專業(yè)運籌學(xué)教學(xué)中的探索[J].教育教學(xué)論壇，2019（45）：181-182.

[5] 陳家焱，洪濤，周娟，等.以案例庫建設(shè)為載體的運籌學(xué)課程教學(xué)改革[J].大學(xué)教育，2019（8）：31-33.

[6] 陳紅兵，王三福.運籌學(xué)課程的教學(xué)改革與實踐[J].教育教學(xué)論壇，2019（42）：125-126.

[責(zé)任編輯：林志恒]