YALMIP工具箱在運籌學實驗教學中的應(yīng)用

俞武揚

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

YALMIP工具箱在運籌學實驗教學中的應(yīng)用

俞武揚

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

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

運籌學； 實驗教學； Matlab； YALMIP工具箱

0 引 言

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

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

1 YALMIP簡介

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

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

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

(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的方陣，如果沒有對決策變量進行參數(shù)指定，則默認x為對稱矩陣，否則需要加以參數(shù)指定，即以x=sdpvar(n,n,’full’)的形式定義，整數(shù)型與0-1型類似。

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

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

>>x=sdpvar(3,1);

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

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

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

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

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

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

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

(4) 求解。

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

>>x_star=double(x);

>>f_star=double(f);

2 線性規(guī)劃問題

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

minZ=CX

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

與該線性規(guī)劃問題相對應(yīng)的Yalmip程序為：

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)目標函數(shù)值為f_star=56.7857。

3 運輸問題

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

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

表1 運輸參數(shù)表

相應(yīng)的Yalmip程序為：

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程序為：

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); %最大化目標函數(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個人去完成n項不同的工作，第i個人完成第j項工作所需時間為cij，要求每人完成一項工作，每項工作只由一人完成，求使得完成所有工作總時間最少的指派方案。

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

表3 時間效率表

相應(yīng)的Yalmip程序為：

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為圖中任意兩點，設(shè)μ是G中從vs到vt的一條路定義路μ的權(quán)為μ中所有邊的權(quán)之和，記為ω(μ)。最短路問題就是要從所有從vs到vt的道路中，求一條從vs到vt的所有道路中總權(quán)最小的道路μ0，即

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

相應(yīng)的Yalmip程序為：

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

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

圖2

相應(yīng)的Yalmip程序為：

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 最小費用最大流問題

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

圖3

相應(yīng)的Yalmip程序為：

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é) 語

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

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

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

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

[4] 韓伯棠. 管理運籌學[M].4版，北京：高等教育出版社，2015.

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

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

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

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

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

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

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

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

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

[14] 洪 文，朱云鵑，金 震，等. Lingo在運籌學實驗教學中的應(yīng)用[J]. 實驗室研究與探索，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

杭州電子科技大學“管理科學與工程”重點研究基地項目(ZD06-201601)

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

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

O 221.6

A

1006-7167(2017)08-0274-05