运筹学第05章.ppt

文档介绍：第五章整数规划
(Integer Programming,IP)
本章内容
整数规划的数学模型及解的特点
解纯整数规划的割平面法
分支定界法
0-1型整数规划
指派问题
整数规划问题
投资组合问题
旅游售货员问题
背包问题
应用案例
投资组合问题背景
证券投资:把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润
项目投资:财团或银行把资金投入到若干项目中以获得中长期的收益最大。
投资组合问题案例
某财团有万元的资金,经出其考察选中个投资项目,每个项目只能投资一个。其中第个项目需投资金额为万元,预计5年后获利万元,问应如何选择项目使得5年后总收益最大?
投资组合问题模型
变量—每个项目是否投资
约束—总金额不超过限制
目标—总收益最大
旅游售货员问题背景
旅游线路安排
预定景点走且只走一次
路上时间最短;
配送线路—货郎担问题
送货地到达一次
总路程最短;
旅游售货员问题案例
有一旅行团从出发要遍游城市,已知从到的旅费为,问应如何安排行程使总费用最小?
旅游售货员问题模型
变量—是否从i第个城市到第j个城市;
约束—每个城市只能到达一次、离开一次;
目标—总费用最小;
背包问题背景
邮递包裹
把形状可变的包裹用尽量少的车辆运走
旅行背包
容量一定的背包里装尽可能的多的物品