Excel平臺下運籌學模型的求解分析

馮英華

（濰坊科技學院，山東 壽光 262700）

0 引 言

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

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

1 Excel在線性規劃中的應用

對于線性規劃問題的求解，課本上的方法是先將規劃模型化為標準形，然后再利用單純形法去進行求解，有時根據模型的需要還要添加人工變量來構造人工基［3－4］。而單純形法中一次次的迭代加大了運算量，手工計算非常繁瑣。在Excel中不需對原模型進行任何的變換，只需要將模型的各項數據全部錄入即可。下面以一個具有一般性的線性規劃模型為例來進行分析。

線性規劃模型：

打開Excel，將上述問題按圖1形式將相應數據依次輸入。

圖1 線性規劃Excel圖

“變量取值”取初始值為0，軟件會自動進行迭代。在E欄中輸入約束條件算式時應注意對變量取值實行絕對引用，以防在向下拖動選定區域時變量單元格發生改變。如E3格內應輸入“＝B3＊＄B＄2＋C3＊＄C＄2＋D3＊＄D＄2”，然后向下拖動選定區域，擴展至E4，E5，在目標函數“B7”中輸入“＝B6＊B2＋C6＊C2＋D6＊D2”，這樣已知數據準備完畢，下面開始對問題進行分析。

選中目標函數單元格B7，點擊“工具”一欄中的“規劃求解”，如圖2所示。

圖2 規劃求解參數圖

2 Excel在運輸問題中的應用

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

在目標單元格中輸入目標函數，然后點擊規劃求解，根據要求將各個參數與約束條件在彈出的頁面中依次填好即可。這里強調一下，選中“可變單元格”后，在Excel表格中點擊運量表中變量的左上角單元格，再輸入冒號，然后再點擊運量表中變量的右下角單元格，這就代表了運量表的這個矩形框內的所有變量。在約束條件參數中使“各廠的產量＝已知產量”、“各地的銷量＝已經銷量”，同時在約束條件中要求所有變量非負。如果需要變量取整數，則只需在約束條件中約束好即可。點擊求解后得到所求結果。

利用Excel建立好問題模型，它的特點是使用簡單、便捷、利于調整。如果各廠的生產量或是各地的銷售量有所變化，只需要在已經建好的Excel模型中更改一下有關數據就可以得出新的計算結果，使用非常方便，能夠更好地服務于實際需求。

3 Excel在整數規劃中的應用

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

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

4 Excel在目標規劃中的應用

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

如多目標規劃模型：

將上面模型中的相關數據與前面介紹的方法一樣有條、有序的錄入到Excel表格中。在這里需要說明3點：

3）目標函數為優先因子pi分別乘上對應的子目標之和，其中的優先因子可以根據實際需要來定義它的取值，這里取p1＝10 000，p2＝100，p3＝1，以滿足pk?pk＋1。

明確這3點，并將規劃求解參數設置好后，進行求解輸出結果報告。

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

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

該問題一樣可以利用Excel平臺來進行求解，其原理是：令邊的變量（決策變量）為0或1，1表示最短路經過該邊，0表示不經過該邊，起點進出權和為1，終點進出權和為－1，除此外各點處的進出權和為0，目標函數可借助SUMPRODUCT函數，設定為各邊的變量和權之積的和的最小值［9］。

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

圖3 最短路網絡圖

以此為例在Excel表格中進行問題分析，將相關數據列出，如圖4所示。

圖4 最短路Excel圖

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

6 結 語

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

Excel操作簡單，其中的“規劃求解”易于學習掌握，對初學者而言是一個非常不錯的運算工具。

［1］呂劍亮，朱坤.運籌學線性規劃模型求解的計算機應用［J］.長春工程學院學報：自然科學版，2001，2（3）：59－62.

［2］劉建知.利用Excel求解線性規劃問題［J］.湖南農業大學學報：自然科學版，2005，31（5）：562－564.

［3］胡運權.運籌學基礎及應用［M］.5版.北京：高等教育出版社，2008.

［4］馬振華.現代應用數學手冊（運籌學與最優化理論卷）［M］.北京：清華大學出版社，1998.

［5］陳士成，李橋興，何麗紅.運籌學網絡優化模型的Excel求解的減化方法［J］.蘭州大學學報：自然科學版，2010，46（9）：179－182.

［6］雷真，繆昇，屈俊童.整數規劃法在防火預案制定中的應用［J］.云南大學學報：自然科學版，2009，31（S1）：289－293.

［7］李如兵，宗鳳喜.運籌學教學中Excel的應用研究［J］.綿陽師范學院學報，2012，31（8）：148－152.

［8］楊波，羅領俊，張仰福.運籌學在實踐教學中存在的問題與改進措施［J］.山西建筑，2012，38（3）：271－272.

［9］張美玉.求解線性網絡最優化問題的新型進行算法［J］.廣西師范大學學報：自然科學版，2006（4）：74－77.

［10］徐海霞，任紅松，袁繼勇，等.用Excel及其“規劃求解”功能擬合曲線方程［J］.農業網絡信息，2004（2）：37－39.