运筹学 整数线性规划.ppt

《运筹学 整数线性规划.ppt》由会员分享，可在线阅读，更多相关《运筹学 整数线性规划.ppt（82页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming1整整 数数 规规 划划n整数规划问题与模型整数规划问题与模型n整数规划算法整数规划算法n计算软件计算软件n应用案例应用案例2整数规划问题整数规划问题n实例实例n特点特点n模型分类模型分类3应用案例应用案例n投资组合问题投资组合问题n旅游售货员问题旅游售货员问题n背包问题背包问题4投资组合问题投资组合问题n背背 景景n实实 例例n模模 型型5背背 景景n证券投资证券投资：把

2、一定的资金投入到合适的：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利有价证券上以规避风险并获得最大的利润。润。n项目投资项目投资：财团或银行把资金投入到若：财团或银行把资金投入到若干项目中以获得中长期的收益最大干项目中以获得中长期的收益最大。6案案 例例n某财团有某财团有 万元的资金，经出其考察选中万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其个投资项目，每个项目只能投资一个。其中第中第 个项目需投资金额为个项目需投资金额为 万元，预计万元，预计5年后获利年后获利 （）万元，问应如何）万元，问应如何选择项目使得选择项目使得5年后总收益最大？年后总收益最大？7模模

3、 型型n变量变量每每个项目是否投资个项目是否投资n约束约束总总金额不超过限制金额不超过限制n目标目标总收益最大总收益最大89旅游售货员问题旅游售货员问题n背景背景n案例案例n模型模型10背背 景景n旅游线路安排旅游线路安排 预定景点走且只走一次预定景点走且只走一次 路上时间最短路上时间最短n配送线路配送线路货郎担问题货郎担问题 送货地到达一次送货地到达一次 总路程最短总路程最短11案案 例例n有一旅行团从有一旅行团从 出发要遍游城市出发要遍游城市 ，已知从，已知从 到到 的旅费为的旅费为 ，问应如何安排行程使总费用最，问应如何安排行程使总费用最小小？12模模 型型n变量变量是是否从否从i第个城

4、市到第第个城市到第j个城市个城市n约束约束 每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次13n避免出现断裂避免出现断裂 每个点给个位势每个点给个位势 除了初始点外要求前除了初始点外要求前点比后点大点比后点大14n目标目标总总费用最小费用最小1516背包问题背包问题n背景背景n案例案例n模型模型17背背 景景n邮递包裹邮递包裹 把形状可变的包裹用尽量少的车辆运走把形状可变的包裹用尽量少的车辆运走n旅行背包旅行背包 容量一定的背包里装尽可能的多的物品容量一定的背包里装尽可能的多的物品18实实 例例n某人出国留学打点行李，现有三个旅行包，容某人出国留学打点行李，现有三个旅行包，容积大

5、小分别为积大小分别为1000毫升、毫升、1500毫升和毫升和2000毫升，毫升，根据需要列出需带物品清单，其中一些物品是根据需要列出需带物品清单，其中一些物品是必带物品共有必带物品共有7件，其体积大小分别为件，其体积大小分别为400、300、150、250、450、760、190、（单、（单位毫升）。尚有位毫升）。尚有10件可带可不带物品，如果不件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排量及价格分别见下表，试给出一

6、个合理的安排方案把物品放在三个旅行包里。方案把物品放在三个旅行包里。19物品物品12345678910体积体积200350500430320120700420250100价格价格154510070507520090203020问题分析问题分析n变量变量对对每个物品要确定是否带同时要确定每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品个物

7、品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设的总容量就很难写成变量的函数。为此我们设变量为变量为第第i个物品是否放在个物品是否放在第第j个包裹个包裹中中21n约束约束包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选带物品限制22n目标函数目标函数未未带物品购买费用最小带物品购买费用最小23模模 型型24n特征特征变变量整数性要求量整数性要求n来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要n性质性质可可行域是离散集合行域是离散集合2526线性整数规划模型线性整数规划模型n一般整数规划模型一般整数规划模型n0-1整数规

8、划模型整数规划模型n混合整数规划模型混合整数规划模型27一般整数规划模型一般整数规划模型280-1整数规划模型整数规划模型29混合整数规划模型混合整数规划模型30算算 法法n与线性规划的关系与线性规划的关系n分支定界算法分支定界算法n割平面算法割平面算法n近似算法近似算法31与线性规划的关系与线性规划的关系整数规划整数规划放松的线性规划放松的线性规划可行解是放松问题的可行解可行解是放松问题的可行解最优值大于等于放松问题的最优值最优值大于等于放松问题的最优值323334注注 释释n最优解不一定在顶点上达到最优解不一定在顶点上达到n最优解不一定是放松问题最优解的邻近整最优解不一定是放松问题最优解的

9、邻近整数解数解n整数可行解远多余于顶点，枚举法不可取整数可行解远多余于顶点，枚举法不可取35分支定界算法分支定界算法n算法思想算法思想n算法步骤算法步骤n算例算例n注释注释36算算 法法 思思 想想隐枚举法隐枚举法求解放松问题求解放松问题最优值比界坏最优值比界坏 最优解为整数最优解为整数最优值比界好最优值比界好 最优解为非整最优解为非整数最优值比界好数最优值比界好分分 支支边边 界界分分 支支舍舍 弃弃37分支的方法分支的方法383940定定 界界n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分支后计算放松的线性规划的最优解分支后计算放松的线性规划的最优解整数解且目标值小

10、于原有最好解的值则替代原有最好整数解且目标值小于原有最好解的值则替代原有最好解解整数解且目标值大于原有最好解的值则整数解且目标值大于原有最好解的值则 删除该分支删除该分支其中无最优解其中无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解分支其中无最优解41选一分支写出并求解选一分支写出并求解放松问题，同时从分放松问题，同时从分支集中删除该分支支集中删除该分支判判定是否定是否为整数为整数解解初始分支为可行解初始分支为可行解集，初始界为无穷大集，

11、初始界为无穷大判判定是否定是否分支集分支集空空是是停止停止当前最好解当前最好解为最优解为最优解是是否否42判定最判定最优值是否优值是否小于小于当前界当前界判定最判定最优值是否优值是否小于小于当前界当前界是是否否按非整数变量分按非整数变量分支并加入分支集支并加入分支集否否是是以最优解替代当前最以最优解替代当前最好解最优值替代当前界好解最优值替代当前界43算算 例例44454647注注 释释n求解混合整数规划问题，只对整数变量分支，求解混合整数规划问题，只对整数变量分支，对非整数变量不分支。对非整数变量不分支。48n对对0-1整数规划分支时整数规划分支时49n算法思想算法思想n算法步骤算法步骤n算

12、例算例割平面算法割平面算法50算算 法法 思思 想想n由放松问题的可行域由放松问题的可行域向整数规划的可行域向整数规划的可行域逼近逼近n方法方法利利用超平面切用超平面切除除n要求要求 整数解保留整数解保留 放松问题最优值增放松问题最优值增加加51割平面生成方法割平面生成方法n条件条件-保留整数解删除最优保留整数解删除最优解解52整数可行解整数可行解最优基可行解最优基可行解535455565758正则解正则解59算算 法法 步步 骤骤求放松问题的求放松问题的最优基可行解最优基可行解判断是否判断是否为整数解为整数解是是停止停止得到最优解得到最优解否否在单纯性表中加入在单纯性表中加入一列利用对偶单纯

13、一列利用对偶单纯性算法求最优解性算法求最优解60算算 例例(1,1.5)61626364656667计计 算算 软软 件件n整数变量定义整数变量定义 LinDo 一般整数变量一般整数变量:GIN 0-1整数变量整数变量:INT LinGo 一般整数变量一般整数变量:GIN(variable_name);0-1整数变量：整数变量：BIN(variable_name);n算例算例68算算 例例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2+5 x3=2000endgin x1gin x369应用案例分析应用

14、案例分析n人力资源分配问题人力资源分配问题n应急设施选址问题应急设施选址问题70人力资源分配问题人力资源分配问题n某个中型百货商场对售货人员（周工某个中型百货商场对售货人员（周工资资200元）的需求经统计如下表元）的需求经统计如下表 为了保证销售人员充分休息，销售人员为了保证销售人员充分休息，销售人员每周工作每周工作5天，休息天，休息2天。问应如何安天。问应如何安排销售人员的工作时间，使得所配售排销售人员的工作时间，使得所配售货人员的总费用最小？货人员的总费用最小？星期星期一一二二三三四四五五六六七七人数人数 12 15 12 14 16 18 1971模型假设模型假设n每天工作每天工作8小时

15、，不考虑夜班的情况；小时，不考虑夜班的情况；n每个人的休息时间为连续的两天时每个人的休息时间为连续的两天时间；间；n每天安排的人员数不得低于需求量，每天安排的人员数不得低于需求量，但可以超过需求量但可以超过需求量72问题分析问题分析因素因素 不可变因素不可变因素：需求量、休息时间、单位费用；：需求量、休息时间、单位费用；可变因素可变因素：安排的人数、每人工作的时间、总费用；：安排的人数、每人工作的时间、总费用；方案方案 确定每天工作的人数，由于连续休息确定每天工作的人数，由于连续休息2天，当确定每天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定个人开始休息的时间就等于知道工作的时间

16、，因而确定每天开始休息的人数就知道每天开始工作的人数，从而每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。求出每天工作的人数。变量变量 每天开始休息的人数每天开始休息的人数 约束条件约束条件 1.每人休息时间每人休息时间2天，自然满足。天，自然满足。73 3.变量非负约束：变量非负约束：74目标函数目标函数：总费用最小，总费用与使用的总人总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于开始休息，所以总人数等于75模模 型型76注注 解解n该问题本质上是个整数规划问题，该问题本质上是个整数规划问

17、题，放松的线性规划的最优解是个整数放松的线性规划的最优解是个整数解，所以两规划等价。解，所以两规划等价。n定义整数变量用函数定义整数变量用函数gin(x1)gin(x7);0-1整数变量为整数变量为bin(x1)77应急选址问题应急选址问题 某城市要在市区设置某城市要在市区设置k个个应急服务中心应急服务中心,经过初步筛选确定了经过初步筛选确定了m个备选地，现已个备选地，现已知共有知共有n个居民小区，各小区到个备选地个居民小区，各小区到个备选地的距离为的距离为 为了使为了使得各小区能及时得到应急服务，要求各得各小区能及时得到应急服务，要求各小区到最近的服务中心的距离尽可能的小区到最近的服务中心的

18、距离尽可能的短，试给出中心选址方案。短，试给出中心选址方案。78问题分析问题分析 该问题与传统的选址问题的该问题与传统的选址问题的主要区别主要区别在在于其目标不再是要求费用最小，而是要于其目标不再是要求费用最小，而是要求最长距离最短。也就是离服务中心距求最长距离最短。也就是离服务中心距离最远的小区离最近的服务中心距离最离最远的小区离最近的服务中心距离最小。小。变量变量：当中心的位置确定下来后，各小：当中心的位置确定下来后，各小区对应的最近中心也就确定，所以真正区对应的最近中心也就确定，所以真正的变量也就是小区的位置。设的变量也就是小区的位置。设 79问题分析问题分析 为了便于说明问题引入间接变量，第为了便于说明问题引入间接变量，第i小区是否由第小区是否由第j个中心服务个中心服务 以及最远的距离以及最远的距离 约束条件约束条件 小区服务约束小区服务约束80问问 题题 分分 析析最远距离约束最远距离约束中心个数约束中心个数约束目标函数目标函数：最远距离：最远距离 最小最小81模模 型型82