纯整数规划与线性规划的区别

所谓整数规划,是指决策变量有整数要求的数学规划问题。整数规划分为线性整数规划和非线性整数规划。本章只讨论线性整数规划。线性整数规划主要分为纯整数规划、混合整数规划和0-1整数规划三类。当所有决策变量均取整数时,称为纯整数规划;当只有部分决策变量取整数时,称为混合整数规划;决策变量只取0和1时称为0-1整数规划。

对于线性整数规划,如果放松整数约束,整数规划就变成线性规划。通常称放松整数约束得到的线性规划问题为该整数规划的线性规划松弛问题,简称松弛问题。任何一个整数规划都可以看作一个线性规划松弛问题加上整数约束。这意味着整数规划是比线性规划约束得更紧的方法,它的可行域是其松弛问题的可行域的一个子集,即只是整数解部分。以下通过几个实例来说明整数线性规划在实际中的应用。

例7.1 某公司有5个投资项目被列入投资计划,各项目需要的投资额和期望的收益如表7.1所示。已知该公司只有600万元资金可用于投资,由于技术上的原因,投资受到以下约束:

①项目1、项目2 和项目3 至少应有一项被选中;

②项目3 和项目4 只能选一项;

③项目5 选中的前提是项目1 必须被选中。

如何选择投资方案才能使投资收益最大?

表7.1　投资收益信息

解 设0-1变量xi 为决策变量,即xi=1表示项目i被选中,xi=0表示项目i被淘汰,则模型可以表示为(www.xing528.com)

例7.2 某厂拟用集装箱托运甲、乙两种货物,每箱的体积、重量、可获利润以及托运所受限制如表7.2所示。两种货物各托运多少箱,可使获得利润为最大?

表7.2　托运信息表

解 设x1,x2 分别为甲、乙两种货物的托运箱数,这是一个纯整数线性规划问题,用数学式可表示为

它和线性规划问题的区别仅在于最后的条件“x1,x2 为整数”。