優化建模軟件在運籌學整數規劃教學中的應用

王建江 杜振國 劉進

摘 要

運籌學是一本應用性很強，與實踐結合很緊密的課程。本文分析了運籌學（整數規劃）教學存在的不足，簡要介紹了幾種常用的優化建模軟件，通過幾個典型示例，分別闡述了EXCEL規劃求解工具、LINGO、MATLAB等優化軟件在運籌學（整數規劃）教學中的應用。通過引入優化軟件，有助于提高學生的學習興趣，提高學生的動手實踐能力。

關鍵詞

運籌學;整數規劃;教學;EXCEL;LINGO;MATLAB

中圖分類號： 022;G642.0 ? ? ? ? ? ? ? ? ?文獻標識碼： A

DOI：10.19694/j.cnki.issn2095-2457.2020.09.010

整數規劃是運籌學中的典型問題，應用于解決生產實踐、經濟管理、國防軍事領域的諸多問題，有著廣泛的應用前景和重要意義。整數規劃問題大部分是線性的，傳統的線性規劃問題中，部分可行解或者最優解可能是分數或小數，但是對于某些特定問題，常要求可行解、最優解必須是整數（稱為整數解）。例如， 所求的解是開設工廠的臺數、完成工作的人數或運送貨物的車數等，分數或小數解答就不滿足要求[1]。因此，需要在線性規劃模型中強制要求決策變量或部分決策變量為整數，即得到整數規劃（integer programming，IP）或者混合整數規劃（mixed integer programming，MIP）模型[2]。針對整數規劃或混合整數規劃問題，學者們已提出了相應的求解方法，例如分枝定界法、窮舉法、割平面算法等，但是算法普遍計算量大、步驟非常煩瑣，難以手工完成，需要借助計算機建模求解工具實現。因此，運籌學（整數規劃）教學中引入優化建模工具的應用，對于激發學生的學習興趣，鼓勵學生解決實際問題，提高實踐能力具有重要意義[3]。

1 整數規劃模型

整數規劃（混合整數規劃）要求所有變量（部分變量）取整數，其標準形式如下所示。

2 常用優化建模軟件簡介

目前常用的優化應用軟件有LINGO、MATLAB、MATHEM ATIC、CPLEX等，其中MATHEMATIC和CPLEX專業性太強，操作復雜，不便于在教學中使用。此外，EXCEL具有強大的數據處理功能，其規劃求解工具也可用于整數規劃問題的建模和求解，并且操作簡便，適合在課堂教學中使用。因此，本文主要介紹EXCEL、LINGO和MATLAB三類優化建模軟件在整數規劃教學中的應用。

2.1 EXCEL規劃求解工具

如前所述，現實中整數規劃問題通常是線性問題，適合利用EXCEL強大的表格計算處理能力進行建模求解，因此人們開發了基于EXCEL的規劃求解工具。EXCEL規劃求解工具求解算法包括單純形法、非線性GRG算法和演化算法，整數規劃可采用非線性GRG算法求解，該方法由Leon Lasdon和AIlan Waren共同開發[4]。規劃求解工具是EXCEL中的一個加載項，使用前需要加載，打開“工具/選項/加載項”菜單欄，在打開的“加載項”對話框中選中“規劃求解加載項”，點擊確定，就將“規劃求解”工具添加到“數據”菜單欄中了。

2.2 LINGO

LINGO（Linear Interactive and General Optimizer）是一個交互式的優化求解器，可以求解線性規劃問題，也可以求解非線性規劃規劃問題和非線性方程組。它最初是由美國芝加哥大學的Linus Schrage教授開發的，通過不斷完善和擴充，并成立了Lindo公司進行商業化運作[5]。其特色在于可以允許決策變量是整數（即可求解整數規劃），操作簡便，求解速度快。

優化軟件LINGO可以求解整數規劃活混合整數規劃問題，首先需要根據實際問題，建立問題一般數學模型;然后通過LINGO軟件編輯框，采用優化建模語言對數學模型進行描述，使得計算機能夠理解，最后調用LINGO軟件后臺算法求解模型。

2.3 MATLAB

MATLAB是美國MathWorks公司推出的高性能數值計算和可視化軟件，主要功能包括數值分析、矩陣計算、信號處理、圖形顯示、算法開發和模擬仿真等，廣泛地應用于數值計算、程序開發、數據采集、系統建模與仿真、數據分析和可視化等領域，是一個功能強大的商業數學軟件[6]。MATLAB還是一個開放的開發平臺，可以根據需求自己開發相應的功能模塊，例如運籌優化常用的YALMIP等[7]。由于具有強大的矩陣計算能力，MATLAB也可用于求解運籌學中的線性規劃和整數規劃問題。

3 運籌學（整數規劃）教學存在的問題

目前，運籌學（整數規劃）教學過程中存在一些問題，導致教學效果不佳，主要表現在以下兩點：

（1）運籌學被當作數學理論課程，重理論輕實踐

運學學課程數學知識、數學理論較多，課程教學過程中存在大量的數學模型，以及相關數學定理的證明及推導，因此運籌學通常被學生們誤認為純數學理論課程。特別是整數規劃教學，涉及凸包理論、解空間分解、上下界證明、對偶理論等諸多相對深奧、復雜的數學理論。如果不介紹相關數學理論，則導致學生理解不深入，只知其然不知其所以然，但是如果單純大量的理論學習，又可能使學生產生畏懼心理，降低學習興趣。因此，學習過程應當理論指導實踐，加深理論基礎的同時，注重培養動手實踐能力。

（2）整數規劃動手實踐能力，軟件應用能力需要加強

整數規劃通常屬于NP難問題，運算量大，求解過程極為復雜，即使簡單的小規模問題也很難通過手工計算求解，更不用說現實中復雜的大規模問題。因此，如果學生不能熟練使用優化求解軟件，就不便于求解大規模問題，進而學生動手能力不足，學習興趣下降。

4 優化建模軟件應用實例

4.1 EXCEL規劃求解工具應用實例

例1.某工廠計劃期內要安排生產Ⅰ、Ⅱ兩種產品，已知生產單位產品所需的設備臺時及A、B 兩種原材料的消耗，如表1所示[1]。

該工廠每生產一件產品Ⅰ可獲利2元， 每生產一件產品Ⅱ可獲利3元， 請問應如何安排計劃使該工廠獲利最多？

第一步，設生產Ⅰ、Ⅱ兩種產品的數量分別為x1，x2，建立數學模型，如下所示：

第二步，建立整數規劃問題的電子表格模型，如圖1所示。

第三步，設置可變單元格和目標單元格，確定決策變量、目標函數和約束條件。設置可變單元格，表示決策變量，記錄問題的最優解，令單元格B7和C7作為可變單元格（分別記錄變量x1，x2的值）。在可變單元格中輸入任意初值，此處都輸入0。設置目標單元格，記錄目標函數值，即當問題求解完成時，該單元格將顯示最優的目標函數值。令D6作為目標單元格（記錄目標z的值），輸入目標函數公式為D6=SUMPRODUCT（B6：C6，B7：C7），其中SUMPRODUCT表示數組乘積之和，即D5=B6×B7+C6×C7。輸入約束條件。選定單元格D3、D4、D5分別表示問題的3個約束條件。利用數組乘積函數SUMPRODUCT，分別輸入D3=SUMPRODUCT（B3：C3，B7：C7），D4=SUMPROD UCT（B4：C4，B7：C7），D5=SUMPRODUCT（B5：C5，B7：C7），如圖2所示。

第四步，設置規劃求解參數。單擊菜單欄“數據”中的“規劃求解”命令，彈出“規劃求解參數”對話框，在“設置目標”選項中輸入“$D$6”，“通過更改可變單元格”中輸入“$B$7：$C$7”，目標類型選擇最大值。設置需要遵守約束條件，單擊“添加”按鈕，出現“添加約束”對話框，“單元格引用”中輸入“$D$3：$D$5”，“約束”輸入“$F$3：$F$5”，符號選擇“”。本題要求變量為整數，需再輸入整數約束，“單元格引用”輸入$B$7$C$7，“約束”選擇“int整數”。如圖3所示。

第五步，調用算法，計算得到規劃求解結果。完成求解參數設置后，選擇求解方法為“非線性GRG”，勾選“使無約束變量為非負數”，點擊“求解”，彈出規劃求解結果對話框，如圖4所示。

點擊確定，就得到相應的求解結果，如圖5所示。圖中的單元格B7和C7里的數據就是得到的最優解。D6中的數據是z的最大值，即z=14元。

4.2 LINGO應用實例

例1.某廠擬用集裝箱托運甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運所受限制如表2 所示。問兩種貨物各托運多少箱， 可使獲得利潤為最大[1]？

第一步，設x1，x2分別為甲、乙兩種貨物的托運箱數（非負整數），建立數學模型，如下所示：

第二步，在LINGO窗口中輸入以下代碼：

model：

max=20*x1+10* x2;

5*x1+4* x2 <= 24;

2* x1+5* x2<= 13;

@gin（ x1）;

@gin（ x2 ）;

第三步，點擊LINGO 界面的運行按鈕，就得到最優值為90，其中x1=4，x2=1，如圖6所示。

4.3 MATLAB應用實例

以4.1節例1為例，介紹MATLAB如何求解整數規劃問題，首先建立問題數學模型，如4.1節所示，此處省略。然后，采用MATLAB腳本文件編制如下程序

f=[-2，-3];

A=[1，2;4，0;0，4];

b=[8;16;12];

C=[];

d=[];

xm=[0;0];

xM=1e+10*[1;1];

[x，y，flag]=intlinprog（f，[1，2]，A，b，C，d，xm，xM）;

此處，需要注意的是MATLAB默認求解最小化問題，而本問題是最大化問題，需轉化為最小化問題，因此目標函數系數f為負數。程序編寫完成后，點擊運行，即可得到問題的解為x1=4，x2=2，目標函數為-14（真實目標為14）元。

5 結語

運籌學是一門緊貼實際應用的學科，運籌學教學不僅要向學生傳授理論知識，介紹模型和算法，也要培養學生的實踐能力，指導學生運用運籌學知識解決實際問題。傳統教學過程中，學生普遍沉迷于數學推導和解題，動手實踐能力普遍不足。在教學過程中引入優化建模軟件，能夠促進學生運用所學知識解決實際問題，提高學生的學習興趣，實現更好的學習效果。

參考文獻

[1]運籌教材編寫組.運籌學[M].北京： 清華大學出版社，2012.

[2]Jünger，M.，Liebling，T.M.，Naddef，D.，Nemhauser，G.L.，Pulleyblank，W.R.，Reinelt，G.，...& Wolsey，L.A.（Eds.）.50 Years of integer programming 1958-2008：From the early years to the state-of-the-art[M]. Springer Science & Business Media，2009.

[3]陳候炎，徐玉娥，陳其嶙.整數規劃模型EXCEL求解的簡化方法[J].科學與財富， 2011（12）：116-116.

[4]于瑛英.EXCEL在運籌學規劃論教學中的應用[J].教育教學論壇，（10）：285-287.

[5]管梅.LINGO在運籌學實踐教學中的應用[J].科技視界， 2015（12）：21-22+24.

[6]張明，王文文.MATLAB在經管類運籌學教學中的探索與實踐[J].大學教育， 2012（07）：83-84+91.

[7]俞武揚.YALMIP工具箱在運籌學實驗教學中的應用[J].實驗室研究與探索， 2017（8）.