第六章-线性规划方法建模.doc

例1 设某工厂生产两种产品A和B，每件需用两种原料I和II，其所需数量如下表6.1.3所示： 表6.1.3 A B 可用资源 I II 4 2 6 24 30 利润 6 9 试安排生产使总利润最大. 设A产品生产x件，设B产品生产y件，则问题可描述成如下的规划： 注意到上面的线性规划中有一个约束x和y为整数，所以这是一个整数线性规划. 例2 设某工厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表6.1.4所示： 表6.1.4 货物 体积（立方米每箱） 重量（百斤每箱） 利润（百元每箱） 甲 乙 5 4 2 5 20 10 托运限制 24 13 问两种货物各托运多少箱，可使获得利润最大？ 现在我们用数学语言来描述问题.设，分别为甲、乙两种货物的托运箱数（当然都是非负整数）.这是一个整数规划问题，用数学式可表示为： 如果把整数线性规划的“整数约束”去掉，那么它就是一个线性规划（似乎整数线性规划是线性规划的特殊情形）.因为线性规划已经有了比较成熟的解法——单纯形法，人们自然认为整数线性规划的求解并不会太难.但事实恰恰相反，到现在为止人们还没有整数线性规划求解的完善算法，它是被称之为“HP问题”（即hard problem）.起初，一个合理的想法是将去掉“整数约束”的线性规划的最优解进行“舍入化整”就能得到整数线性规划的最优解了.但这常常是不行的，因为：一、化整后不见得是可行解；二、即使是可行解，但不一定是最优解. 我们来考察例子2.先不去考虑“整数约束”.即考虑它对应的线性规划： 很容易求得它的最优解为：（4.8，0）目标值为：96.但此解不满足整数约束.我们是否可以经过“化整”而得到问题的最优解呢？如果“四舍五入”，那么得到（5，0），但这不是可行解（不满足约束条件中的第一个不等式）；如果“舍去尾数”，则得到（4，0），这是问题的可行解，但它是不是最优解呢？我们用列举法来证明.此问题只有12个可行解，解与目标值如表6.1.5： 表6.1.5 0 0 0 1 1 1 2 2 3 3 4 4 0 1 2 0 1 2 0 1 0 1 0 1 目标值 0 10 20 20 30 40 40 50 60 70 80 90 从表2－3中看出，（4，0）不是问题的最优解.问题的最优解为（4，1），其目标值为90. 下面我们介绍一种求解整数线性规划的比较有效的方法——分枝定界法. 6.1.5 求解整数线性规划的分支定界法 在求解整数线性规划时，如果可行域是有界的，人们首先容易想到，那么可行解是有限多的，可通过列举法一一列举出来并比较它们的目标函数值而得到最优解.这对于变量比较少，可行解的数目相对少时是可行的.但当变量较多，可行解的数目较多时这很难办到.我们将会看到，大多数情况下可行解的数量太过巨大！此时，我们仅检验可行解的一部分.分枝定界法（branch and bound method）就是这样的. 分枝定界法可用于解纯整数或混合整数规划问题.在本世纪六十年代初由Land Doig和Dakin等人提出.由于该方法灵活且便于用计算机求解，所以现在它已经是解整数线性规划的重要方法.设有最大化的整数线性规划A，与它相应的线性规划为B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数的上界，而A的任意可行解的目标函数值将是A的最优目标函数值的一个下界.分枝定界法就是将B的可行域分成子区域（称为分枝）的方法.下面用例子来说明. 例 求解A问题 解 A问题相应的线性规划问题B 的最优解为：（4.81，1.82）目标值为356.显然，它不符合整数条件.这时356是问题A的最优目标函数值的上界.显然，A问题的最优目标函数值介于0到356之间. 分枝定界法的解法，首先注意问题B的解（4.81，1.82）的一个非整数分量，如4.81，于是对A问题增加两个约束条件：和.可将问题A分解为两个子问题B1和B2（即两枝），给每枝增加一个约束条件，不考虑整数约束解问题B1和B2，即解下面规划： 问题B1： 问题B2： 称此为第一次迭代.其B1的解为（4，2.1），最优目标值为349；B2的解为（5，1.57），最优目标值为341.于是我们可以知道，原问题A的最优目标值介于0和349之间.继续对问题B1和B2进行分解.因为B1的最优目标值大于B2的最优目标值，故先分解B1为两枝.增加条件和分别得到问题B3和B4如下： 问题B3：