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)對(duì)于運(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)典模型的求解，對(duì)線性規(guī)劃、運(yùn)輸問(wèn)題、背包問(wèn)題、最短路問(wèn)題等等結(jié)合具體例子說(shuō)明了YALMIP語(yǔ)言的建模方法。利用YALMIP的統(tǒng)一建模語(yǔ)言，很容易對(duì)各種運(yùn)籌學(xué)典型問(wèn)題的模型加以實(shí)現(xiàn)，從而降低了利用軟件解決模型問(wèn)題的難度，同時(shí)也對(duì)解決運(yùn)籌學(xué)實(shí)驗(yàn)中的其它問(wèn)題有借鑒作用。

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

0 引 言

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

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

1 YALMIP簡(jiǎn)介

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

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

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

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

>>x=sdpvar(m,n,[option]): 創(chuàng)建m*n的連續(xù)型決策變量矩陣，option是對(duì)矩陣的一些參數(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的方陣，如果沒(méi)有對(duì)決策變量進(jìn)行參數(shù)指定，則默認(rèn)x為對(duì)稱矩陣，否則需要加以參數(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的約束，直接寫(xiě)成：

>>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’指定顯示冗余度(冗余度越大，求解過(guò)程信息越詳細(xì))。

(4) 求解。

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

>>x_star=double(x);

>>f_star=double(f);

2 線性規(guī)劃問(wèn)題

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

minZ=CX

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

與該線性規(guī)劃問(wèn)題相對(duì)應(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)輸問(wèn)題

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

例2 現(xiàn)有4個(gè)產(chǎn)地，5個(gè)銷(xiāo)地，其中cij、ai、bj見(jiàn)表1，求該運(yùn)輸問(wè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 背包問(wèn)題

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

例3 有10種物品的質(zhì)量wi、體積Vi、數(shù)量ci以及效用ei見(jiàn)表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 指派問(wèn)題

指派問(wèn)題也是一類重要的整數(shù)規(guī)劃問(wèn)題，其一般描述如下：現(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 最短路問(wèn)題

最短路問(wèn)題的一般提法如下：設(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)之和，記為ω(μ)。最短路問(wèn)題就是要從所有從vs到vt的道路中，求一條從vs到vt的所有道路中總權(quán)最小的道路μ0，即

例5 設(shè)有一批貨物要從V1運(yùn)到V7，網(wǎng)絡(luò)圖見(jiàn)圖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)觀測(cè)器框圖

7 最大流問(wèn)題

設(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)行。對(duì)于給定的容量網(wǎng)絡(luò)，如何求出從發(fā)點(diǎn)到收點(diǎn)的最大可行流量就是最大流問(wèn)題。

例6 假設(shè)某山區(qū)有6個(gè)村莊。村莊與村莊之間雖有公路，但是通行的能力有很大差異，邊上的數(shù)字小則表示通行能力差，反之則表示通行能力強(qiáng)(見(jiàn)圖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)用最大流問(wèn)題

例7 假設(shè)從倉(cāng)庫(kù)V4到商店V5要運(yùn)送8個(gè)流量的貨物，邊上左邊數(shù)字表示線段最大通過(guò)能力，右邊數(shù)字表示通過(guò)單位流量的費(fèi)用(見(jiàn)圖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ǔ)

在運(yùn)籌學(xué)教學(xué)過(guò)程中結(jié)合實(shí)驗(yàn)教學(xué)要求，利用YALMIP工具箱在Matlab環(huán)境中求解問(wèn)題是一種新的嘗試。由于YALMIP工具箱提供了一種簡(jiǎn)潔而統(tǒng)一的建模語(yǔ)法，比Matlab原有語(yǔ)言的表達(dá)方法更為易于掌握，可使學(xué)生更為關(guān)注問(wèn)題建模的本質(zhì)，而不需要在求解函數(shù)的區(qū)別上分散注意力，因此從運(yùn)籌學(xué)實(shí)驗(yàn)教學(xué)的角度來(lái)看，結(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ī)劃問(wèn)題教學(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ì)市場(chǎng)，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