单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级第三章 整数规划Integer Programming§1 问题的提出 [eg.1]用集装箱托运货物 问:甲乙货物托运多少箱使总利润最大货物m3箱百斤箱百元箱甲5220乙4510限制2413 分析:设x1为甲货物托运箱数x2为乙货物托运箱数 则 max z = 20x1 10x2
52(mixed integer linear programming)对于整数线性规划问题为了得到整数解初看起来似乎只要先不管整数要求而求线性规划的解然后将求得的非整数最优解舍零取整就可以了.但实际上这个想法却常常行不通有时舍零取整后的整数解根本就不是可行解有的虽然为可行解却不是最优解 .2(3)图1 中四边形 OABC 是松弛问题(2)的可行域.它的最优解为 C 点( 0)自20世纪60年代以
#
#
#
#
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级整 数 规 划(Integer Programming)整数规划的模型分支定界法0-1 整数规划 在很多场合我们建立最优化模型时实际问题要求决策变量只能取整数值而非连续取值此时这类最优化模型就称为整数规划(离散最优化)模型 整数规划的求解往往比线性规划求解困难得多而且一般来说不能简单地将相应的线性规划的解
#
单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级第六章 整数规划整数规划的概念和模型图解法分枝定界法0-1规划的隐枚举法指派问题的匈牙利法第一节 整数规划的概念和模型若在一般的线性规划模型中加入决策变量X的某些分量或每一个分量都是整数的要求这样的线性规划问题即为整数规划问题整数规划问题的形式1全整数线性规划:即要求所有变量均为整数2混合整数规划:既要求部分变量是整数30
#
违法有害信息,请在下方选择原因提交举报