《数据模型与决策》第十章 离散型优化

Chapter 10 Discrete optimization 离散型优化

Chapter 10 Discrete optimization 离散型优化

10.1建模 例P578投资预算问题 1500万可投于4个项目 项目 ⅣV 投资额865 4 净限值12 7 6

10.1 建模 例 P578 投资预算问题 1500万可投于4个项目 项目 Ⅰ Ⅱ Ⅲ Ⅳ 投资额 8 6 5 4 净限值 12 8 7 6

●离散型问题中,上例中“投于不投”(或“有与 无”)的“二项”决策问题,常引入0-1变量,有时 又称0-1规划: x=0不往处投资;x=1投往处项目 ●模型 max12x1+8x2+7x3+6X st8x1+6x2+5x3+4x4≤15(百万美元) x1234为0或1

●离散型问题中，上例中“投于不投”（或“有与 无”）的“二项”决策问题，常引入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+x<2 b如果投项目(4),则必须投项目(3): c.若投项目(1),则不允许投项目(3): x1+x2≤1(注:x1+x2≤1更贴近逻辑关系是两者至多 只许投其1或不许两项两项一起投,但其内容涵盖了 要求c。) 软件求解得:x1=1,x2=1,x3=X=0, 最大NPV为2(千万美元)

该模型尚可根据实际情况（约束）而进一步处 理，如若再要求： 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（千万美元）

Fbi. P580 An airplane manufacturing problem 四种型号的飞机 Table10.2 AR1 AR2 aR3 AR4 订单 17 11 15 攸益(千$)6284 103 125 时间(天)4 7 9 11 发动机

例 .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(天)的有 效工作日 max62X1+84x,+103x3+125X st.4x计+7x+9x3+11x4270(工作日) X+X2+2x2+2x<60 11 ⅹ为非负整数(j=1、2、3、4)

下一季有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）

若不计整约束,可得最优:x18,x2=17, x3=11,x=1.18,最优值3,284273$ 若按整约束,可得最优:ⅹ1-8,x2-=17,X3=1, X=10,最优值3,277000 可见用“四舍五入”不能奏效

若不计整约束，可得最优：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可选择 LMPHIR 运输费用(百万)2015222116

例. 维修服务中心的重新配置，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 L MPHR Switzerland 15%o E0.52.51.523 Italy 10 G2310.52 france 20 S3221.51 I|31220.5 F1.520.512

主要业务 耗时表 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变量:y=1,处被选中y=0,j处未被选中 般变量x1国往j处的顾客份额,有∑x=1 附加变量”w:i平均延误时间,有w≤1.5 (服务要求达到的指标) 及0.25w1+0.30w2+0.15w3+0.10w4+0.20w5≤1.1

目标：● 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