優(yōu)化建模軟件在運(yùn)籌學(xué)教學(xué)中應(yīng)用

前言：想要寫(xiě)出一篇引人入勝的文章？我們特意為您整理了優(yōu)化建模軟件在運(yùn)籌學(xué)教學(xué)中應(yīng)用范文，希望能給你帶來(lái)靈感和參考，敬請(qǐng)閱讀。

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

關(guān)鍵詞：運(yùn)籌學(xué)；整數(shù)規(guī)劃；教學(xué)；EXCEL；LINGO；MATLAB

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

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

整數(shù)規(guī)劃（混合整數(shù)規(guī)劃）要求所有變量（部分變量）取整數(shù)，其標(biāo)準(zhǔn)形式如下所示。其中，xi，i=1，...，s為整數(shù)變量，xj，j=s+1，...，n為實(shí)數(shù)變量，整數(shù)規(guī)劃問(wèn)題可以是最小化問(wèn)題，也可以是最大化問(wèn)題。

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

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

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

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

2.2LINGO

LINGO(LinearInteractiveandGeneralOptimizer)是一個(gè)交互式的優(yōu)化求解器，可以求解線(xiàn)性規(guī)劃問(wèn)題，也可以求解非線(xiàn)性規(guī)劃規(guī)劃問(wèn)題和非線(xiàn)性方程組。它最初是由美國(guó)芝加哥大學(xué)的LinusSchrage教授開(kāi)發(fā)的，通過(guò)不斷完善和擴(kuò)充，并成立了Lindo公司進(jìn)行商業(yè)化運(yùn)作[5]。其特色在于可以允許決策變量是整數(shù)（即可求解整數(shù)規(guī)劃），操作簡(jiǎn)便，求解速度快。優(yōu)化軟件LINGO可以求解整數(shù)規(guī)劃活混合整數(shù)規(guī)劃問(wèn)題，首先需要根據(jù)實(shí)際問(wèn)題，建立問(wèn)題一般數(shù)學(xué)模型；然后通過(guò)LINGO軟件編輯框，采用優(yōu)化建模語(yǔ)言對(duì)數(shù)學(xué)模型進(jìn)行描述，使得計(jì)算機(jī)能夠理解，最后調(diào)用LINGO軟件后臺(tái)算法求解模型。2.3MATLABMATLAB是美國(guó)MathWorks公司推出的高性能數(shù)值計(jì)算和可視化軟件，主要功能包括數(shù)值分析、矩陣計(jì)算、信號(hào)處理、圖形顯示、算法開(kāi)發(fā)和模擬仿真等，廣泛地應(yīng)用于數(shù)值計(jì)算、程序開(kāi)發(fā)、數(shù)據(jù)采集、系統(tǒng)建模與仿真、數(shù)據(jù)分析和可視化等領(lǐng)域，是一個(gè)功能強(qiáng)大的商業(yè)數(shù)學(xué)軟件[6]。MATLAB還是一個(gè)開(kāi)放的開(kāi)發(fā)平臺(tái)，可以根據(jù)需求自己開(kāi)發(fā)相應(yīng)的功能模塊，例如運(yùn)籌優(yōu)化常用的YALMIP等[7]。由于具有強(qiáng)大的矩陣計(jì)算能力，MATLAB也可用于求解運(yùn)籌學(xué)中的線(xiàn)性規(guī)劃和整數(shù)規(guī)劃問(wèn)題。

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

目前，運(yùn)籌學(xué)（整數(shù)規(guī)劃）教學(xué)過(guò)程中存在一些問(wèn)題，導(dǎo)致教學(xué)效果不佳，主要表現(xiàn)在以下兩點(diǎn)：（1）運(yùn)籌學(xué)被當(dāng)作數(shù)學(xué)理論課程，重理論輕實(shí)踐運(yùn)學(xué)學(xué)課程數(shù)學(xué)知識(shí)、數(shù)學(xué)理論較多，課程教學(xué)過(guò)程中存在大量的數(shù)學(xué)模型，以及相關(guān)數(shù)學(xué)定理的證明及推導(dǎo)，因此運(yùn)籌學(xué)通常被學(xué)生們誤認(rèn)為純數(shù)學(xué)理論課程。特別是整數(shù)規(guī)劃教學(xué)，涉及凸包理論、解空間分解、上下界證明、對(duì)偶理論等諸多相對(duì)深?yuàn)W、復(fù)雜的數(shù)學(xué)理論。如果不介紹相關(guān)數(shù)學(xué)理論，則導(dǎo)致學(xué)生理解不深入，只知其然不知其所以然，但是如果單純大量的理論學(xué)習(xí)，又可能使學(xué)生產(chǎn)生畏懼心理，降低學(xué)習(xí)興趣。因此，學(xué)習(xí)過(guò)程應(yīng)當(dāng)理論指導(dǎo)實(shí)踐，加深理論基礎(chǔ)的同時(shí)，注重培養(yǎng)動(dòng)手實(shí)踐能力。（2）整數(shù)規(guī)劃動(dòng)手實(shí)踐能力，軟件應(yīng)用能力需要加強(qiáng)整數(shù)規(guī)劃通常屬于NP難問(wèn)題，運(yùn)算量大，求解過(guò)程極為復(fù)雜，即使簡(jiǎn)單的小規(guī)模問(wèn)題也很難通過(guò)手工計(jì)算求解，更不用說(shuō)現(xiàn)實(shí)中復(fù)雜的大規(guī)模問(wèn)題。因此，如果學(xué)生不能熟練使用優(yōu)化求解軟件，就不便于求解大規(guī)模問(wèn)題，進(jìn)而學(xué)生動(dòng)手能力不足，學(xué)習(xí)興趣下降。

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

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

例1．某工廠計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗，如表1所示[1]。該工廠每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2元,每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3元,請(qǐng)問(wèn)應(yīng)如何安排計(jì)劃使該工廠獲利最多?第一步，設(shè)生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品的數(shù)量分別為x1，x2，建立數(shù)學(xué)模型，如下所示：第三步，設(shè)置可變單元格和目標(biāo)單元格，確定決策變量、目標(biāo)函數(shù)和約束條件。設(shè)置可變單元格，表示決策變量，記錄問(wèn)題的最優(yōu)解，令單元格B7和C7作為可變單元格(分別記錄變量x1，x2的值)。在可變單元格中輸入任意初值，此處都輸入0。設(shè)置目標(biāo)單元格，記錄目標(biāo)函數(shù)值，即當(dāng)問(wèn)題求解完成時(shí)，該單元格將顯示最優(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分別表示問(wèn)題的3個(gè)約束條件。利用數(shù)組乘積函數(shù)SUMPRODUCT，分別輸入第四步，設(shè)置規(guī)劃求解參數(shù)。單擊菜單欄“數(shù)據(jù)”中的“規(guī)劃求解”命令，彈出“規(guī)劃求解參數(shù)”對(duì)話(huà)框，在“設(shè)置目標(biāo)”選項(xiàng)中輸入“$D$6”，“通過(guò)更改可變單元格”中輸入“$B$7:$C$7”，目標(biāo)類(lèi)型選擇最大值。設(shè)置需要遵守約束條件，單擊“添加”按鈕，出現(xiàn)“添加約束”對(duì)話(huà)框，“單元格引用”中輸入“$D$3:$D$5”，“約束”輸入“$F$3:$F$5”，符號(hào)選擇“”。本題要求變量為整數(shù)，需再輸入整數(shù)約束，“單元格引用”輸入$B$7$C$7，“約束”選擇“int整數(shù)”。如圖3所示。第五步，調(diào)用算法，計(jì)算得到規(guī)劃求解結(jié)果。完成求解參數(shù)設(shè)置后，選擇求解方法為“非線(xiàn)性GRG”，勾選“使無(wú)約束變量為非負(fù)數(shù)”，點(diǎn)擊“求解”，彈出規(guī)劃求解結(jié)果對(duì)話(huà)框，如圖4所示。點(diǎn)擊確定，就得到相應(yīng)的求解結(jié)果，如圖5所示。圖中的單元格B7和C7里的數(shù)據(jù)就是得到的最優(yōu)解。D6中的數(shù)據(jù)是z的最大值，即z=14元。

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

例1．某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表2所示。問(wèn)兩種貨物各托運(yùn)多少箱,可使獲得利潤(rùn)為最大[1]?第一步，設(shè)x1，x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)(非負(fù)整數(shù))，建立數(shù)學(xué)模型，如下所示：第三步，點(diǎn)擊LINGO界面的運(yùn)行按鈕，就得到最優(yōu)值為90，其中x1=4,x2=1，如圖6所示。

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

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

5結(jié)語(yǔ)

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

作者:王建江 杜振國(guó) 劉進(jìn) 單位:國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院 國(guó)防科技大學(xué)系統(tǒng)工程學(xué)院