Matlab 优化算法 - 整数规和多目标规划

优化算法-整数规与多目标规划

整数规划

概念

全部变量限制为整数的规划问题，称为纯整数规划；
部分变量限制为整数的规划问题，称为混合整数规划；
变量只取0或1的规划问题，称为0-1整数规划。

整数规划问题，建议使用Lingo软件求解。

%{
Lingo变量界定函数实现对变量取值范围的附加限制，共4种.
@bin(x)             限制x为0或1
@bnd(（L,x,U)       限制L=<x<=U
@free(x)            取消对变量x的默认下界为0的限制，即x可以取任意实数
@gin(x)             限制x为整数
在默认情况下，LINGO规定变量是非负的，也就是说下界为0，上界为+0。
@free取消了默认的下界为0的限制，使变量也可以取负值。
@bnd用于设定一个变量的上下界，它也可以取消默认下界为0的约束。
%}

常用的整数规划问题解法有：

1. 分枝定界法：可求纯或混合整数线性规划。
2. 割平面法：可求纯或混合整数线性规划。
3. 隐枚举法：用于求解0-1整数规划，有过滤法和分枝法。
4. 匈牙利法：解决指派问题（0-1规划特殊情形）
5. 蒙特卡罗法：求解各种类型规划。

例题

0-1规划

model:
    max = 3*x1-2*x2+5*x3;
    x1+2*x2-x3<=2;
    x1+4*x2+x3<=4;
    x1+x2<=3;
    4*x2+x3<=6;
    @ bin(x1);
    @ bin(x2);
    @ bin(x3);
end

%@bin(x)  限制x为0或1;

整数规划

model:
max = 5*x1+8*x2;
x1+x2<=6;
5*x1+9*x2<=45;
@ gin(x1);
@ gin(x2);
end

% @gin(x)   限制x为整数

蒙特卡罗法（随机取样法）

1. 前面的方法，主要是针对线性整数规划而言，对于非线性整数规划没有通用的有效解法。
2. 整数规划由于限制变量是整数，增加了求解难度，但整数解是有限个，所以可以采用枚举法。
3. 当枚举个数很多时，显性枚举是不现实的，但利用蒙特卡罗随机取样法，在一定的计算量下是可以得到满意解的。
4. 注意点 通常使用lingo处理规划问题，matlab虽然也能够解决问题，都是没有lingo效果好。
   

lingo的一些概念

%sets集合
sets:
    row/1..4/:b;
    col/1..5/:c1,c2,x;
    link(row,col):a;
endsets

% row生成1x4的矩阵b,col生成1x5的矩阵c1,c2,x;
% link(A,B):VAR; %!VAR就是一个A*B的矩阵;
% 生成一个row*col的矩阵 记作a

% 数据
data:
c1 = 1,1,3,4,2;
c2 = -8,-2,-3,-1,-2;
a = 1 1 1 1 1
    1 2 2 1 6
    2 1 6 0 0
    0 0 1 1 5;
b=400,800,200,200;
enddata 
 
%规划解答 集合

max  = @sum(col:c1*x^2+c2*x);
@for(row(i):@sum(col(j):a(i,j)*x(j))<=b(i));
@for(col:@gin(x));
@for(col:@bnd(0,x,99));

例题lingo代码

model:

!集合sets;

sets:
    row/1..4/:b;
    col/1..5/:c1,c2,x;
    link(row,col):a;
endsets

!数据源data;


data:
c1 = 1,1,3,4,2;
c2 = -8,-2,-3,-1,-2;
a = 1 1 1 1 1
    1 2 2 1 6
    2 1 6 0 0
    0 0 1 1 5;
b=400,800,200,200;
enddata

max  = @sum(col:c1*x^2+c2*x);
@for(row(i):@sum(col(j):a(i,j)*x(j))<=b(i));
@for(col:@gin(x));
@for(col:@bnd(0,x,99));

end


!@sum(setname:expression_list) 其中 setname 是要遍历的集合  expression_list是表达(完成函数表达式的编写) 有且仅有一个 sum进行求和操作
max  = @sum(col:c1*x^2+c2*x)  %目标函数
@for(row(i):@sum(col(j):a(i,j)*x(j))<=b(i))  %Ax<=b的约束条件   
!@for(setname:expression_list)  for循环
@for(col:@gin(x))  %对于col集合的元素进行循环操作，@gin(x) 元素都是整数
@for(col:@bnd(0,x,99))  %对于col集合的元素进行循环操作  bnd(low,x,up)限制范围
;

多目标规划