MATLAB在運籌學中的應用

張建勇 于愷 李友朋 張翠艷

摘 ? ?要： 本文根據運籌學的學科特點及在教學中存在的不足，提出了在教學實踐中引入Matlab作為教學輔助手段，主要闡述MATLAB在線性規劃、目標規劃、二次規劃中的應用，實例驗證了Matlab在求解運籌學問題時的高效性和準確性。

關鍵詞： MATLAB ? ?運籌學 ? ?線性規劃 ? ?目標規劃 ? ?二次規劃

一、引言

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

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

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

本文通過線性規劃、二次規劃和目標規劃三個方面，結合具體實例，說明MATLAB在求解運籌學問題時的易操作性與直觀性。

二、MATLAB在線性規劃方面的應用

線性規劃是最優化中的一個分支，是最優化理論的基礎性內容。有關線性規劃問題的建模、求解和應用性研究，構成了運籌學中線性規劃[3]分支。在MATLAB的優化工具箱中，線性規劃問題必須表示為如下[4]：

對于一般的線性規劃問題，可以根據線性規劃的標準化方法，將其轉換為模型（1）的形式。求解模型（1）的MATLAB命令函數為linprog（），完整的調用格式形式為：

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

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

輸出參數x為線性規劃問題的最優解，fval為線性規劃問題在最優解x處的函數值，exitflag返回的是優化函數計算終止時的狀態指示，說明算法終止的原因，當其值為1時說明已經收斂到x，當x取其他值時，其物理意義如表1。

表1 ? ?Exitflag的反饋值與對應的物理意義

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

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

程序如下：

clc;clear;

f=[-1;-1]; %目標函數，為轉化為極小，故取目標函數中設計變量的相反數

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

b=[4;8];

lb=[0;0];

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

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

運算結果如下：

Optimization terminated.

x=[6.0000，1.0000]

fval=-7.0000

由結果可知，當x=6，x=1時，目標函數取得最優解7。

三、MATLAB在二次規劃中的應用

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

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

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

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

例如求解下列二次型規劃問題

程序如下：

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）

運算結果如下：

Optimization terminated.

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

fval=42.7375

exitflag=1

所以當x=0.2，x=0.125，x=5，x=3，x=5時，目標函數取得最小值42.7375。exitflag=1說明函數取得最優解。

四、MATLAB在目標規劃中的應用

目標規劃在處理實際決策問題時，承認各項決策要求的存在有其合理性，即在最終決策時，不強調其絕對意義上的最優性，在一定程度上彌補了線性規劃存在的某些缺陷。因此，在運籌學中所有的規劃問題中，與實際聯系最大的當屬目標規劃。MATLAB所定義的目標函數的標準形式為

γ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為相應維數的向量，A、Aeq為矩陣，c（x）、ceq（x）、f（x）為返回向量的函數，它們可以是線性函數，也可以是非線性函數。

在MATLAB的庫函數中，針對目標規劃的命令函數名為fgoalattain（），調用形式為：

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

其中在輸入參數中，fun為目標函數，x■是求解的初始值，goal是目標函數的期望值，weight是目標權重，nonlcon是非線性約束函數。輸出參數中，attainfactor參數包含解處的γ值，γ取負值時表示結果溢出。

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

該工廠決策認為，這兩個目標中環境污染應優先考慮，設備投資的目標值20萬元，公害損失的目標為12萬元。

相應的MATLAB程序如下：

clc，clear;

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

b=[5;6;7];

x0=[0，0];

goal=[20，12];%設置期望目標值

weight=abs（goal）;%設置目標權重

[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）;

運算結果如下：

x=[2.9167 ? ?4.0833]

fval=26.2500 ? 15.7500

attainfactor=0.3125

由結果可知，每月生產A產品3t，B產品4t時，設備投資費用和公害損失與目標最為接近，設備投資費用為26.25萬元，公害損失為15.75萬元。Attaintfactor>0說明γ值未溢出，結果可信。

五、結語

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

同時，運籌學還包含其他內容，如動態規劃、整數規劃、非線性規劃等內容，在Matlab中，也有與之對應的命令或工具箱，學習者可以結合網絡資源或者Matlab中的help命令進行學習。

參考文獻：

[1]王立欣，王愛維，趙美.運籌學常用軟件綜述[J].科技情報開發與經濟，2009，26：95-96.

[2]張明，王文文.Matlab在經管類運籌學教學中的探索與實踐[J].大學教育，2012，07：81-82.

[3]胡運權.運籌學教程（第三版）[M].北京：清華大學出版社，2007.

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

[5]馬莉.MATLAB數學實驗與建模[M].北京：清華大學出版社，2010.