优化算法-整数规与多目标规划
整数规划
概念
全部变量限制为整数的规划问题，称为纯整数规划；
部分变量限制为整数的规划问题，称为混合整数规划；
变量只取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的约束。
%}
常用的整数规划问题解法有：
- 分枝定界法：可求纯或混合整数线性规划。
- 割平面法：可求纯或混合整数线性规划。
- 隐枚举法：用于求解0-1整数规划，有过滤法和分枝法。
- 匈牙利法：解决指派问题（0-1规划特殊情形）
- 蒙特卡罗法：求解各种类型规划。
例题
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为整数
蒙特卡罗法（随机取样法）
- 前面的方法，主要是针对线性整数规划而言，对于非线性整数规划没有通用的有效解法。
- 整数规划由于限制变量是整数，增加了求解难度，但整数解是有限个，所以可以采用枚举法。
- 当枚举个数很多时，显性枚举是不现实的，但利用蒙特卡罗随机取样法，在一定的计算量下是可以得到满意解的。
- 注意点 通常使用lingo处理规划问题，matlab虽然也能够解决问题，都是没有lingo效果好。
lingo的一些概念
```c
%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就是一个AB的矩阵;
% 生成一个rowcol的矩阵 记作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:c1x^2+c2x);
@for(row(i):@sum(col(j):a(i,j)*x(j))<=b(i));
@for(col:@gin(x));
@for(col:@bnd(0,x,99));
##### 例题lingo代码
```c
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)限制范围
;
