[科普中国]-0-1型整数线性规划

简介

0-1型整数线性规划是整数线性规划中的特殊情形，它的变量仅取值0或1。这时称为0-1变量，或称二进制变量。

仅取值0或1这个条件可由下述约束条件所代替：，整数。

注意它和一般整数线性规划的约束条件形式是一致的。在实际问题中，如果引入0-1变量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们先介绍引入0-1变量的实际问题，再研究解法。

如果变量不是仅取值0或1，而是可取其他范围的非负整数，这时可利用二进制的记数法将它用若干个0-1变量来代替。例如，在给定的问题中，变量x可任取0与10之间的任意整数时，令

这时，x就可用4个0-1变量来代替。

0-1型整数线性规划的解法解0-1型整数线性规划最容易想到的方法，和一般整数线性规划的情形一样，就是穷举法，即检查变量取值为0或1的每一种组合，比较目标函数值以求得最优解，这就需要检查变量取值的个组合。对于变量个数n较大(例如n>10)，这几乎是不可能的。因此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的方法称为隐枚举法(implicit enumeration)，分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

引入0-1变量的实际问题投资场所的选定—相互排斥的计划某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)可供选择。规定：

（1）在东区，由三个点中至多选两个；

（2）在西区，由两个点中至少选一个；

（3）在南区，由两个点中至少选一个。

（4） 如选用点，设备投资估计为元，每年可获利润估计为元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大?1

解题时先引入0-1变量，当点被选用的时候，；当点没有被选用的时候，。于是问题可列成：

关于固定费用的问题在讨论线性规划时，有些问题是要求使成本为最小。那时总设固定成本为常数，并在线性规划的模型中不必明显列出。但有些固定费用(固定成本)的问题不能用一般线性规划来描述，但可改变为混合整数线性规划来解决，见下例。2

某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定投资高的生产方式(选购自动化程度高的设备)，由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定投资低的生产方式，将来分配到每件产品的变动成本可能增加，所以必须全面考虑。今设有三种方式可供选择，令

表示采用第j种方式时的产量；

表示采用第j种方式时每件产品的变动成本；

表示采用第j种方式时的固定成本。

为了说明成本的特点，暂不考虑其他约束条件。采用各种生产方式的总成本分别为：

当时，；当时，。

在构成目标函数时，为了统一在一个问题中讨论，现引入0-1变量，令

当时，即采用第j种生产方式时，；当时，即不采用第j种生产方式时，。

于是目标函数：

上式的规定可由以下3个线性约束条件表示：

（1）其中M是个充分大的常数。

（2）当时必须为1；

（3）当时只有为0时才有意义；

整数线性规划整数线性规划 (integer linear programming )变量取整数值的线性规划.它的一般形式为，满足条件Ax=b，或>0，且取整数值.在一般线性规划的约束条件之上，增加要求变量为整数值之后，使问题发生了深刻的变化，对理论和应用均产生影响，从而，形成了整数线性规划特有分支.在n维欧氏空间E”中的点x，若其所有坐标均为整数，则称此点为整点。而E0中所有的整点记为Z"，是一个格，称此格为整格.于是，整数线性规划就是在整格上的线性规划。