解： 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。 * * * 求解可用《管理运筹学》软件中整数规划方法。
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
3 2 1 1 2
2x1+3x2 =14.66
(4 , 2)
2x1+3x2 =14 3 2x1+3x2 =6 4
性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标 函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函
数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线
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)
若该松弛问题是一个线性规划，则称该整数规划为整数线性 规划。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) 且 部 分 或 全 部 为 整 数
销地 产地 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。这可以表示为一个整数规 划问题：
目标函数： 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分别为甲、乙两种货物托运的件数，建立模型
种容器即 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
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．有四个工人，要分别指派他们完成四项不同的工作，每人做 各项工作所消耗的时间如下表所示，问应如何指派工作，才能使 总的消耗时间为最少。
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地建一个厂，应在哪几个地方建厂?
工作 工人 甲 乙 丙 丁
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
8.1 整数规划的特点及应用
固定成本问题 例5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源 为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数 量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别 为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人 月，机器有100台月，此外，不管每种容器制造的数量是多少，都要 支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200 万元。现在要制定一个生产计划，使获得的利润为最大。
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。 * * * 求解可用《管理运筹学》软件中整数规划方法。