31 整数规划数学模型 Mathematical Model of IP32 整数规划.ppt

【补充例】投资决策问题。某公司有5个项目被列入投资计划，各项目的投资额和期望的投资收益如下表 【解】设xj 为选择第 j（j=1,2,3,4,5)个项目的决策 整数规划的一般形式： max=8.6x11+9.7x12+8.9x13+9.4x14+9.2x21+8.3x22+8.5x23+8.1x24 +8.8x31 +8.7x32+9.3x33+9.6x34+8.5x41+7.8x42+9.5x43+7.9x44+8x51+9.4x52 +8.2x53+7.7x54 x11+x12+x13+x14≦3 x21+x22+x23+x24≦3 x31+x32+x33+x34≦3 x41+x42+x43+x44≦3 x51+x52+x53+x54≦3 x11+x21+x31+x41+x51≧1 x12+x22+x32+x42+x52≧1 x13+x23+x33+x43+x53≧1 x14+x24+x34+x44+x54≧1 x11+x12+x13+x14+x21+x22+x23+x24+x31+x32+x33+x34+x41+x42+x43 +x44+x51+x52+x53+x54=10 xij=0 或 1 (i=1,2,3,4,5;j=1,2,3,4) 整数规划解的特点 整数规划（Ⅰ）的可行解集是其松弛问题（Ⅱ）的可行解集的子集。线性规划问题的可行解集是一个凸集（稠密的），但整数规划的可行解集不是凸集（离散型）。 如果松弛问题（Ⅱ）的最优解是整数解，则一定是整数规划（Ⅰ）的最优解。 整数规划（Ⅰ）的最优值不会优于松弛问题（Ⅱ）的最优值。 说明： 分支定界法适用于求解纯整数规划和混合整数规划 几何意义 由约束条件得： x3=30-6x1-4x2 , x4=10-x1-2x2 代入割平面方程 -x3-2x4≤-2，得 x1+x2≤6 3.2.3 整数规划的图解法 思考： 对于两个变量的纯整数规划问题是否可采用图解法。 3.2.3 整数规划的图解法 步骤： 1.作出松弛问题的可行域。 2.在可行域内作出所有的整数网格。 3.作目标函数等值线，将等值线平行移动，最后接触到的网格点（或平行移动到松弛问题的最优解点再往回移，首先接触到的网格点），就是整数规划的最优解。 长江综合商场有5000m2营业面积招租，拟吸引以下5类商店入租。已知各类商店开设一个店铺占用的面积，在该商场内最多与最少开设的个数，以及每类商店开设不同个数时每个商店的每月预计利润见表。商场除按租用面积每月收取100元/m2租金外，还按利润的10%按月收取屋业管理费。问该商场应招租上述各类商店各多少个，使预期收入为最大？ 思 考 商场招租 用LINDO软件计算，得最优解 x12=x22=x33=x42=x53=1，其余 xij=0 最优值 Z=63（万元） 最优方案： 招租服装店2个，鞋帽店2个，百货店3个，书店2个，餐饮店3个，预期收入最大，为63万元 【案例C-3】证券营业网点设置问题 【解】引入0－1变量 4.? 检查所有分支的解及目标函数值，若某分支的解是整数并且目标函数值大于（max）等于其它分支的目标值，则将其它分支剪去不再计算, 若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分支，再检查，直到得到最优解。 分支原则：始终选Z值大的，且xi中有分数的LP进行分支。 定界原则：满足取整要求，且目标函数值较已定的 “界”更优，则用该目标函数值替换，重新定界。 3.2.1 分支定界法 设纯整数规划 松弛问题的最优解 3.2.2 割平面法 设xi= 不为整数， 将 分离成一个整数与一个非负真分数之和： 则有 等式两边都为整数, 并且有 3.2.2 割平面法 加入松弛变量si得 此式称为以xi行为源行（来源行）的割平面方程，或分数切割式，或R.E.Gomory(高莫雷)约束方程。 将Gomory约束加入到松弛问题的最优表中，用对偶单纯形法计算，若最优解中还有非整数解，再继续切割，直到全部变量为整数。 则 3.2.2 割平面法 例如， x1行： 移项： 加入松弛变量s1得割平面方程 同理，对于x2行有： 3.2.2 割平面法 【例3-6】 用割平面法求解下列IP问题 【解】 对应的松弛问题是 3.2.2 割平面法 加入松弛变量x3及x4后，用单纯形法求解，得到最优表3-3。 最优解X(0)＝(5/2，15/4), 不是IP的最优解。 选择表中的第一行(也可以选第二行)为源行 －1/4 －5/8 0 0