第八章 整数规划
§ 1 整数规划的图解法
§ 2整数规划的计算机求解
§ 3整数规划的应用
§ 4整数规划的分枝定界法
§ 1 整数规划的图解法
例 1,某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备
需要 A,B两种材
料的消耗以及资
源的限制，如右
表。
问题：工厂应分
别生产多少件甲、乙种仪器设备才
能使工厂获利最多？
甲 乙 资源限制
材料 A 3 2 10
材料 B 0 2 5
单件获利 1 万元 1 万元
解、
目标函数,Max z = x1 + x2
约束条件,s.t,
3 x1 + 2 x2 ≤ 10
2 x2 ≤ 5
x1,x2 ≥ 0 为整数
不考虑整数约束得到最优解：
x1 =1.667,x2 = 2.5； z = 4.167
考虑整数约束得到最优解：
x1 = 2,x2 = 2； z = 4
整数规划的最优目标值小于相应
线性规划的最优目标值 (相当于附加一个约束 )
§ 2整数规划的计算机求解
例 2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 为整数
例 2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 为整数 x1 为 0-1变量
用《管理运筹学》软件求解得：
x1 = 0 x2 = 3 x3 = 0
z = 30
用《管理运筹学》软件求解得：
x1 = 1 x2 = 1.5 x3 = 0
z = 30
§ 3整数规划的应用 (1)
一、投资场所的选择
例 4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10个
位置 Aj (j＝ 1,2,3,…, 10)可供选择，考虑到各地区居民的消费水平及居民居住密集
度，规定：
在东区由 A1, A2, A3 三个点至多选择两个；
在西区由 A4, A5 两个点中至少选一个；
在南区由 A6, A7 两个点中至少选一个；
在北区由 A8, A9, A10 三个点中至少选两个 。
Aj 各点的设备投资及每
年可获利润由于地点不同都是
不一样的，预测情况见右表所
示 (单位：万元 )。但投资总额不能超过 720万元，问应选择哪几个销售点，可使年利润为最
大?
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10
投资额 100 120 150 80 70 90 80 140 160 180
利润 36 40 50 22 20 30 25 48 58 61
解,设,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
xj ≥ 0 xj 为 0--1变量, i = 1,2,3,……,10
二、固定成本问题
例 5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机
器设备，制造一个容器所需的各种资源的数量如右
表所示。不考虑固定费用，每种容器售出一只所得
的利润分别为 4万元,5万元,6万元，可使用的金
属板有 500吨，劳动力有 300人月，机器有 100台月，
此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是 l00万元，中号为 150
万元，大号为 200万元。现在要制定一个生产计划，使获得的利润为最大。
解：这是一个整数规划的问题。
设 x1,x2,x3 分别为小号容器、中号容器和大号容器的生产数量。
各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设
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 ≤ 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整数规划的应用 (2) 资源 小号容器 中号容器 大号容器金属板 （吨） 2 4 8
劳动力 （人月） 2 3 4
机器设备 （ 台月） 1 2 3
例 6．有四个工人，要分别指派他们完
成四项不同的工作，每人做各项工作所消
耗的时间如右表所示，问应如何指派工作，
才能使总的消耗时间为最少。
解, 引入 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
* * * 求解可用《管理运筹学》软件中整数规划方法。
§ 3整数规划的应用 (3)
工作
工人
A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
三、指派问题
有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各
项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派
给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。
四、分布系统设计
例 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) 设 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+ x13 ≤ 30 ( A 1 厂的产量限制 )
x21+ x22+ x23 ≤ 10 y2 ( A2 厂的产量限制 ) b） 增加约束,y2+y3=1
x31+ x32+ x33 ≤ 20 y3 ( A3 厂的产量限制 )
x41+ x42+ x43 ≤ 30 y4 ( A4 厂的产量限制 )
x51+ x52+ x53 ≤ 40 y5 ( 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,2,3,4,5； j = 1,2,3
* * * 求解可用《管理运筹学》软件中整数规划方法。
§ 3整数规划的应用 (4)
销地
产地
B 1 B 2 B 3 产量 ( 千吨 )
A 1 8 4 3 30
A 2 5 2 3 10
A 3 4 3 4 20
A 4 9 7 5 30
A 5 10 4 2 40
销量 ( 千吨 ) 30 20 20
§ 3整数规划的应用 (5)
五、投资问题
例 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的投资额；
设 yiA,yiB，是 0— 1变量，并规定取 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；
这样我们建立如下的决策变量：
第 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；
第四年：年初的资金为 1.15x2A+1.06x3D,于是 x4A + x4D = 1.15x2A+ 1.06x3D；
第五年：年初的资金为 1.15x3A+1.06x4D,于是 x5D = 1.15x3A+ 1.06x4D；
关于项目 A的投资额规定, x1A ≥ 40000 y1A, x1A ≤ 200000 y1A, 200000是足够大的数；
保证当 y1A = 0时,x1A = 0 ； 当 y1A = 1时,x1A ≥ 40000 。
关于项目 B的投资额规定, x3B ≥ 30000 y3B, x3B ≤ 50000 y3B ；
保证当 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 ≥ 40000 y1A,
x1A ≤ 200000 y1A,
x3B ≥ 30000 y3B,
x3B ≤ 50000 y3B ；
x2C = 20000y2C,
yiA,yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA, xiB, xiC, xiD ≥ 0 ( i = 1, 2,3,4,5）
§ 4整数规划的分枝定界法 (1)
问题（ A） Min z = c1 x1 + c2 x2 + … + c n xn 记 问题（ B） 为去掉整数约束的问题（ A）
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0 为整数
在分枝定界法过程中求解问题 (B)，应有以下情况之一：
① (B)无可行解，则 (A)亦无可行解，停止对此问题 的计算；
② (B)有最优解，并满足整数约束，即同时为 (A)的最优解，那么 z*同时是当前问题 (A)最优
目标值的上界
和下界。停止对这个问题的计算；
③ (B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题 (A)最优目标值的一个下
界 z ＝ z,于是通过以下判断可对此问题进一步计算。
分枝定界法的计算过程：
1、对原问题 (A)，求解松弛问题 (B)。根据上面分析，若出现情况①，②则停机。若情况③
发生，得到 (A)问题最优值的一个下界。我们任找 (A)问题的一个可行解，那么对应的目标
函数值是 (A)最优值的一个上界 zˉ 。 即得到 z ＜ z* ＜ zˉ。 (注：找 (A)问题的可行解往往需
要较大的计算量，这时可简单记 zˉ＝ +?,而先不必费很大力量去求较好的上界。从以下
分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。 )，
转 2，进行以下一般步的迭代；
§ 4整数规划的分枝定界法 (2)
2、对当前问题进行分枝和定界：
分技,无妨设当前问题为 (A),其松弛问题 (B)的最优解不符合整数约束，任取非整数的分
量 xr 。构造两个附加约束,xr ≤ [xr] 和 xr ≥ [xr]+1,对 (A)分别加入这两个约束，可得到两
个子问题 (A1)和 (A2),显然这两个子问题的可行解集的并是 (A)的可行解集；
定界,根据前面分析，对每个当前问题 (A)可以通过求解松弛问题 (B)，以及找 (A)的可行解
得到当前问题的上、下界 zˉ和 z 。
对一般迭代步，设根据分枝定界方法得到了原问题 (A)的一个同层子问题 (AI ),i＝ 1,2,...，
n 之和的分解。这里的同层子问题是指每个子问题 (AI)都是 (A)经过相同分枝次数得到的。
3、比较与剪枝：
对当前子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪
枝：
① (B)无可行解；
② (B)的最优解符合整数约束；
③ (B)的最优值 z ≥ zˉ 。
通过比较，若子问题不剪枝则返回 2 。
分枝定界法当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界 zˉ 的可
行解即原问题的最优解,算法结束。
§ 4整数规划的分枝定界法 (3)
分枝定界法是
求整数规划的一种
常用的有效的方法，
既能解决纯整数规
划的问题，也能解
决混合整数规划的
问题。
例：
Min f = -5x1-4x2
s.t,3x1+4x2 ≤ 24
9x1+5x2 ≤ 45
x1,x2 ≥ 0 整数
§ 4整数规划的分枝定界法 (4)
隐枚举法是求解 0— 1规划最常用的方法之一
对于 n 个决策变量的完全 0— 1 规划，其可行点最多有 2n 个，当 n 较大时其
计算量大得惊人。隐枚举法的基本思想是根据 0— 1规划的特点，进行分技逐步
求解。
1、用于隐枚举法的 0— 1规划标准形式：
为了计算的方便，需要把一般的 0— 1规划问题等价地化成下列标准形式
Min f = c1 x1 + c2 x2 + … + c n xn cj ≥ 0 j = 1,2,…,n
s.t,ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m
x1, x2, …, xn = 0 或 1
下面说明一个完全的 0— 1规划问题可以化为等价的标准形式：
(1)若目标函数求最大,Max z,可令 f = - z,变为求最小 Min f ；
(2)若目标函数的系数有负值时，如 cj ＜ 0。那么，可以令相应的 yj = 1- xj ；
(3)当某个约束不等式是,≥”时，只需两端同乘以 -1，即变为,≤” ；
(4)当某个约束是等式约束时，可得到两个方向相反的不等式。
§ 4整数规划的分枝定界法 (5)
隐枚举法的基本过程：
1、将 0— 1规划问题化为标准形式，设其最优解为 x*,最优目标值为 f* 。显然 x =
0 时，目标值 f ＝ 0 是不考虑线性不等式约束的最小解，于是 f* ≥ 0。若 x = 0 是
可行解，那末 f ＝ 0是该问题的最优解，结束计算。否则，置所有分量为自由变量。
转 2；
2、任选一自由变量 xk, 令 xk 为固定变量，分别固定为 xk = 0 与 xk ＝ 1,令所有自
由变量取零值，则得到两个分枝。对每个分枝的试探解进行检验（把自由变量逐
次定为固定变量的顺序可以是任意的，在不进行先验考察时，常按指标变量从小
到大的顺序进行）。转 3；
3、检验当前试探解时，遇到下列 4种情况就剪枝，即不必再向下分枝，在剪枝的子
问题下方标记“×”：
情况一：若子问题的试探解可行，即满足所有线性不等式约束，则此问题的目标值
是原问题最优目标值的一个上界记为 fˉ 即 f* ≤ fˉ 。把 fˉ 的值记在子问题框的
旁边，并在下方标记上“×”；
§ 4整数规划的分枝定界法 (6)
情况二：若试探解不可行，且存在一个线性不等式约束，将所有固定变量值代入后，
所得到的不等式中所有负系数之和大于右端项或若无负系数时，最小的系数大于
右端项，那么此问题的任何分枝都是不可行的问题。于是在此问题框的下方标记
“×”；
情况三：若试探解不可行，且它的目标值与目标函数中对应当前自由变量的任一
个系数之和大于所有已得到的上界中最小者时，说明在当前问题的基础上，固定
任何自由变量都不可能对目标函数有改善，于是在该问题框的下方标记“×”；
情况四：若试探解不可行，但所有变量已被置为固定变量，也应剪枝，于是在该
问题框的下方标记“×”。
把已标记“×”的子问题，称为已探明的枝。转 4。
4、进一步考察。如果所有的枝均为已探明的枝，则停机结束计算。找出所有子问
题框边标记 fˉ 值的问题，比较得到其中最小者，其对应的试探解即原问题的最
优解，相应值即原问题的最优目标值 f*；若没有标记 fˉ 值的框，则说明原问题无
最优解，实际上原问题无可行解。
如果仍存在尚未探明的分枝，则可任选一个未探明的分枝。转 2。
§ 4整数规划的分枝定界法 (7)
0-1规划的隐枚举法
例：
Max z=100x1+30x2+40x3+45x4
s.t,50x1+30x2+25x3+10x4≤95
7x1+ 2x2+ 3x3+ 4x4≤11
2x1+ x2+ x3+10x4≤12
x4 ≤ x2+ x3
xj= 0 或 1, i = 1,2,3,4
标准化：
取 f’=-z=-100x1-30x2-40x3 -45x4
令 y1=1-x1,y2=1-x2,y3=1-x3,
y4=1-x4
f’=100y1+30y2+40y3 +45y4-215,
记 f = f’ + 215,得到
Min f=100y1+30y2+40y3 +45y4
s.t,
-50y1-30y2-25y3 -10y4≤ -20
- 7y1- 2y2- 2y3 - 4y4≤ - 4
- 2y1- y2- y3 -10y4≤ - 2
y2+ y3 - y4≤ 1
yj= 0 或 1, i = 1,2,3,4
第九章 动态规划
§ 1 多阶段决策过程最优化问题举例
§ 2 基本概念、基本方程与最优化原理
§ 3 动态规划的应用
（见文本）
§ 1 多阶段决策过程最优化问题举例
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
例 1最短路径问题
右图表示从起点 A到终点
E之间各点的距离 。 求 A
到 E的最短路径 。
如果用穷举法，则从 A到 E一共有 3× 3× 2=18条不同的路径，逐个计算每条路径的长度，
总共需要进行 4× 18=72次加法计算；对 18条路径的长度做两两比较，找出其中最短的一
条，总共要进行 18－ 1=17次比较。如果从 A到 C的站点有 k个，则总共有 3k-1× 2条路径，
用穷举法求最短路径总共要进行 (k+1)3k-1× 2次加法,3k-1× 2-1次比较。当 k的值增加时，
需要进行的加法和比较的次数将迅速增加。例如当 k=10时，加法次数为 433026次，比较
39365次。
以上这求从 A到 E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子
问题，即分别从 B1,B2,B3到 E的最短路径问题。
记从 Bi (i=1,2,3) 到 E的最短路径为 S(Bi),则从 A到 E的最短距离 S(A)可以表示为：
§ 1 整数规划的图解法
§ 2整数规划的计算机求解
§ 3整数规划的应用
§ 4整数规划的分枝定界法
§ 1 整数规划的图解法
例 1,某工厂在计划期内要安排甲、乙两种仪器设备的生产，已知生产仪器设备
需要 A,B两种材
料的消耗以及资
源的限制，如右
表。
问题：工厂应分
别生产多少件甲、乙种仪器设备才
能使工厂获利最多？
甲 乙 资源限制
材料 A 3 2 10
材料 B 0 2 5
单件获利 1 万元 1 万元
解、
目标函数,Max z = x1 + x2
约束条件,s.t,
3 x1 + 2 x2 ≤ 10
2 x2 ≤ 5
x1,x2 ≥ 0 为整数
不考虑整数约束得到最优解：
x1 =1.667,x2 = 2.5； z = 4.167
考虑整数约束得到最优解：
x1 = 2,x2 = 2； z = 4
整数规划的最优目标值小于相应
线性规划的最优目标值 (相当于附加一个约束 )
§ 2整数规划的计算机求解
例 2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0 为整数
例 2：
Max z = 15x1 + 10x2 + 7x3
s.t.
5x1 - 10x2 + 7x3 ≤ 8
6x1 + 4x2 + 8x3 ≤ 12
-3x1 + 2x2 + 2x3 ≤ 10
x1,x2,x3 ≥ 0
x3 为整数 x1 为 0-1变量
用《管理运筹学》软件求解得：
x1 = 0 x2 = 3 x3 = 0
z = 30
用《管理运筹学》软件求解得：
x1 = 1 x2 = 1.5 x3 = 0
z = 30
§ 3整数规划的应用 (1)
一、投资场所的选择
例 4、京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有 10个
位置 Aj (j＝ 1,2,3,…, 10)可供选择，考虑到各地区居民的消费水平及居民居住密集
度，规定：
在东区由 A1, A2, A3 三个点至多选择两个；
在西区由 A4, A5 两个点中至少选一个；
在南区由 A6, A7 两个点中至少选一个；
在北区由 A8, A9, A10 三个点中至少选两个 。
Aj 各点的设备投资及每
年可获利润由于地点不同都是
不一样的，预测情况见右表所
示 (单位：万元 )。但投资总额不能超过 720万元，问应选择哪几个销售点，可使年利润为最
大?
A 1 A 2 A 3 A 4 A 5 A 6 A 7 A 8 A 9 A 10
投资额 100 120 150 80 70 90 80 140 160 180
利润 36 40 50 22 20 30 25 48 58 61
解,设,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
xj ≥ 0 xj 为 0--1变量, i = 1,2,3,……,10
二、固定成本问题
例 5．高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机
器设备，制造一个容器所需的各种资源的数量如右
表所示。不考虑固定费用，每种容器售出一只所得
的利润分别为 4万元,5万元,6万元，可使用的金
属板有 500吨，劳动力有 300人月，机器有 100台月，
此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是 l00万元，中号为 150
万元，大号为 200万元。现在要制定一个生产计划，使获得的利润为最大。
解：这是一个整数规划的问题。
设 x1,x2,x3 分别为小号容器、中号容器和大号容器的生产数量。
各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设
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 ≤ 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整数规划的应用 (2) 资源 小号容器 中号容器 大号容器金属板 （吨） 2 4 8
劳动力 （人月） 2 3 4
机器设备 （ 台月） 1 2 3
例 6．有四个工人，要分别指派他们完
成四项不同的工作，每人做各项工作所消
耗的时间如右表所示，问应如何指派工作，
才能使总的消耗时间为最少。
解, 引入 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
* * * 求解可用《管理运筹学》软件中整数规划方法。
§ 3整数规划的应用 (3)
工作
工人
A B C D
甲 15 18 21 24
乙 19 23 22 18
丙 26 17 16 19
丁 19 21 23 17
三、指派问题
有 n 项不同的任务，恰好 n 个人可分别承担这些任务，但由于每人特长不同，完成各
项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把 n 项任务指派
给 n 个人，使得完成 n 项任务的总的效率最高，这就是指派问题。
四、分布系统设计
例 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) 设 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+ x13 ≤ 30 ( A 1 厂的产量限制 )
x21+ x22+ x23 ≤ 10 y2 ( A2 厂的产量限制 ) b） 增加约束,y2+y3=1
x31+ x32+ x33 ≤ 20 y3 ( A3 厂的产量限制 )
x41+ x42+ x43 ≤ 30 y4 ( A4 厂的产量限制 )
x51+ x52+ x53 ≤ 40 y5 ( 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,2,3,4,5； j = 1,2,3
* * * 求解可用《管理运筹学》软件中整数规划方法。
§ 3整数规划的应用 (4)
销地
产地
B 1 B 2 B 3 产量 ( 千吨 )
A 1 8 4 3 30
A 2 5 2 3 10
A 3 4 3 4 20
A 4 9 7 5 30
A 5 10 4 2 40
销量 ( 千吨 ) 30 20 20
§ 3整数规划的应用 (5)
五、投资问题
例 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的投资额；
设 yiA,yiB，是 0— 1变量，并规定取 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；
这样我们建立如下的决策变量：
第 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；
第四年：年初的资金为 1.15x2A+1.06x3D,于是 x4A + x4D = 1.15x2A+ 1.06x3D；
第五年：年初的资金为 1.15x3A+1.06x4D,于是 x5D = 1.15x3A+ 1.06x4D；
关于项目 A的投资额规定, x1A ≥ 40000 y1A, x1A ≤ 200000 y1A, 200000是足够大的数；
保证当 y1A = 0时,x1A = 0 ； 当 y1A = 1时,x1A ≥ 40000 。
关于项目 B的投资额规定, x3B ≥ 30000 y3B, x3B ≤ 50000 y3B ；
保证当 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 ≥ 40000 y1A,
x1A ≤ 200000 y1A,
x3B ≥ 30000 y3B,
x3B ≤ 50000 y3B ；
x2C = 20000y2C,
yiA,yiB = 0 或 1,i = 1,2,3,4,5
y2C = 0,1,2,3,4
xiA, xiB, xiC, xiD ≥ 0 ( i = 1, 2,3,4,5）
§ 4整数规划的分枝定界法 (1)
问题（ A） Min z = c1 x1 + c2 x2 + … + c n xn 记 问题（ B） 为去掉整数约束的问题（ A）
s.t,a11 x1 + a12 x2 + … + a1n xn = b1
a21 x1 + a22 x2 + … + a2n xn = b2
…… ……
am1 x1 + am2 x2 + … + amn xn = bm
x1, x2, …, xn ≥ 0 为整数
在分枝定界法过程中求解问题 (B)，应有以下情况之一：
① (B)无可行解，则 (A)亦无可行解，停止对此问题 的计算；
② (B)有最优解，并满足整数约束，即同时为 (A)的最优解，那么 z*同时是当前问题 (A)最优
目标值的上界
和下界。停止对这个问题的计算；
③ (B)有最优解 x 及最优值 z 但不符合整数条件。这时得到当前问题 (A)最优目标值的一个下
界 z ＝ z,于是通过以下判断可对此问题进一步计算。
分枝定界法的计算过程：
1、对原问题 (A)，求解松弛问题 (B)。根据上面分析，若出现情况①，②则停机。若情况③
发生，得到 (A)问题最优值的一个下界。我们任找 (A)问题的一个可行解，那么对应的目标
函数值是 (A)最优值的一个上界 zˉ 。 即得到 z ＜ z* ＜ zˉ。 (注：找 (A)问题的可行解往往需
要较大的计算量，这时可简单记 zˉ＝ +?,而先不必费很大力量去求较好的上界。从以下
分析可以看到，找到一个好的最优目标值上界，将对算法的快速求得目标非常有效。 )，
转 2，进行以下一般步的迭代；
§ 4整数规划的分枝定界法 (2)
2、对当前问题进行分枝和定界：
分技,无妨设当前问题为 (A),其松弛问题 (B)的最优解不符合整数约束，任取非整数的分
量 xr 。构造两个附加约束,xr ≤ [xr] 和 xr ≥ [xr]+1,对 (A)分别加入这两个约束，可得到两
个子问题 (A1)和 (A2),显然这两个子问题的可行解集的并是 (A)的可行解集；
定界,根据前面分析，对每个当前问题 (A)可以通过求解松弛问题 (B)，以及找 (A)的可行解
得到当前问题的上、下界 zˉ和 z 。
对一般迭代步，设根据分枝定界方法得到了原问题 (A)的一个同层子问题 (AI ),i＝ 1,2,...，
n 之和的分解。这里的同层子问题是指每个子问题 (AI)都是 (A)经过相同分枝次数得到的。
3、比较与剪枝：
对当前子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪
枝：
① (B)无可行解；
② (B)的最优解符合整数约束；
③ (B)的最优值 z ≥ zˉ 。
通过比较，若子问题不剪枝则返回 2 。
分枝定界法当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界 zˉ 的可
行解即原问题的最优解,算法结束。
§ 4整数规划的分枝定界法 (3)
分枝定界法是
求整数规划的一种
常用的有效的方法，
既能解决纯整数规
划的问题，也能解
决混合整数规划的
问题。
例：
Min f = -5x1-4x2
s.t,3x1+4x2 ≤ 24
9x1+5x2 ≤ 45
x1,x2 ≥ 0 整数
§ 4整数规划的分枝定界法 (4)
隐枚举法是求解 0— 1规划最常用的方法之一
对于 n 个决策变量的完全 0— 1 规划，其可行点最多有 2n 个，当 n 较大时其
计算量大得惊人。隐枚举法的基本思想是根据 0— 1规划的特点，进行分技逐步
求解。
1、用于隐枚举法的 0— 1规划标准形式：
为了计算的方便，需要把一般的 0— 1规划问题等价地化成下列标准形式
Min f = c1 x1 + c2 x2 + … + c n xn cj ≥ 0 j = 1,2,…,n
s.t,ai1 x1 + ai2 x2 + … + ain xn ≤ bi i = 1,2,…,m
x1, x2, …, xn = 0 或 1
下面说明一个完全的 0— 1规划问题可以化为等价的标准形式：
(1)若目标函数求最大,Max z,可令 f = - z,变为求最小 Min f ；
(2)若目标函数的系数有负值时，如 cj ＜ 0。那么，可以令相应的 yj = 1- xj ；
(3)当某个约束不等式是,≥”时，只需两端同乘以 -1，即变为,≤” ；
(4)当某个约束是等式约束时，可得到两个方向相反的不等式。
§ 4整数规划的分枝定界法 (5)
隐枚举法的基本过程：
1、将 0— 1规划问题化为标准形式，设其最优解为 x*,最优目标值为 f* 。显然 x =
0 时，目标值 f ＝ 0 是不考虑线性不等式约束的最小解，于是 f* ≥ 0。若 x = 0 是
可行解，那末 f ＝ 0是该问题的最优解，结束计算。否则，置所有分量为自由变量。
转 2；
2、任选一自由变量 xk, 令 xk 为固定变量，分别固定为 xk = 0 与 xk ＝ 1,令所有自
由变量取零值，则得到两个分枝。对每个分枝的试探解进行检验（把自由变量逐
次定为固定变量的顺序可以是任意的，在不进行先验考察时，常按指标变量从小
到大的顺序进行）。转 3；
3、检验当前试探解时，遇到下列 4种情况就剪枝，即不必再向下分枝，在剪枝的子
问题下方标记“×”：
情况一：若子问题的试探解可行，即满足所有线性不等式约束，则此问题的目标值
是原问题最优目标值的一个上界记为 fˉ 即 f* ≤ fˉ 。把 fˉ 的值记在子问题框的
旁边，并在下方标记上“×”；
§ 4整数规划的分枝定界法 (6)
情况二：若试探解不可行，且存在一个线性不等式约束，将所有固定变量值代入后，
所得到的不等式中所有负系数之和大于右端项或若无负系数时，最小的系数大于
右端项，那么此问题的任何分枝都是不可行的问题。于是在此问题框的下方标记
“×”；
情况三：若试探解不可行，且它的目标值与目标函数中对应当前自由变量的任一
个系数之和大于所有已得到的上界中最小者时，说明在当前问题的基础上，固定
任何自由变量都不可能对目标函数有改善，于是在该问题框的下方标记“×”；
情况四：若试探解不可行，但所有变量已被置为固定变量，也应剪枝，于是在该
问题框的下方标记“×”。
把已标记“×”的子问题，称为已探明的枝。转 4。
4、进一步考察。如果所有的枝均为已探明的枝，则停机结束计算。找出所有子问
题框边标记 fˉ 值的问题，比较得到其中最小者，其对应的试探解即原问题的最
优解，相应值即原问题的最优目标值 f*；若没有标记 fˉ 值的框，则说明原问题无
最优解，实际上原问题无可行解。
如果仍存在尚未探明的分枝，则可任选一个未探明的分枝。转 2。
§ 4整数规划的分枝定界法 (7)
0-1规划的隐枚举法
例：
Max z=100x1+30x2+40x3+45x4
s.t,50x1+30x2+25x3+10x4≤95
7x1+ 2x2+ 3x3+ 4x4≤11
2x1+ x2+ x3+10x4≤12
x4 ≤ x2+ x3
xj= 0 或 1, i = 1,2,3,4
标准化：
取 f’=-z=-100x1-30x2-40x3 -45x4
令 y1=1-x1,y2=1-x2,y3=1-x3,
y4=1-x4
f’=100y1+30y2+40y3 +45y4-215,
记 f = f’ + 215,得到
Min f=100y1+30y2+40y3 +45y4
s.t,
-50y1-30y2-25y3 -10y4≤ -20
- 7y1- 2y2- 2y3 - 4y4≤ - 4
- 2y1- y2- y3 -10y4≤ - 2
y2+ y3 - y4≤ 1
yj= 0 或 1, i = 1,2,3,4
第九章 动态规划
§ 1 多阶段决策过程最优化问题举例
§ 2 基本概念、基本方程与最优化原理
§ 3 动态规划的应用
（见文本）
§ 1 多阶段决策过程最优化问题举例
BA
CB
D
B
C
D
E
C
2
1
2
3
1
2
3
1
2
5
1
12
14
10
6
10
4
13
12
11
3
9
6
5
8
10
5
2
例 1最短路径问题
右图表示从起点 A到终点
E之间各点的距离 。 求 A
到 E的最短路径 。
如果用穷举法，则从 A到 E一共有 3× 3× 2=18条不同的路径，逐个计算每条路径的长度，
总共需要进行 4× 18=72次加法计算；对 18条路径的长度做两两比较，找出其中最短的一
条，总共要进行 18－ 1=17次比较。如果从 A到 C的站点有 k个，则总共有 3k-1× 2条路径，
用穷举法求最短路径总共要进行 (k+1)3k-1× 2次加法,3k-1× 2-1次比较。当 k的值增加时，
需要进行的加法和比较的次数将迅速增加。例如当 k=10时，加法次数为 433026次，比较
39365次。
以上这求从 A到 E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子
问题，即分别从 B1,B2,B3到 E的最短路径问题。
记从 Bi (i=1,2,3) 到 E的最短路径为 S(Bi),则从 A到 E的最短距离 S(A)可以表示为：
