標籤:

Lingo和Matlab在解決最優化問題的時候的優缺點?

先說下我的看法吧 。

在我看來,Matlab解決優化問題的時候,需要自己去選擇演算法、運算元、初始條件等;而Lingo只需要列好式子就可以了。從這點看來,Lingo方便多了。我不知道Lingo的這種方式適應性強不強,以及它是怎麼根據算式自動選擇相應的演算法的。用Matlab,適應性肯定更強,但需要自己事先對各種演算法掌握。我肯定沒這種能力,從這點看Lingo適合我。打個比方,Matlab和Lingo的這點差別相當於手動擋和自動擋的差別。

另一方面,Matlab裡面的目標函數不一定非得是數學表達式,可以是一串代碼;而Lingo則必須列成數學的式子。所以說,有些場景,Lingo就不適用了。

總體而言,當遇到能列出數學式子的情況下,我選擇Lingo,因為我對那些優化演算法的特點都不了解,也不怎麼會選擇初始點。還是說,這種情況下Matlab也是夠用的,隨便選擇一個優化演算法,和初始點,也能達到Lingo那樣的效果呢?如果是這樣,我就不需要再用Lingo了。


謝邀。這周正好把幾個問題的LINGO的模型轉換成了MATLAB模型來求解,有了比較深刻的了解。

無需多說,MATLAB在許多領域確實都很強大,在最優化這一塊也是如此。MATLAB的優化工具箱提供了大量的優化函數,可用於求解線性規劃、二次規劃、有約束和無約束條件下的非線性規劃問題,而且還集成了並行計算功能,能夠在多核處理器上有效減少計算時間。並且還提供了第三方庫KNITRO用於求解多變數非線性最優化問題。除此之外,MATLAB還提供了一個遺傳演算法工具,為使用智能優化演算法提供了方便。多種優化工具提供了解決問題的不同方法,但也會讓初學者不知如何選擇。

LINGO能夠求解線性規劃、二次規劃、整數規劃和部分非線性規劃。但與MATLAB不同,LINGO根據模型自己選擇合適的求解器,基本上不需要用戶來選擇求解器。這一點正如題主所說。至於LINGO在非線性優化方面是否能夠比得上MATLAB,我也沒有太多經驗,不好說。對於參加數學建模的同學來說,可能會用到各種數學數模,例如求解微分方程,數值計算和分析或者符號計算,即使遇到最優化問題,也往往可能是非線性優化,所以熟悉MATLAB的最優化工具箱還是非常需要的。

但作為幾乎面面俱到的數學工具軟體,MATLAB在某些專門的領域使用起來確實不如專業軟體方便,特別是在線性規劃和整數規劃方面。

對於線性規劃問題,MATLAB提供了linprog函數用改進單純型法進行計算。但對於整數規劃,至少到版本2012b,也只提供了bintprog函數用於求解0-1整數規劃,而對於一般的整數規劃問題,MATLAB並沒有提供任何求解工具,用戶通常都必須得自己編寫分支定界演算法來求解問題。或者通過安裝第三方軟體包如YALMIP,調用其他軟體如GLPK來求解。自2014b版起,MATLAB才提供了一個真正的整數規劃求解函數intlinprog,可用於求解純整數規劃和混合整數規劃。LINGO不僅能求解線性規劃,而且很早就能夠求解各種整數規劃問題。

但兩者最大的區別在於模型的表達不同。

用MATLAB求解線性規劃和整數規劃問題,需要先將問題轉化成如下標準型,其中X只能是向量,也就是單下標變數,然後用向量和矩陣來表達目標函數和約束條件。

egin{align*} min;Z=f^TX \ s.t. egin{cases} Acdot X leqslant b \ A_{eq} cdot X = b_{eq} \ lb leq X leq ub \ X(intcon) 	ext{ are integers} end{cases} end{align*}

然而,許多問題(如指派問題和運輸問題)由於參數和決策變數是雙下標變數,必須在基本的數學模型的基礎上進行變換才能求解,這樣得到的等式約束和不等式約束的係數矩陣規模就非常龐大,當然由MATLAB計算問題不大,但轉換工作完全要由人工完成,工作量大而且容易出錯,因此在這一塊效率不高。

而LINGO有自己的建模語言,在建立了集合的基礎上,能夠高效表達目標函數和各種約束條件。所寫的模型基本上可以看作是對數學模型的翻譯,不需要太多的轉換。

不妨以指派問題為例,對MATLAB和LINGO進行一下對比。

指派問題可描述為:有n項任務要分配給n個人去做,每人只完成一項任務,每個任務也只由一個人完成。已知第 個人完成第 項任務所需的時間C_{ij} (稱為效率矩陣)。問如何分配任務,使完成所有工作所用的總時間最少?

例如:任務為1,2,3,4,人員為1,2,3,4,效率矩陣為:

引入決策變數 x_{ij} ,如果讓第 i 個人去完成第 j 項任務,則 x_{ij}=1 ,否則 x_{ij}=0 。則指派問題的數學模型為:

egin{align*} min;Z=sum_{i=1}^nsum_{j=1}^n c_{ij} x_{ij} \ s.t.; egin{cases} sumlimits_{j=1}^nx_{ij}=1, i=1,2,cdots,n, \ sumlimits_{i=1}^nx_{ij}=1, j=1,2,cdots,n, \ x_{ij} in {0,1}, i=1,2,cdots,n;;j=1,2,cdots,n. end{cases} end{align*}

由於用MATLAB求解線性規劃或混合整數規劃時,決策變數只能是向量(即一維數組),所以需要把上述數學模型中的雙下標常量和決策變數都轉化成單下標變數。

也就是說要把 egin{bmatrix} x_{11}  x_{12}  x_{13}  x_{14}\ x_{21}  x_{22}  x_{23}  x_{24}\ x_{31}  x_{32}  x_{33}  x_{34}\ x_{41}  x_{42}  x_{43}  x_{44} end{bmatrix} 轉換成: egin{bmatrix} y_{1}  y_{5}  y_{9}  y_{13} \ y_{2}  y_{6}  y_{10}  y_{14} \ y_{3}  y_{7}  y_{11}  y_{15} \ y_{4}  y_{8}  y_{12}  y_{16} end{bmatrix}

對應的效率矩陣 C=egin{bmatrix} 2  15  13  4 \ 10  4  14  5 \ 9  14  16  13 \ 7  8  11  9 end{bmatrix} 就要修改為一個新的效率向量 f

f=[2,10,9,7,15,4,14,8,13,14,16,11,4,5,13,9]

這樣就把目標函數修改成了:

min;Z=sum_{i=1}^{16}f_iy_i

相應地:

約束條件 sum_{j=1}^nx_{ij}=1, i=1,2,cdots,n 所對應的四個等式約束:

egin{cases} x_{11}+x_{12}+x_{13}+x_{14} = 1\ x_{21}+x_{22}+x_{23}+x_{24} = 1\ x_{31}+x_{32}+x_{33}+x_{34} = 1\ x_{41}+x_{42}+x_{43}+x_{44} = 1 end{cases} 就要轉換成: egin{cases} y_{1}+y_{5}+y_{9}+y_{13} = 1 \ y_{2}+y_{6}+y_{10}+y_{14} = 1 \ y_{3}+y_{7}+y_{11}+y_{15} = 1 \ y_{4}+y_{8}+y_{12}+y_{16} = 1 end{cases}

約束條件 sum_{i=1}^nx_{ij}=1, j=1,2,cdots,n 所對應的四個等式約束:

egin{cases} x_{11}+x_{21}+x_{31}+x_{41} = 1\ x_{12}+x_{22}+x_{32}+x_{42} = 1\ x_{13}+x_{23}+x_{33}+x_{43} = 1\ x_{14}+x_{24}+x_{34}+x_{44} = 1 end{cases} 就要轉換成: egin{cases} y_{1}+y_{2}+y_{3}+y_{4} = 1 \ y_{5}+y_{6}+y_{7}+y_{8} = 1 \ y_{9}+y_{10}+y_{11}+y_{12} = 1 \ y_{13}+y_{14}+y_{15}+y_{16} = 1 end{cases}

這樣才能得到MATLAB所需要的等式約束矩陣 A_{eq} 和右端列向量 b_{eq}

此時才可以用下面的MATLAB代碼求解:

f=[2,10,9,7,15,4,14,8,13,14,16,11,4,5,13,9];
intcon = 1:16;
Aeq=[
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;
1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]
beq = ones(8,1);
lb=zeros(1,16);
ub=ones(1,16);

[Y,fval,exitflag] = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub);
x=reshape(Y,4,4)
fval

求解的結果是:

目標函數值為28分鐘,具體方案是:第1個人去完成任務4,第2個人去完成任務2,第3個人去完成任1,第4個人去完成任務3。

如果用LINGO來求解這個指派問題,只需要會建立集合及其屬性,其它就基本上是對數學模型的直接翻譯,無需複雜的轉換。

LINGO模型如下:

MODEL:

DATA:
N = 4;
ENDDATA

SETS:

AGENTS/1..N/;
TASKS/1..N/;
MATRIX(AGENTS,TASKS):COST, X;

ENDSETS

DATA:

COST =
2,15,13,4,
10,4,14,5,
9,14,16,13
7,8,11,9;

ENDDATA

MIN = @SUM(AGENTS(I) :
@SUM(TASKS(J): COST(I,J)*X(I,J))
);

@FOR(AGENTS(I):
@SUM(TASKS(J):X(I,J)) = 1
);

@FOR(TASKS(J):
@SUM(AGENTS(I):X(I,J)) = 1
);

@FOR(AGENTS(I):
@FOR(TASKS(J) : @GIN(X(I,J)))
);

END

得到的結果是:

這一方案與MATLAB求出的完全相同。

特別要提醒大家注意LINGO對於約束條件表達。由於使用了集合遍歷函數,每一條約束條件的表達實際上表達了一組約束。

@FOR(AGENTS(I):
@SUM(TASKS(J):X(I,J)) = 1
);

表示每個人只完成一項任務,本問題只有4個人,所以相當於4個約束條件。就對應著第一組約束條件:

@FOR(TASKS(J):
@SUM(AGENTS(I):X(I,J)) = 1
);

表示每項任務也只由一個人來完成,本問題只有4項任務,所以也相當於4個約束條件。也就對應著第二組約束條件:sum_{i=1}^nx_{ij}=1, j=1,2,cdots,n

@FOR(AGENTS(I):
@FOR(TASKS(J) : @GIN(X(I,J)))
);

表示決策變數 x_{ij} 是0-1變數,一共有16個約束條件。

對應如下約束條件: x_{ij} in {0,1}, i=1,2,cdots,n;;j=1,2,cdots,n

所以,通過上述對照,可以看出基本上LINGO模型就是對指派問題數學模型的逐句翻譯。因此LINGO建模語言實際上有更高的抽象性。儘管在計算時LINGO也會將其轉換成和MATLAB一樣的矩陣形式進行計算,但這一步是由LINGO自動進行的,不需要人工轉換。特別地,如果我們遇到了一個100個人100項任務的指派問題,只需要把原模型中的N=4轉換成N=100,然後將COST矩陣的數據輸入或複製到模型中即可,模型的其他語句完全不需要修改。所以這種模型的通用性非常好,從建立模型到求解的整體效率比較高,對人來說難度也非常小。開源的規劃求解軟體GLPK也在這個層面上做到了高度的抽象,只是GLPK不能用於求解非線性規劃問題。

本周我把自己用LINGO編寫的模型轉換成MATLAB來求解,由於等式約束矩陣 A_{eq} 有112行57列,所以人工轉換花了將近6個小時,累得我頭暈眼花,計算速度卻與LINGO基本相當,計算結果等價。如果你是在參加數學建模,你花得起有這麼多時間嗎?即使是平時研究或解決問題,不麻煩嗎?

結論:以後我本人只要能用LINGO或GLPK解決的線性規劃或整數規劃問題都盡量用LINGO或GLPK解決,而不用MATLAB。

當然我寫這些不是為了說明MATLAB不強大,只是在求解有雙下標變數的線性規劃或整數規劃問題時,需要選用更好的工具而已。只要能解決問題就好。工具是為人服務的。人要善於選用工具,而不是成為某種工具的信徒或粉絲。


謝邀,以我最近不多的經驗看,最近在做整數線性規劃問題,matlab可以處理的矩陣大小有限,lingo可以處理稍大規模的。如果是想得出精確解,lingo得出的解比matlab要準確。


推薦閱讀:

matlab畫圖,明明標記了11個點的坐標,最後畫出來的圖卻只有10個點,坐標沒有重疊。這是為什麼?
(新手提問)matlab中@的含義?
MATLAB中如何畫出下圖?文獻中的圖片如補充說明所示,謝謝。?
matlab計算積分無解?
matlab中有哪些有趣的命令?

TAG:MATLAB | lingo |