《整数线性规划课件》由会员分享，可在线阅读，更多相关《整数线性规划课件（82页珍藏版）》请在金锄头文库上搜索。
1、运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming1整数线性规划课件整整 数数 规规 划划n整数规划问题与模型整数规划问题与模型n整数规划算法整数规划算法n计算软件计算软件n应用案例应用案例2整数线性规划课件整数规划问题整数规划问题n实例实例n特点特点n模型分类模型分类3整数线性规划课件应用案例应用案例n投资组合问题投资组合问题n旅游售货员问题旅游售货员问题n背包问题背包问题4整数线性规划课件投资组合问题投资组合问题n背背
2、 景景n实实 例例n模模 型型5整数线性规划课件背背 景景n证券投资证券投资：把一定的资金投入到合适的有：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润。价证券上以规避风险并获得最大的利润。n项目投资项目投资：财团或银行把资金投入到若干：财团或银行把资金投入到若干项目中以获得中长期的收益最大项目中以获得中长期的收益最大。6整数线性规划课件案案 例例n某财团有某财团有 万元的资金，经出其考察选中万元的资金，经出其考察选中 个个投资项目，每个项目只能投资一个。其中第投资项目，每个项目只能投资一个。其中第 个项目需投资金额为个项目需投资金额为 万元，预计万元，预计5年后获利年后获利 （
3、 ）万元，问应如何选择项目使得）万元，问应如何选择项目使得5年后总收益最大？年后总收益最大？7整数线性规划课件模模 型型n变量变量每个项目是否投资每个项目是否投资n约束约束总金额不超过限制总金额不超过限制n目标目标总收益最大总收益最大8整数线性规划课件9整数线性规划课件旅游售货员问题旅游售货员问题n背景背景n案例案例n模型模型10整数线性规划课件背背 景景n旅游线路安排旅游线路安排 预定景点走且只走一次预定景点走且只走一次 路上时间最短路上时间最短n配送线路配送线路货郎担问题货郎担问题 送货地到达一次送货地到达一次 总路程最短总路程最短11整数线性规划课件案案 例例n有一旅行团从有一旅行团从
4、出发要遍游城市出发要遍游城市 ，已知从，已知从 到到 的旅费为的旅费为 ，问应如何安排行程使总费用最小，问应如何安排行程使总费用最小？12整数线性规划课件模模 型型n变量变量是否从是否从i第个城市到第第个城市到第j个城市个城市n约束约束 每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次13整数线性规划课件n避免出现断裂避免出现断裂 每个点给个位势每个点给个位势 除了初始点外要求前点除了初始点外要求前点比后点大比后点大14整数线性规划课件n目标目标总费用最小总费用最小15整数线性规划课件16整数线性规划课件背包问题背包问题n背景背景n案例案例n模型模型17整数线性规划课件背背 景景n
5、邮递包裹邮递包裹 把形状可变的包裹用尽量少的车辆运走把形状可变的包裹用尽量少的车辆运走n旅行背包旅行背包 容量一定的背包里装尽可能的多的物品容量一定的背包里装尽可能的多的物品18整数线性规划课件实实 例例n某人出国留学打点行李，现有三个旅行包，容积某人出国留学打点行李，现有三个旅行包，容积大小分别为大小分别为1000毫升、毫升、1500毫升和毫升和2000毫升，根毫升，根据需要列出需带物品清单，其中一些物品是必带据需要列出需带物品清单，其中一些物品是必带物品共有物品共有7件，其体积大小分别为件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有、（单位毫
6、升）。尚有10件件可带可不带物品，如果不带将在目的地购买，通可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。出一个合理的安排方案把物品放在三个旅行包里。 19整数线性规划课件物品物品12345678910体积体积200350500430320120700420250100价格价格154510070507520090203020整数线性规划课件问题分析问题分析n变量变量对每个物品要确定是否带同
7、时要确定放在对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第难写成变量的函数。为此我们设变量为第i个物品个物品是否放在第是否放在第j个包裹中个包裹中21整数线性规划课件n约束约束包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选
8、带物品限制22整数线性规划课件n目标函数目标函数未带物品购买费用最小未带物品购买费用最小23整数线性规划课件模模 型型24整数线性规划课件n特征特征变变量整数性要求量整数性要求n来源来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要n性质性质可可行域是离散集合行域是离散集合25整数线性规划课件26整数线性规划课件线性整数规划模型线性整数规划模型n一般整数规划模型一般整数规划模型n0-1整数规划模型整数规划模型n混合整数规划模型混合整数规划模型27整数线性规划课件一般整数规划模型一般整数规划模型28整数线性规划课件0-1整数规划模型整数规划模型29整数线性规划课件混合整
9、数规划模型混合整数规划模型30整数线性规划课件算算 法法n与线性规划的关系与线性规划的关系n分支定界算法分支定界算法n割平面算法割平面算法n近似算法近似算法31整数线性规划课件与线性规划的关系与线性规划的关系放松的线性规划放松的线性规划可行解是放松问题的可行解可行解是放松问题的可行解最优值大于等于放松问题的最优值最优值大于等于放松问题的最优值 整数规划整数规划32整数线性规划课件33整数线性规划课件34整数线性规划课件注注 释释n最优解不一定在顶点上达到最优解不一定在顶点上达到n最优解不一定是放松问题最优解的邻近整数最优解不一定是放松问题最优解的邻近整数解解n整数可行解远多余于顶点，枚举法不可
10、取整数可行解远多余于顶点，枚举法不可取35整数线性规划课件分支定界算法分支定界算法n算法思想算法思想n算法步骤算法步骤n算例算例n注释注释36整数线性规划课件算算 法法 思思 想想隐枚举法隐枚举法求解放松问题求解放松问题最优值比界坏最优值比界坏 最优解为整数最优解为整数最优值比界好最优值比界好 最优解为非整最优解为非整数最优值比界好数最优值比界好分分 支支边边 界界分分 支支舍舍 弃弃37整数线性规划课件分支的方法分支的方法38整数线性规划课件39整数线性规划课件40整数线性规划课件定定 界界n当前得到的最好整数解的目标函数值当前得到的最好整数解的目标函数值n分支后计算放松的线性规划的最优解分
11、支后计算放松的线性规划的最优解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值小于原有最好解的值则替代原有最好解整数解且目标值大于原有最好解的值则整数解且目标值大于原有最好解的值则 删除该分支其中删除该分支其中无最优解无最优解非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值小于原有最好解的值则继续分支非整数解且目标值大于等于原有最好解的值则删除该分非整数解且目标值大于等于原有最好解的值则删除该分支其中无最优解支其中无最优解41整数线性规划课件选一分支写出并求解选一分支写出并求解放松问题，同时从分放松问题，同时从分支集中删除该分支支集中删除该分支判判定是否定是否为整数为
12、整数解解初始分支为可行解初始分支为可行解集，初始界为无穷大集，初始界为无穷大判判定是否定是否分支集分支集空空是停止是停止当前最好解当前最好解为最优解为最优解是是否否42整数线性规划课件判定最判定最优值是否优值是否小于小于当前界当前界判定最判定最优值是否优值是否小于小于当前界当前界是是否否按非整数变量分按非整数变量分支并加入分支集支并加入分支集否否是是以最优解替代当前最以最优解替代当前最好解最优值替代当前界好解最优值替代当前界43整数线性规划课件算算 例例44整数线性规划课件45整数线性规划课件46整数线性规划课件47整数线性规划课件注注 释释n求解混合整数规划问题，只对整数变量分支，对求解混合
13、整数规划问题，只对整数变量分支，对非整数变量不分支。非整数变量不分支。48整数线性规划课件n对对0-1整数规划分支时整数规划分支时49整数线性规划课件分枝问题解可能出现的情况分枝问题解可能出现的情况情况情况 2, 4, 5 找到最优解找到最优解情况情况 3 在缩减的域上继续分枝定界法在缩减的域上继续分枝定界法情况情况 6 问题问题 1 的整数解作为的整数解作为界界被保留，用于以后与问题被保留，用于以后与问题 2 的后的后续分枝所得到的解进行比较，结论如情况续分枝所得到的解进行比较，结论如情况 4 或或 550整数线性规划课件分枝定界法举例分枝定界法举例 例例4解解：松弛问题的最优解为：松弛问题
14、的最优解为 x1=2.5, x2=2, OBJ=23 由由 x1=2.5 得到两个分枝如下：得到两个分枝如下：51整数线性规划课件 表表4.2.3 分枝问题的松弛解分枝问题的松弛解问题问题II的解即原整数问题的最优解的解即原整数问题的最优解 可能存在两个分枝都是非整数解的情况，则需要两边同时可能存在两个分枝都是非整数解的情况，则需要两边同时继续分枝，直到有整数解出现，就可以进行定界过程继续分枝，直到有整数解出现，就可以进行定界过程 当存在很多变量有整数约束时，分枝即广又深，在最坏情当存在很多变量有整数约束时，分枝即广又深，在最坏情况下相当于组合所有可能的整数解况下相当于组合所有可能的整数解 一
15、般整数规划问题属于一类未解决的难题，一般整数规划问题属于一类未解决的难题，NP-complete，只有少数特殊问题有好的算法，如只有少数特殊问题有好的算法，如任务分配问题任务分配问题、匹配问题匹配问题52整数线性规划课件n算法思想算法思想n算法步骤算法步骤n算例算例割平面算法割平面算法53整数线性规划课件算算 法法 思思 想想n由放松问题的可行域向由放松问题的可行域向整数规划的可行域逼近整数规划的可行域逼近n方法方法利用超平面切除利用超平面切除n要求要求 整数解保留整数解保留 放松问题最优值增加放松问题最优值增加54整数线性规划课件割平面生成方法割平面生成方法n条件条件-保留整数解删除最优解保
16、留整数解删除最优解55整数线性规划课件整数可行解整数可行解最优基可行解最优基可行解56整数线性规划课件57整数线性规划课件58整数线性规划课件59整数线性规划课件60整数线性规划课件61整数线性规划课件正则解正则解62整数线性规划课件算算 法法 步步 骤骤求放松问题的求放松问题的最优基可行解最优基可行解判断是否判断是否为整数解为整数解是停止是停止得到最优解得到最优解否否在单纯性表中加入在单纯性表中加入一列利用对偶单纯一列利用对偶单纯性算法求最优解性算法求最优解63整数线性规划课件算算 例例(1,1.5)64整数线性规划课件65整数线性规划课件66整数线性规划课件67整数线性规划课件68整数线性
17、规划课件69整数线性规划课件70整数线性规划课件计计 算算 软软 件件n整数变量定义整数变量定义 LinDo 一般整数变量一般整数变量:GIN 0-1整数变量整数变量: INT LinGo 一般整数变量一般整数变量: GIN( variable_name); 0-1整数变量：整数变量：BIN( variable_name);n算例算例71整数线性规划课件算算 例例 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 x372整数线性规划课件4.6 任务分配问题任务
18、分配问题例例4.6.1 有四个熟练工人，他们都是多面手，有四项任务要他们有四个熟练工人，他们都是多面手，有四项任务要他们完成。若规定每人必须完成且只完成一项任务，而每人完成每完成。若规定每人必须完成且只完成一项任务，而每人完成每项任务的工时耗费如表项任务的工时耗费如表4.6.1，问如何分配任务使完成四项任，问如何分配任务使完成四项任务的总工时耗费最少？务的总工时耗费最少？73整数线性规划课件 任务分配问题的数学模型任务分配问题的数学模型模型中：模型中：xij 为第为第 i 个工人分配去做第个工人分配去做第 j 项任务；项任务； aij 为第为第 i 个工人为完成第个工人为完成第 j 项任务时的
19、工时消耗；项任务时的工时消耗； aijm m 称为称为效率矩阵效率矩阵 运输问题是任务分配问题的松弛问题运输问题是任务分配问题的松弛问题 任务分配问题不但是整数规划，而且是任务分配问题不但是整数规划，而且是0 1规划规划 任务分配问题有任务分配问题有2m个约束条件，但有且只有个约束条件，但有且只有m个非零解，个非零解，是自然是自然高度退化高度退化的的任务分配是任务分配是两部图两部图的的匹配问题匹配问题，有著名的，有著名的匈牙利算法匈牙利算法下面介绍一种适合手算的算法下面介绍一种适合手算的算法(出自清华教科书出自清华教科书)74整数线性规划课件 4.6.1 清华算法清华算法定理定理 1 如果从效
20、率矩阵如果从效率矩阵aijm m中每行元素分别减去一个常数中每行元素分别减去一个常数 ui，从每列元素分别减去一个常数从每列元素分别减去一个常数 vj ，所得新的效率矩阵，所得新的效率矩阵bijm m的的任务分配问题的最优解等价于原问题的最优解。任务分配问题的最优解等价于原问题的最优解。 证明：略证明：略定理定理 2 若方阵中一部分元素为零，一部分元素非零，则覆盖方阵若方阵中一部分元素为零，一部分元素非零，则覆盖方阵内所有零元素的最少直线数等于位于不同行、不同列的零元素的内所有零元素的最少直线数等于位于不同行、不同列的零元素的最多个数。最多个数。 证明：略证明：略 清华算法的清华算法的基本思路
21、基本思路：n根据根据定理定理 1 变换效率矩阵，使矩阵中有足够多的零。若矩阵中变换效率矩阵，使矩阵中有足够多的零。若矩阵中存在存在 m 个不同行不同列的零，就找到了最优解个不同行不同列的零，就找到了最优解n若覆盖变换后的效率矩阵零元素的直线少于若覆盖变换后的效率矩阵零元素的直线少于m 条，就尚未找到条，就尚未找到最优解，设法进一步变换矩阵，增加新的零最优解，设法进一步变换矩阵，增加新的零75整数线性规划课件 清华算法的步骤：例清华算法的步骤：例4.6.1第一步第一步：变换效率矩阵，使每行每列至少有一个零：变换效率矩阵，使每行每列至少有一个零q行变换行变换：找出每行最小元素，从该行各元素中减去之
22、：找出每行最小元素，从该行各元素中减去之q列变换列变换：找出每列最小元素，从该列各元素中减去之：找出每列最小元素，从该列各元素中减去之第二步第二步：检查覆盖所有零元素的直线是否为：检查覆盖所有零元素的直线是否为m条条划线规则划线规则1、逐行检查、逐行检查，若该行只有一个未标记的零，对其加，若该行只有一个未标记的零，对其加( )标记，将标记，将 ( )标记元素同行同列上其它的零打上标记元素同行同列上其它的零打上*标记。若该行有二个以上标记。若该行有二个以上未标记的零，暂不标记，转下一行检查，直到所有行检查完；未标记的零，暂不标记，转下一行检查，直到所有行检查完；76整数线性规划课件 清华算法的步
23、骤：例清华算法的步骤：例4.6.12、逐列检查、逐列检查，若该列只有一个未标记的零，对其加，若该列只有一个未标记的零，对其加( )标记，将标记，将( )标记元素同行同标记元素同行同列上其它的零打上列上其它的零打上*标记。若该列有二个以上未标记的零，暂不标记，转下一列标记。若该列有二个以上未标记的零，暂不标记，转下一列检查，直到所有列检查完；检查，直到所有列检查完；3、重复、重复1、2后，可能出现三种情况：后，可能出现三种情况：a. 每行都有一个每行都有一个 (0)，显然已找到最优解，令对应，显然已找到最优解，令对应(0)位置的位置的 xij=1；b. 仍有零元素未标记，此时，一定存在某些行和列
24、同时有多个零，称仍有零元素未标记，此时，一定存在某些行和列同时有多个零，称为为僵局状态僵局状态，因为无法采用，因为无法采用 1、 2 中的方法继续标记。中的方法继续标记。4、打破僵局打破僵局。令未标记零对应的同行同列上其它未标记零的个数为。令未标记零对应的同行同列上其它未标记零的个数为该零的该零的指数指数，选，选指数最小指数最小的先标记的先标记 ( )；采用这种方法直至所有零都；采用这种方法直至所有零都被标记，或出现被标记，或出现 情况情况 a，或，或 情况情况 c 。77整数线性规划课件 清华算法的步骤：例清华算法的步骤：例4.6.1c. 所有零都已标记，但标有所有零都已标记，但标有( )的
25、零的个数少于的零的个数少于m； 开始开始划线过程划线过程： 对没有标记对没有标记 ( ) 的行打的行打 对打对打 行上所有其它零元素对应的列打行上所有其它零元素对应的列打 再对打再对打 列上有列上有 ( ) 标记的零元素对应的行打标记的零元素对应的行打 重复重复 ，直至无法继续，直至无法继续 对没有打对没有打 的行划的行划横线横线，对所有打，对所有打 的列划的列划垂线垂线 划线后会出现两种情况：划线后会出现两种情况：(1) 标记标记( )的零少于的零少于m个，但划有个，但划有 m条直线，说明矩阵中已存在条直线，说明矩阵中已存在 m 个不个不同行不同列的零，但打破僵局时选同行不同列的零，但打破僵
26、局时选择不合理，没能找到。回到择不合理，没能找到。回到 b 重新重新标记；标记；(2) 少于少于m条直线，到条直线，到第三步第三步；78整数线性规划课件 清华算法的步骤：例清华算法的步骤：例4.6.1第三步：第三步：进一步变换；进一步变换； 在未划线的元素中找在未划线的元素中找最小者最小者，设为，设为 对未被直线覆盖的各元素减去对未被直线覆盖的各元素减去 对两条直线交叉点覆盖的元素加上对两条直线交叉点覆盖的元素加上 只有一条直线覆盖的元素保持不变只有一条直线覆盖的元素保持不变以上步骤实际上仍是利用以上步骤实际上仍是利用 定理定理 1第四步：第四步：抹除所有标记，回到抹除所有标记，回到第二步第二
27、步，重新标记；，重新标记；79整数线性规划课件 清华算法的步骤：例清华算法的步骤：例4.6.1答：最优分配方案为答：最优分配方案为 x13= x21= x34 = x42 =1，其余为，其余为0， 即甲即甲C，乙，乙A，丙，丙D，丁，丁B，OBJ=2080整数线性规划课件 4.6.2 关于清华算法的适用条件关于清华算法的适用条件n要求所有要求所有aij 0q若某些若某些 aij 0 ，则利用定理，则利用定理 1 进行变换，使所有进行变换，使所有 bij 0n目标函数为目标函数为min型型q对于对于max型目标函数，将效率矩阵中所有型目标函数，将效率矩阵中所有 aij 反号，则等效于求反号，则等
28、效于求min型问题；再利用定理型问题；再利用定理 1 进行变换，使所有进行变换，使所有 bij 0，则可采用，则可采用清华算法清华算法 打破僵局时选择不当的结果：打破僵局时选择不当的结果： 结果仅出现结果仅出现 3 个标记个标记( )，但却划出，但却划出 4 条线，条线， 说明什么？！说明什么？！81整数线性规划课件线性规划有关的英文词汇线性规划有关的英文词汇nOperational/operations research 运筹学运筹学nLinear programming 线性规划线性规划 Feasible domain 可行域可行域nConvex set 凸集凸集 Basic feasib
29、le solutions 基础可行解基础可行解nSimplex algorithm 单纯型法单纯型法 Pivot 主元主元 Pivoting 主元变换主元变换nRevised, dual simplex algorithm 修正、对偶单纯型法修正、对偶单纯型法nRelative cost 相对成本相对成本(机会成本机会成本) Shadow price 影子价格影子价格nSlack, Surplus, Artificial variable 松弛，剩余，人工变量松弛，剩余，人工变量nUnbounded, Infeasible, Degenerate solution 无界解无界解, 无可行解无可行解, 退化退化解解nDuality 对偶性对偶性 Primal, dual problem 原问题，对偶问题原问题，对偶问题nComplementary slackness 互补松弛互补松弛 Sensitivity analysis 灵敏度灵敏度分析分析nTtransportation problem 运输问题运输问题nAssignment problem 任务分配任务分配(指派指派) 问题问题nBipartite matching 两部图匹配两部图匹配 Hungarian method 匈牙利算法匈牙利算法82整数线性规划课件
