YALMIP工具箱在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中的應(yīng)用

俞武揚(yáng)

( 杭州電子科技大學(xué) 管理學(xué)院，杭州 310018)

YALMIP工具箱在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中的應(yīng)用

俞武揚(yáng)

( 杭州電子科技大學(xué) 管理學(xué)院，杭州 310018)

Matlab平臺(tái)對于運(yùn)籌學(xué)中各種經(jīng)典優(yōu)化模型的實(shí)驗(yàn)教學(xué)具有重要作用，然而由于Matlab工具箱中函數(shù)的調(diào)用格式限制條件非常嚴(yán)格，從而導(dǎo)致將實(shí)驗(yàn)數(shù)據(jù)表示成Matlab所需矩陣形式時(shí)容易造成實(shí)驗(yàn)教學(xué)效率低下的情況。借助于YALMIP工具箱結(jié)合Matlab軟件實(shí)現(xiàn)了運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中經(jīng)典模型的求解，對線性規(guī)劃、運(yùn)輸問題、背包問題、最短路問題等等結(jié)合具體例子說明了YALMIP語言的建模方法。利用YALMIP的統(tǒng)一建模語言，很容易對各種運(yùn)籌學(xué)典型問題的模型加以實(shí)現(xiàn)，從而降低了利用軟件解決模型問題的難度，同時(shí)也對解決運(yùn)籌學(xué)實(shí)驗(yàn)中的其它問題有借鑒作用。

運(yùn)籌學(xué)； 實(shí)驗(yàn)教學(xué)； Matlab； YALMIP工具箱

0 引 言

線性規(guī)劃、運(yùn)輸問題、整數(shù)規(guī)劃以及圖論中的最小樹、最短路、最大流等問題都是運(yùn)籌學(xué)中的經(jīng)典問題[1-5]，在運(yùn)籌學(xué)教學(xué)特別是運(yùn)籌學(xué)實(shí)驗(yàn)中需要學(xué)生掌握這些經(jīng)典問題的軟件求解[6-8]。目前國內(nèi)高校在運(yùn)籌學(xué)實(shí)驗(yàn)中最常見的工具主要有Excel、WinQSB、Matlab和Lingo軟件。其中Excel功能相對比較簡單，適用于小型問題的求解演示[9]。WinQSB主要是采用模塊化的程序進(jìn)行演示，可擴(kuò)展性較差且在國內(nèi)應(yīng)用相對較少[10]。Matlab軟件功能非常強(qiáng)大，對于一些工科類學(xué)科而言具有不可替代的地位，然而在運(yùn)籌學(xué)教學(xué)過程中由于Matlab軟件對于輸入約束條件都要求采用矩陣乘積形式，這對于一般形式的優(yōu)化模型造成了不小的轉(zhuǎn)換困難[11-12]。而Lingo軟件在功能方面比較單一，對于優(yōu)化結(jié)果的圖形化顯示方面不如Matlab強(qiáng)大[13-14]。本文介紹在Matlab軟件平臺(tái)上開發(fā)的用于求解最優(yōu)化問題的Yalmip工具箱，它不僅可以利用Matlab強(qiáng)大的計(jì)算能力，調(diào)用Matlab中各種工具箱中的函數(shù)，而且對其他優(yōu)化求解器(如Cplex和Gurobi等)提供了一種統(tǒng)一的建模調(diào)用方案。

利用YALMIP工具箱結(jié)合Matlab軟件建立相應(yīng)的模型在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)過程中是一種新的嘗試。本文闡述了利用Yalmip工具箱求解運(yùn)籌學(xué)經(jīng)典問題的方法，并結(jié)合實(shí)例說明了Yalmip工具箱在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中的具體應(yīng)用。

1 YALMIP簡介

YALMIP是Lofberg開發(fā)的一個(gè)免費(fèi)Matlab工具箱，它提供了關(guān)于凸優(yōu)化與非凸優(yōu)化問題的一種高級建模求解語言。YALMIP不但包含基本的線性規(guī)劃求解算法，如linprog(線性規(guī)劃)、bintprog(二值線性規(guī)劃)、bnb(分支定界算法)等，它還提供了對Cplex、Gurobi、Glpk、Lpsolve等求解工具箱的包裝。通常，不同的求解器對于優(yōu)化問題的描述并不一致，在使用時(shí)需要較多的學(xué)習(xí)成本并且容易出錯(cuò)。而Yalmip真正實(shí)現(xiàn)了建模和算法二者的分離，提供了一種簡單而統(tǒng)一的建模語言和編程接口，以實(shí)現(xiàn)不同求解器之間的集成。因此，我們只需要知道在Matlab下如何用Yalmip的方式建模，而不需要針對每一種工具箱學(xué)習(xí)新的建模語法。

Yalmip工具箱可以通過下載網(wǎng)址http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Installation獲得。下載安裝包并解壓后，通過如下步驟在Matlab軟件中設(shè)置引用路徑：① 點(diǎn)擊File中的Set Path菜單；② 點(diǎn)擊Add with subfolders菜單，找到解壓好的文件夾Yalmip；③ 點(diǎn)擊確定、保存。對于外部的求解器，可采用類似方式設(shè)置Matlab路徑。

Yalmip的建模語法簡單到只有四個(gè)最基本的命令：

(1) 創(chuàng)建決策變量。

>>x=sdpvar(m,n,[option]): 創(chuàng)建m*n的連續(xù)型決策變量矩陣，option是對矩陣的一些參數(shù)指定；

>>x=intvar(m,n,[option]): 創(chuàng)建m*n的整數(shù)型決策變量矩陣；

>>x=binvar(m,n,[option]): 創(chuàng)建m*n的0-1型決策變量矩陣。

注：若決策變量x是n*n的方陣，如果沒有對決策變量進(jìn)行參數(shù)指定，則默認(rèn)x為對稱矩陣，否則需要加以參數(shù)指定，即以x=sdpvar(n,n,’full’)的形式定義，整數(shù)型與0-1型類似。

(2) 約束條件設(shè)置。

>>F=set(constraint,[tag]): 創(chuàng)建一個(gè)以constraint指定的約束，可選參數(shù)tag可以給該約束指定一個(gè)字符串標(biāo)記。其中constraint的表示極為自然，例如有x1+x2+x3<=10的約束，直接寫成：

>>x=sdpvar(3,1);

>>F=set(x(1)+x(2)+x(3)<=10);

如果要添加多個(gè)約束可以直接用+連接：

>>F=set(constraint1,[tag1])+set(constraint2,[tag2])。

(3) 參數(shù)配置。

>>ops=sdpsettings(option1,value1,option2,value2,…);

例如：>>ops=sdpsettings(‘solver’,’Cplex’,verbose’,2);

參數(shù)‘solver’指定程序用Cplex求解器(必須已安裝，否則報(bào)錯(cuò))，如果不指定’solver’參數(shù)，Yalmip會(huì)根據(jù)決策變量類型自動(dòng)選擇最適合的求解器；’verbose’指定顯示冗余度(冗余度越大，求解過程信息越詳細(xì))。

(4) 求解。

>>result=solvesdp(F,f,ops); 求解一個(gè)最小化數(shù)學(xué)規(guī)劃問題，該問題的目標(biāo)函數(shù)由f指定，約束由F指定，ops指定求解參數(shù)，最后的結(jié)果則存儲(chǔ)在result結(jié)構(gòu)體中，可用double命令顯示。

>>x_star=double(x);

>>f_star=double(f);

2 線性規(guī)劃問題

線性規(guī)劃是運(yùn)籌學(xué)中最重要的一個(gè)分支，幾乎所有的優(yōu)化求解器都可以求解線性規(guī)劃問題，下面先給出線性規(guī)劃問題的數(shù)學(xué)模型：

minZ=CX

例1 minZ=12x1+5x2+8x3

與該線性規(guī)劃問題相對應(yīng)的Yalmip程序?yàn)椋?/p>

C=[12 5 8];

A=[2 3 1;4 1 5];

b=[30; 15];

x=sdpvar(3,1);

f=C*x;

F=set(A*x>=b)+set(x>=0);

result=solvesdp(F,f);

x_star=double(x)

f_star=double(f)

求得結(jié)果為：最優(yōu)解x_star=[0;9.6429;1.0714]，最優(yōu)目標(biāo)函數(shù)值為f_star=56.7857。

3 運(yùn)輸問題

運(yùn)輸問題模型是運(yùn)籌學(xué)中的經(jīng)典模型之一，運(yùn)輸問題的一般描述如下：某種物資有m個(gè)產(chǎn)地和n個(gè)銷地，產(chǎn)地i到銷地j的單位物資運(yùn)輸費(fèi)用為cij，各個(gè)產(chǎn)地的產(chǎn)量分別為ai，各個(gè)銷地的銷量分別為bj，要求在滿足產(chǎn)銷約束條件下使總運(yùn)輸費(fèi)用最少的運(yùn)輸方案。

例2 現(xiàn)有4個(gè)產(chǎn)地，5個(gè)銷地，其中cij、ai、bj見表1，求該運(yùn)輸問題的解。

表1 運(yùn)輸參數(shù)表

相應(yīng)的Yalmip程序?yàn)椋?/p>

C=[1 3 5 7 13; 6 4 3 14 8; 13 3 1 7 4; 1 10 12 7 11];

a_i=[40;50;30;80];

b_j=[10;20;15;18;25];

x=sdpvar(4,5,'full');

f=sum(sum(C.*x));

F=set(sum(x,2)<=a_i)+set(sum(x,1)>=b_j')+

set(x>=0); %sum(x,2)表示關(guān)于矩陣x按行求和，

%sum(x,1)表示關(guān)于矩陣x按列求和。

result=solvesdp(F,f);

x_star=double(x)

f_star=double(f)

求得結(jié)果為：

4 背包問題

背包問題是一類重要的整數(shù)規(guī)劃模型，其一般描述如下：設(shè)背包的載重量和容積分別為W和V，第i種物品的重量、體積和數(shù)量分別為wi、vi和ci，該種物品的效用為ei，在背包載重量和容積限制條件下，使得背包裝載物品總效用最大化。

例3 有10種物品的質(zhì)量wi、體積Vi、數(shù)量ci以及效用ei見表2所示，背包載重量為80，容積為60，求背包裝載物品總效用最大化的方案。

表2 物品屬性表

相應(yīng)的Yalmip程序?yàn)椋?/p>

wi=[17,19,3,19,13,2,6,11,20,20];

Vi=[2,10,10,5,9,2,5,10,8,10];

ci=[5,2,4,3,5,4,3,1,5,3];

ei=[8,1,11,12,9,10,9,5,8,3];

W=80;

V=60;

x=intvar(10,1,'full');

f=ei*x;

F=set(wi*x<=W)+set(Vi*x<=V)+

set(0<=x’<=ci);

result=solvesdp(F,-f); %最大化目標(biāo)函數(shù)

x_star=double(x’)

f_star=double(f)

求得結(jié)果為：

x_star=[1 0 3 1 0 4 3 0 0 0]，f_star=120。

5 指派問題

指派問題也是一類重要的整數(shù)規(guī)劃問題，其一般描述如下：現(xiàn)要安排n個(gè)人去完成n項(xiàng)不同的工作，第i個(gè)人完成第j項(xiàng)工作所需時(shí)間為cij，要求每人完成一項(xiàng)工作，每項(xiàng)工作只由一人完成，求使得完成所有工作總時(shí)間最少的指派方案。

例4 現(xiàn)有5人完成5項(xiàng)工作所需時(shí)間如表3所示，要求每人只做一項(xiàng)工作，每項(xiàng)工作只由一人完成且所用總時(shí)間最少的指派方案。

表3 時(shí)間效率表

相應(yīng)的Yalmip程序?yàn)椋?/p>

cij=[12 7 9 7 9;8 9 6 6 6;7 17 12 14 9;15 14 6 6 10; 4 10 7 10 9];

xij=binvar(5,5,'full');

f=sum(sum(cij.*xij));

F=set(sum(xij,1)==1)+set(sum(xij,2)==1);

result=solvesdp(F,f);

x_star=double(xij)

f_star=double(f)

求得結(jié)果為：

6 最短路問題

最短路問題的一般提法如下：設(shè)G=(V,E)為連通圖，圖中各邊[vi,vj]有權(quán)l(xiāng)ij(lij=∞表示vi,vj不相鄰)，vs,vt為圖中任意兩點(diǎn)，設(shè)μ是G中從vs到vt的一條路定義路μ的權(quán)為μ中所有邊的權(quán)之和，記為ω(μ)。最短路問題就是要從所有從vs到vt的道路中，求一條從vs到vt的所有道路中總權(quán)最小的道路μ0，即

例5 設(shè)有一批貨物要從V1運(yùn)到V7，網(wǎng)絡(luò)圖見圖1，邊上的數(shù)字表示該路距離，求最短距離的運(yùn)輸路線。

相應(yīng)的Yalmip程序?yàn)椋?/p>

C=[0 1 4 100 100 100 100; 1 0 2 4 2 5 100; 4 2 0 100 100 1 100; 100 4 100 0 2 100 100; 100 2 1 2 0 3 2; 100 5 1 100 3 0 6; 100 100 100 100 2 6 0];

x=binvar(7,7,’full’);

F=set(sum(x(1,:)-sum(x(:,1))==1)+set(sum(x(7,:))-sum(x(:,7))==-1);

fori=2:6

F=F+set(sum(x(i,:))-sum(x(:,i))==0);

end

f=sum(sum(C.*x));

result=solvesdp(F,f);

x_star=double(x)

f_star=double(f)

結(jié)果為：x(1,2)=1,x(2,5)=1,x(5,7)=1;相應(yīng)的最短路線為V1→V2→V5→V7，最短距離為5。

圖1 非線性狀態(tài)觀測器框圖

7 最大流問題

設(shè)有向圖G=(V,E)，G的每一條邊(vi,vj)上的非負(fù)數(shù)cij稱為邊的容量，僅有一個(gè)入次為0的點(diǎn)vs稱為發(fā)點(diǎn)(源)，一個(gè)出次為0的點(diǎn)vt稱為收點(diǎn)(匯)，其余的點(diǎn)為中間點(diǎn)，這樣的網(wǎng)絡(luò)G稱為容量網(wǎng)絡(luò)，記作：G=(V,E,C)。當(dāng)每條邊上的實(shí)際流量小于等于其容量時(shí)，流動(dòng)才能順利進(jìn)行。對于給定的容量網(wǎng)絡(luò)，如何求出從發(fā)點(diǎn)到收點(diǎn)的最大可行流量就是最大流問題。

例6 假設(shè)某山區(qū)有6個(gè)村莊。村莊與村莊之間雖有公路，但是通行的能力有很大差異，邊上的數(shù)字小則表示通行能力差，反之則表示通行能力強(qiáng)(見圖2)。試求出從村莊1～6之間的最大流。

圖2

相應(yīng)的Yalmip程序?yàn)椋?/p>

C=[0 4 0 0 6 0;0 0 4 4 1 0;0 0 0 2 2 0;0 0 0 0 0 9;0 0 0 6 0 7;0 0 0 0 0 0];

x=intvar(6,6,'full');

F=set(sum(x(:,1))==0)+set(sum(x(6,:))==0)+set(0<=x<=C);

fori=2:5

F=F+set(sum(x(i,:))-sum(x(:,i))==0);

end

f=sum(x(s,:));

result=solvesdp(F,-f);

f_star=double(f)

x_star=double(x)

結(jié)果為：

8 最小費(fèi)用最大流問題

例7 假設(shè)從倉庫V4到商店V5要運(yùn)送8個(gè)流量的貨物，邊上左邊數(shù)字表示線段最大通過能力，右邊數(shù)字表示通過單位流量的費(fèi)用(見圖3)，試求出費(fèi)用最小的運(yùn)輸方案。

圖3

相應(yīng)的Yalmip程序?yàn)椋?/p>

C=[0 0 2 0 7;5 0 10 0 0;0 0 0 0 4;10 8 0 0 0;0 0 0 0 0];

D=[0 0 6 0 1;2 0 3 0 0;0 0 0 0 2;4 1 0 0 0;0 0 0 0 0];

x=intvar(5,5,'full');

F=set(sum(x(:,4))==0)+set(sum(x(5,:))==0)+set(0<=x<=C)+set(sum(x(4,:))==8);

fori=1:3

F=F+set(sum(x(i,:))-sum(x(:,i))==0);

end

f=sum(sum(D.*x));

result=solvesdp(F,f);

f_star=double(f)

x_star=double(x)

結(jié)果為：

9 結(jié) 語

在運(yùn)籌學(xué)教學(xué)過程中結(jié)合實(shí)驗(yàn)教學(xué)要求，利用YALMIP工具箱在Matlab環(huán)境中求解問題是一種新的嘗試。由于YALMIP工具箱提供了一種簡潔而統(tǒng)一的建模語法，比Matlab原有語言的表達(dá)方法更為易于掌握，可使學(xué)生更為關(guān)注問題建模的本質(zhì)，而不需要在求解函數(shù)的區(qū)別上分散注意力，因此從運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)的角度來看，結(jié)合YALMIP與Matlab以用于求解運(yùn)籌學(xué)模型值得進(jìn)一步的推廣。

[1] 韓大衛(wèi). 管理運(yùn)籌學(xué)[M].6版，大連：大連理工大學(xué)出版社，2010.

[2] 胡運(yùn)權(quán)，郭耀煌. 運(yùn)籌學(xué)教程[M].4版，北京：清華大學(xué)出版社，2012.

[3] 弗雷德里克.S.希利爾. 運(yùn)籌學(xué)導(dǎo)論[M].10版，北京：清華大學(xué)出版社，2015.

[4] 韓伯棠. 管理運(yùn)籌學(xué)[M].4版，北京：高等教育出版社，2015.

[5] 卜心怡，俞武揚(yáng)，余福茂，等.管理運(yùn)籌學(xué)[M].北京：電子工業(yè)出版社，2016.

[6] 夏良玉.案例教學(xué)和上機(jī)實(shí)驗(yàn)一體化的運(yùn)籌學(xué)教學(xué)模式探討[J].科教導(dǎo)刊，2013(14)：113-115.

[7] 趙清俊，陳桂蘭.運(yùn)籌學(xué)實(shí)驗(yàn)軟件在線性規(guī)劃問題教學(xué)中的應(yīng)用[J].重慶文理學(xué)院學(xué)報(bào)，2013，32(3)：110-112.

[8] 鄧勝岳，周立前，方四林，等.數(shù)學(xué)建模和數(shù)學(xué)實(shí)驗(yàn)在《運(yùn)籌學(xué)》課程教學(xué)中的應(yīng)用研究[J].湖南理工學(xué)院學(xué)報(bào)(自然科學(xué)版)，2015，28(1)：91-94.

[9] 于瑛英.EXCEL運(yùn)籌學(xué)規(guī)劃論教學(xué)中的應(yīng)用[J].教育教學(xué)論壇，2014(10)：278-280.

[10] 鄧 萍，呂俊娜，閆 芳，等.基于QSB軟件的運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)研究[J].課程教育研究(學(xué)法教法研究)，2015(34)：21-21.

[11] 楊毓玲.基于Matlab的運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)研究[J].科技經(jīng)濟(jì)市場，2012(11)：115-116.

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

[13] 謝金星，薛 毅. 優(yōu)化建模與LindoLingo軟件[M].北京：清華大學(xué)出版社，2005.

[14] 洪 文，朱云鵑，金 震，等. Lingo在運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)中的應(yīng)用[J]. 實(shí)驗(yàn)室研究與探索，2012，31(4)：265-270.

Application of YALMIP in Experiment Teaching of Operations Research

YU Wuyang

(Management School, Hangzhou Dianzi University, Hangzhou 310018, China)

Matlab platform plays an important role in operations research experiment teaching for all kinds of classical optimization models. Since many functions within Matlab toolboxes have very strict format constraints, which result in the poor efficiency of experiment teaching when we represent experimental data into the matrix form of Matlab. Combining the YALMIP toolbox with Matlab can solve the classic models in operations research, such as linear programming, transportation problem, knapsack problem, the most short circuit problem, and so on. Concrete examples are given to illustrate the modeling method of YALMIP language. Using unified modeling language of YALMIP, it is easy to implement these classical optimization models of operations research. The method reduces the difficulty of solving the problem of models by software, and this toolbox can also be used to solve other problems in operations research experiment.

ooperations research; experiment teaching; Matlab; YALMIP toolbox

2016-11-22

杭州電子科技大學(xué)“管理科學(xué)與工程”重點(diǎn)研究基地項(xiàng)目(ZD06-201601)

俞武揚(yáng)(1974-)，男，浙江嵊州人，博士，副教授，研究方向：物流建模與優(yōu)化計(jì)算。

Tel.：0571-86878533；E-mail:yu_wuyang@163.com

O 221.6

A

1006-7167(2017)08-0274-05