文档介绍:1整数规划的MATLAB求解方法
(一) 用MATLAB求解一般混合整数规划问题
由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函
数,因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的
工具箱可以og(...)
[x,fval,exitflag] = bintprog(...)
[x,fval,exitflag,output] = bintprog(...)
命令详解
x = bintprog(f)
该函数调用格式求解如下形式的
0-1 规划问题
min
.
f cTx
x 0,1
2 x = bintprog(c,A,b)
该函数调用格式求解如下形式的0-1规划问题
T minfcx
x 0,1
x = bintprog (c,A,b,Aeq,beq)
该函数调用格式求解如下形式的 0-1 规划问题: min fcTx
. Ax b Aeqx beq x 0,1
x = bintprog (c,A,b,Aeq,beq,x0)
该函数调用格式求解如下形式的 0-1 规划问题 min fcT x
. b
Aeqxbeq
x 0,1
在前一个调用格式的基础上同时设置求解算法的初始解为X0,如果初始解 x0 不在 0-1 规划问题的可行域中,算法将采用默认的初始解
5 X = bintprog (c,A,b,Aeq,beq,X0,options)
用 options 指定的优化参数进行最小化。可以使用 optimset 来设置这些
参数
上面的函数调用格式仅设置了最优解这一输出参数,如果需要更多的输出 参数,则可以参照下面的调用格式:
[X,fval] = bintprog(...)
在优化计算结束之时返回整数规划问题在解X 处的目标函数值fval
[X,fval,eXitflag] = bintprog(...)
在优化计算结束之时返回 exitflag 值,描述函数计算的退出条件。
[x,fval,exitflag,output] = bintprog(...)
在优化计算结束之时返回结构变量output
例 2:
0-1 规划问题
max
Ex
ij xij
j1
.
xij
i 1,2,
,n
j1
n
xij
i1
j 1,2,
,n
20
12
33
26
22
15
29
23
21
13
31
24
22
16
32
23
E
xij 0或1(1,2,3,4)
i 1,2, ,n; j 1,2, ,n
为了程序的可读性, 我们用一维下标来表示设计变量,
x1
~ x4 表示 x11 ~ x14 ,
用 x5 ~ x8 表示 x21 ~ x24 ,用 x9 ~ x12 表示 x31
x34 ,用
x13 ~ x16 表示 x41 ~ x44 ,
f E11x1 E12x2 E13x3 E14 x4
E44x16
是约束条件和目标函数分别为:
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)
E21 x5E22x6
算法:
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;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1;
];
beq=ones(1,8);
[x,fval]=bintprog(c,[],[],Aeq,beq);
B=reshape(x,4,4); %由于x是一列元素,为了使结果更加直观,故排成与效率矩阵E相对
应的形式
B'
fval
结果: