韩伯棠管理运筹学(第三版)第八章整数规划解说.ppt

1第八章第八章整整数数规规划划运筹学运运筹筹学学 2 第六章整数规划§ 1 整数规划的图解法§ 2 整数规划的计算机求解§ 3 整数规划的应用*§ 4 整数规划的分枝定界法 3 ?整数规划是一类要求变量取整数值的数学规划, 可分成线性和非线性两类。?整数线性规划(Integer Linear Programming , 简记为 ILP ) 问题研究的是要求变量取整数值时, 在一组线性约束条件下一个线性函数最优问题, 是应用非常广泛的运筹学的一个重要分支。应用实例: ●项目投资问题●工作分配问题 ●选址问题 ●背包问题第六章整数规划 4 ?根据变量的取值情况,整数线性规划又可以分为纯整数规划(所有变量取整数),混合整数规划(部分变量取整数), 0-1 整数规划(变量只取0或1)等。?求整数解的线性规划问题,不是用四舍五入法或去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。?整数规划是数学规划中一个较弱的分支,目前有成熟的方法解线性整数规划问题,而非线性整数规划问题,还没有好的办法。第六章整数规划 5 §1 整数规划的图解法例1. 某公司拟用集装箱托运甲、乙两种货物, 这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运 4 件,问两种货物各托运多少件,可使获得利润最大。货物每件体积(立方米) 每件重量(百千克) 每件利润(百元) 甲乙 195 273 4 40 23 托运限制 1365 140 6 货物每件体积(立方米) 每件重量(百千克) 每件利润(百元) 甲乙 195 273 4 40 23 托运限制 1365 140 解:设 x 1 、x 2 分别为甲、乙两种货物托运的件数,建立模型。目标函数: Max z = 2 x 1 +3 x 2 约束条件: . 195 x 1 + 273 x 2 ≤1365 4 x 1 + 40 x 2 ≤140 x 1 ≤4x 1,x 2 ≥0, 为整数。如果去掉最后一个约束,就是一个线性规划问题. §1 整数规划的图解法 7 利用图解法,得到线性规划的最优解为 x 1 =, x 2 =, 目标函数值为 。由图表可看出, 整数规划的最优解为 x 1 =4, x 2 =2, 目标函数值为 14。 Max z = 2 x 1 +3 x 2195 x 1 +273 x 2 =1365 4 x 1 +40 x 2 =140 4231 1 2 3 x 2x 1§1 整数规划的图解法 8 对于整数规划,易知有以下性质: 性质 1 :任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值;任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。§1 整数规划的图解法 9 §2 分支定界法以及计算机求解?分枝定界法步骤: 求解与 IP相应的 LP 问题,可能会出现下面几种情况: ?若所得的最优解的各变量恰好取整数,则这个解也是原整数规划的最优解,计算结束。?若无可行解,则原整数规划问题也无可行解, 计算结束。?若有最优解,但其各分量不全是整数,则这个解不是原整数规划的最优解,转下一步。?分枝定界法步骤(续): ?从不满足整数条件的基变量中任选一个 x l进行分枝,它必须满足 x l?[x l ] 或x l?[x l ] +1中的一个,把这两个约束条件加进原问题中,形成两个互不相容的子问题(分枝)。?定界:把满足整数条件各分枝的最优目标函数值作为上(下)界,用它来判断分枝是保留还是剪枝。?剪枝:把那些子问题的最优值与界值比较, 凡不优或不能更优的分枝全剪掉,直到每个分枝都查清为止。