文档介绍：第三章整数规划和分配问题
整数规划的数学模型及分类
解纯整数规划的分枝定界法
解分配问题的匈牙利法
教学目的与要求:能建立整数规划的数学模型,会用匈牙利法解分配问题.
重点与难点:重点是建模和解分配问题,难点是在分枝定界法中如何分枝及定界.
教学方法:以课堂讲授为主,配合课件和软件.
思考题,讨论题,作业:教材第四章****题.
参考资料:见前言.
学时分配:4学时.
第三章整数规划和分配问题
(Integer programming and assignment problem )
第一节整数规划问题的提出
线性规划的决策变量的取值是非负实数,但是有些实际问题的线性规划模型中,决策变量取值只能是非负整数,甚至只能取0,1两个数,这类的线性规划模型称为整数线性规划,简称整数规划.
例1 某厂拟托运甲,乙两种货物,,才能获得最大利润.
货物
每箱体积
每箱重量
每箱利润
甲
5
2
20
乙
4
5
10
托运限制
24
13
建立数学模型:
这个模型称为纯整数规划,有时模型中的决策变量一部分取整数,另一部分取实数,称为混合整数规划.
例2 投资模型(如物流配送网点的选择,工厂布局,基本设备的配置,科研课题的选择等)
这个模型称为0-1整数规划.
在投资模型中,如果只有一种资源限制,则模型可简化为:
该模型称为”背包问题”
(Knapsack problem)
整数规划的解法分析
整数规划与线性规划的区别在于对决策变量有无整数限制,因此有人认为,先不考虑整数限制求解线性规划,,
第二节整数规划的解法
整数规划与线性规划解的性质:
⑴如果LP的最优值在其可行域T的某个顶点上达到,则相应的IP最优值,在T中去掉不含整数点的区域后的T*中的整数点上达到.
⑵对于求最大化(最小化)问题,LP最优解对应的目标函数值,是相应的IP最优解对应的目标函数值的上界(下界).
最早的整数规划论文是在1954年发表的,(依据性质1),,(依据性质2),该方法概念简单,方法灵活,容易在计算机上运算,成为IP解法的基础.