整数规划和多目标规划模型及应用

1 整数规划的MATLAB求解方法

（一） 用MATLAB求解一般混合整数规划问题

由于MATLAB优化工具箱中并未提供求解纯整数规划和混合整数规划的函数，因而需要自行根据需要和设定相关的算法来实现。现在有许多用户发布的工具箱可以解决该类问题，例如比较著名的YALMIP，读者可以自行到网上下载相关的工具包并进行学习。这里我们给出开罗大学的Sherif和Tawfik在MATLAB Central上发布的一个用于求解一般混合整数规划的程序，在此命名为intprog，笔者在原程序的基础上做了简单的修改，将其选择分枝变量的算法由自然序改造成分枝变量选择原则中的一种，即：选择与整数值相差最大的非整数变量首先进行分枝。intprog函数的调用格式如下：

[x,fval,exitflag]=intprog(c,A,b,Aeq,beq,lb,ub,M,TolXInteger) 该函数解决的整数规划问题为：

?min??s.t.????????f?cTxAx?bAeqx?beqlb?x?ubxi?0(i?1,2,?,n)xj取整数（j?M）

在上述标准问题中，假设x为n维设计变量，且问题具有不等式约束m1个，等式约束m2个，那么：c、x均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1?n维矩阵，Aeq为m2?n维矩阵。

在该函数中，输入参数有c,A,b,Aeq,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即为该整数。

在该函数中，输出参数有x, fval和exitflag。其中x为整数规划问题的最优解向量，fval为整数规划问题的目标函数在最优解向量x处的函数值，exitflag为函数计算终止时的状态指示变量。

例1 求解整数规划问题：

f?x1?x2?max?s.t. 4x1?2x2?1 ?? 4x1?2x2?11 ? ? 2x2?1 ?? x1,x2?0，且取整数值 ? 算法：

c=[-1;-1];

A=[-4 2;4 2;0 -2]; b=[-1;11;-1]; lb=[0;0]; M=[1;2]; %均要求为整数变量 Tol=1e-8; %判断是否整数的误差限 [x,fval]=linprog(c,A,b,[],[],lb,[]) %求解原问题松弛线性规划 [x1,fval1]=intprog(c,A,b,[],[],lb,[],M,Tol) %求最优解整数解 结果：

x = %松弛线性规划问题的最优解 1.5000 2.5000 fval =

-4.0000 x1 = %整数规划的最优解 2 1 fval2 = -3.0000

（二） 用MATLAB求解0-1规划问题

在MATLAB优化工具箱中，提供了专门用于求解0-1规划问题的函数bintprog，其算法基础即为分枝界定法，在MATLAB中调用bintprog函数求解0-1规划时，需要遵循MATLAB中对0-1规划标准性的要求。

0-1规划问题的MATLAB标准型

?min??s.t.????f?cTxAx?b

Aeqx?beqx?0,1在上述模型中，目标函数f 需要极小化，以及需要满足的约束条件，不等式约束一定要化为形式为“?”。

假设x为n维设计变量，且问题具有不等式约束m1个，等式约束m2个，那么：c、x均为n维列向量，b为m1维列向量，beq为m2维列向量，A为m1?n维矩阵，Aeq为m2?n维矩阵。

如果不满足标准型的要求，则需要对原问题进行转化，化为标准型之后才能使用相关函数，标准化的方法和线性规划中的类似。

0-1规划问题的MATLAB求解函数

MATLAB优化工具箱中求解0-1规划问题的命令为bintprog bintprog的调用格式

x = bintprog(f)

x = bintprog(f,A,b)

x = bintprog(f,A,b,Aeq,beq) x = bintprog(f,A,b,Aeq,beq,x0)

x = bintprog(f,A,b,Aeq,Beq,x0,options) [x,fval] = bintprog(...)

[x,fval,exitflag] = bintprog(...)

[x,fval,exitflag,output] = bintprog(...)

命令详解

1）x = bintprog(f)

该函数调用格式求解如下形式的0-1规划问题

?min??s.t.f?cTx

x?0,12）x = bintprog(c,A,b)

该函数调用格式求解如下形式的0-1规划问题

?min??s.t.??f?cTxAx?bx?0,1

3）x = bintprog (c,A,b,Aeq,beq)

该函数调用格式求解如下形式的0-1规划问题：

?min??s.t.????f?cTxAx?b

Aeqx?beqx?0,14）x = bintprog (c,A,b,Aeq,beq,x0)

该函数调用格式求解如下形式的0-1规划问题

?min??s.t.????f?cTxAx?b

Aeqx?beqx?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规划问题

nn?f???Eijxij?maxi?1j?1??20n??22xij?1 ?i?1,2,?,n??s.t. ?E??j?1??21?n?? ?xij?1 ?j?1,2,?,n??22?i?1? xij?0或1（ 1，2,3,4） ?i?1,2,?,n;j?1,2,?,n? ?121513163329313226?23?? 24??23?

为了程序的可读性，我们用一维下标来表示设计变量，即用x1~x4表示x11~x14，用

x5~x8表示x21~x24，用x9~x12表示x31~x34，用x13~x16表示x41~x44，于是约束

条件和目标函数分别为：

?x1?x2?x3?x4?1?x?x?x?x?1678?5?x9?x10?x11?x12?1??x13?x14?x15?x16?1??x1?x5?x9?x13?1 ?x?x?x?x?161014?2?x3?x7?x11?x15?1??x4?x8?x12?x16?1??xi?0,1 (i?1,2,?,16)f?E11x1?E12x2?E13x3?E14x4?E21x5?E22x6???E44x16

算法：

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);