运筹学课件2012 第08章 整数规划.ppt

《运筹学课件2012 第08章 整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章整数规划运筹学1第八章整数规划§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用*§4整数规划的分枝定界法2整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。整数线性规划(IntegerLinearProgramming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。应用实例：●项目投资问题　●工作分配问题●选址问题　　　　　●背包问题第八章整数规划3根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变量取整数），混合整数规划（部分变量取

2、整数），0-1整数规划（变量只取0或1）等。求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。整数规划是数学规划中一个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。第八章整数规划4§1整数规划的图解法例1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。货物每件体积(立方米)每件重量(百千克)每

3、件利润（百元）甲乙19527344023托运限制13651405货物每件体积(立方米)每件重量(百千克)每件利润（百元）甲乙19527344023托运限制1365140解：设x1、x2分别为甲、乙两种货物托运的件数，建立模型。目标函数：Maxz=2x1+3x2约束条件：s.t.195x1+273x2≤13654x1+40x2≤140x1≤4x1，x2≥0,为整数。如果去掉最后一个约束，就是一个线性规划问题.§1整数规划的图解法6利用图解法，得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出,整数规划的最优解为x1=4,

4、x2=2,目标函数值为14。Maxz=2x1+3x2195x1+273x2=13654x1+40x2=1404231123x2x1§1整数规划的图解法7对于整数规划，易知有以下性质：性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。§1整数规划的图解法8§2分支定界法以及计算机求解分枝定界法步骤：求解与IP相应的LP问题，可能会出现下面几种情况：若所得的最优解的各变量恰好取整数，则这个解也是原整

5、数规划的最优解，计算结束。若无可行解，则原整数规划问题也无可行解，计算结束。若有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。9分枝定界法步骤（续）：从不满足整数条件的基变量中任选一个xl进行分枝，它必须满足xl[xl]或xl[xl]+1中的一个，把这两个约束条件加进原问题中，形成两个互不相容的子问题（分枝）。定界：把满足整数条件各分枝的最优目标函数值作为上（下）界，用它来判断分枝是保留还是剪枝。剪枝：把那些子问题的最优值与界值比较，凡不优或不能更优的分枝全剪掉，直到每个分枝都查清为止。10例：分支定界法的求解思路图线性规划1Z

6、1=14.66X1=2.44X2=3.26z=13,=14.66线性规划2Z2=13.90X1=2X2=3.30X1≤2X1≥3X2≤2X2≥3z=13,=14.58z=14,=14线性规划4Z4=14.00X1=4X2=2线性规划5无可行解线性规划3Z3=14.58X1=3X2=2.8611例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0,为整数例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x

7、3≥0x1，x3为整数，x3为0-1变量用《管理运筹学》软件求解得：x1=5x2=2x3=2用《管理运筹学》软件求解得:z=16.25x1=4x2=1.25x3=1§2整数规划的计算机求解12§3整数规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j=1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定:在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选

8、两个。Aj各点的设备投资及每年可获利润由于地点不同都