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

由天下分享时间：2025/6/6 16:03:05 加入收藏我要投稿点赞

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

B=reshape(x,4,4); %由于x是一列元素，为了使结果更加直观，故排成与效率矩阵E相

对应的形式

B' fval 结果：

Optimization terminated. ans =

0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 fval = 85

整数规划的应用——组件配套问题

某机械产品需要由由三个工厂开工一起生产后组装完成。每件机械需要4个组件1和3个组件2。生产这两种组件需要消耗两种原材料A和B。已知这两种原材料的供应量分别为400kg和600kg。

由于三个工厂的生产条件和拥有设备工艺条件不同，每个工厂生产组件的能力和原材料的消耗也不尽相同，且每个工厂开工一次都是配套生产一定数量的组件1和组件2，其具体的数据如表所示。

表11-2 各工厂生产能力和消耗原材料的数据表工厂１工厂２工厂３每个工厂消耗原材料的数量（公斤）每个工厂各组件的生产能力（件数） A材料 9 6 4 B材料 7 10 9 组件1 8 7 9 组件2 6 9 5 现在的最优化问题是，这三个工厂应当如何安排生产，才能使该产品的配套数达到最大？

（Ⅰ）组件配套问题的建模