《管理运筹学整数规划》由会员分享，可在线阅读，更多相关《管理运筹学整数规划（20页珍藏版）》请在金锄头文库上搜索。
1、第八章 整数规划1 整数规划的图解法2整数规划的计算机求解3整数规划的应用4整数规划的分枝定界法1 整数规划的图解法例1. 某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备 需要A、B两种材 料的消耗以及资 源的限制，如右 表。 问题：工厂应分 别生产多少件甲、乙种仪器设备才 能使工厂获利最多？ 解、 目标函数： Max z = x1 + x2 约束条件： s.t. 3 x1 + 2 x2 10 2 x2 5x1，x2 0 为整数 不考虑整数约束得到最优解：x1 =1.667， x2 = 2.5；z = 4.167 考虑整数约束得到最优解：x1 = 2， x2 = 2； z =
2、 4 整数规划的最优目标值小于相应 线性规划的最优目标值(相当于附加一个约束)2整数规划的计算机求解例2：Max z = 15x1 + 10x2 + 7x3 s.t.5x1 - 10x2 + 7x3 86x1 + 4x2 + 8x3 12-3x1 + 2x2 + 2x3 10x1,x2,x3 0 为整数例2：Max z = 15x1 + 10x2 + 7x3 s.t.5x1 - 10x2 + 7x3 86x1 + 4x2 + 8x3 12-3x1 + 2x2 + 2x3 10x1,x2,x3 0 x3 为整数 x1 为0-1变量 用管理运筹学软件求解得：x1 = 0 x2 = 3 x3 = 0
3、 z = 30用管理运筹学软件求解得：x1 = 1 x2 = 1.5 x3 = 0 z = 303整数规划的应用(1)一、投资场所的选择例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个 位置 Aj (j1，2，3，10)可供选择，考虑到各地区居民的消费水平及居民居住密集 度，规定：在东区由A1 ， A2 ，A3 三个点至多选择两个；在西区由A4 ， A5 两个点中至少选一个；在南区由A6 ， A7 两个点中至少选一个；在北区由A8 ， A9 ， A10 三个点中至少选两个。Aj 各点的设备投资及每 年可获利润由于地点不同都是 不一样的，预测情况见右表所 示 (单
4、位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最 大?解：设：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 720x1 + x2 + x3 2x4 + x5 1x6 + x7 1x8 + x9 + x10 2xj 0 xj 为0-1变量，i = 1,2,3,10二、固定
5、成本问题例5高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机 器设备，制造一个容器所需的各种资源的数量如右 表所示。不考虑固定费用，每种容器售出一只所得 的利润分别为 4万元、5万元、6万元，可使用的金 属板有500吨，劳动力有300人月，机器有100台月， 此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。解：这是一个整数规划的问题。设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定
6、费用的这种性质，设yi = 1(当生产第 i种容器, 即 xi 0 时) 或0（当不生产第 i种容器即 xi = 0 时）引入约束 xi M yi ，i =1，2，3，M充分大，以保证当 yi = 0 时，xi = 0 。 这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 5002x1 + 3x2 + 4x3 300x1 + 2x2 + 3x3 100xi M yi ，i =1，2，3，M充分大xj 0 yj 为0-1变量，i = 1,2,33整数规划的应用(2)例6有四个工
7、人，要分别指派他们完 成四项不同的工作，每人做各项工作所消 耗的时间如右表所示，问应如何指派工作， 才能使总的消耗时间为最少。解：引入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 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x
8、24= 1 (乙只能干一项工作)x31+ x32+ x33+ x34= 1 (丙只能干一项工作)x41+ x42+ x43+ x44= 1 (丁只能干一项工作)x11+ x21+ x31+ x41= 1 ( A工作只能一人干)x12+ x22+ x32+ x42= 1 ( B工作只能一人干)x13+ x23+ x33+ x43= 1 ( C工作只能一人干)x14+ x24+ x34+ x44= 1 ( D工作只能一人干)xij 为0-1变量，i,j = 1,2,3,4* * * 求解可用管理运筹学软件中整数规划方法。 3整数规划的应用(3)三、指派问题有 n 项不同的任务，恰好 n 个人可分别
9、承担这些任务，但由于每人特长不同，完成各 项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派 给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。四、分布系统设计 例7某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2，A3，A4，A5地中再 选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固 定成本分别为175千元、300千元、375千元、500千元，另 外， A1产量及A2，A3，A4，A5建成厂的产量，那时销地 的销量以及产地到销地的单位运价(每千箱运费)如右表所示。a) 问应该在哪几个地
10、方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂? 解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yi = 1(当Ai 被选中时)或0（当Ai 没被选中时)这可以表示为一个整数规划问题： Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10x51 +4x52+2x53 其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x1
11、3 30 ( A1 厂的产量限制) x21+ x22+ x23 10y2 ( A2 厂的产量限制) b）增加约束：y2+y3=1x31+ x32+ x33 20y3 ( A3 厂的产量限制)x41+ x42+ x43 30y4 ( A4 厂的产量限制)x51+ x52+ x53 40y5 ( A5 厂的产量限制)x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制)x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制)x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制)xij 0 yi为0-1变量，i = 1
12、,2,3,4,5；j = 1,2,3* * * 求解可用管理运筹学软件中整数规划方法。 3整数规划的应用(4)3整数规划的应用(5) 五、投资问题例8某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额 为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年未能回收本利128，但规定最低投资金额为3万元，最高金额为5 万元；项目 C：第二年初需要投资，到第五年未能回收本利140%，但规定其投资额或为2万元或为4万元或为6 万元或为8万元。项目 D：五年内每年初可购买公债，于当年末归还，并加利息6%
13、，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额 为最大?解：1) 设xiA、xiB、xiC、xiD ( i 1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额；设yiA， yiB，是01变量，并规定取 1 时分别表示第 i 年给A、B投资，否则取 0（ i = 1, 2, 3, 4, 5）。设yiC 是非负整数变量，并规定：2年投资C项目8万元时，取值为4；2年投资C项目6万元时，取值为3；2年投资C项目4万元时，取值为2；2年投资C项目2万元时，取值为1；2年不投资C项目时， 取值为0；这样我们建立如下的决
14、策变量：第1年 第2年 第3年 第4年 第5年A x1A x2A x3A x4A B x3B C x2C (=20000y2C) D x1D x2D x3D x4D x5D 3整数规划的应用(6)2）约束条件： 第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000； 第二年：A次年末才可收回投资故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D = 1.06x1D； 第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D； 第四年：年初的资金为
15、 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D； 关于项目A的投资额规定: x1A 40000y1A ，x1A 200000y1A ，200000是足够大的数；保证当 y1A = 0时， x1A = 0 ；当y1A = 1时，x1A 40000 。 关于项目B的投资额规定: x3B 30000y3B ，x3B 50000y3B ；保证当 y3B = 0时， x3B = 0 ；当y3B = 1时，50000 x3B 30000 。 关于项目C的投资额规定: x2C = 20000y2C ，y2C = 0，1，2，3，4。 3）目标函数及模型：Max z = 1.15x4A+ 1.40x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000；x2A+x2C+x2D = 1.06x1D；x3A+x3B+x3D = 1.15x1A+ 1.0
