运筹学第四章整数规划课件.ppt

《运筹学第四章整数规划课件.ppt》由会员分享，可在线阅读，更多相关《运筹学第四章整数规划课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章：特殊的线性规划整数规划 本章的主要内容：本章的主要内容：l理解整数规划的基本概念l掌握分枝定界法的思想和方法l掌握0-1变量的含义和用法l掌握指派问题的求解方法4.1 整数规划问题的提出整数规划的应用背景4.1 整数规划问题的提出l决策问题中经常有整数要求，如人数、件数、机器台数、货物箱数如何解决？四舍五入不行，枚举法太慢l所谓整数规划，就是指决策变量有整数要求的数学规划问题。l问题分类：纯整数规划、混合整数规划、0-1整数规划l专门方法：分枝定界法、割平面法、隐枚举法、匈牙利法应用举例1：投资问题 l5个投资项目；600万元资金，投资受到约束：l(1)项目1、2和3至少一项被选中；l

2、(2)项目3和4只能选一项；l(3)项目5选中的前提是1必须被选中。l问如何投资才能使收益最大？项目投资额(万元)期望收益(万元)121015023002103100604130805260180投资问题的数学模型：01规划l设01变量为决策变量，即xi=1表示项目i被选中，xi=0表示项目i被淘汰，则模型可表示为应用举例2：背包问题l目标：在不超过一定重量的前提下，使所携带物品的重要性系数之和最大。l 例：登山队员需携带的物品及每一件物品的重量和重要性系数见下表。假定允许携带的最大重量为25千克，试确定一最优方案。数据 物品项目食品氧气冰镐绳索帐篷照相器材通信设备重量(千克)55261224

3、重要系数201518148410背包问题的数学模型l解：设01变量表示携带物品i，表示不携带物品i，则问题可写为l可通过计算每一物品的重要性系数和重量的比值ci/ai来解决。应用举例3：布点问题 l共同目标：满足公共要求，布点最少，节约投资费用。l学校、医院、商业区、消防队等公共设施的布点问题。l例：某市6个区，希望设置最少消防站以便节省费用。条件：l必须保证在城区任何地方发生火警时，消防车能在15 15分钟分钟之内赶到现场。各区之间消防车行驶的时间见右表。l请确定设站方案。地点一区二区三区四区五区六区一区0二区100三区16240四区2832120五区271727150六区201021251

4、40布点问题的数学模型：l设01为决策变量，当表示i地区设站，表示i地区不设站。这样根据消防车15分钟赶到现场的限制，可得到如下模型4.2 整数规划的求解方法 分枝定界法、隐枚举法、匈牙利法4.2 整数规划的求解方法l在一般情况下，单纯形法求得的解并不能保证是整数最优解。l例：求整数规划l求解其松弛问题，很容易得出最优解为l 。整数规划图解法x2x1 1 2 3 4 5 6 7 231AB图解法的启示lA（4.8，0）点是LP问题的可行解，不是IP问题的可行解，B（4，1）才是IP的最优解l纯整数规划可行解是可行域中的整数点l非整数点不是可行解，对于求解没有意义，故切割掉可行域中的非可行解，不

5、妨碍整数规划问题的优化lIP问题的最优解不优于LP问题的最优解求解整数规划的分枝定界法l思路：分枝和定界两部分：l分枝：切割可行域，去掉非整数点。一次分枝变成两个可行域，分别求最优解l定界：松弛问题最优解上界；IP问题的任意可行解下界，不断减小上界和增加上界，最终的最优解。l对于最大化问题 l 对于最小化问题 l例1.求解整数规划Al解：先不考虑整数要求，解相应的LP问题，得：l是IP问题的上界,记作l Z=0，是的一个下界。分枝定界法（续）l(第一次分枝前）（第一次分枝后）l B1 B2l子问题B1，l子问题B2，分枝定界法（续）l因为Z1 Z2，故将 改为5.333，那么必存在最优整数解，

6、得到 ，并且 。l继续对子问题B1和B2进行分枝。l因为Z1 Z2，因此先将B1再分为两枝。增加条件 。前者称为子问题B3，后者称为子问题B4。在图中再舍去之间的可行域，再进行第二次迭代。得到的最优解为l子问题B3，；l子问题B4无可行解。分枝定界法（续2）l因子问题B3的解中所有变量均为整数，因此它的目标函数值 可取为 ，由于它大于 ，因此没有必要对子问题B2进行分枝。于是可以断定 。子问题B3的解 为最优整数解。l该问题整数解的分枝树如下图所示。总结：总结：分枝定界法的解题步骤分枝定界法的解题步骤l1、不考虑整数约束，解相应LP问题l2、检查是否符合整数要求，是，则得最优解，完毕。否则，转

7、下步l3、任取一个非整数变量xi=bi，构造两个新的约束条件：xi bi ,xi bi+1,分别加入到上一个LP问题，形成两个新的分枝问题。l4、不考虑整数要求，解分枝问题。若整数解的Z值所有分枝末梢的Z值，则得最优解。否则，取Z值最大的非整数解，继续分解，Go to 34.3 求解01规划隐枚举法01规划问题的求解方法l某些问题，只做是非选择，故变量设置简化为0或1，1代表选择，0代表不选择。l例投资方案的选择问题：600万元投资5个项目，求利润最大的方案？项目投资额项目收益约束条件210160 中选1项300210 之中选1项15060选必先选13080260180求解01规划的隐枚举法l

8、解：0 当项目未被选中 1 当项目被选中 max Z=160X1+210X2+60X3+80X4+180X5 210X1+300X2+150X3+130X4+260X5 600 X1+X2+X3=1 X3+X4=1 X5 X1 Xj=0或1 j=1，2,5增加过滤条件：160X1+210X2+60X3+80X4+180X5 240 建模：设xj=用隐枚举法解例题：(x1,x2,x3,x4,x5）Z值（1，0，0，1，0）240（1，1，1，1，1）X（1，1，1，1，0）X（1，1，1，0，1）X（1，1，1，0，0）X（1，1，0，1，1）X（1，1，0，1，0）X（1，1，0，0，1）X（

9、1，1，0，0，0）X（1，0，1，1，1）X（1，0，1，1，0）X（1，0，0，1，1）420 .4.4 求解指派问题匈牙利法指派问题的描述及特点指派问题的描述及特点l问题描述：ln项任务恰好由n个人完成。指派哪个人去完成哪项任务，才能使完成n项任务的总效率最高(或所需总时间最小)。l问题的特点：若从系数矩阵C的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵B，那么以B矩阵为系数矩阵求得的最优解和原系数矩阵求得的最优解相同。数学家库恩(W.W.Kuhn)提出指派问题的解法，称为匈牙利法。指派问题举例1：l例:一份说明书，须译成英、日、德、俄四种文字，分别记作E、J、G、R。现有

10、甲、乙、丙、丁四人。问应指派何人去完成何工作，才使所需总时间最少？minZ=CijXij Xij=1 i=1,n Xij=1 j=1,n Xij=0或1 人 任务 E J G R 甲 乙 丙 丁 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9指派问题解法匈牙利法l第一步 造0各行各列减其最小元素l第二步 圈0寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉 l0 13 7 l6 6 9l 5 3 2l0 1 0整数规划的求解方法 分枝定界法、隐枚举法、匈牙利法指派问题举例2：l例 甲乙丙丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如

11、何指派不同的人去做不同的工作使效率最高？任务人 时间 A B C D 甲 乙 丙 丁 4 10 7 5 2 7 6 3 3 3 4 4 4 6 6 3指派问题解法匈牙利法l解：l第一步 造0各行各列减其最小元素l 4 10 7 5 -4 0 6 3 1 6 2 1 l Cij=2 7 6 3 -2 0 5 4 1 0 5 3 1 l 3 3 4 4 -3 0 0 1 1 0 0 1l 4 6 6 3 -3 1 3 3 0 1 3 2 l -1 l第二步 圈0寻找不同行不同列的0元素，圈之。所在行和列其它0元素划掉 l第三步 打无的行打，打行上0列打，打列上行打，打行上0列打 指派问题解法匈牙利法（续）l第四步 划线无行、打列划线l第五步 造0直线未覆盖的元素，减去其最小值，交叉点上加最小元素，产生新的0元素，Go to 2l 0 6 2 1 -1 5 1 0 0 4 0 Cij=0 5 3 1 -1 0 4 2 0 3 1 0 0 0 0 1 1 0 1 2 0 2 1 3 2 0 2 3 2 2 2 1 +1 最优解：x13=1,x21=1,x32=1,x44=1 Z=15相关问题：l非标准型的转化maxZ=CijXij minZ=(-Cij)Xij minZ=(M-Cij)Xij=CijXij M是足够大的常数，新问题的最优解就是原问题的最优解