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