简介

0-1 规划是一种特殊形式的整数规划 。这种规划的决策变量仅取值 0或1 ，故称为 0-1 变量或二进制变量 ，因为一个非负整数都可以用二进制记数法用若干个 0-1 变量表示 。 0-1 变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此 0-1 规划非常适合描述和解决如线路设计 、工厂选址 、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。

实际上，凡是有界变量的整数规划都可以转化为 0-1 规划来处理 。由于 0-1 规划具有深刻的背景和广泛的应用，几十年来一直受到人们的重视 。0-1 规划主要用于求解互斥的计划问题、约束条件互斥问题、固定费用问题和分派问题等方面。

应用

互斥计划问题

如确定投资项目，选定投资场所，决定投产产品等。设有几种产品，各产品投产后获得的利润为cj，投资限额为B，规定决策变量xj的取值为

则此0-1规划的数学模型为

图3

式中max表示求极大值；s.t.表示“受约束于”；z是目标函数；aj是各种产品的投资额。

约束条件问题

设有m个互相排斥的约束条件（≤型）ai1x1+ai2x2+…+ainxn≤bi(i=1，2，…，m)，为了保证这m个约束条件中只有一个起作用，引入m个 0-1 变量yi和一个足够大的常数M，构造m+1 个约束条件

ai1x1+ai2x2+…+ainxn≤bi+yiM

y1+y2+…+ym=m-1

因为m个yi中只有一个能取 0 值，所以只有一个约束条件能起作用。如运送两种货物，其数量分别为x1和x2，车运时货物体积不得超过b1，船运时货物重量不得超过b2，即

a11x1+a12x2≤b1（车运），

a21x1+a22x2≤b2（船运）。

若只能采用一种运送方式，这两个约束条件是互相排斥的。为了统一在一个问题中，引用 0-1 变量yi，设

图5

把上述约束条件改造成为下面一组约束条件：