资源描述：
《管理运筹学 第四章整数规划与指派问题PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章整数规划与指派问题2017年4月北京物资学院运筹学课件•线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义。例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。•要求全部或部分决策变量的取值为整数的线性规划问题，称为整数线性规划，简称整数规划(IntegerProgramming)。第一节整数线性规划问题的数学模型第二节整数规划的求解方法*第三节指派问题及匈牙利解法本章内容的安排第一节整数线性规划问题的数学模型引例逻辑变量在整数规划建模中
2、的作用整数规划问题的特征与性质整数规划模型的分类例1（装载问题）有一辆卡车的最大载重量为b吨,现有n种货物可供装载。设第j种货物每件重aj吨,每件的装载费用为cj元(j=1,…n)。问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大?解:设xj为卡车装载第j种货物的件数(j=1,2,…,,n),z表示卡车一次装载的收入,则该问题的数学模型为maxz=c1x1+c2x2+…+cnxns.t.a1x1+a2x2+…+anxnbxj0且为整数(j=1,2,…,,n)1.引例例2.（选址问题—相互排斥的计划）某公司准备投资
3、100万元在甲、乙两座城市修建健身中心，经过多方考察，最后选定A1,A2,A3,A4和A5五个位置，并且决定在甲城市的A1、A2、A3三个位置中最多投建两个；在乙城市的A4、A5两个位置中最少投建一个。如果已知各点的投资金额和年利润如下表。问：健身中心投建在哪些位置才会使总的年利润最大？待定地址A1A2A3A4A5投资总额投资金额（万元）2030254045100年利润（万元）1025202530解：设则该问题的数学模型为例3工厂选址问题：某商品有n个销地，各销地的需求量为bj吨/天；现拟在m个地点中选址建生产厂，一个地点最
4、多只能建一个工厂；若选i地建厂，生产能力为ai吨/天，固定费用为di元/天；已知i地至第j销地的单位运费为cij元/吨。问如何选址和安排调运，才能使总费用最小？设：yi=1，表示选择第i地建厂，yi=0，表示不选择第i地建厂；从厂址i至销地j运量为xij，总费用为z。该问题的数学模型为例4某公司制造小、中、大3种尺寸的金属容器，所用的资源为金属板、劳动力和机时。制造一只容器所需的各种资源数量如下表所示，不考虑固定费用，每售出一只小、中、大号容器所得的利润分别为4元、5元、6元，可使用的金属板有500张，劳动力有300个，机时
5、有100小时，如果生产某种容器，不管生产数量多少，都要支付一笔固定费用，小、中、大号容器的固定费用分别为100元、150元、200元，现要制订一生产计划，使获得的利润最大。资源小号容器中号容器大号容器资源拥有量金属板（张）248500劳动力（个）234300机时（小时）123100利润456解：设x1,x2,x3分别表示小、中、大号容器的生产数量，M为很大的正数，z表示总利润引入逻辑变量若xj=0时，yj=0,若xj>0时，yj=1。2.逻辑变量在整数规划建模中的作用(1)m个约束条件中只有k个起作用。定义则上述条件可以表示
6、成(2)约束条件的右端可能是r个值中的某一个定义则上述条件可以表示成(3)两组条件中满足其中的一组定义则问题可以表示为4用以表示含固定费用的函数总费用目标函数是总费用最小定义则目标函数可以表示成3.整数规划问题的特征与性质特征—变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质—可行域是离散集合4.整数规划的分类纯整数规划要求全部决策变量的取值都为整数,则称为纯整数规划(AllIP)；混合整数规划仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)；0-1整数规划要求决策变量只能取0或1值，则称为0-1
7、规划(0-1Programming)。第二节整数规划的求解方法分支定界法割平面法1.分支定界法整数规划ILP放松的线性规划LP分枝定界法是本世纪60年代初由LandDoig和Dakin等人提出的，可用于解纯整数规划或混合整数规划。整数规划问题的最优目标函数等值线放松问题的最优目标函数等值线整数规划的最优解不一定在顶点上达到；整数规划的最优解不一定是放松问题最优解的邻近整数解；整数可行解的个数远多于顶点个数，枚举法不可取。整数规划ILP和放松问题LP的关系ILP的可行区域是LP的可行区域的子集；如果LP无可行解，则ILP无可行
8、解；LP的最优值是ILP的最优值的一个上界；若LP的最优解为整数向量，则它也是ILP的最优解。整数规划ILP放松的线性规划LP分枝定界法的基本思想先求放松的LP的最优解，若放松LP问题无解，则原ILP问题也无解。若放松LP问题的最优解符合整数要求，则是原ILP的最优解；若放松LP问题的最优
