0—1规划

---

规定决策变量只能取值0或1的这类特殊整数规划及其求解的数学方法。

在处理经济管理中的某些规划问题时，若能引用0－1变量(即决策变量，也可叫逻辑变量)，可以把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。

0－1规划主要用于：(1)确定是否给某几个工程项目投资或决定某几种产品是否投产。

设有n种新产品，各产品如投产可获得的利润为C_j(j=1，2，…，n)，决策变量Xj取值规定

目标函数总利润最大化的数学模型是：

投资限额等约束条件为：

(2)确定具有先后要求的计划。

上例中，如根据生产过程的要求，要投产第j₁种产品就必须投产第j₂种产品，这一条件用上述0－1变量表示就是X_j1≤X_j2。

(3)确定相互排斥的约束条件。

如在运送两种货物(数量分别以X₁和X₂表示)时，由于运送方式(车运或船运)不同，所受约束条件也不同。车运，货物体积不超过b(米³)；船运，货物重量不能超过d(吨)，则：

车运 a₁X₁+a₂X₂≤b (1)

船运 C₁X₁+C₂X₂≤d (2)

由于只能采用一种运输方式，所以两个约束条件是相互排斥的。为了统一在一个问题中，引入0－1变量Y。

令

考虑下式：

a₁X₁+c₂X₂≤b+YM (3)

c₁X₁+c₂X₂≤d+(1－Y)M (4)

式中M是充分大的数，当Y=0(车运)时，(3)即是(1)，(4)自然成立；当Y=1(船运)时，(4)即是(2)，(3)自然成立。于是(1)、(2)两相互排斥的条件就由(3)、(4)两联系的条件所代替。