Excel平臺(tái)下運(yùn)籌學(xué)模型的求解分析

馮英華

（濰坊科技學(xué)院，山東 壽光 262700）

0 引 言

在運(yùn)籌學(xué)教材中詳細(xì)介紹了規(guī)劃問題的分類及其解法，針對(duì)每種類型的問題都有不同的解決方法，但這些方法在實(shí)際計(jì)算過(guò)程中并不實(shí)用。一是手工計(jì)算篇幅會(huì)過(guò)長(zhǎng)，二是計(jì)算占用時(shí)間太多。我們的目的是學(xué)會(huì)分析問題、建立模型和求解模型的方法，至于具體的求解過(guò)程可以交給計(jì)算機(jī)去處理。但現(xiàn)在學(xué)生對(duì)于 MATLAB，LINDO和LINGO等編程還沒有接觸，在這種情況下有一種簡(jiǎn)單而實(shí)用的運(yùn)算工具就是Excel。Excel是平時(shí)用的比較多的一個(gè)軟件，其中有一個(gè)工具“規(guī)劃求解”，專門求解運(yùn)籌學(xué)中的系列問題［1－2］，下面根據(jù)相應(yīng)案例來(lái)分析一下Excel的各種使用方法。

在運(yùn)用Excel求解之前先檢查一下本機(jī)的Excel中是否安裝了相關(guān)模塊。方法是打開Excel，一般在2007版本中的工具欄下都帶有規(guī)劃求解選項(xiàng)，而2003版本中不帶。現(xiàn)在用的最多的還是2003版本，如何實(shí)現(xiàn)2003版本下的求解運(yùn)算呢？我們可以通過(guò)加載宏對(duì)本工具進(jìn)行加載。

1 Excel在線性規(guī)劃中的應(yīng)用

對(duì)于線性規(guī)劃問題的求解，課本上的方法是先將規(guī)劃模型化為標(biāo)準(zhǔn)形，然后再利用單純形法去進(jìn)行求解，有時(shí)根據(jù)模型的需要還要添加人工變量來(lái)構(gòu)造人工基［3－4］。而單純形法中一次次的迭代加大了運(yùn)算量，手工計(jì)算非常繁瑣。在Excel中不需對(duì)原模型進(jìn)行任何的變換，只需要將模型的各項(xiàng)數(shù)據(jù)全部錄入即可。下面以一個(gè)具有一般性的線性規(guī)劃模型為例來(lái)進(jìn)行分析。

線性規(guī)劃模型：

打開Excel，將上述問題按圖1形式將相應(yīng)數(shù)據(jù)依次輸入。

圖1 線性規(guī)劃Excel圖

“變量取值”取初始值為0，軟件會(huì)自動(dòng)進(jìn)行迭代。在E欄中輸入約束條件算式時(shí)應(yīng)注意對(duì)變量取值實(shí)行絕對(duì)引用，以防在向下拖動(dòng)選定區(qū)域時(shí)變量單元格發(fā)生改變。如E3格內(nèi)應(yīng)輸入“＝B3＊＄B＄2＋C3＊＄C＄2＋D3＊＄D＄2”，然后向下拖動(dòng)選定區(qū)域，擴(kuò)展至E4，E5，在目標(biāo)函數(shù)“B7”中輸入“＝B6＊B2＋C6＊C2＋D6＊D2”，這樣已知數(shù)據(jù)準(zhǔn)備完畢，下面開始對(duì)問題進(jìn)行分析。

選中目標(biāo)函數(shù)單元格B7，點(diǎn)擊“工具”一欄中的“規(guī)劃求解”，如圖2所示。

圖2 規(guī)劃求解參數(shù)圖

2 Excel在運(yùn)輸問題中的應(yīng)用

在運(yùn)輸問題中條件會(huì)相對(duì)較復(fù)雜，里面的數(shù)據(jù)通常涉及到產(chǎn)銷平衡表和單位運(yùn)價(jià)表，課本上的表上作業(yè)法運(yùn)算量相對(duì)龐大。那么，怎樣運(yùn)用Excel輕松解決運(yùn)輸問題？在Excel中建立好單位運(yùn)價(jià)表和產(chǎn)銷平衡表兩個(gè)表格，產(chǎn)銷平衡表中初始數(shù)據(jù)填0，將其余相關(guān)數(shù)據(jù)列入表中。而該問題中的總運(yùn)費(fèi)支出最小又應(yīng)如何表示呢？引入SUMPRODUCT函數(shù)對(duì)兩表相應(yīng)元素對(duì)應(yīng)相乘并求和，即為總的運(yùn)費(fèi)支出。如“SUMPRODUCT（B2：E4，B7：E9）”表示對(duì)矩陣B2：E4與矩陣B7：E9的對(duì)應(yīng)元素的乘積求和。

在目標(biāo)單元格中輸入目標(biāo)函數(shù)，然后點(diǎn)擊規(guī)劃求解，根據(jù)要求將各個(gè)參數(shù)與約束條件在彈出的頁(yè)面中依次填好即可。這里強(qiáng)調(diào)一下，選中“可變單元格”后，在Excel表格中點(diǎn)擊運(yùn)量表中變量的左上角單元格，再輸入冒號(hào)，然后再點(diǎn)擊運(yùn)量表中變量的右下角單元格，這就代表了運(yùn)量表的這個(gè)矩形框內(nèi)的所有變量。在約束條件參數(shù)中使“各廠的產(chǎn)量＝已知產(chǎn)量”、“各地的銷量＝已經(jīng)銷量”，同時(shí)在約束條件中要求所有變量非負(fù)。如果需要變量取整數(shù)，則只需在約束條件中約束好即可。點(diǎn)擊求解后得到所求結(jié)果。

利用Excel建立好問題模型，它的特點(diǎn)是使用簡(jiǎn)單、便捷、利于調(diào)整。如果各廠的生產(chǎn)量或是各地的銷售量有所變化，只需要在已經(jīng)建好的Excel模型中更改一下有關(guān)數(shù)據(jù)就可以得出新的計(jì)算結(jié)果，使用非常方便，能夠更好地服務(wù)于實(shí)際需求。

3 Excel在整數(shù)規(guī)劃中的應(yīng)用

整數(shù)規(guī)劃只是對(duì)變量的要求有所變化，它是要求全部或部分變量的取值必須是整數(shù)。所以和線性規(guī)劃問題在Excel中的求解一樣，只需要在“規(guī)劃求解參數(shù)”約束條件中添加變量取整數(shù)（int）的條件就可以，不再單獨(dú)舉例說(shuō)明。

在該規(guī)劃中還有一類“指派問題”，它的解法和第二類運(yùn)輸問題的解法類似，需在Excel中建立效率矩陣和分配矩陣兩個(gè)表格，利用SUMPRODUCT函數(shù)對(duì)效率矩陣和分配矩陣兩表相應(yīng)元素對(duì)應(yīng)相乘并求和。只是其中的變量取值只能取0或1，所以要在“規(guī)劃求解參數(shù)”中對(duì)變量輸入約束條件bin（二進(jìn)制），也可以用“≥0”，“≤1”同時(shí)加取整數(shù)的條件來(lái)進(jìn)行約束［6］。

4 Excel在目標(biāo)規(guī)劃中的應(yīng)用

目標(biāo)規(guī)劃是一種處理多目標(biāo)優(yōu)化問題的工具，應(yīng)用非常廣泛，其模型與線性規(guī)劃模型基本相同，所以可以用單純形法進(jìn)行求解［7－8］。但因不同目標(biāo)重要程度相差懸殊，對(duì)目標(biāo)函數(shù)的優(yōu)化是按優(yōu)先級(jí)順序逐級(jí)進(jìn)行的，所以人工運(yùn)算量是非常大的，而Excel節(jié)省時(shí)間，能夠快速地給出運(yùn)算結(jié)果報(bào)告。

如多目標(biāo)規(guī)劃模型：

將上面模型中的相關(guān)數(shù)據(jù)與前面介紹的方法一樣有條、有序的錄入到Excel表格中。在這里需要說(shuō)明3點(diǎn)：

3）目標(biāo)函數(shù)為優(yōu)先因子pi分別乘上對(duì)應(yīng)的子目標(biāo)之和，其中的優(yōu)先因子可以根據(jù)實(shí)際需要來(lái)定義它的取值，這里取p1＝10 000，p2＝100，p3＝1，以滿足pk?pk＋1。

明確這3點(diǎn)，并將規(guī)劃求解參數(shù)設(shè)置好后，進(jìn)行求解輸出結(jié)果報(bào)告。

5 Excel在圖論問題中的應(yīng)用（最短路徑和最大流問題）

在很多實(shí)際問題中，經(jīng)常會(huì)從圖中求出任意兩點(diǎn)間的最短距離以及其經(jīng)過(guò)的路徑，如選址、管道鋪設(shè)、投資、設(shè)備更新等都可歸結(jié)為最短路問題［3］。針對(duì)此問題一般有求從其中一點(diǎn)到另外其它各點(diǎn)之間的Dijkstra算法和求圖上任意兩個(gè)點(diǎn)之間的矩陣算法，但當(dāng)涉及到的點(diǎn)比較多時(shí)，人工算法就不方便了。所以需要尋找一種既簡(jiǎn)單又方便的方法。

該問題一樣可以利用Excel平臺(tái)來(lái)進(jìn)行求解，其原理是：令邊的變量（決策變量）為0或1，1表示最短路經(jīng)過(guò)該邊，0表示不經(jīng)過(guò)該邊，起點(diǎn)進(jìn)出權(quán)和為1，終點(diǎn)進(jìn)出權(quán)和為－1，除此外各點(diǎn)處的進(jìn)出權(quán)和為0，目標(biāo)函數(shù)可借助SUMPRODUCT函數(shù)，設(shè)定為各邊的變量和權(quán)之積的和的最小值［9］。

求從v1～v7的最短路，如圖3所示。

圖3 最短路網(wǎng)絡(luò)圖

以此為例在Excel表格中進(jìn)行問題分析，將相關(guān)數(shù)據(jù)列出，如圖4所示。

圖4 最短路Excel圖

圖4中邊的變量初始值設(shè)為0，單元格F列中錄入每個(gè)頂點(diǎn)的進(jìn)出權(quán)和，如：F2中錄入“＝D2＋D3”，…，F(xiàn)8中錄入“＝0－D10－D13”。本例中有兩個(gè)特殊點(diǎn)v5，v6，以v5點(diǎn)為例，v6－v5是進(jìn)邊，v5－v6是出邊，F(xiàn)6中錄入“＝D10＋D11－D5－D8－D12”。在B14一格中輸入“SUMPRODUCT（C2：C13，D2：D13）”。在彈出的求解參數(shù)表中輸入“＄D＄2：＄D＄13＝二進(jìn)制、＄F＄2＝1，＄F＄8＝－1，＄F＄3：＄F＄7＝0”的約束，點(diǎn)擊“求解”后邊的變量值為1的即為所通過(guò)的邊。

6 結(jié) 語(yǔ)

運(yùn)籌學(xué)是在解決實(shí)際問題的過(guò)程中發(fā)展起來(lái)的，而其手工的運(yùn)算在實(shí)際問題中也不太切合實(shí)際，特別是問題比較復(fù)雜、運(yùn)算量比較大的模型。因此，需要我們借助于更好的工具去運(yùn)算，這樣既大量節(jié)省時(shí)間，又增強(qiáng)了學(xué)生對(duì)計(jì)算機(jī)應(yīng)用的進(jìn)一步認(rèn)識(shí)。Excel功能強(qiáng)大，它在運(yùn)籌學(xué)中的應(yīng)用不僅限于上述幾個(gè)方面，存貯論、排除論等問題也可在Excel中建立模型進(jìn)行直接求解，另外，還可運(yùn)用“treeplan”宏建立決策樹求解風(fēng)險(xiǎn)型決策問題，運(yùn)用“teachdp”宏求解動(dòng)態(tài)規(guī)劃問題，通過(guò)VB編程進(jìn)行隨機(jī)模擬實(shí)驗(yàn)（如擲幣游戲）等［9－10］。

Excel操作簡(jiǎn)單，其中的“規(guī)劃求解”易于學(xué)習(xí)掌握，對(duì)初學(xué)者而言是一個(gè)非常不錯(cuò)的運(yùn)算工具。

［1］呂劍亮，朱坤.運(yùn)籌學(xué)線性規(guī)劃模型求解的計(jì)算機(jī)應(yīng)用［J］.長(zhǎng)春工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2001，2（3）：59－62.

［2］劉建知.利用Excel求解線性規(guī)劃問題［J］.湖南農(nóng)業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2005，31（5）：562－564.

［3］胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用［M］.5版.北京：高等教育出版社，2008.

［4］馬振華.現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè)（運(yùn)籌學(xué)與最優(yōu)化理論卷）［M］.北京：清華大學(xué)出版社，1998.

［5］陳士成，李橋興，何麗紅.運(yùn)籌學(xué)網(wǎng)絡(luò)優(yōu)化模型的Excel求解的減化方法［J］.蘭州大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，46（9）：179－182.

［6］雷真，繆昇，屈俊童.整數(shù)規(guī)劃法在防火預(yù)案制定中的應(yīng)用［J］.云南大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，31（S1）：289－293.

［7］李如兵，宗鳳喜.運(yùn)籌學(xué)教學(xué)中Excel的應(yīng)用研究［J］.綿陽(yáng)師范學(xué)院學(xué)報(bào)，2012，31（8）：148－152.

［8］楊波，羅領(lǐng)俊，張仰福.運(yùn)籌學(xué)在實(shí)踐教學(xué)中存在的問題與改進(jìn)措施［J］.山西建筑，2012，38（3）：271－272.

［9］張美玉.求解線性網(wǎng)絡(luò)最優(yōu)化問題的新型進(jìn)行算法［J］.廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2006（4）：74－77.

［10］徐海霞，任紅松，袁繼勇，等.用Excel及其“規(guī)劃求解”功能擬合曲線方程［J］.農(nóng)業(yè)網(wǎng)絡(luò)信息，2004（2）：37－39.