优化算法-整数规与多目标规划
整数规划
概念
全部变量限制为整数的规划问题,称为纯整数规划;
部分变量限制为整数的规划问题,称为混合整数规划;
变量只取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的一些概念
文章来源:https://www.toymoban.com/news/detail-425209.html
%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)限制范围
;
文章来源地址https://www.toymoban.com/news/detail-425209.html
多目标规划
到了这里,关于优化算法-整数规与多目标规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!