资源描述：
《第六章-线性规划方法建模》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、例1设某工厂生产两种产品A和B,每件需用两种原料I和II，其所需数量如下表6.1.3所示：表6.1.3AB可用资源I3424II2630利涧69试安排生产使总利润最人.设A产品生产x件，设B产品生产y件，则问题可描述成如下的规划:max6x+9y"3x+4y<24s.t<2x+6y<30注意到上面的线性规划中有一个约束x和y为整数，所以这是一个整数线性规划.例2设某工厂拟用集装箱托运甲乙两种货物，每筘的体积、重量、可获利润以及托运所受限制如表6.1.4所示：表6.1.4货物体积（立方米每箱）重量（百斤每箱）利润（百元每箱）甲5220乙4510
2、托运限制2413问两种货物各托运多少箱，吋使获得利润敁大？现在我们用数学语言来描述问题.设&,x2分别为甲、乙两种货物的托运箱数（当然都足非负整数）.这足一个整数规划问题，川数学式讨表示为：max20x,+10x25%,+4x2<242七+5x2<13x,>0;x2>0xpx2为整数如果把整数线性规划的“整数约束”去掉，那么它就是一个线性规划（似乎整数线性规划是线性规划的特殊情形）.因为线性规划已经科了比较成熟的解法——单纯形法，人们自然汄为整数线性规划的求解并不会人难.但事实恰恰相反，到现在为止人们还没有整数线性规划求解的完善算法，它是被称
3、之为“HP问题”（即hardproblem）.起初，一个合理的想法是将去掉“整数约束”的线性规划的最优解进行“舍入化整”就能得到整数线性规划的最优解了.但这常常是不行的，因为.•一、化整f不见得是可行解；二、即使是可行解，但不一定是最优解.我们来考察例子2.先不去考虑“整数约朿”.即考虑它对应的线性规划：max20^,+10%25x,+4x2<24*2xl+5^r2<13%,,%2>0很矜易求得它的最优解为：（4.8,0）g标值为：96.供此解不满足整数约束.我们足否可以经过“化整”而得到问题的敁优解呢？如果“四舍五入”，那么彳U到（5,0）
4、,但这不是可行解（不满足约束条件中的第一个不等式）；如果“舍去尾数”，则得到（4,0）,这是问题的可行解，伹它足不足最优解呢？我们川列举法來证明.此问题只奋12个可行解，解与H标值如表6.1.5:表6.1.5000111223344X,012012010101目标位01020203040405060708090从表2—3巾看出，（4,0）不是问题的最优解.闷题的最优解为（4,1），其目标值为90.卜而我们介绍一•种求解整数线性规划的比较有效的方法——分枝定界法.6.1.5求解整数线性规划的分支定界法在求解整数线性规划时，如果可行域是柯界的，人
5、们首先界易想到，那么可行解是杏限多的，可通过列举法一一列举出来丼比较它们的目标函数值而得到最优解.这对于变景比较少，可行解的数FI相对少吋是可行的.但当变量较多，可行解的数FI较多时这很难办到.我们将会看到，人多数情况下可行解的数景太过巨人！此时，我们仅检验可行解的一部分.分枝定界法（branchandboundmethod）就是这样的.分枝定界法可川于解纯整数或混合整数规划问题.在本世纪六十年代初由LandDoig和Dakin等人提出.由于该方法灵活且便于用计算机求解，所以现在它已经是解整数线性规划的重耍方法.设有最大化的整数线性规划A,与
6、它相应的线性规划为B，从解问题B开始，若其最优解不符合A的整数条件，那么B的最优FI标函数必是A的最优FI标函数的上界，而A的任意可行解的H标函数值将是A的最优U标函数值的•-个下界.分枝定界法就是将B的可行域分成子区域（称为分枝）的方法.下面用例子来说明.例求解A问题maxz=40%+90v9jr+7y<56<7x+20y<70X，y为非负整数解AfnJ题相成的线性规划问题Bmaxz=40义+90),9x+7y<56<7x+20y<70x.y>0的最优解为：（4.81，1.82）Il标值为356.敁然，它不符合整数条件.这时356是问题A的
7、最优0标函数值的上界.显然，A问题的最优0标函数值介于0到356之间.分枝定界法的解法，酋先注意问题B的解（4.81，1.82）的一个非整数分景，如4.81,于是对A问题增加两个约朿条件：xS4和;v25.可将问题A分解为两个子问题Bi和B2（即两枝），给每枝增加一个约束条件，不考虑整数约束解问题队和&,即解下面规划：maxz=40x+90》’maxz=40x+90y9x+7y<56问题Bi:7x+20y<7009x+7y<56问题B2:7x+20y<70x>5x,y>0y<2^y>3分别得到问题83和Bi如下:maxz-4
8、0x+90y问题B3:9x+7y<567x+20>’<70x<4;)’<2称此为第一次迭代.其B,的解为（4,2.1）,最优目标值为349;B2的解为（5,1.57
