整数规划数学模型及其解法.ppt

《整数规划数学模型及其解法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章整数规划IntegerProgramming特点-解法-应用1知识点要求了解整数规划的特点；掌握逻辑变量的灵活运用；掌握整数规划的求解方法：匈牙利法：寻找位于不同行不同列的m个零元素、行和列的位势的确定割平面法分支定界法：分支与定界的条件隐枚举法（0-1规划问题）根据实际问题建立整数规划数学模型。2主要内容整数规划的性质整数规划的解法匈牙利法割平面法分支定界法隐枚举法（0-1规划问题）整数规划的应用3引例1-1例1．某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表所示4货物每件体积(立方英尺)每件重量(百千克)每件利润(百元)甲乙1952

2、7344023托运限制1365(立方英尺)140(百千克)甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？引例1-25引例2-1例．某公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Ai(i=1，2，3，...，10)可供选择，6引例2-2规定：在东区由A1，A2，A3三个点至多选择两个；在西区由A4，A5两个点中至少选一个；在南区由A6，A7两个点中至少选一个；在北区由A9，A9，A10三个点中至少选两个。7A1A2A3A4A5A6A7A8A9A10投资额10012015080709080140160180利润36405022203025485861

3、引例2-3各点的设备投资及年获利预测表投资总额不能超过720万元。问应选择哪几个点，可使年利润为最大？8整数规划的特点（1）在很多实际问题中，全部或部分变量的取值必须是整数，如人或机器设备等不可分割。此外还有一些问题，如要不要在某地建设工厂，可选用一个逻辑变量x，令x=1表示在该地建厂，x=0表示不在该地建厂，逻辑变量也是只允许取整数值的一类变量。9整数规划的特点（2）纯整数线性规划：在一个线性规划中要求全部变量取整数值，或简称纯整数规划。混合整数(线性)规划：在一个线性规划中只要求一部分变量取整数值。10整数规划的图解有人认为，对整数规划问题的求解可以先不考虑对变量的整数约束，作为一

4、般线性规划问题来求解，当解为非整数时可用四舍五人或凑整方法寻找最优解。当然在变量取值很大时，用上述方法得到的解与最优解差别不大。但当变量取值较小时，得到的解就可能与实际整数最优解差别很大。再者当问题规模较大时，用凑整办法来算工作量很大。11例1．求下述整数规划问题的最优解12(3,3)(3,2)(4,3)(4,2)(4,1)，Z=14(3.25，2.5)13如果不考虑x1、x2取整数的约束，用图解法求得最优解为(3.25，2.5)。由于x1、x2必须取整数值，实际上问题的可行解集只是图中可行域内的那些整数点。用凑整法来解时需要比较四种组合，但(4，3)、(4，2)、(3，3)都不是可行解

5、，(3，2)虽属可行解，但代入目标函数得z=13，并非最优。实际上问题的最优解应该是(4，1)，z*=14。但我们注意到(4，1)不是可行域的顶点，因此直接用图解法或单纯形法都无法找出整数规划问题的最优解来，这就要求研究解整数规划问题的特殊方法。14整数规划与对应的线性规划解的关系1.任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；2.任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数。3.整数规划之相应线性规划的最优解经四舍五入不能得到其最优解15逻辑变量在建立数学模型中的作用整数

6、规划的模型对研究管理问题有重要意义。很多管理问题无法归结为线性规划的数学模型，但却可以通过设置逻辑变量建立起整数规划的数学模型。M个约束条件中只有k个起作用；约束条件的右端项可能是r个值（b1,b2,…,br）中的某一个；两组条件中满足其中一组；用以表达含固定费用的函数。161．M个约束条件中只有k个起作用表明m个约束条件中有(m-k)个的右端项为（bi+M），不起约束作用，因而只有k个约束条件真正起到约束作用。172．约束条件的右端项可能是r个值（b1,b2,…,br）中的某一个183．两组条件中满足其中一组若x1≤4，则x2≥1；（1）否则（即x1>4），则x2≤3。（2）194．用

7、以表达含固定费用的函数如用xj代表产品j的生产数量，其生产费用函数通常可表示为：式中kj是同产量无关的生产准备费用。问题的目标是使所有产品的总生产费用为最小。即：20设置一个逻辑变量yj，当xj=0时，yj=0，当xj>0时，yj=1。由此引进一个特殊的约束条件：于是有：21逻辑变量应用举例-1试用逻辑变量表达以下约束条件变量x只能取2、3、5、8或11中的一个。解题：右端项只能取多个值b1=2,b2=3,b3=5,b4=8,b5=