运筹学整数线性规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一节 整数线性规划问题,整数线性规划问题举例,解整数线性规划问题的困难性,整数线性规划问题,整数线性规划（,ILP,）具有下述形式,0-1,整数线性规划模型,混合整数线性规划,1.,整数线性规划问题举例,例,3.1.1,例,3.1.1,投资决策问题,分析,变量,每个项目是否投资,约束,总金额不超过限制,目标,总收益最大,例,3.1.1,投资决策问题,数学模型,旅行售货员问题,此外，运筹学还有一个著名的问题：,旅行售货员问题（,TSP,）,显示问题,2.,解整数线性规划问题的困难性,整数规划,可行解是松弛问题的可行解,最优值大于等于松弛问题的最优值,松弛的线性规划问题,与线性规划的关系：,2.,解整数线性规划问题的困难性,LP,的可行集合,费用下降方向,LP,问题的最优解,ILP,问题的最优解,2.,解整数线性规划问题的困难性续,最优解不一定在顶点上达到,最优解不一定是松弛问题最优解的邻近整数解,整数可行解远多于松弛问题的顶点，枚举法不可取,解,ILP,问题要远难于解松弛的,LP,问题,如果松弛的,LP,问题无解，显然原,ILP,问题无解。反之，不一定成立。,如果松弛的,LP,问题无界呢？可以证明原,ILP,问题也无界,