0%

YALMIP工具箱——Matlab上解决规划问题的大杀器

发表于 更新于 分类于 阅读次数：

数学建模过去很多年了，但是YALMIP工具箱的易用性仍然让我影响深刻，用过这个之后再想想现在用的z3约束求解真的是弱爆了，什么时候Python上面能有一个那么好用的规划工具就好了>_<

简介

规划问题可以算是数模竞赛常见的问题(作为信工院的小白,实在佩服数科院的牛人们能把任何问题搞成优化问题).由于MATLAB自带的规划工具箱并不好用,部分同学不得不用Lingo等软件专门解决规划问题,但Lingo的语法可读性并没有matlab好.YALMIP解决了这个问题.

简单来说,YALMIP是一个MATLAB上的一个工具箱.它让你用MATLAB语法优雅地解决各种规化问题.(MATLAB的函数都能用，妈妈再也不用担心我的学习orz)

往细了说,它将优化问题进行分类,在底层通过B/S模式调用外部的各种解析器(每一解析器可以对应一类或多类问题,如Lingo的解析器Lindo就在其中),而在外部,你不需要了解各种解析器的具体语法,只需掌握YALMIP的语法就可轻松的调用他们.由此解决大多数规划问题.
yal

安装

  1. 确保MATLAB版本在2015a及以上.

  2. 点击此处下载zip安装包,随后解压到MATLAB目录下,如果你的MATLAB安装在默认目录下,那么结果如下:

path

  1. 将YALMIP的目录加入到MATLAB的PATH中,其中包括:

addPath

  1. 验证YALMIP的安装工作

    在MATLAB中输入yalmiptest,若出现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    +++++++++++++++++++++++++++++++++++++++++++++++
    |       Searching for installed solvers       |
    +++++++++++++++++++++++++++++++++++++++++++++++
    |        Solver|   Version/module|      Status|
    +++++++++++++++++++++++++++++++++++++++++++++++
    |       LINPROG|                 |       found|
    |      QUADPROG|                 |       found|
    |        LMILAB|                 |       found|
    |       FMINCON|        geometric|       found|
    |                .......                      |
    |         FRLIB|                 |   not found|
    +++++++++++++++++++++++++++++++++++++++++++++++

    那么恭喜你,YALMIP安装成功!

  2. 安装基础的解析器
    细心的朋友应该发现了,当我们执行yalmiptest时,实际上是检查可使用的解析器.下面就介绍一些常用的解析器以及安装

    Gurobi/CPLEX:Gurobi和CPLEX适用的范围差不多,所以上只要装一个就行.性能的话还是CPLEX会好一点(毕竟IBM,但差别不大),两者都有针对学术的免费版本,CPLEX学术版本的获取需要以教师身份注册,而Gurobi是需要教育网IP验证.同时Gurobi还有免费的社区版本(半年).各版本的区别都在于支持的变量数上,然而Gurobi的社区版本个人以为完全可以满足国赛的需要了(超了那个数量自己想想思路有没有问题).

    以下是Gurobi的安装流程.

    1. 先到Gurobi官网上注册账号.
    2. 申请对应版本的序列号.
    3. 下载对应版本Gurobi,安装后重启.
    4. Win+R运行cmd回车后 输入激活码grbgetkey xxx-xxx-xxx-xxx.
    5. 在MATLAB下运行Gurobi/win/matlab/gurobi_setup.m 同时保存PATHsavepath

    6. 在运行yalmiptest应该看到Gurobi变成found了.

      当然,如果你确实需要一个支持大量变量的解析器,那么你只能用mosek了,只需要edu邮箱验证,然而解题速度会慢很多.

基本使用

  1. 设未知量

    1
    x = sdpvar(n,m); %生成a行b列的未知量

    之前也说过YALMIP的未知量有3中类型.分别为

    • sdpvar %实型
    • intvar %整型
    • binvar %0-1型
      需要混合规划多设几个变量就行了

  2. 约束条件, 例如:

    1
    F = [-2 <= x <= 2];

  3. 写目标函数

    1
    obj = x(1)^2+x(2)^2;

  4. 求解

    1
    optimize(F,obj[,options]);

    F为约束,obj为目标函数(默认求最小值),options可选择求解器,改变输出方式,如:

    1
    optimize(F,obj,sdpsettings('solver','gurobi','verbose',2));

    指定solver为Gurobi,不打印解析过程.

  5. 获取结果 
    1
    opt=value(x); %x的值

具体案例

案例一:求 x^2+y^2在x,y∈[-2,2]上的最小值

1
2
3
4
5
6
7
8
9
10
11
%生成2*1的矩阵变量
x = sdpvar(2,1);
%限制条件
F = [-2 <= x <= 2];
%目标函数
obj = x(1)^2+x(2)^2;
%求解
optimize(F,obj);
%取得值以及对应的x的值
optobj = value(obj)
optx = value(x)

结果如下(我的gurobi过期了,以下为MATLAB自带求解器结果)

1
2
3
4
5
optobj =
   1.5449e-43
optx =
   1.0e-21 *
    0.2779    0.2779

案例二:指派问题,A,B,C为3个员工,P,Q,R为3样工作,成本表如下:

A B C
P 9 6 2
Q 3 1 4
R 5 6 10

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
%设x(a,b)==1为a做b工作
x=binvar(3,3);
%成本矩阵
work=[9,6,2;3,1,4;5,6,10];
%限制条件,每人只能做一份工作
F=[sum(x)==1];
%目标函数,总花费最小
obj=sum(sum(x.*work));
%启动求解器
optimize(F,obj);
%获取结果
optx=value(x)
optObj=value(obj)

结果如下:

1
2
3
4
5
6
7
optx =
 0     0     1
 0     1     0
 1     0     0

optObj =
 8

总结

YALMIP让我们用MATLAB语言方便地调用专业的求解器,而借助于MATLAB自带的一些函数,我们可以更容易的解决各种规划问题.

但有一点需要注意,MATLAB的语法虽好用,但也不是所有函数都可以与YALMIP结合,例如神经网络,模拟退火的函数是不可以当做限制函数或限制条件参与规划的.