文档介绍：Integer Linear Programming
整数线性规划
1
整数规划
整数规划问题与模型
整数规划算法
分支定界法
割平面法
隐枚举法
2
背景
证券投资:把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。
项目投资:财团或银行把资金投入到若干项目中以获得中长期的收益最大。
3
某财团有万元的资金,经出其考察选中个投资项目,每个项目只能投资一个。其中第个项目需投资金额为万元,预计5年后获利( )万元,问应如何选择项目使得5年后总收益最大?
案例
4
模型
变量—每个项目是否投资
约束—总金额不超过限制
目标—总收益最大
5
6
旅游线路安排
预定景点走且只走一次
路上时间最短
配送线路—货郎担问题
送货地到达一次
总路程最短
旅游售货员问题
7
案例
有一旅行团从出发要遍游城市
,已知从到的旅费为,问应如何安排行程使总费用最小?
8
模型
变量—是否从i第个城市到第j个城市
约束
每个城市只能到达一次、离开一次
从第i个城市离开的次数
到达第j个城市的次数
9
避免出现断裂
每个点给个位势除了初始点外要求前点比后点大
目标—总费用最小
10