5
20 <=
20
0
0
<=
10
0
10 <=
30
0
0
<=
15
0
25 <=
25
10
10 <=
10
5
5
<=
5
0
0
<=
10
20
=
Total Cost
20
($millions)
77.4
北方飞机制造公司的最优生产进度安排
月份 1 (RT) 2 (RT) 3 (RT) 3 (OT) 4 (RT)
产量 20 10 25 10 5
序 服装 市场 租金 生产 销售 人工 设备 可用工 种类 需求 元/台 成本 价格 工时 工时 时/台
1 西服 150 5000 280 400 5 3 300 2 衬衫 800 2000 30 40 1 0.5 500 3 羽绒服 350 3000 200 300 4 2 300
服装厂生产模型
20
5
10
1.13
1.15
Northern Airplane Co. Production-Scheduling Problem
Production Cost Regular
Storage Cost
($millions)
Time Overtime ($millions per month)
Month 1 1.08
Nifty Co. Product-Distribution Problem
Unit Profit
Customer 1
Plant 1
$55
Plant 2
$37
Plant 3
$29
Customer 2 $42 $18 $59
Customer 3 $46 $32 $51
Customer 4 $53 $48 $35
x1 = 1.000 x2 = 4.333
x2 ≤ 4
zU = 5.33 zL = 5.00
SUB 3
z3 = 5.0 x1 = 1.0 x2 = 4.0
LP松弛
z0 = 5.545 x1 = 1.477 x2 = 4.068
SUB 2
max x1 + x2
s.t. 6x1 + 2x2 ≤ 17
5x1 + 9x2 ≤ 44
问题：每月生产多少发动机的计划，使制造和存储的总成本达到最小
月份
1 2 3 4
计划安装量
最大产量 正常时间 加班时间
单位生产成本（百万 美元）
正常时间 加班时间
单位存储 成本（美
元）
10
20
10
1.08
1.10
15000
15
30
15
1.11
1.12
15000
25
25
10
1.10
1.11
15000
x1 + x2 + x3
+x6 + x7 ≥ 15
x1 + x2 + x3 + x4
+x7 ≥ 19
x1 + x2 + x3 + x4 + x5
≥ 14
x2 + x3 + x4 + x5 + x6
≥ 16
x3 + x4 + x5 + x6 + x7 ≥ 11
xi ≥ 0 i = 1, 2, . . . , 7
规模问题。
穷举法
方法简单，只可解小问题，计算量很大；对0-1整数规 划，计算量为2n，按指数增长：
n
计算量
计算时间
10
1.02×103
1.02毫秒
20
1.05×106
1.05秒
30
1.07×109
18 分钟
40
1.10×1012
13 天
50
1.73×1015
36 年
100
1.27×1030
4 亿亿年
选择顾客
耐芙迪公司在３个工厂中专门生产一种产品 这种产品有着优良的品质，所以现在公司接到了许多订单，产
品供不应求． 主要是由于运输成本的差异，销售一个产品得到的净利润也不
同，很大程度上取决于哪个工厂供应哪个顾客． 问题：公司需要向每一位顾客供应的产品数量是多少？每一个
工厂向每一个顾客供应多少单位的货物？
6x1+ 2x2 ≤ 17
0
1.0
2.0
3.0
4.0 x1
x2
5.0
整数最优解
线性规划最优解
4.0
5x1+ 9x2 ≤ 44
目标函数线 3.0
2.0
x1 ≤ 1
1.0
x1 ≥ 2
6x1+ 2x2 ≤ 17
0
1.0
2.0
3.0
4.0
x1
SUB 1
max: x1 + x2
s.t. 6x1 + 2x2 ≤ 17
Total
Shipment
Customer 1 Customer 2 Customer 3 Customer 4 Production
Plant 1 7,000
0
1,000
0
8,000
=
Plant 2
0
0
0
5,000
5,000
=
Plant 3
0
6,000
1,000
0
7,000
=
Min Purchase Total Shipped Max Purchase
x2
整数规划问题：
5.0
max: z = x1 + x2
4.0
s.t. 6x1 + 2x2 ≤ 17
5x1 + 9x2 ≤ 44 3.0
x1, x2 为整数
按线性规划求解： 2.0
x1= 1.477, x2= 4.068 1.0 z = 5.545
整数规划最优解 线性规划最优解 5x1+ 9x2 ≤ 44 目标函数线
LP解： x = (1.3, 3.3, 2, 7.3, 0, 3.3, 5) z = 22.3
整数解：x = ( 4, 4, 2, 6, 0, 4, 3)
z = 23
固定费用问题
例2: 服装厂可生产西服、衬衫和羽绒服。生产不同服装要使 用不同设备，该厂可从租赁公司租用这些设备（每种设备 可租用多台）。服装厂每月可用人工工时为 3000小时，该 厂如何安排生产可使每月利润最大。市场需求、设备租金 和其它经济参数见下表：
4 . 0 x1
求解整数规划方法
穷举法：方法简单，只可解小问题，计算量很 大；对0-1整数规划，计算量为2n，按指数增长；
凑整法：解的质量差，有时无法得到可行解 分枝定界: 计算效率高, 应用广泛; 割平面法: 有理论意义, 但计算效率较低； 启发算法: 效率高, 但不能保证找到最优解, 可解大
一二三四五六日 17 13 15 19 14 16 11
邮局排班模型
解：设 xi 为第 i 天开始上班的人数：
min: z = x1 + x2 + x3 + x4 + x5 + x6 + x7
s.t.
x1
+x4 + x5 + x6 + x7 ≥ 17
x1 + x2
+x5 + x6 + x7 ≥ 13
-
Month Installed
2
3
1.10
1.11
1.12
1.13
1.11
1.13
1.12
1.14
-
1.10
-
1.11
-
-
-
-
4 1.13 1.15 1.14 1.15 1.12 1.13 1.13 1.15
Units Produced
1
1 (RT) 10
1 (OT) 0
2 (RT) 0
Month 2 (OT) 0
运筹学 Operations Research
运输与整数规划
西南交通大学经济管理学院
The Transportation Problem 运输问题
Sources
Destinations
运输问题的特征
每一个出发地都有一定的供应量（supply）配送到目 的地，每一个目的地都有需要从一定的需求量（ demand），接收从出发地发出的产品 需求假设（The Requirements Assumption） 可行解特性（The Feasible Solutions Property） 成本假设（The Cost Assumption） 整数解性质（Integer Solutions Property）
2.0
x1 ≤ 2
x1, x2 为非负整数
1.0
松弛问题解：x = (2, 1.8 ) T z = 11 四舍五入解：x = (2, 2.0 ) T 不是可行 0
解；
x = (2, 1.0 ) T z = 7 整数最优解：x = (0, 2.0 ) T z = 10
1.0 2.0 x1
分枝定界算法举例
7,000 <=
7,000 <=
7,000
3,000 <=
6,000 <=
9,000
2,000 <=
2,000 <=