第1页整 数 规 划 整数规划问题与模型 整数规划算法 计算软件 应用案例第1页/共82页第2页整数规划问题实例特点模型分类第2页/共82页第3页应用案例 投资组合问题 旅游售货员问题 背包问题第3页/共82页第4页投资组合问题 背 景 实 例 模 型第4页/共82页第5页背 景 证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大第5页/共82页第6页案 例n某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个其中第 个项目需投资金额为 万元，预计5年后获利 （）万元，问应如何选择项目使得5年后总收益最大？Bnjcjbnj.,2,1j第6页/共82页第7页模 型n变量每个项目是否投资n约束总金额不超过限制n目标总收益最大0,1 jxnj.,2,1 Bxbnjjj 1 njjjxc1max第7页/共82页第8页 njxBxbtsxcjnjjjnjjj.,2,1;0,1.max11第8页/共82页第9页旅游售货员问题 背景 案例 模型第9页/共82页第10页背 景 旅游线路安排 预定景点走且只走一次 路上时间最短 配送线路货郎担问题 送货地到达一次 总路程最短第10页/共82页第11页案 例n有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？0vnvvv,.,21jvivijc第11页/共82页第12页模 型n变量是否从i第个城市到第j个城市n约束 每个城市只能到达一次、离开一次;0,1ijxnjxnixniijnjij,.2,1;1,.2,1;100第12页/共82页第13页 避免出现断裂 每个点给个位势 除了初始点外要求前点比后点大第13页/共82页第14页 目标总费用最小ijninjijxc00第14页/共82页第15页njnixnjinnxuunjxnixtsxcijijjiniijnjijijninjij,.,2,1,.,2,1,0,11;1,.,2,1;1,.,2,1;1.min0000第15页/共82页第16页背包问题 背景 案例 模型第16页/共82页第17页背 景 邮递包裹 把形状可变的包裹用尽量少的车辆运走 旅行背包 容量一定的背包里装尽可能的多的物品第17页/共82页第18页实 例 某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。
尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里第18页/共82页第19页物品12345678910体积200350500430320120700420250100价格1545100705075200902030第19页/共82页第20页问题分析n变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数为此我们设变量为第i个物品是否放在第j个包裹中3,2,1,17.,2,1;0,1jixij第20页/共82页第21页约束3,2,1;171jrxcjijii7.,2,1;131ixjij17.,2,8;131ixjij包裹容量限制必带物品限制选带物品限制第21页/共82页第22页 目标函数未带物品购买费用最小17.,2,8;131ixjij)1(31178jijiixp第22页/共82页第23页模 型)1(min31178jijiixp3,2,1;171jrxcjijii7.,2,1;131ixjij17.,2,8;131ixjij3,2,1,17.,2,1;0,1jixij第23页/共82页第24页n特征变量整数性要求n来源 问题本身的要求 引入的逻辑变量的需要n性质可行域是离散集合第24页/共82页第25页第25页/共82页第26页线性整数规划模型 一般整数规划模型 0-1整数规划模型 混合整数规划模型第26页/共82页第27页一般整数规划模型 为整数为整数xxbAxtsxc,0.min 第27页/共82页第28页0-1整数规划模型 nixbAxtsxci,.,2,1;1,0.min 第28页/共82页第29页混合整数规划模型pixxbAxtsxci,.,2,1,0.min为整数 第29页/共82页第30页算 法 与线性规划的关系 分支定界算法 割平面算法 近似算法第30页/共82页第31页与线性规划的关系 为整数为整数xxbAxtsxc,0.min 整数规划 0.minxbAxtsxc 放松的线性规划可行解是放松问题的可行解最优值大于等于放松问题的最优值第31页/共82页第32页第32页/共82页第33页第33页/共82页第34页注 释 最优解不一定在顶点上达到 最优解不一定是放松问题最优解的邻近整数解 整数可行解远多余于顶点，枚举法不可取第34页/共82页第35页分支定界算法 算法思想 算法步骤 算例 注释第35页/共82页第36页算 法 思 想 隐枚举法求解放松问题最优值比界坏 最优解为整数最优值比界好 最优解为非整数最优值比界好分 支边 界分 支舍 弃第36页/共82页第37页分支的方法NB1IbBcB1N0bB1Zbxrr rrrbxb第37页/共82页第38页为整数xxbAxtsxc,0.min 为整数xxbxbAxtsxcrr,0.min 为整数xxbxbAxtsxcrr,0.min 第38页/共82页第39页第39页/共82页第40页定 界 当前得到的最好整数解的目标函数值 分支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则 删除该分支其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解第40页/共82页第41页选一分支写出并求解放松问题，同时从分支集中删除该分支判定是否为整数解初始分支为可行解集，初始界为无穷大判定是否分支集空是停止当前最好解为最优解是否第41页/共82页第42页判定最优值是否小于当前界判定最优值是否小于当前界是否按非整数变量分支并加入分支集否是以最优解替代当前最好解最优值替代当前界第42页/共82页第43页算 例第43页/共82页第44页第44页/共82页第45页第45页/共82页第46页第46页/共82页第47页注 释 求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。
第47页/共82页第48页 对0-1整数规划分支时1,0.minxbAxtsxc 1,01.minxxbAxtsxcr 1,00.minxxbAxtsxcr 第48页/共82页第49页 算法思想 算法步骤 算例割平面算法第49页/共82页第50页算 法 思 想 由放松问题的可行域向整数规划的可行域逼近 方法利用超平面切除 要求 整数解保留 放松问题最优值增加第50页/共82页第51页割平面生成方法 条件-保留整数解删除最优解rNjjrjrbxaxNB1IN0BbBcB101bBBxNx第51页/共82页第52页rNjjrjrbxaxrNjjrjrbxax rNjjrjrbxax rNjjrjrbxaxrjrjrjfaarjrjaa rrrfbb rrbb 整数可行解最优基可行解第52页/共82页第53页为整数xxbAxtsxc,0.min 为整数xxbxaxbAxtsxcNjrrjrjr,0.min 第53页/共82页第54页 为整数xxbsxaxbAxtsxcNjrrrjrjr,0.min 第54页/共82页第55页1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbbBcB1第55页/共82页第56页1xnx2x1mxmx0111mabBcB101m00110nna11mmamna1bmbrx011rmarnarbrs000011rmarna1 rb第56页/共82页第57页1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs000011rmrmaarnrnaa1 rrbbbBcB10第57页/共82页第58页1xnx2x1mxmx0111ma01m00110nna11mmamna1bmbrx011rmarnarbrs00001rmfrnf1rfbBcB100rf正则解第58页/共82页第59页算 法 步 骤求放松问题的最优基可行解判断是否为整数解是停止得到最优解否在单纯性表中加入一列利用对偶单纯性算法求最优解第59页/共82页第60页算 例整数,0,023623.max2121212xxxxxxtsx(1,1.5)第60页/共82页第61页 0,023623.min43214213212xxxxxxxxxxtsx第61页/共82页第62页1x3x2x4x010 0031206310021x3x2x4x005.0061165.15.000105.1第62页/共82页第63页1x3x2x4x006/16/1414/12/3101104/14/12/31s000010111001432sxxx0011x3x2x4x006/16/1414/12/3101104/14/12/3第63页/共82页第64页1x3x2x4x006/16/1414/12/3101104/14/12/31s00002/114/14/101x3x2x4x003/1101011s3/2024011001103/2001第64页/共82页第65页1x3x2x4x003/1101011s3/2024011001103/20012s00003232321000第65页/共82页第66页1x3x2x4x00101011s01501001100012s002/300011102/3012/11第66页/共82页第67页计 算 软 件 整数变量定义 LinDo 一般整数变量:GIN 0-1整数变量:INT LinGo 一般整数变量:GIN(variable_name);0-1整数变量：BIN(variable_name);算例第67页/共82页第68页算 例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x 1+2 x 2 +5 x3=2000endgin x1gin x3为整数313213213221321,0,200052380042150032.453maxxxxxxxxxxxxxtsxxx第68页/共82页第69页应用案例分析 人力资源分配问题 应急设施选址问题第69页/共82页第70页人力资源分配问题 某个中型百货商场对售货人员（周工资200元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周工作5天，休息2天。
问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？星期星期一一二二三三四四五五六六七七人数人数 12 15 12 14 16 18 19第70页/共82页第71页模型假设 每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量第71页/共82页第72页问题分析因素 不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案 确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数变量 每天开始休息的人数 约束条件 1.每人休息时间2天，自然满足7,.,2,1,ixi 2.每每天天工工作作人人数数不不低低于于需需求求量量，第第i天天工工作作的的人人数数就就是是从从第第2i天天往往前前数数5 天天内内开开始始工工作作的的人人数数，所所以以有有约约束束：第72页/共82页第73页1265432xxxxx 1576543xxxxx 1217654xxxxx 1421765xxxxx 1632176xxxxx 1843217xxxxx 1954321xxxxx 3.变量非负约束：7,.,2,1,0ixi 第73页/共82页第74页目标函数：总费用最小，总费用与使用的总人数成正比。
由于每个人必然在且仅在某一天开始休息，所以总人数等于 71iix 第74页/共82页第75页模 型7,.,2,1,019181614121512.200min5432174321763217652117654765436543271ixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxtsxiii 第75页/共82页第76页注 解 该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价定义整数变量用函数gin(x1)gin(x7);0-1整数变量为bin(x1)第76页/共82页第77页应急选址问题 某城市要在市区设置k个应急服务中心,经过初步筛选确定了m个备选地，现已知共有n个居民小区，各小区到个备选地的距离为 为了使得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的短，试给出中心选址方案2,1,.,2,1,mjnidij 第77页/共82页第78页问题分析 该问题与传统的选址问题的主要区别在于其目标不再是要求费用最小，而是要求最长距离最短也就是离服务中心距离最远的小区离最近的服务中心距离最小变量：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正的变量也就是小区的位置。
设 ,.,2,1,1,0mjxj 第78页/共82页第79页问题分析 为了便于说明问题引入间接变量，第i小区是否由第j个中心服务 以及最远的距离 约束条件 小区服务约束,.,2,1,.,2,1,1,0mjniyij ,.,2,1,.,2,1,mjnixyjij ,.,2,1,11niymjij ,z第79页/共82页第80页问 题 分 析最远距离约束中心个数约束目标函数：最远距离 最小mjnizydijij,.,2,1,.,2,1,z,1kxmjj 第80页/共82页第81页模 型0,.,2,1,.,2,1,1,0,.,2,1,.,2,1,.,2,1,1,.,2,1,.,2,1,.min11zmjniyxkxmjnizydniymjnixytszijjmjjijijmjijjij第81页/共82页第82页感谢您的观看！第82页/共82页。