运 筹 学 第八章 整 数 规 划

第六章 整数规划 §1 整数规划的图解法 §2 整数规划的计算机求解 §3 整数规划的应用 §4 整数规划的分枝定界法

第六章 整数规划 整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 第六章 整数规划 整数规划是一类要求变量取整数值的数学规划，可分成线性和非线性两类。 求整数解的线性规划问题，不是用四舍五入法和去尾法对线性规划的非整数解加以处理就能解决的。整数线性规划一些基本算法的设计是以相应线性规划的最优解为出发点而发展出来的。 根据变量的取值情况，整数线性规划又可以分为纯整数规划（所有变量取非负整数），混合整数规划（部分变量取非负整数），0-1整数规划（变量只取0或1）等。

第六章 整数规划 整数规划是数学规划中一个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。 第六章 整数规划 整数规划是数学规划中一个较弱的分支，目前有成熟的方法解线性整数规划问题，而非线性整数规划问题，还没有好的办法。 整数线性规划(Integer Linear Programming，简记为ILP)问题研究的是要求变量取整数值时，在一组线性约束条件下一个线性函数最优问题，是应用非常广泛的运筹学的一个重要分支。

§1 整数规划的图解法 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。 甲种货物至多托运4件，问两种货物各托运多少件，可使获得的利润最大。 货物 每件体积 (立方米) 每件重量 (百千克) 每件利润 （百元） 甲 乙 195 273 4 40 2 3 托运限制 1365 140  

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

§1 整数规划的图解法 4 x1+40 x2 =140 Max z = 2x1 +3x2 195x1+273x2=1365 约束条件：s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 §1 整数规划的图解法 x2 4 x1+40 x2 =140 3 × × × Max z = 2x1 +3x2 2 × × × × × 1 × × × × × 195x1+273x2=1365 × × × × x1 1 2 3 4 利用图解法，得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出, 整数规划的最优解（黄色叉号）为x1=4, x2=2,目标函数值为14。

§1 整数规划的图解法 由于相应的线性规划的可行域包含了其整数规划的可行点，则对于整数规划，易知有以下性质： 性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。

§2 整数规划的计算机求解 例3： Max z = 3x1 + x2 + 3x3 例2： s.t. 纯整数规划问题 用《管理运筹学》软件求解得： x1 = 5 x2 = 2 x3 = 2 用《管理运筹学》软件求解得: z = 16.25 x1 = 4 x2 = 1.25 x3 = 1

§3 整数规划的应用 应用实例： ● 投资场所的选择问题 ● 背包问题 ● 固定成本问题　　 ● 指派问题　　　　　 ● 分布系统设计 ● 投资问题

§3 整数规划的应用 一、投资场所的选择 例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j=1,2,3,…,10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定: 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。 Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?

解：设：0--1变量 xi = 1 (Ai 点被选用)或 0 (Ai 点没被选用)。 这样我们可建立如下的数学模型： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个 解：设：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

例、解决某市消防站的布点问题，该城市有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 10 21 25 14 0

设 xi =1,0; 1－i 区建消防站，0－i 区不建消防站，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 21 4 28 32 12 0 15 25 5 27 17 27 15 0 14 6 20 10 21 25 14 0

二、背包问题 背包可装入8单位重量，10单位体积物品。若背包中每件物品至多只能装一个，怎样才能使背包装的物品价值最高。 　　背包可装入8单位重量，10单位体积物品。若背包中每件物品至多只能装一个，怎样才能使背包装的物品价值最高。 物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15

解：xi为是否带第 i 种物品 Max Z=20x1 + 30x2 +10x3+18x4 +15x5 物品 名称 重量 体积 价值 1 书 5 2 20 2 摄像机 3 1 30 3 枕头 1 4 10 4 休闲食品 2 3 18 5 衣服 4 5 15 解：xi为是否带第 i 种物品 Max Z=20x1 + 30x2 +10x3+18x4 +15x5 5x1+3x2 +x3 +2x4 +4x5  8 2x1+x2 +4x3 +3x4 +5x5  10 xi为0, 1

一般形式： , 整数 xi为是否携带第i 种物品 ai为i 物品单位重量，b为最大负重 ci为i 物品重要性估价

§3 整数规划的应用 三、固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。

§3 整数规划的应用 解：这是一个整数规划的问题。 设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 整数规划的应用 这样我们可建立如下的数学模型： 投入固定费用，生产小号容器 这样我们可建立如下的数学模型： Max 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 没有固定投入，就不生产. yi =0，则xi=0. xi是数量，M为一个充分大的数。 一个容器至少需要2个劳动力，共有300个劳动力，因此数量不会超过150. 因此当yi =1时，M可取150

§3 整数规划的应用 三、指派问题 有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给n个人，使得完成 n 项任务的总的效率最高，这就是指派问题。

§3 整数规划的应用 例6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。

§3 整数规划的应用 解：引入0—1变量 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 整数规划的应用 整数规划模型为： s.t. x11+ x12+ x13+ x14= 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+ x24= 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 每人只能干一项工作 一项工作只能由一个人干

对于有m个人完成n项任务的一般指派问题，设： m不一定等于n，当m>n时，有的人没有任务。 第i个人完成的任务 且最多承担一项 第j项工作正好有一人承担 注意：当m<n时，需要设假想的n-m个人，使得新的总人数等于工作数，按照常规解法求解。

不管m和n是什么关系，只要利用“指派”问题求解即可。输入：“人数”、“工作数”、每个人完成各项任务的成本，即可求得最优解。

§3 整数规划的应用 四、分布系统设计 例7．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了扩大生产，打算在 A2,A3,A4,A5地中再选择几个地方建厂。已知在 A2 ,A3,A4,A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?

§3 整数规划的应用

§3 整数规划的应用 解：a) 设xij为从工厂Ai运往销地Bj的运输量(单位千箱)，yk = 1(当Ak被选中时)或0（当Ak没被选中时), k =2,3,4,5．这可以表示为一个整数规划问题： 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+ x13≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 销地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 销地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 销地的限制) xij≥0, i=1,2,3,4,5; j=1,2,3, yk为0-1变量, k =2,3,4,5. A1厂已经有了

其中前4项为固定投资额，后面的项为运输费用。 s.t. x11+ x12+ x13 ≤ 30 ( A1 厂的产量限制) 整数规划模型为： 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+ x13 ≤ 30 ( A1 厂的产量限制) x21+ x22+ x23 ≤ 10y2 ( A2 厂的产量限制) x31+ 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, i = 1,2,3,4,5; j =1,2,3, yk为0-1变量, k =2,3,4,5. y2 y3 y4 y5

（2）再加一个约束条件 y2+ y3=1 即可。

§3 整数规划的应用 五、投资问题 例8.某公司在今后五年内考虑给以下的项目投资.已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限； 项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元； 项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。 该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?

解：1) 设xiA、xiB、xiC、xiD ( i ＝1，2，3，4，5)分别表示第 i 年年初给项目A，B，C，D的投资额； 这样我们建立如下的决策变量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C=20000y2C D x1D x2D x3D x4D x5D

§3 整数规划的应用 2）约束条件： 第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是 x1A+ x1D = 100000； 第二年：A的投资第二年末才可收回，第一年年末只有D项目可收回，故第二年年初的资金为1.06x1D，于是 x2A+x2C+x2D = 1.06x1D； 第三年：年初的资金为 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D。

关于项目A、B、C的投资额度的约束： 项目A第一年年初投资最低金额为4万元； 项目B第三年年初投资最低金额为3万元，最高金额为5万元； 这些年份可以给相应项目投资，也可以不投资，如果投资的话就要遵守上述约定。 因此，设0-1变量， yiA，yiB ，yiC是第i年年初给项目A,B,C投资的情况，1为投资，0为不投资。 对应上述约定，应该分别设为 y1A，y3B ，y2C（ y2C只用0,1不能详尽表述），则对y2C重新规定: 第2年投资C项目8万元时, 取值为4； 第2年投资C项目6万元时, 取值3; 第2年投资C项目4万元时, 取值2； 第2年投资C项目2万元时,取值1; 第2年不投资C时,取值0;

§3 整数规划的应用 关于项目A的投资额规定: x1A ≥ 40000y1A ，x1A ≤ My1A ， M是足够大的数，取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.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D； x1A ≥ 40000y1A ， x1A ≤ 200000y1A ， x3B ≥ 30000y3B ， x3B ≤ 50000y3B ； x2C = 20000y2C ， y1A， y3B = 0 或 1 y2C = 0，1，2，3，4 xiA ，xiB ，xiC ，xiD ≥ 0 ( i = 1、2、3、4、5）

§4 整数规划的分枝定界法 分枝定界法既能求解纯整数规划问题，又能求解混合整数规划问题。 分枝定界法是先求解整数规划相应的线性规划问题，若其最优解不符合整数条件，则求出整数规划的上下界用增加约束条件的方法，并把相应的线性规划的可行域分成子区域(分枝)，再求解上述子区域的线性规划问题，不断缩小整数规划的上下界的距离，最终求得整数规划的最优解。

线性规划1 用分枝定界法求解整数线性规划问题 例9. max 2x1 + 3x2 s.t. 195x1 +273 x2 ≤1365, 4x1 + 40x2 ≤140 x1 ≤4 x1, x2 ≥0,且为整数 解：（1）先求出相应LP问题的解，即 max 2x1 + 3x2 s.t. 195x1 +273 x2 ≤1365, 4x1 + 40x2 ≤140 x1 ≤4， x1, x2 ≥0 z1=14.66，x1=2.44, x2=3.26 线性规划1

(2) 确定整数规划的最优目标函数值Z的初始上界和下界。 上界不超过14.66（性质1） 下界：观察法求出一个整数规划的可行解，求得目标函数值，作为最优目标函数值的下界。 约束方程的变量系数都大于等于0，不等号都为小于等于，因此，将LP问题的解去尾取整（都变小了），一定是整数规划问题的可行解。 则：x1=2, x2=3， 2x1 + 3x2=13(下界) x1=2.44, x2=3.26

（3）将一个线性规划问题分为两枝，求解。 怎么分枝？ 将线性规划1中的最优解的两个非整数变量x1=2.44, x2=3.26中挑选一个离整数最远的变量x1。若X1取整数值，则X1可由x1 ≤2或x2 ≥3范围内取得。 在线性规划1中加入两个上述约束条件，将其 分枝为线性规划2和线性规划3.

线性规划2 线性规划3 max 2x1 + 3x2 s.t. 195x1 +273 x2 ≤1365, 4x1 + 40x2 ≤140 z2=13.9, x1 =2, x2 =3.30 z2=14.58, x1 =3, x2 =2.86

(4) 修改整数线性规划的最优目标函数值的上、下界 上界： 线性规划2中（增加x1 ≤2），整数规划的最优目标函数值不超过13.90（性质1） 线性规划3中（增加x1 ≥ 3），整数规划的最优目标函数值不超过14.58 （性质1） 因此，上界修改为14.58（取大者） 下界： 线性规划2中，一定有整数规划可行解x1 =2, x2 =3，目标函数值为13 线性规划3中，一定有整数规划可行解x1 =3, x2 =2，目标函数值为12 因此，下界修改为13（取大者） 为了求出最优整数解，不断缩小其最优目标函数值的上下界的距离，通过分枝使得上界越来越小，下界越来越大，才有可能使得上下界重合，找到最终的整数最优解 相比原来的上界14.66，变小了 相比原来的下界，恰好没变

（5）在线性规划2和线性规划3中选择一个上界最大线性规划进行分枝。 怎么分枝？ 线性规划3的最优解为x1 =3, x2 =2.86，x2 与整数距离最远，将其分成x2 ≤2和x2 ≥3两种情况。分别作为约束条件加在线性规划3中。 因此，线性规划3分枝成线性规划4和线性规划5.

无可行解 线性规划5 线性规划4 max 2x1 + 3x2 s.t. 195x1 +273 x2 ≤1365, z2=14, x1 =4, x2 =2 无可行解

考察线性规划2,4,5 上下界重合 （6）进一步修改整数规划最优目标函数值的上下界 上界： 下界： 最优值改为目标函数值分别为13.90,14和无解，因此上界14（取大者） 下界： 线性规划2存在整数可行解x1 =2, x2 =3，目标函数值为13 线性规划4存在整数可行解x1 =4, x2 =2 ，目标函数值为14 线性规划5无解 下界改为14（取大者） 1 考察线性规划2,4,5 2 3 4 5 上下界重合

性质2 当整数规划的最优目标函数值的上界等于其下界时，该整数规划的最优解已被求出，这个整数规划的最优解即为其目标函数值取此下界的对应线性规划的整数可行解。

× 例：分枝定界法的求解思路图 线性规划1 Z1=14.66 X1=2.44 X2=3.26 X1=2， X2=3求出下界 线性规划2 Z2=13.90 X1=2 X2=3.30 线性规划3 Z3=14.58 X1=3 X2=2.86 x1=2,x2=3求出目标函数值12 x1=3,x2=2求出目标函数值13 × X2≤2 X2≥3 线性规划4 Z4=14.00 X1=4 X2=2 线性规划5 无可行解 x1=4,x2=2求出目标函数值14 z=14, =14

§4 整数规划的分支定界法 分枝定界法步骤（总结）： 第一步： 求解与IP（整数规划，问题A）相应的LP（线性规划，问题B）问题，可能会出现下面几种情况： 若B所得的最优解的各变量恰好取整数，则这个解也是原整数规划的最优解，计算结束。 若B无可行解，则原整数规划问题也无可行解，计算结束。 若B有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，记录其目标函数Z1值。

第二步：确定A的最优目标函数值的Z*上下界，上界 即为刚才记录的Z1，下界利用观察法找到A的一个整数可行解，将其目标函数值作为Z*的下界z 第四步：在B的不满足整数条件的最优解中选一个最远离整数的变量如xl，进行分枝，构造两个约束条件xl [xl] ，xl [xl] +1，把这两个约束条件分别加进原问题B中，形成两个互不相容的子问题Bl ，B2 （分枝）。

第五步：求解分枝Bl ，B2，修改问题A的最优目标函数值的上下界。 取分枝Bl ，B2的最优目标函数值中最大的值作为新的上界； 用观察法取分枝Bl ，B2的各自的整数可行解，选择其中一个较大的目标函数值作为新的下界。 第六步：各个分枝的最优目标函数中小于目前的上界，则剪掉该分枝；若大于，但不符合整数条件，则重复第三步至第六步，直到上下界相等。

第六章 整数规划 作业： 3－7 本章结束

第3题 设Xi为第i项工程，i=1,2,3,4,5，Xi为0-1变量： Xi为0时，表明该项目没有被选中 Xi为1时，表明该项目被选中 三年后总收入最大的目标函数为： MAX Z=20X1+40X2+20X3+15X4+30X5 S.T. 5X1+4X2+3X3+7X4+8X5≤25 X1+7X2+9X3+4X4+6X5≤25 8X1+10X2+2X3+X4+10X5≤25 X1，X2，X3，X4，X5 ≥0，且为0-1变量

第4题 设X1，X2，X3分别为利用A,B,C设备生产的产品的件数。成本包括生产准备费，生产成本两部分。生产准备费为固定费用，只有利用该设备时才发生这部分费用. 因此设一个0-1变量yi，设 yi=1时，当利用第i种设备生产时，此时相应的Xi>0 yi=0时，当不利用第i种设备生产时，此时相应的Xi=0 目标函数为： Min Z=7x1+2x2+5x3+100y1+300y2+200y3

(1) 约束条件 X1≤ 800，X2≤ 1200，X3≤ 1400， X1+X2+X3=2000(改大于等于结果相同) 0.5X1+1.8X2+1.0X3 ≤ 2000 还得保证Yi=0时，Xi=0.(没有准备费就不启用该设备)，引入一个很大的M Xi ≤ M Yi（i=1,2,3） Xi ≥ 0,（i=1,2,3） Yi（i=1,2,3）是0-1变量

（2）约束条件改为 0.5X1+1.8X2+1.0X3 ≤ 2500

（3）约束条件改为 0.5X1+1.8X2+1.0X3 ≤ 2800

（4）去掉电量的约束条件

第5题 5：

yi是0-1变量， yi=0，相当于该库房不存在 北京 上海 广州 武汉 yi是0-1变量， yi=0，相当于该库房不存在 华北 华中 华南 需求量 上海y2，武汉y4 0,1 0,0 1,1 最多3个库房 武汉和广州不能同时建

第6题：指派问题 （1）引入0—1变量 xij，并令 xij =1(当指派第i人去完成第j项工作时) 0(当不指派第i人去完成第j项工作时)． 目标函数 Min Z= 20x11+ 19x12+ 20x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x44

x11+ x12+ x13+ x14= 1 (甲只能干一项工作) x21+ x22+ x23+ x24= 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工作只能一人干)

约束条件不变 （2）把目标函数改为求最大值即可，即： Max Z= 20x11+ 19x12+ 20x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x44 约束条件不变

（3）增加了一项工作E，问应指派四个人干哪四项工作，共有五项工作，则结果中肯定有一项工作无人做。 m<n，人数少于任务数。此时，添加虚拟人数n-m=1个，该人是虚拟的，因此完成各项工作所需的时间都设为0.此时变为5个人完成5项工作的问题了。 Min Z= 20x11+ 19x12+ 20x13+ 28x14+17x15 + 18x21+24x22+27x23+ 20x24+ 20x25+ 26x31+16x32+15x33+ 18x34+ 15x35+ 17x41+ 20x42+ 24x43+ 19x44 +16x45 + 0x51+ 0x52+ 0x53+ 0x54 +0x55

约束条件 x11+ x12+ x13+ x14 + x15 = 1 x21+ x22+ x23+ x24 + x25 = 1 结果中安排第5个虚拟人去做哪项工作，表明实际中该项工作无人做

（4）增加了一个人，问应指派哪四个人去干这四项工作，肯定有一个人没有工作做。 目标函数 Min Z= 20x11+ 19x12+ 20x13+ 28x14+ 18x21+ 24x22+ 27x23+ 20x24+ 26x31+ 16x32+ 15x33+ 18x34+ 17x41+ 20x42+ 24x43+ 19x44 + 16x51+ 17x52+ 20x53+ 21x54

x11+ x12+ x13+ x14 ≤ 1 (甲至多干一项工作) x21+ x22+ x23+ x24 ≤ 1 (乙至多干一项工作) x31+ x32+ x33+ x34 ≤ 1 (丙至多干一项工作) x41+ x42+ x43+ x44 ≤ 1 (丁至多干一项工作) x51+ x52+ x53+ x54 ≤ 1 (戊至多干一项工作) x11+ x21+ x31+ x41 + x51 = 1 ( A工作只能一人干) x12+ x22+ x32+ x42 + x52 = 1 ( B工作只能一人干) x13+ x23+ x33+ x43 + x53 = 1 ( C工作只能一人干) x14+ x24+ x34+ x44 + x54 = 1 ( D工作只能一人干)

第7题 对于城市A 分城市讨论 到达 停留1小时费用为x元 101 102 103 104 105 起飞 到达 101 9:00 102 10:00 103 15:00 104 20:00 105 22:00 106 7:00 2*2x=4x 3*3x=9x 8*8x=64x 13*13x=169x 15*15x=225x 107 14:00 19*19x=361x (次日) 20*20x=400x 25*25x=625x 6*6x=36x 108 18:00 15*15x=225x(次日) 16*16x=256x 21*21x=441x 4*4x=16x 109 11:00 22*22x=484x 23*23x=529x 9*9x=81x 11*11x=121x 110 19:00 14*14x=196x 分城市讨论 101 102 103 104 105 106 107 108 109 110 例：106航班7:00达到A，让102航班10:00起飞

依此分析城市B，城市C 根据上一航班到达的时间与下一航班起飞时间的时间差，如果大于2小时，当天可起飞，否则，只能次日起飞。根据停留时间，计算出每一种情况的停留损失费，填入矩阵中即可利用“指派问题”求解。 最优值一定，最优解或许不唯一。