《运筹学第章PPT课件》由会员分享，可在线阅读，更多相关《运筹学第章PPT课件（82页珍藏版）》请在金锄头文库上搜索。
1、第五章第五章 整整 数数 规规 划划(Integer Programming,IP)本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题整整数数规规划划问问题题|投资组合问题|旅游售货员问题|背包问题应用案例应用案例投资投资组合组合问题问题背景背景|证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润|项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资投资组合组合问题问题案例案例|某财团有 万元的资金，经出其考察选中 个投资项目，每个项目只能投资一个。其中第 个项目需投资金额为 万元，预计5年后获利
2、 万元 ，问应如何选择项目使得5年后总收益最大？投资投资组合组合问题问题模型模型|变量每个项目是否投资|约束总金额不超过限制|目标总收益最大旅游旅游售货售货员问员问题背题背景景|旅游线路安排 预定景点走且只走一次 路上时间最短；|配送线路货郎担问题 送货地到达一次 总路程最短；旅游旅游售货售货员问员问题案题案例例|有一旅行团从 出发要遍游城市 ，已知从 到 的旅费为 ，问应如何安排行程使总费用最小？旅游旅游售货售货员问员问题模题模型型|变量是否从i第个城市到第j个城市；|约束每个城市只能到达一次、离开一次；|目标总费用最小；背包背包问题问题背景背景|邮递包裹 把形状可变的包裹用尽量少的车辆运走
3、|旅行背包 容量一定的背包里装尽可能的多的物品背包背包问题问题实例实例|某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升，根据需要列出需带物品清单，其中一些物品是必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）。尚有10件可带可不带物品，如果不带将在目的地购买，通过网络查询可以得知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表，试给出一个合理的安排方案把物品放在三个旅行包里。 物品12345678910体积200350500430320120700420250100价格1545100
4、705075200902030背包背包问题问题模型模型|变量对每个物品要确定是否带同时要确定放在哪个包裹里，如果增加一个虚拟的包裹把不带的物品放在里面，则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号，则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设变量为第i个物品是否放在第j个包裹中|约束 包裹容量限制： 必带物品限制： 选带物品限制：|目标函数 未带物品购买费用最小背包背包问题问题模型模型背包背包问题问题模型模型s.t.整数整数规划规划问题问题n特征变量整数性要求；n来源 问题本身的要求； 引入的逻辑变量的需要；n性质可行域是离散集合；线线性性整整
5、数数规规划划模模型型|一般整数规划模型|0-1整数规划模型|混合整数规划模型一一般般整整数数规规划划模模型型整数线性规划线性数学问题模型的一般形式为0-10-1整整数数规规划划模模型型混混合合整整数数规规划划模模型型|令|问题模型为：|例2 现有资金总额为B。可供选择的投资项目有n个，项目j所需投资额和预期收益分别为aj和cj(j=1,2,，n)。此外，由于种种原因，有三个附加条件：第一，若选择项目1，就必须同时选择项目2。反之，则不一定；第二，项目3和项目4中至少选择一个；第三，项目5、项目6和项目7中恰好选择两个。应当怎样选择投资项目，才能使总预期收益最大?属于 0-1规划问题整数整数规划
6、规划问题问题解的解的特点特点（IP）问题的松弛问题松弛问题的最优值是原整数规划的目标函数值的上界。注释注释|最优解不一定在顶点上达到|最优解不一定是放松问题最优解的邻近整数解|整数可行解远多余于顶点，枚举法不可取本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题割平面法的基本思想：若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的
7、最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.割平割平面法面法|由放松问题的可行域向整数规划的可行域逼近|方法利用超平面切除|要求整数解保留 放松问题最优值向最优解逼近|目标得到的新的可行域的某个整数坐标的极点恰好是问题的最优解割平割平面法面法非基变量下标集合n符号*表示不超过“*”的最大整数，f(*)表示“*”的非负真分数。|Gomory约束L0的最优单纯形表：x1 xi xmxm+1 xm+j xn解检0 0 01 m+j nz-z0 x11 0 0a1m+1 a1m+j a1nb10 xi0 1 0aim+1 aim+j
8、 ainbi0 xm0 0 1amm+1 amm+j amnbm0源方程-对应于生成行i的割平面x1 xixmxm+1xm+jxn解检0 001m+jnz-z0 x11 00a1m+1a1m+ja1nb10 xi0 10aim+1aim+jainbi0 xm0 01amm+1amm+jamnbm0L0的最优单纯形表：生成行对应于生成行i的割平面非基变量|求解整数线性规划第一步：解整数规划问题的松弛问题，见表5-3 ，x1=13/7， x2=9/7；cj3-1000cBxBbx1x2x3x4x53x113/7101/702/7-1x29/701-2/703/70 x431/700-3/7122/
9、7cj-zj00-5/70-3/7表 5-3|第二步：写出割平面方程，选择第一行产生割平面约束，cj3-10000cBxBibix1x2x3x4x5x63-100 x1x2x4x613/79/731/7-6/7100001001/7-2/7-3/7-1/700102/73/722/7-2/70001cj-zj-5/200-5/70-3/703-100 x2x1x3x515/45/27/41000010000100-1/4-1/21/400011-5/4-11/2-3/4cj-zj000-1/40-17/4表 5-4cj3-1000 00cBxBibix1x2x3x4x5x6x73-1000 x
10、1x2x3x5x41241310000010000010000001000101-1-5-110-1-21-4cj-zj-100000-4-1表 5-5原整数规划问题的最优解为，x1=1, x2=2,max z=1四、割平面计算步骤：第一步： 用单纯刑法解整数问题IP的松弛问题L0若L0没有最优解，则IP没有最优解。停止若L0有最优解X0:(1)X0是整数解， 则X0也是IP的最优解，停止(2)X0不是整数解， 转第二步第二步： 求割平面方程第三步：将割平面加到L0得L1第四步：解L1在L0的最优单纯型表中增加一行一列，得L1的单纯型表，用对偶单纯刑法求解，若其解是整数解，则该解也是原整数规划
11、的最优解否则将该解记为X0，返回第二步本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题分分支支定定界界法法 分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration)或部分枚举法，它不是一种有效算法，是枚举法基础上的改进。 分支定界法的关键是分支和定界。 分支 求解放松问题 舍弃 变界 分支最优值比界坏最优解为整数最优值比界好最优解为非整数最优值比界好|分枝定界法的基本思路： 通过对松弛问题的分枝，不断降低（IP）最优值的上界，提高下界，当上界等于下界时，得到最优解。分支分
12、支 是不超过 的最大整数 IP松弛问题L0L1L2通过对（L0）分枝，使（IP）的最优值的上界不断下降，L3L4L5L6下界不断上升，上界=下界得最优值定界定界|当前得到的最好整数解的目标函数值|分支后计算放松的线性规划的最优解|整数解且目标值优于原有最好解的值则替代原有最好解；|整数解且目标值劣于原有最好解的值则 删除该分支其中无最优解；|非整数解且目标值优于原有最好解的值则继续分支；|非整数解且目标值劣于原有最好解的值则删除该分支其中无最优解；算例算例|例6 求解下述整数规划算例算例|第一步：舍弃整数要求，用单纯形法求解，得X(0)=(3/2,10/3),点 A,目标函数值z (0) =2
13、9/6（上界），（0，0）显然是一个可行解，目标函数值0（下界）算例算例|第二步，由于x1,x2都不是整数，分解成子问题（分支）。先考虑x1 ， x1 =3/2。 （1）（2）X(1)=(2,23/9), B点z (1) =41/9X(2)=(1,7/3), C点,z (2) =10/3 (新下界)算例算例算例算例|第三步，由于z (2) z (1) z (0) , z (1) =41/9代替z (0) 成为新的上界。此时，问题（2）已探明，结束。问题（1）需继续分支。（3）（4）无可行解，删去（剪枝）X(4)=(33/14,2), D点， z (4) =61/14算例算例算例算例|第四步，由
14、于z (2) z (4) z (0) , 问题（1）需继续分支。（5）（6）X(6)=(2,2), F点, z (6) =4X(5)=(3,1), E点, z (5) =4得到原整数规划问题的最优解。S0Ax1=3/2,x2=10/3 z=29/6S2Bx1=2,x2=23/9 z=41/9S4Dx1=33/14,x2=2 z=61/14S3无可行解S1Cx1=1,x2=7/3 z=10/3S6Ex1=3,x2=1 z=4S5Fx1=2,x2=2 z=4算例算例初始分支为可行解集，确定初始界是停止当前最好解为最优解判定是否分支集空是按非整数变量分支并加入分支集判定是否为整数解判定最优值是否优于
15、当前界否判定最优值是否优于当前界是否以最优解替代当前最好解最优值替代当前界是否选一分支写出并求解放松问题，同时从分支集中删除该分支否分分支支定定界界法法一一般般步步骤骤本章本章内容内容|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题一、决策问题与0-1变量10做第i件事不做第i件事n件事中必须做k件并只做k件事n件事中最多做k件事n件事中至少做k件事做第i件事的充要条件是做第j件事做第i件事的充要条件是不做第j件事只在做了第i件事前提下才考虑是否做第j件事例 8 有三种资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单耗量及组织三种产品
16、生产的固定费用见表5-6。要求制订一个生产计划，使总收益最大。表5-6 4 40-10-1整数整数规划规划|求解设xj是第 j 种产品的产量，j=1,2,3；再设其中约束条件 如何理解？0-10-1整数整数规划规划解法解法|隐枚举法（适合于变量个数较少的0-1规划）| 例 10 求解0-1整合规划（5.14a）（5.14b）（5.14d）（5.14c）算例算例|解： 约束条件(x2, x1, x3)abcdz(0,0,0) 0（初始滤值）(0,0,1) 5（新滤值）(0,1,0)-2(0,1,1)-3(1,0,0)-3(1,0,1)-8 （最后过滤值）(1,1,0)-1(1,1,1)-6最优解整整数数规规划划|整数规划的数学模型及解的特点|解纯整数规划的割平面法|分支定界法|0-1型整数规划|指派问题（assignment problem）指派指派问题问题模型模型n模型一般称矩阵C=(cij)nn为指派问题的系数矩阵。令指派指派问题问题的匈的匈牙利牙利解法解法|性质：假定C=(cij)为分派问题的价值系数矩阵。现将它的某一行（或某一列）的各元素都减去一个常数k，得到一新矩阵 。若以C代
