整数规划和多目标规划模型
- 格式：docx
- 大小：121.04 KB
- 文档页数：22
1 整数规划的 MATLAB 求解方法
用 MATLAB 求解一般混合整数规划问题
由于 MATLAB 优化工具箱中并未提供求解纯整数规划和混合整数规划的
函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布 精选文库
2
1
2
的工具箱可以解决该类问题。这里我们给出开罗大学的 Sherif 和 Tawfik 在
MATLAB Central 上发布的一个用于求解一般混合整数规划的程序，在此命名 为
intprog ，在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自
然序改造成分枝变量选择原则中的一种，即:选择与整数值相差最大的非整数
变量首先进行分枝。 intprog 函数的调用格式如下:
[X,fval,eXitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger)
该函数解决的整数规划问题为：
min
s.tf
Ax T
cX
b
AeqX beq
lb X ub
Xi 0 (i 1,2, ,n)
Xj取整数(j M)
在上述标准问题中，假设X为n维设计变量，且问题具有不等式约束 mi个,
等式约束m2个，那么: c、X均为n维列向量，b为m1维列向量，beq为m2维列
向量，A为rnij n维矩阵，Aeq为m2 n维矩阵。
在该函数中，输入参数有 c,A,b,A eq,beq,lb,ub,M 和 TolXInteger 。其中 c 为 目标函数所对应设计变量的系数， A 为不等式约束条件方程组构成的系数矩阵，
b为不等式约束条件方程组右边的值构成的向量。 Aeq为等式约束方程组构成的 系数矩阵，beq为等式约束条件方程组右边的值构成的向量。lb和ub为设计变
量对应的上界和下界。 M 为具有整数约束条件限制的设计变量的序号，例如问
题中设计变量为X1,X2, , X6，要求X2,X3和X6为整数，则 M=[2;3;6];若要求全
为整数，则M=1:6，或者M=[1;2;3;4;5;6]。TolXInteger为判定整数的误差限,
即若某数 x 和最邻近整数相差小于该误差限，则认为 x 即为该整数。 精选文库
2
1
3
在该函数中，输出参数有X, fval和exitflag。其中x为整数规划问题的最优
解向量，fval为整数规划问题的目标函数在最优解向量 X处的函数值，exitflag
为函数计算终止时的状态指示变量。
例1求解整数规划问题:
X1 X2
算法:
C=[-1；-1]；
A=[-4 2;4 2;O -2];
b=[-1;11;-1];
lb=[0;0];
[x1,fval1]=i ntp
rog(c,A,b,[],[],lb,[],M,Tol)
结果:
%松弛线性规划问题的最优解
1.5000 2.5000
fval =
-4.0000
%整数规划的最优解
fval2 = max
s.t. 4xi 2x2 1
4x1 2X2 11
1
x1, x2 0,且取整数值 2X2
M=[1;2]; %均要求为整数变量
Tol=1e-8; %判断是否整数的误差限
[x,fval]=li np rog(c,A,b,叮],lb,[]) %求解原问题松弛线性规划
%求最优解整数解
x1 = 精选文库
2
1
4
-3.0000精选文库
5
用MATLAB求解0-1规划问题
在MATLAB 优化工具箱中，提供了专门用于求解 0-1规划问题的函数
bintprog，其算法基础即为分枝界定法, MATLAB中调用bintprog函数求解
0-1规划时，需要遵循 MATLAB中对 0-1 规划标准性的要求。
0-1规划问题的MATLAB标准型
min
s.tf
Ax
Aeq X beq
x 0,1
在上述模型中，目标函数f需要极小化，以及需要满足的约束条件，不等式
约束一定要化为形式为“”
假设x为n维设计变量，且问题具有不等式约束 叶个，等式约束m2个，那么:
c、x均为n维列向量，b为m1维列向量，beq为m?维列向量，A为m^ n维矩阵,
Aeq为m2 n维矩阵。
如果不满足标准型的要求，则需要对原问题进行转化， 化为标准型之后才能
使用相关函数，标准化的方法和线性规划中的类似。
0-1规划问题的MATLAB求解函数
MATLAB优化工具箱中求解0-1规划问题的命令为bintprog
bintprog的调用格式
x = bintp rog(f)
x = bintp rog(f,A,b)
x = bintp rog(f,A,b,Aeq,beq)
x = bintp rog(f,A,b,Aeq,beq,xO)
x = bintp rog(f,A,b,Aeq,Beq,x0 ,op tio ns)
[x,fval] = bintp rog(...)
[x,fval,exitflag] = bintp rog(...)
[x,fval,exitflag,out put] = bintp rog(...)
命令详解 精选文库
6
x = bi ntprog (c,A,b,Aeq,beq,xO)
该函数调用格式求解如下形式的
f cTx
Ax b
Aeqx beq
x 0,1
在前一个调用格式的基础上同时设置求解算法的初始解为 x0，如果初始解 xO不在0-1规划问题的可行域中，算法将采用默认的初始解 5)x = bintprog
(c,A,b,Aeq,beq,xO,options)
用options指定的优化参数进行最小化。可以使用 optimset来设置这些
参数
上面的函数调用格式仅设置了最优解这一输出参数，如果需要更多的输出 参数，则可以参照下面的调用格式:
[x,fval] = bintp rog(...)
[x,fval,exitflag] = bintp rog(...)1) x = bi ntprog(f)
该函数调用格式求解如下形式的 0-1规划问题
2) x = bintp rog(c,A,b)
3) min
s.tf cTx
x 0,1
该函数调用格式求解如下形式的
min
s.t. 0-1
f
Ax 规划问题
T c x
b
0,1
x = bi ntprog (c,A,b,Aeq,beq)
该函数调用格式求解如下形式的 0-1
min
s.t规划问题:
f cTx
Ax b
AeqX beq
x 0,1
4)
0-1规划问题
min
s.t在优化计算结束之时返回整数规划问题在解 x处的目标函数值fval 精选文库
7
在优化计算结束之时返回exitflag值，描述函数计算的退出条件。
[x,fval,exitflag,out put] = bintp rog(...)
在优化计算结束之时返回结构变量 out put
是约束条件和目标函数分别为:
算法:
c=[20;12;33;26;22;15;29;23;21;13;31;24;22;16;32;23];
Aeq=[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;
1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0; X1 X2 X3 X4 1
X5 X6 X7 X8 1
X9 X10 X11 X12 1
X13 X14 X15 X16 1
X1 X5 X9 X13 1
X2 X6 X10 X14 1
X3 X7 X11 X15 1
X4 X8 X12 X16 1
Xi 0,1 (i 1,2, ,16)
E14X4 E21X5 E22X6
E44x16 f E11X1 E12X2 E13X3 例2： 求解0-1规划问题
max
st. 20 12 33 26
1 i 1Z ,n 22 15 29 23
E
21 13 31 24
1 j 12, ,n 22 16 32 23
Xij 0或 1 (1,2,3,4) i 1,2, ,n; j 1Z ,n
为了程序的可读性，我们用一维下标来表示设计变量, 即用 x1 ~ x4 表示 x11 ~ x14，
用 X5 ~ X8 表示 X21 ~ X24，用 X9 ~ X12 表示 X31 X34，用 X13 ~ X16 表示 X41 ~ x44 ， xij
j 1
n
Xij n
Ej xij
j 1
