管理运筹学 第8章——整数规划

目标函数： Max Z = 2x1 +3 x2
约束条件： s.t. 195 x1 + 273 x2 ≤1365 4 x1 + 40 x2 ≤140 x1 ≤4 x1，x2 ≥ 0 ,且为整数。
5
8.1 整数规划的特点及应用
如果去掉最后一个约束，就是一个线性规划问题。利用图解法，
x2
(2.44 , 3.26)
例1. 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、 重量、可获利润以及托运所受限制如表所示。
货物 甲 乙 托运限制 每件体积 （立方英尺） 195 273 1365 每件重量 （百千克） 4 40 140 每件利润 （百元） 2 3
甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？ 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型
工作 工人 甲 乙 丙 丁
A 15 19 26 19
B 18 23 17 21
C 21 22 16 23
D 24 18 19 17
8.1 整数规划的特点及应用
解：引入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 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
x1 = 3.08，x2 = 2.32，x3 = 3.44 z = 21.88
2、 1, 3 ≥ 0， 2为整数 用《管理运筹学》软件求解得（P165E2-2）：
x
x1 = 2.82，x2 = 2，x3 = 3.09 z = 19.73
3、 1, 2, 3为整数 用《管理运筹学》软件求解得（P165E2-3） ：
8.1 整数规划的特点及应用
固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源 为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数 量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别 为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人 月，机器有100台月，此外，不管每种容器制造的数量是多少，都要 支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200 万元。现在要制定一个生产计划，使获得的利润为最大。
解： b) 设 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 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 销地的限制) y2+y3 = 1 (A2，A3地建一个厂) xij ≥0，i = 1,2,3,4,5； j = 1,2,3， yk 为0--1变量，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 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。 * * * 求解可用《管理运筹学》软件中整数规划方法。
若该松弛问题是一个线性规划，则称该整数规划为整数线性 规划。Integer Linear Programming
max Z (或 min Z )
c
j 1
n
j
xj
n ( i 1.2 m ) a ij x j bi j 1 x j 0 (j 1.2 n) 且 部 分 或 全 部 为 整 数
x x x
x1 = 2， x2 = 2 ， x3 = 3
z = 17
4、 1, 2为整数, 3为0-1 用《管理运筹学》软件求解得（P165E2-4） ：
x x
x
x1 = 1， x2 = 2 ， x3 = 1
z = 8
8.1 整数规划的特点及应用 投资场所的选择
例4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部， 拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民 的消费水平及居民居住密集度，规定： 在东区由A1 ， A2 ，A3 三个点至多选择两个； 在西区由A4 ， A5 两个点中至少选一个； 在南区由A6 ， A7 两个点中至少选一个； 在北区由A8 ， A9 ， A10 三个点中至少选两个。
性规划的最小目标函数值。
6
8.1 整数规划的特点及应用
整数规划的计算机求解
1、 1, 2, 3 ≥ 0 用《管理运筹学》软件求解得（P165E2-1）：
x x x x x
例2 ： Max z = 3x1 + x2 + 3x3 - x 1 + 2 x 2 + x 3≤ 5 s.t. 4x2 -3x3 ≤2 x1 -3x2 + 2x3 ≤3 x 1, x 2, wenku.baidu.com 3 ≥ 0
3 2 1 1 2
2x1+3x2 =14.66
(4 , 2)
2x1+3x2 =14 3 2x1+3x2 =6 4
性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标 函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函
数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线
8.1 整数规划的特点及应用
整数线性规划问题的种类：
Page 4
纯整数线性规划：指全部决策变量都必须取整数值的整数 线性规划。 混合整数线性规划：决策变量中有一部分必须取整数值， 另一部分可以不取整数值的整数线性规划。 0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
8.1 整数规划的特点及应用
2x1 + 3x2 + 4x3 ≤ 300
x1 + 2x2 + 3x3 ≤ 100
xi ≤ M yi ，i =1，2，3，M充分大
xi ≥ 0 且为整数， yi 为0-1变量，i = 1,2,3
8.1 整数规划的特点及应用
指派问题
有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于 每人特长不同，完成各项任务的效率等情况也不同。 现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。 例6．有四个工人，要分别指派他们完成四项不同的工作，每人做 各项工作所消耗的时间如下表所示，问应如何指派工作，才能使 总的消耗时间为最少。
A1 投资额 利润 100 36 A2 40 A3 50 A4 80 22 A5 70 20 A6 90 30 A7 80 25 A8 140 48 A9 160 58 A10 180 61 120 150
Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预 测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择 哪几个销售点，可使年利润为最大?(P166E4)
销地 产地 A1 A2 A3 A4 A5 销量(千吨) B1 8 5 4 9 10 30 B2 4 2 3 7 4 20 B3 3 3 4 5 2 20 产量(千吨) 30 10 20 30 40
解： a) 设 xij为从Ai 运往Bj 的运输量(单位千箱)， yk = 1(当Ak 被选 中时)或0（当Ak 没被选中时),k =2,3,4,5。这可以表示为一个整数规 划问题：
资源 金属板（吨） 劳动力（人月） 机器设备（台月）
小号容器 2 2 1
中号容器 4 3 2
大号容器 8 4 3
8.1 整数规划的特点及应用
解：设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用
的这种性质，设 yi = 1(当生产第 i种容器, 即 xi ＞ 0 时) 或0（当不生产第 i
Chapter 08：
整数规划
整数规划

8.1 整数规划的特点与应用 8.2

整数规划的求解方法
分支定界法 分配问题与匈牙利法
8.1 整数规划的特点及应用
整数规划（简称：IP）
Page 3
一部分或全部决策变量取整数值的规划问题称为整数规划。 不考虑整数条件，由余下的目标函数和约束条件构成的规划 问题称为该整数规划问题的松弛问题。
8.1 整数规划的特点及应用
投资场所的选择
解：设：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 把上述模型输入管理运筹学软件,即得到此问题的最优解如下: 最优目标函数值为245. 最优解为: x1=1,x2=1,x3=0,x4=0,x5=1,x6=1,x7=0,x8=0,x9=1,x10=1
8.1 整数规划的特点及应用
四、分布系统设计
例7．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了 扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知 在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、 375千元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量 ，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所 示。 a) 问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成 本和总的运输费用之和最小? b) 如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?
种容器即 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 ≤ 500