如何用matlab求解0-1规划问题?

例 求解下列0-1整数线性规划

目标拿亮函睁带数

max f=-3x1+2x2-5x3

约束条件

x1+2x2-x3≤2，

x1+4x2+x3≤4，

x1+x2≤3，

4x1+x3≤6，

x1，x2，x3为0或1.

在Matlab命令窗口中输入如下命令：

f=[-3,2,-5]

a=[1,2,-1,1,4,11,1,00,4,1]b=[2436]

[x,fval]=bintprog(-f,a,b)

%因为bintprog求解的为目标函数的最小值，所以要消早宽在f前面加个负号。

运行结果为：

Optimization terminated.

x = 0

1

0

fval = -2

表示x1=0，x2=1，x3=0时，f取最大值2。

当然，我们还可以在Matlab命令窗口中输入如下命令查询0-1整数规划命令的用法。

help bintprog

§3 0 −1型整数规划

0 −1型整数规划是整数规划中的特殊情形，它的变量j x 仅取值0 或1。这时j x 称

为0 −1变量，或称二进制变量。j x 仅取值0 或1 这个条件可由下述约束条件：

0 ≤ ≤ 1 j x ，整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0 −1变

量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个毁搏问题中讨论了。我们

先介绍引入0 −1变量的实际问题，再研究解法。

如果有m 个互相排斥的约束条件：

a x a x b i m i in n i 1,2, , 1 1 +L+ ≤ = L

为了保证这m 个约束条件只有一个起作用，我们引入m 个0 −1变量y (i 1,2, ,m) i = L

和一个充分大的常数M ，而下面这一组m +1个约束条件

a x a x b y M i m i in n i i 1,2, , 1 1 +L+ ≤ + = L （1）

1 1 y + + y = m − L m （2）

就合于上述的要求。这是因为，由于（2），m 个i y 中只有一个能取0 值，设0 * = i y ，

代入（1），就只有i = i*的约束条件起作用，而别的式子都是多余的。

3.2 0 −1型整数规划解法之一（过滤隐枚举法）

解0 −1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，

即检查变量取值为0 或1 的每一种组合，比较目标函数值以求得最优解，这就需要检查

变量取值的2n个组合。对于变量个数n较大（例如n >100），这几乎是不可能的。因

此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的

方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时迹毁穷举法还是必要的。

蒙特卡洛法（随机姿余备取样法）

前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线

性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解

法尚未找到，更何况是非线性整数规划。

然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限

个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图

用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一

定的计算量的情况下，完全可以得出一个满意解。

指派问题的计算机求解

整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，无法

直接利用Matlab 的函数，必须利用Matlab 编程实现分枝定界解法和割平面解法。但对

于指派问题等0 −1整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。

---