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只能是向量,也就是单下标变量,然后用向量和矩阵来表达目标函数和约束条件。
然而,许多问题(如指派问题和运输问题)由于参数和决策变量是双下标变量,必须在基本的数学模型的基础上进行变换才能求解,这样得到的等式约束和不等式约束的系数矩阵规模就非常庞大,当然由MATLAB计算问题不大,但转换工作完全要由人工完成,工作量大而且容易出错,因此在这一块效率不高。
而LINGO有自己的建模语言,在建立了集合的基础上,能够高效表达目标函数和各种约束条件。所写的模型基本上可以看作是对数学模型的翻译,不需要太多的转换。
不妨以指派问题为例,对MATLAB和LINGO进行一下对比。
指派问题可描述为:有n项任务要分配给n个人去做,每人只完成一项任务,每个任务也只由一个人完成。已知第个人完成第 项任务所需的时间
例如:任务为1,2,3,4,人员为1,2,3,4,效率矩阵为:
引入决策变量
由于用MATLAB求解线性规划或混合整数规划时,决策变量只能是向量(即一维数组),所以需要把上述数学模型中的双下标常量和决策变量都转化成单下标变量。
也就是说要把
对应的效率矩阵
这样就把目标函数修改成了:
相应地:
约束条件Misplaced&所对应的四个等式约束:
约束条件Misplaced&所对应的四个等式约束:
这样才能得到MATLAB所需要的等式约束矩阵
此时才可以用下面的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个约束条件。也就对应着第二组约束条件:Misplaced&
@FOR(AGENTS(I):
@FOR(TASKS(J) : @GIN(X(I,J)))
);
表示决策变量 是0-1变量,一共有16个约束条件。
对应如下约束条件Misplaced&:
所以,通过上述对照,可以看出基本上LINGO模型就是对指派问题数学模型的逐句翻译。因此LINGO建模语言实际上有更高的抽象性。尽管在计算时LINGO也会将其转换成和MATLAB一样的矩阵形式进行计算,但这一步是由LINGO自动进行的,不需要人工转换。特别地,如果我们遇到了一个100个人100项任务的指派问题,只需要把原模型中的N=4转换成N=100,然后将COST矩阵的数据输入或复制到模型中即可,模型的其他语句完全不需要修改。所以这种模型的通用性非常好,从建立模型到求解的整体效率比较高,对人来说难度也非常小。开源的规划求解软件GLPK也在这个层面上做到了高度的抽象,只是GLPK不能用于求解非线性规划问题。
结论:以后我本人只要能用LINGO或GLPK解决的线性规划或整数规划问题都尽量用LINGO或GLPK解决,而不用MATLAB。
当然我写这些不是为了说明MATLAB不强大,只是在求解有双下标变量的线性规划或整数规划问题时,需要选用更好的工具而已。只要能解决问题就好。工具是为人服务的。人要善于选用工具,而不是成为某种工具的信徒或粉丝。