欢迎来到天天文库
浏览记录
ID：57191014
大小：1.51 MB
页数：11页
时间：2020-08-03
《§31 整数线性规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一节整数线性规划问题整数线性规划问题举例解整数线性规划问题的困难性整数线性规划问题整数线性规划（ILP）具有下述形式0-1整数线性规划模型混合整数线性规划1.整数线性规划问题举例例3.1.1例3.1.1投资决策问题分析变量—每个项目是否投资约束—总金额不超过限制目标—总收益最大例3.1.1投资决策问题数学模型旅行售货员问题此外，运筹学还有一个著名的问题：旅行售货员问题（TSP）显示问题2.解整数线性规划问题的困难性整数规划可行解是松弛问题的可行解最优值大于等于松弛问题的最优值松弛的线性规划问题与线性规划的关系：2.解整数线性规划问题的困难性LP的可行集合费用下
2、降方向LP问题的最优解ILP问题的最优解2.解整数线性规划问题的困难性续最优解不一定在顶点上达到最优解不一定是松弛问题最优解的邻近整数解整数可行解远多于松弛问题的顶点，枚举法不可取解ILP问题要远难于解松弛的LP问题如果松弛的LP问题无解，显然原ILP问题无解。反之，不一定成立。如果松弛的LP问题无界呢？可以证明原ILP问题也无界
此文档下载收益归作者所有
