MATLAB在運(yùn)籌學(xué)中的應(yīng)用

張建勇 于愷 李友朋 張翠艷

摘 ? ?要： 本文根據(jù)運(yùn)籌學(xué)的學(xué)科特點(diǎn)及在教學(xué)中存在的不足，提出了在教學(xué)實(shí)踐中引入Matlab作為教學(xué)輔助手段，主要闡述MATLAB在線性規(guī)劃、目標(biāo)規(guī)劃、二次規(guī)劃中的應(yīng)用，實(shí)例驗證了Matlab在求解運(yùn)籌學(xué)問題時的高效性和準(zhǔn)確性。

關(guān)鍵詞： MATLAB ? ?運(yùn)籌學(xué) ? ?線性規(guī)劃 ? ?目標(biāo)規(guī)劃 ? ?二次規(guī)劃

一、引言

運(yùn)籌學(xué)是利用現(xiàn)代數(shù)學(xué)研究各種廣義資源的運(yùn)用、籌劃與相關(guān)決策等問題的一門新興學(xué)科。該課程的主要特點(diǎn)是運(yùn)用量化的分析方法，對有限的資源進(jìn)行統(tǒng)籌安排，其研究成果為決策者提供科學(xué)依據(jù)。由于很多問題來源于實(shí)際的生產(chǎn)和管理活動，因此在建立數(shù)學(xué)模型時往往會涉及很多變量和約束條件，使得所建立的模型較復(fù)雜。如何求解這類模型成為解決問題的關(guān)鍵。

在運(yùn)籌學(xué)的教學(xué)中，盡管目前的教學(xué)改革使得教學(xué)手段豐富多樣，但這些教學(xué)手段只是將教材內(nèi)容搬運(yùn)到多媒體課件上。加之多媒體的教學(xué)節(jié)奏較快，使得原本生動的教學(xué)內(nèi)容，只側(cè)重于理論分析和公式推導(dǎo)，忽略計算過程和結(jié)果，導(dǎo)致課堂教學(xué)效果差。手工推演和計算運(yùn)籌學(xué)中實(shí)例的可行性太低，成熟的商業(yè)軟件能夠為運(yùn)籌學(xué)教學(xué)提供較好的輔助作用。

目前最好的方法是借助于計算機(jī)和商業(yè)軟件進(jìn)行求解，常見的軟件主要有LINGO、LINDO和MATLAB等[1]。LINGO是美國LINDO系統(tǒng)公司研發(fā)的，常用于求解線性規(guī)劃及一些簡單的非線性規(guī)劃問題。該軟件在處理復(fù)雜的非線性規(guī)劃問題時存在一定的局限性。1984年美國MathWorks公司開發(fā)的MATLAB軟件，已經(jīng)發(fā)展成國際上應(yīng)用最廣泛的科學(xué)與工程計算軟件之一。其中包含與運(yùn)籌學(xué)緊密相關(guān)的優(yōu)化工具箱，該工具箱的基本功能有：求解線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃、目標(biāo)規(guī)劃及多目標(biāo)規(guī)劃等問題，在求解各類優(yōu)化問題時都有著無可替代的優(yōu)勢[2]。

本文通過線性規(guī)劃、二次規(guī)劃和目標(biāo)規(guī)劃三個方面，結(jié)合具體實(shí)例，說明MATLAB在求解運(yùn)籌學(xué)問題時的易操作性與直觀性。

二、MATLAB在線性規(guī)劃方面的應(yīng)用

線性規(guī)劃是最優(yōu)化中的一個分支，是最優(yōu)化理論的基礎(chǔ)性內(nèi)容。有關(guān)線性規(guī)劃問題的建模、求解和應(yīng)用性研究，構(gòu)成了運(yùn)籌學(xué)中線性規(guī)劃[3]分支。在MATLAB的優(yōu)化工具箱中，線性規(guī)劃問題必須表示為如下[4]：

對于一般的線性規(guī)劃問題，可以根據(jù)線性規(guī)劃的標(biāo)準(zhǔn)化方法，將其轉(zhuǎn)換為模型（1）的形式。求解模型（1）的MATLAB命令函數(shù)為linprog（），完整的調(diào)用格式形式為：

[x，fval，exitflag，output，lambda]=linprog（f，A，b，Aeq，beq，lb，ub，x0，options）

其中，f為目標(biāo)函數(shù)中系數(shù)向量的轉(zhuǎn)置，是一維行向量，A、b滿足不等式Ax≤b，若沒有不等式約束，則A=[]，b=[];Aeq、beq滿足等式約束Aeq=beq，若沒有，則取Aeq=[]，beq=[];lb、ub滿足，若無界，可令lb=[]，ub=[];x0為初始值;options為包含算法控制參數(shù)的結(jié)構(gòu)變量，可以通過optimset命令對這些具體的控制參數(shù)進(jìn)行設(shè)置。

輸出參數(shù)x為線性規(guī)劃問題的最優(yōu)解，fval為線性規(guī)劃問題在最優(yōu)解x處的函數(shù)值，exitflag返回的是優(yōu)化函數(shù)計算終止時的狀態(tài)指示，說明算法終止的原因，當(dāng)其值為1時說明已經(jīng)收斂到x，當(dāng)x取其他值時，其物理意義如表1。

表1 ? ?Exitflag的反饋值與對應(yīng)的物理意義

output輸出優(yōu)化信息，lambda為lagrange乘子，它體現(xiàn)某個約束的有效性。在使用linprog（）命令時，必須嚴(yán)格遵循它的調(diào)用格式（1）。比如下面的線性規(guī)劃問題：

max z=x■+x■s.t. ? ?x■-2x■≤4 ? ? ? ? x■+2x■≤8 ? ? ? ? x■，x■≥0

程序如下：

clc;clear;

f=[-1;-1]; %目標(biāo)函數(shù)，為轉(zhuǎn)化為極小，故取目標(biāo)函數(shù)中設(shè)計變量的相反數(shù)

A=[1 ?-2;1 ?2];%線性不等式約束

b=[4;8];

lb=[0;0];

ub=[Inf;Inf];%邊界約束，由于無上界，故設(shè)置ub=[Inf;Inf]

[x，fval]=linprog（f，A，b，[]，[]，lb，ub）%x為最優(yōu)解，fval為最優(yōu)值

運(yùn)算結(jié)果如下：

Optimization terminated.

x=[6.0000，1.0000]

fval=-7.0000

由結(jié)果可知，當(dāng)x=6，x=1時，目標(biāo)函數(shù)取得最優(yōu)解7。

三、MATLAB在二次規(guī)劃中的應(yīng)用

二次型規(guī)劃問題是一種簡單的有約束非線性規(guī)劃問題，它已成為運(yùn)籌學(xué)、經(jīng)濟(jì)數(shù)學(xué)及組合優(yōu)化科學(xué)的基本方法。非線性規(guī)劃問題在計算上是困難的，理論上也不像線性規(guī)劃那樣有簡潔的結(jié)果和成熟的理論。通常情況下，采用迭代的思想計算非線性規(guī)劃問題，即從一個滿足約束條件的初始可行點(diǎn)出發(fā)，按照一定的搜索機(jī)制，找到下一個使目標(biāo)函數(shù)更優(yōu)的可行解，直到找到最優(yōu)解其目標(biāo)。在Matlab中，二次規(guī)劃函數(shù)是x的二次型形式，約束條件仍為線性的。一般的二次規(guī)劃問題的數(shù)學(xué)表示為[4]：

與線性規(guī)劃相比，二次型規(guī)劃多出一項XHX描述x和xx項。在MATLAB工具箱中，求解二次型規(guī)劃的是命令函數(shù)是quadprog（）。函數(shù)調(diào)用形式如下所示：

[x，fval，exitflag，output，lambda]=quadprog（H，f，A，b，Aeq，beq，lb，ub，x0，options）

其輸入?yún)?shù)H為對角矩陣，表示x和xx項前面的系數(shù)，其他參數(shù)的輸入格式與linprog（）完全相同，見表1。

例如求解下列二次型規(guī)劃問題

程序如下：

clc，clear;

H=diag（[10 8 6 4 2]）;

f=[-2，-1，-2，-5，-10];

A=[1，1，1，1，1;-5，4，-3，2，-1;1，1，0，0，-1;0，0，0，1，1;0，0，-1，0，0;0，0，0，-1，0];

b=[20;-5;8;10;-5;-3];

[x，fval，exitflag]=quadprog（H，f，A，b）

運(yùn)算結(jié)果如下：

Optimization terminated.

x=[0.2000 ? 0.1250 ? 5.0000 ? 3.0000 ? 5.0000]

fval=42.7375

exitflag=1

所以當(dāng)x=0.2，x=0.125，x=5，x=3，x=5時，目標(biāo)函數(shù)取得最小值42.7375。exitflag=1說明函數(shù)取得最優(yōu)解。

四、MATLAB在目標(biāo)規(guī)劃中的應(yīng)用

目標(biāo)規(guī)劃在處理實(shí)際決策問題時，承認(rèn)各項決策要求的存在有其合理性，即在最終決策時，不強(qiáng)調(diào)其絕對意義上的最優(yōu)性，在一定程度上彌補(bǔ)了線性規(guī)劃存在的某些缺陷。因此，在運(yùn)籌學(xué)中所有的規(guī)劃問題中，與實(shí)際聯(lián)系最大的當(dāng)屬目標(biāo)規(guī)劃。MATLAB所定義的目標(biāo)函數(shù)的標(biāo)準(zhǔn)形式為

γs.t. ? f（x）-weight·γ≤goal ? ? ? ?c（x）≤0 ? ? ? ?ceq（x）=0 ? ? ? ?Ax≤b ? ? ? ?Aeqx=beq ? ? ? ?lb≤x≤ub

其中x、weight、goal、b、beq、lb、ub為相應(yīng)維數(shù)的向量，A、Aeq為矩陣，c（x）、ceq（x）、f（x）為返回向量的函數(shù)，它們可以是線性函數(shù)，也可以是非線性函數(shù)。

在MATLAB的庫函數(shù)中，針對目標(biāo)規(guī)劃的命令函數(shù)名為fgoalattain（），調(diào)用形式為：

[x，fval，attainfactor，exitflag，output，lambda]=fgoalattain（fun，x0，goal，weight，A，b，Aeq，beq，lb，ub，nonlcon，options）

其中在輸入?yún)?shù)中，fun為目標(biāo)函數(shù)，x■是求解的初始值，goal是目標(biāo)函數(shù)的期望值，weight是目標(biāo)權(quán)重，nonlcon是非線性約束函數(shù)。輸出參數(shù)中，attainfactor參數(shù)包含解處的γ值，γ取負(fù)值時表示結(jié)果溢出。

例如，某化工廠擬生產(chǎn)兩種新產(chǎn)品A和B，其生產(chǎn)設(shè)備費(fèi)用分別為：2萬元/t和5萬元/t。這兩種產(chǎn)品均造成環(huán)境污染，假設(shè)由公害所造成的損失可折算為4萬元/t和1萬元/t。由于條件限制，該廠的兩種產(chǎn)品的最大生產(chǎn)能力分別為每月5t和6t，而市場需要這兩種產(chǎn)品的總量每月不少于7t。試問工廠如何安排生產(chǎn)計劃，在滿足市場需要的前提下，使設(shè)備投資和公害損失均達(dá)到最小？

該工廠決策認(rèn)為，這兩個目標(biāo)中環(huán)境污染應(yīng)優(yōu)先考慮，設(shè)備投資的目標(biāo)值20萬元，公害損失的目標(biāo)為12萬元。

相應(yīng)的MATLAB程序如下：

clc，clear;

A=[1，0;0，1;-1;-1];

b=[5;6;7];

x0=[0，0];

goal=[20，12];%設(shè)置期望目標(biāo)值

weight=abs（goal）;%設(shè)置目標(biāo)權(quán)重

[x，fval，attainfactor]=fgoalattain（@funa，x0，goal，weight，A，b）

function f=funa（x）

f（1）=2*x（1）+5*x（2）;

f（2）=4*x（1）+x（2）;

運(yùn)算結(jié)果如下：

x=[2.9167 ? ?4.0833]

fval=26.2500 ? 15.7500

attainfactor=0.3125

由結(jié)果可知，每月生產(chǎn)A產(chǎn)品3t，B產(chǎn)品4t時，設(shè)備投資費(fèi)用和公害損失與目標(biāo)最為接近，設(shè)備投資費(fèi)用為26.25萬元，公害損失為15.75萬元。Attaintfactor>0說明γ值未溢出，結(jié)果可信。

五、結(jié)語

以上實(shí)例說明，利用MATLAB可以方便地求出線性規(guī)劃等優(yōu)化問題的解，不僅算法簡單，避免了手工的繁瑣計算，而且可以大大提高計算速度和計算的準(zhǔn)確性。將MATLAB軟件用于運(yùn)籌學(xué)教學(xué)，可以更直觀地理解運(yùn)籌學(xué)中的基本概念理論，并可培養(yǎng)動手和科研實(shí)踐能力。

同時，運(yùn)籌學(xué)還包含其他內(nèi)容，如動態(tài)規(guī)劃、整數(shù)規(guī)劃、非線性規(guī)劃等內(nèi)容，在Matlab中，也有與之對應(yīng)的命令或工具箱，學(xué)習(xí)者可以結(jié)合網(wǎng)絡(luò)資源或者M(jìn)atlab中的help命令進(jìn)行學(xué)習(xí)。

參考文獻(xiàn)：

[1]王立欣，王愛維，趙美.運(yùn)籌學(xué)常用軟件綜述[J].科技情報開發(fā)與經(jīng)濟(jì)，2009，26：95-96.

[2]張明，王文文.Matlab在經(jīng)管類運(yùn)籌學(xué)教學(xué)中的探索與實(shí)踐[J].大學(xué)教育，2012，07：81-82.

[3]胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第三版）[M].北京：清華大學(xué)出版社，2007.

[4]楊云峰，胡金燕，宋國亮.數(shù)學(xué)建模與數(shù)學(xué)軟件[M].哈爾濱：哈爾濱工程大學(xué)出版社，2012.

[5]馬莉.MATLAB數(shù)學(xué)實(shí)驗與建模[M].北京：清華大學(xué)出版社，2010.