優(yōu)化建模軟件在運(yùn)籌學(xué)整數(shù)規(guī)劃教學(xué)中的應(yīng)用

王建江 杜振國 劉進(jìn)

摘 要

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

關(guān)鍵詞

運(yùn)籌學(xué);整數(shù)規(guī)劃;教學(xué);EXCEL;LINGO;MATLAB

中圖分類號： 022;G642.0 ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A

DOI：10.19694/j.cnki.issn2095-2457.2020.09.010

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

1 整數(shù)規(guī)劃模型

整數(shù)規(guī)劃（混合整數(shù)規(guī)劃）要求所有變量（部分變量）取整數(shù)，其標(biāo)準(zhǔn)形式如下所示。

2 常用優(yōu)化建模軟件簡介

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

2.1 EXCEL規(guī)劃求解工具

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

2.2 LINGO

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

優(yōu)化軟件LINGO可以求解整數(shù)規(guī)劃活混合整數(shù)規(guī)劃問題，首先需要根據(jù)實(shí)際問題，建立問題一般數(shù)學(xué)模型;然后通過LINGO軟件編輯框，采用優(yōu)化建模語言對數(shù)學(xué)模型進(jìn)行描述，使得計(jì)算機(jī)能夠理解，最后調(diào)用LINGO軟件后臺算法求解模型。

2.3 MATLAB

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

3 運(yùn)籌學(xué)（整數(shù)規(guī)劃）教學(xué)存在的問題

目前，運(yùn)籌學(xué)（整數(shù)規(guī)劃）教學(xué)過程中存在一些問題，導(dǎo)致教學(xué)效果不佳，主要表現(xiàn)在以下兩點(diǎn)：

（1）運(yùn)籌學(xué)被當(dāng)作數(shù)學(xué)理論課程，重理論輕實(shí)踐

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

（2）整數(shù)規(guī)劃動手實(shí)踐能力，軟件應(yīng)用能力需要加強(qiáng)

整數(shù)規(guī)劃通常屬于NP難問題，運(yùn)算量大，求解過程極為復(fù)雜，即使簡單的小規(guī)模問題也很難通過手工計(jì)算求解，更不用說現(xiàn)實(shí)中復(fù)雜的大規(guī)模問題。因此，如果學(xué)生不能熟練使用優(yōu)化求解軟件，就不便于求解大規(guī)模問題，進(jìn)而學(xué)生動手能力不足，學(xué)習(xí)興趣下降。

4 優(yōu)化建模軟件應(yīng)用實(shí)例

4.1 EXCEL規(guī)劃求解工具應(yīng)用實(shí)例

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

該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元， 每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元， 請問應(yīng)如何安排計(jì)劃使該工廠獲利最多？

第一步，設(shè)生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品的數(shù)量分別為x1，x2，建立數(shù)學(xué)模型，如下所示：

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

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

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

第五步，調(diào)用算法，計(jì)算得到規(guī)劃求解結(jié)果。完成求解參數(shù)設(shè)置后，選擇求解方法為“非線性GRG”，勾選“使無約束變量為非負(fù)數(shù)”，點(diǎn)擊“求解”，彈出規(guī)劃求解結(jié)果對話框，如圖4所示。

點(diǎn)擊確定，就得到相應(yīng)的求解結(jié)果，如圖5所示。圖中的單元格B7和C7里的數(shù)據(jù)就是得到的最優(yōu)解。D6中的數(shù)據(jù)是z的最大值，即z=14元。

4.2 LINGO應(yīng)用實(shí)例

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

第一步，設(shè)x1，x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)（非負(fù)整數(shù)），建立數(shù)學(xué)模型，如下所示：

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

model：

max=20*x1+10* x2;

5*x1+4* x2 <= 24;

2* x1+5* x2<= 13;

@gin（ x1）;

@gin（ x2 ）;

第三步，點(diǎn)擊LINGO 界面的運(yùn)行按鈕，就得到最優(yōu)值為90，其中x1=4，x2=1，如圖6所示。

4.3 MATLAB應(yīng)用實(shí)例

以4.1節(jié)例1為例，介紹MATLAB如何求解整數(shù)規(guī)劃問題，首先建立問題數(shù)學(xué)模型，如4.1節(jié)所示，此處省略。然后，采用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默認(rèn)求解最小化問題，而本問題是最大化問題，需轉(zhuǎn)化為最小化問題，因此目標(biāo)函數(shù)系數(shù)f為負(fù)數(shù)。程序編寫完成后，點(diǎn)擊運(yùn)行，即可得到問題的解為x1=4，x2=2，目標(biāo)函數(shù)為-14（真實(shí)目標(biāo)為14）元。

5 結(jié)語

運(yùn)籌學(xué)是一門緊貼實(shí)際應(yīng)用的學(xué)科，運(yùn)籌學(xué)教學(xué)不僅要向?qū)W生傳授理論知識，介紹模型和算法，也要培養(yǎng)學(xué)生的實(shí)踐能力，指導(dǎo)學(xué)生運(yùn)用運(yùn)籌學(xué)知識解決實(shí)際問題。傳統(tǒng)教學(xué)過程中，學(xué)生普遍沉迷于數(shù)學(xué)推導(dǎo)和解題，動手實(shí)踐能力普遍不足。在教學(xué)過程中引入優(yōu)化建模軟件，能夠促進(jìn)學(xué)生運(yùn)用所學(xué)知識解決實(shí)際問題，提高學(xué)生的學(xué)習(xí)興趣，實(shí)現(xiàn)更好的學(xué)習(xí)效果。

參考文獻(xiàn)

[1]運(yùn)籌教材編寫組.運(yùn)籌學(xué)[M].北京： 清華大學(xué)出版社，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]陳候炎，徐玉娥，陳其嶙.整數(shù)規(guī)劃模型EXCEL求解的簡化方法[J].科學(xué)與財(cái)富， 2011（12）：116-116.

[4]于瑛英.EXCEL在運(yùn)籌學(xué)規(guī)劃論教學(xué)中的應(yīng)用[J].教育教學(xué)論壇，（10）：285-287.

[5]管梅.LINGO在運(yùn)籌學(xué)實(shí)踐教學(xué)中的應(yīng)用[J].科技視界， 2015（12）：21-22+24.

[6]張明，王文文.MATLAB在經(jīng)管類運(yùn)籌學(xué)教學(xué)中的探索與實(shí)踐[J].大學(xué)教育， 2012（07）：83-84+91.

[7]俞武揚(yáng).YALMIP工具箱在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中的應(yīng)用[J].實(shí)驗(yàn)室研究與探索， 2017（8）.