《第8章 整数规划带答案资料》由会员分享，可在线阅读，更多相关《第8章 整数规划带答案资料（75页珍藏版）》请在金锄头文库上搜索。
1、1,第八章 整 数 规 划,运 筹 学,2,第八章 整数规划,1 整数规划的图解法 2 整数规划的计算机求解 3 整数规划的应用 4 整数规划的分枝定界法,3,整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 求整数解的线性规划问题，应注意： 不是用四舍五入法和去尾法对线性规划的非整数解加以处理就能解决的。 整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。 根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变量取非负整数），混合整数规划（部分变量取非负整数），0-1整数规划（变量只取0或1）等。,第八章 整数规划,4,整数规划是数学规划中一
2、个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。 整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。,第八章 整数规划,5,1 整数规划的图解法,例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得的利润最大。,6,解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型。 目标函数： Max z =
3、 2x1 +3x2 约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4 x1，x2 0, 为整数。 如果去掉最后一个约束，就是一个线性规划问题.,1 整数规划的图解法,7,利用图解法，得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出, 整数规划的最优解（黄色叉号）为x1=4, x2=2,目标函数值为14。,Max z = 2x1 +3x2,195x1+273x2=1365,4 x1+40 x2 =140,4,2,3,1,1,2,3,x2,x1,1 整数规划的图解法,Max z = 2x1 +3x
4、2 约束条件：s.t. 195 x1 + 273 x2 1365 4 x1 + 40 x2 140 x1 4,8,由于相应的线性规划的可行域包含了其整数规划的可行点，则对于整数规划，易知有以下性质： 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。,1 整数规划的图解法,9,例2： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 -3x2 + 2x3 3 x1
5、, x2, x3 0 , 均为整数,用管理运筹学软件求解得： x1 = 5 x2 = 2 x3 = 2,2 整数规划的计算机求解,纯整数规划问题,10,11,例3： Max z = 3x1 + x2 + 3x3 s.t. -x1 + 2x2 + x3 4 4x2 -3x3 2 x1 - 3x2 + 2x3 3 x3 1 x1, x2, x3 0 x1，x3 为整数，x3 为0-1变量,用管理运筹学软件求解得: z = 16.25 x1 = 4 x2 = 1.25 x3 = 1,12,3 整数规划的应用,应用实例： 投资场所的选择问题 背包问题 固定成本问题 指派问题 分布系统设计 投资问题,1
6、3,14,3 整数规划的应用,一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j=1,2,3,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?,解
7、：设：0-1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。 这样我们可建立如下的数学模型： Max z=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xi 0 且xi 为0-1变量，i = 1, 2, 3, ,10,在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ，
8、A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个,补充例、解决某市消防站的布点问题，该城市有6个区，每个区都可以建消防站。市政府希望设置的消防站最少，但必须满足在城市的任何地区发生火警时，消防车要在15分钟内赶到现场。据实地测定，各区之间消防车行驶的时间如下表所示，请帮助该市制定一个最省的计划。,1 2 3 4 5 6 1 0 10 16 28 27 20 2 10 0 24 32 17 10 3 16 24 0 12 27 21 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20
9、 10 21 25 14 0,设 xi =1,0; 1i 区建消防站，0i 区不建消防站，i=1,6 min z = x1 + x2 + x3 + x4 + x5 + x6 约束方程保证每个地区都有一个消防站在15分钟行程内。 将6个地区的条件分别列出： s.t. x1 + x2 1, x1 + x2 + x6 1 x3 + x4 1, x3 + x4 + x5 1 x4 + x5 + x6 1, x2 + x5 + x6 1 xi = 0, 1; i=1,6,1 2 3 4 5 6 1 0 10 16 28 27 20 2 10 0 24 32 17 10 3 16 24 0 12 27 2
10、1 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20 10 21 25 14 0,18,1 2 3 4 5 6 1 0 10 16 28 27 20 2 10 0 24 32 17 10 3 16 24 0 12 27 21 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20 10 21 25 14 0,第2个地区建一个（地区1、2、6都解决了）,第4个地区建一个（地区3、4、5都解决了）,二、背包问题（补充）,背包可装入8单位重量，10单位体积物品。若背包中每件物品至多只能装一个，怎样才能使背包装的物品价值最高。,解：xi
11、为是否带第 i 种物品,Max Z=20x1 + 30x2 +10x3+18x4 +15x5,一般形式：, 整数,xi为是否携带第i 种物品 ai为i 物品单位重量，b为最大负重 ci为i 物品重要性估价,22,3 整数规划的应用,三、固定成本问题 例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号
12、为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。,23,解：这是一个整数规划的问题。 设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，若不生产则没有这部分费用，为了说明固定费用的这种性质，设 yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时）。 引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。,3 整数规划的应用,即：不投入固定费用，是不能投入生产的,24,这样我们可建立如下的数学模型： Ma
13、x z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 为0-1变量，i = 1,2,3,3 整数规划的应用,没有固定投入，就不生产. yi =0，则xi=0. xi是数量，M为一个充分大的数。 一个容器至少需要2个劳动力，共有300个劳动力，因此容器数量不会超过150.因此当yi =1时，M可取150,投入固定费用，生产小号容器,y1 y2 y3,25,三、指派问题 有
14、 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给n个人，使得完成 n 项任务的总的效率最高，这就是指派问题。,3 整数规划的应用,26,例6有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。,3 整数规划的应用,27,解：引入01变量 xij，并令 xij =1(当指派第 i人去完成第j项工作时)或0(当不指派第i人去完成第j项工作时)这可以表示为一个0-1整数规划问题： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44,3 整数规划的应用,28,整数规划模型为： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24 +26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项
