Chapter 10
Discrete optimization
离散型优化
10.1 建模例 P578 投资预算问题
1500万可投于 4个项目项目 Ⅰ Ⅱ Ⅲ Ⅳ
投资额 8 6 5 4
净限值 12 8 7 6
● 离散型问题中,上例中,投于不投,（ 或,有与无,） 的,二项,决策问题,常引入 0-1变量,有时又称 0-1规划：
令 xj=0 不往 j处投资； xj=1 投往 j处项目
● 模型
max 12x1+8x2+7x3+6x4
s.t,8x1+6x2+5x3+4x4≤15(百万美元 )
x1,2,3,4为 0或 1
该模型尚可根据实际情况 （ 约束 ） 而进一步处理,如若再要求：
a.最多只投两项,x1+x2+x3+x4≤2
b.如果投项目 （ 4）,则必须投项目 （ 3）,
x3-x4≥0
c.若投项目 （ 1）,则不允许投项目 （ 3）,
x1 +x3≤1（ 注,x1 +x3≤1更贴近逻辑关系是两者至多只许投其 1或不许两项两项一起投,但其内容涵盖了要求 c。 ）
软件求解得,x1=1,x2=1,x3=x4=0，
最大 NPV为 2（千万美元）
例,P580 An airplane manufacturing problem
四种型号的飞机
Table10.2
AR1 AR2 AR3 AR4
订单 8 17 11 15
收益（千 $） 62 84 103 125
时间（天） 4 7 9 11
发动机 1 1 2 2
下一季有 3处可生产，共 90*3=270（天）的有效工作日。
max 62x1+84x2+103x3+125x4
s.t,4x1+ 7x2+ 9x3+ 11x4≤270（ 工作日 ）
x1+ x2+ 2x3+ 2x4≤60
x1 ≤8
x2 ≤17
x3 ≤11
x4≤15
xj为非负整数（ j=1,2,3,4）
若不计整约束,可得最优,x1=8,x2=17，
x3=11,x4=1.18,最优值 3,284,273$
若按整约束,可得最优,x1=8,x2=17,x3=1，
x4=10,最优值 3,277,000$
可见用,四舍五入,不能奏效例,维修服务中心的重新配置,P581
TRD,inc 大型计算机制造商原已设三处,London,Madrid,Paris
先考虑设 2-3处，除原有 3处外，外加 Hamburg,
Rome可选择
L M P H R
运输费用（百万） 20 15 22 21 16
主要业务 耗时表
England 25%
Germany 30%
Switzerland 15%
Italy 10%
France 20%
L M P H R
E 0.5 2.5 1.5 2 3
G 2 3 1 0.5 2
S 3 2 2 1.5 1
I 3 1 2 2 0.5
F 1.5 2 0.5 1 2
目标,● min总运营费用
● 对任一国家顾客,平均 1.5天内需得到服务
● 总体平均变量设置,
0-1变量,yj =1,j处被选中 ; yj = 0,j处未被选中一般变量 xij:I国往 j处的顾客份额,有 ∑xij=1
“附加变量,wi,i国平均延误时间,有 wi≤1.5
（服务要求达到的指标）
及 0.25w1+0.30 w2+0.15 w3+0.10 w4+0.20 w5≤ 1.1
有模型 （ P584）
min (20 15 22 16)y (y=(y1,y2,y3,y4,y5 )T)
s.t,∑ xij=1 (i=1,2,…,5)
w1=(0.5 2.5 1.5 2 3)(x11 x12 x13 x14 x15) T
w2=( 2 3 1 0.5 2) (x21 x22 x23 x24 x25) T
w3=( 3 2 2 1.5 1) (x31 x32 x33 x34 x35) T
w4=( 3 1 2 2 0.5) (x41 x42 x43 x44 x45) T
w5=(1.5 2 0.5 1 2) (x51 x52 x53 x54 x55) T
wi≤ 1.5 (i=1,2,…,5)
(continued)
s.t:
(0.25 0.30 0.15 0.10 0.20) (w1 w2 w3 w4 w5 )T≤1.1
xij≤yj,i,j=1,2,3,4,5（ 注意不等价于 0≤xij≤1）
2≤y1+y2+y3+y4+y5≤3
xij≥0,i,j=1,2,3,4,5
yj=0或 1
混合整数规划
10.2 分支定界法 （ P586-589）
max 12x1+8x2+7x3+6x4
s.t,8x1+6x2+5x3+4x4≤15
x1,2,3,4为 0或 1
给出一种处理问题的逻辑框架
P587.分支一
P588.再分
P589.分支求解的过程
Discrete optimization
离散型优化
10.1 建模例 P578 投资预算问题
1500万可投于 4个项目项目 Ⅰ Ⅱ Ⅲ Ⅳ
投资额 8 6 5 4
净限值 12 8 7 6
● 离散型问题中,上例中,投于不投,（ 或,有与无,） 的,二项,决策问题,常引入 0-1变量,有时又称 0-1规划：
令 xj=0 不往 j处投资； xj=1 投往 j处项目
● 模型
max 12x1+8x2+7x3+6x4
s.t,8x1+6x2+5x3+4x4≤15(百万美元 )
x1,2,3,4为 0或 1
该模型尚可根据实际情况 （ 约束 ） 而进一步处理,如若再要求：
a.最多只投两项,x1+x2+x3+x4≤2
b.如果投项目 （ 4）,则必须投项目 （ 3）,
x3-x4≥0
c.若投项目 （ 1）,则不允许投项目 （ 3）,
x1 +x3≤1（ 注,x1 +x3≤1更贴近逻辑关系是两者至多只许投其 1或不许两项两项一起投,但其内容涵盖了要求 c。 ）
软件求解得,x1=1,x2=1,x3=x4=0，
最大 NPV为 2（千万美元）
例,P580 An airplane manufacturing problem
四种型号的飞机
Table10.2
AR1 AR2 AR3 AR4
订单 8 17 11 15
收益（千 $） 62 84 103 125
时间（天） 4 7 9 11
发动机 1 1 2 2
下一季有 3处可生产，共 90*3=270（天）的有效工作日。
max 62x1+84x2+103x3+125x4
s.t,4x1+ 7x2+ 9x3+ 11x4≤270（ 工作日 ）
x1+ x2+ 2x3+ 2x4≤60
x1 ≤8
x2 ≤17
x3 ≤11
x4≤15
xj为非负整数（ j=1,2,3,4）
若不计整约束,可得最优,x1=8,x2=17，
x3=11,x4=1.18,最优值 3,284,273$
若按整约束,可得最优,x1=8,x2=17,x3=1，
x4=10,最优值 3,277,000$
可见用,四舍五入,不能奏效例,维修服务中心的重新配置,P581
TRD,inc 大型计算机制造商原已设三处,London,Madrid,Paris
先考虑设 2-3处，除原有 3处外，外加 Hamburg,
Rome可选择
L M P H R
运输费用（百万） 20 15 22 21 16
主要业务 耗时表
England 25%
Germany 30%
Switzerland 15%
Italy 10%
France 20%
L M P H R
E 0.5 2.5 1.5 2 3
G 2 3 1 0.5 2
S 3 2 2 1.5 1
I 3 1 2 2 0.5
F 1.5 2 0.5 1 2
目标,● min总运营费用
● 对任一国家顾客,平均 1.5天内需得到服务
● 总体平均变量设置,
0-1变量,yj =1,j处被选中 ; yj = 0,j处未被选中一般变量 xij:I国往 j处的顾客份额,有 ∑xij=1
“附加变量,wi,i国平均延误时间,有 wi≤1.5
（服务要求达到的指标）
及 0.25w1+0.30 w2+0.15 w3+0.10 w4+0.20 w5≤ 1.1
有模型 （ P584）
min (20 15 22 16)y (y=(y1,y2,y3,y4,y5 )T)
s.t,∑ xij=1 (i=1,2,…,5)
w1=(0.5 2.5 1.5 2 3)(x11 x12 x13 x14 x15) T
w2=( 2 3 1 0.5 2) (x21 x22 x23 x24 x25) T
w3=( 3 2 2 1.5 1) (x31 x32 x33 x34 x35) T
w4=( 3 1 2 2 0.5) (x41 x42 x43 x44 x45) T
w5=(1.5 2 0.5 1 2) (x51 x52 x53 x54 x55) T
wi≤ 1.5 (i=1,2,…,5)
(continued)
s.t:
(0.25 0.30 0.15 0.10 0.20) (w1 w2 w3 w4 w5 )T≤1.1
xij≤yj,i,j=1,2,3,4,5（ 注意不等价于 0≤xij≤1）
2≤y1+y2+y3+y4+y5≤3
xij≥0,i,j=1,2,3,4,5
yj=0或 1
混合整数规划
10.2 分支定界法 （ P586-589）
max 12x1+8x2+7x3+6x4
s.t,8x1+6x2+5x3+4x4≤15
x1,2,3,4为 0或 1
给出一种处理问题的逻辑框架
P587.分支一
P588.再分
P589.分支求解的过程
