资源描述：
《第8章_整数规划(带答案)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章 整数规划运筹学1第八章整数规划§1整数规划的图解法§2整数规划的计算机求解§3整数规划的应用§4整数规划的分枝定界法2整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。求整数解的线性规划问题，应注意：不是用四舍五入法和去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变量取非负整数），混合整数规划（部分变量取非负整数），0-1整数规划（变量只取0或1）等。第八章整数规划3整
2、数规划是数学规划中一个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。整数线性规划(IntegerLinearProgramming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。第八章整数规划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
4、.66。由图表可看出,整数规划的最优解（黄色叉号）为x1=4,x2=2,目标函数值为14。Maxz=2x1+3x2195x1+273x2=13654x1+40x2=1404231123x2x1§1整数规划的图解法×××××××××××××××××Maxz=2x1+3x2约束条件：s.t.195x1+273x2≤13654x1+40x2≤140x1≤47由于相应的线性规划的可行域包含了其整数规划的可行点，则对于整数规划，易知有以下性质：性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规
5、划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。§1整数规划的图解法8例2：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x1,x2,x3≥0,均为整数用《管理运筹学》软件求解得：x1=5x2=2x3=2§2整数规划的计算机求解纯整数规划问题910例3：Maxz=3x1+x2+3x3s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3
6、为整数，x3为0-1变量用《管理运筹学》软件求解得:z=16.25x1=4x2=1.25x3=11112§3整数规划的应用应用实例：●投资场所的选择问题●背包问题●固定成本问题●指派问题 ●分布系统设计●投资问题13§3整数规划的应用一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j=1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定:在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6
7、，A7两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?14解：设：0--1变量xi=1(Ai点被选用)或0(Ai点没被选用)。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+1
8、40x8+160x9+180x10≤720x1+x2+x3≤2x4+x5≥1x6+x7≥1x8+x9+x10≥2xi≥0且xi为0--1变量，i=1,2,3,…,10在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北
