运筹学-第5章整数规划

《运筹学-第5章整数规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章整数规划第5章整数规划Subtitle内容提要第一节整数规划问题及数学模型纯整数规划0-1规划混合整数规划第二节整数规划求解分枝定界法割平面法隐枚举法匈牙利法2第一节整数规划问题及数学模型一、整数规划问题简述线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数规划(IntegerProgramming)。全部决策变量的取值都为整数，全整数规划(AllIP)仅要求部分决策变量的取值为整数，混

2、合整数规划(MixedIP)要求决策变量只取0或1值，则称0-1规划(0-1Programming)3一、全(纯)整数规划产品资源甲乙现有量A219B5735单台利润65例：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示，问如何安排利润最大(变量取整)？解：设x1为甲产品的台数，x2为乙产品的台数，则模型为：maxZ=6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0,且为整数4二、0-1规划登山队员可携带最大重量为25公斤，问应带哪些物品，重要性最大？解：对于每一种物品无非有两种状态，带或者不带，不妨设序号1234567物品食品氧气冰

3、镐绳索帐篷相机设备重量55261224重要性系数2015181484100-1规划的模型：5三、混合整数规划例：某产品有n个区域市场，各区域市场的需求量为bj吨/月；现拟在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选i地建厂，生产能力为ai吨/月，其运营固定费用为Fi元/月；已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？解：假设yi=1，选择第i址建厂，yi=0，不选择第i址建厂；计划从厂址i至市场j的运输量为xij(连续型决策变量)。6第一节整数规划问题及数学模型二、整数规划问题建模举例参见教材：P110:5.1P115:5.1-5.6

4、P122:5.97整数规划建模举例一、生产基地规划例：某公司拟建A、B两种类型的生产基地若干个，每个基地占地面积，所需经费，建成后生产能力及现有资源情况如下表所示，问A、B类型基地各建设多少个，可使总生产能力最大？解：设A、B两类基地各建设x1,x2个，则其模型为：8二、人员安排规划某服务部门各时段(每2小时为一时段)需要的服务人数如表：解：设第j时段开始时上班的服务员人数为xj第j时段来上班的服务员将在第j+3时段结束时下班，故决策变量有x1,x2,x3,x4,x5。按规定，服务员连续工作8小时(4个时段)为一班。如何安排服务员的工作时间，使服务员总数最少？9三、项目投资选择有6

5、00万元投资5个项目，收益如表，求利润最大的方案？10四、互斥约束问题例如关于煤资源的限制，其约束条件为：企业也可以考虑采用天然气进行加热处理：这两个条件是互相排斥。引入0-1变量y，令互斥问题可由下述的条件来代替，其中M是任意大的正数。11五、租赁生产问题某服装公司租用生产线拟生产T恤、衬衫和裤子，每年可使用劳动力8200h，布料8800m2，问如何安排利润最大？T恤衬衫裤子劳动力(h)326布料(m2)0.81.11.5售价(元)250400600可变成本(元)100180300生产线租金(万)201510假设：yj=1，要租用生产线jyi=0，不租用生产线j第j种服装生产量x

6、jx1≤My1x2≤My2x3≤My3其中，M为任意大的正数。12六、任务指派问题甲乙丙丁四个人，ABCD四项任务，如何指派总时间最短？解：引入0-1变量xij，xij=1：任务j指派人员i去完成xij=0：任务j不派人员i去完成一项任务只由一个人完成一人只能完成一项任务13第二节整数规划问题求解一、舍入化整法maxZ=6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0且为整数x1x2369359(28/9,25/9)对于本例，松驰问题的最优解：x1*=28/9，x2*=25/9，Z*=293/9整数规划问题取消整数限制后称为松驰问题。x1=3，x2=3，Z=33，不

7、满足约束条件5x1+7x2≤35，不可行；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，而且是最优解。14从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得倒的解是整数可行解。整数规划与线性规划的关系15二、穷举整数法对于决策变量少，整数可行解