4整数规划.pptx

1运筹学5讲课教师：赵晋都太原理工大学经济管理学院2第四章 整数规划与分配问题 4.1 一般整数规划问题及分枝定界法4.2 0-1规划问题及模型4.3 分配问题及匈牙利法4.4 整数规划模型的应用 34.1 一般整数规划问题及分枝定界法一、引例4-1 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙 2 2 3 3 1 2 14米3 9 吨托运限制4二、建模 解：设 托运甲货物x1箱，乙货物x2箱 Max z=3 x1+2 x2 st.2 x1+3 x214 2 x1+x29 x10，x20，且为整数524624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6624624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)724624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)8三、分枝定界法:1.解原问题的替代问题L0Max z=3 x1+2 x2 st.2 x1+3 x2 14 2 x1+x2 9 x1 0，x2 0 L0的最优解为(3.25;2.5),不是原问题的可行解。2.分枝与定界 选择X2进行分枝,L0变为二个子问题L1 Max z=3 x1+2 x2 L2 Max z=3 x1+2 x2 st.2 x1+3 x2 14 st.2 x1+3 x2 14 2 x1+x2 9 2 x1+x2 9 x2 2 x2 3 x1 0，x2 0;x1 0，x2 0;x1(3.5;2)Z1=14.5 x2(2.5;3)Z2=13.59L1和L2的最优解仍不是原问题的可行解,继续分枝与定界,因为L1的边界值较大,所以选择L1L11 Max z=3x1+2 x2 L12 Max z=3x1+2x2 st.2 x1+3 x2 14 st.2 x1+3 x2 14 2 x1+x2 9 2 x1+x2 9 x2 2 x2 2 x1 3 x1 4 x1 0，x2 0;x1 0，x2 0;x11(3;2)Z1=13 x12(4;1)Z12=14 x11 和 x12都是原问题的可行解;选择x12103.剪枝确定最优解 L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x22x23x13x14X11 X12 是原问题的可行解,也是最优解。原问题最优解为:X(4;1);max Z=14 124.2 0-1规划问题及模型一、0-1规划问题的概念 在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。0-1变量通常用来表示逻辑性选择的决策。13二、0-1变量的应用 例4-2：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设 xj=10-选择开采第j个构造 -不选择开采第j个构造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年总收益-投资额限制1、表示选择性决策142.表示选择性约束 例4-3：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f 度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：djxj f采用自备柴油机发电：0.3djxj pj=110j=110+(1y1)M+(1y2)My1+y2=1y1,y2=0或1M-非常大的正数153.表示条件性约束例4-4：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2 号和4号至少开采一个；（d）8 号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。16（a）当x8=1x6=1，x60当x8=0 x6=1，x6=0 x8 x6（b）当x5=1x3=0，x3 1当x5=0 x3=0，x3=1 x5+x3 1（c）x2+x4 1（d）x8=x7（e）x1+x4+x6+x9 2174.两组条件满足其中一组若x1 4，则x21，否则(x14)，则x2 3。设 yi=1 0第 i 组条件起作用第 i 组条件不起作用则i=1,2x1 4(1-y1)M x2 1(1-y1)MM充分大正数x1 4(1-y2)M x2 3(1-y2)My1y2=1 y1，y2=0或1185.分段函数线性表示设有 f(xj)=Kj+cjxj 当xj0 0 当xj=0，将min f(xj)表示成线性函数。设 yj=10当xj0当xj=0Min f(xj)=kjyj+cjxjst.xjyjM xj0,yj=0或1M非常大的正常数则f(xj)=kjyj+cjxj xjyjM yjxjM xj0,yj=0或1或为：19三、隐枚举法步骤：化标准形(隐枚举法)：1)目标函数极小化 2)约束条件化成 3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj 4)使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。(a)对可行解，保留边界值最小的一枝zmin，其余全剪掉；(b)zmin分枝，剪掉；(c)能判断出为无可行解的分枝，剪掉；(d)非上述情况，继续分枝。20例4-5：求解下述 0-1规划问题：Max z=8x1+2x2-4x3-7x4-5x5st.3x1+3x2+x3+2x4+3x5 4 5x1+3x2-2x3-x4+x5 4 xj=0或1 (j=1,2,3,4,5)1)目标函数极小化:min z=-8x1-2x2+4x3+7x4+5x5 化标准形：2)约束条件：-3x1-3x2-x3-2x4-3x5-4 -5x1-3x2+2x3+x4-x5-4xj=0或1 (j=1,2,3,4,5)213)使目标函数系数皆为正：令 x1=1-x1，x2=1-x2 min z=-8+8 x1-2+2 x2+4x3+7x4+5x5st.-3+3 x1-3+3 x2-x3-2x4-3x5-4 -5+5 x1-3+3 x2+2x3+x4-x5-4x1,x2,xj=0或1 (j=3,4,5)4)变量按顺序排列：min z=2 x2+4x3+5x5+7x4+8 x1-10st.3 x2-x3-3x5-2x4+3 x1 23 x2+2x3-x5+x4+5 x1 4x1,x2,xj=0或1 (j=3,4,5)22求解图示：1234567891011z=-10z=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0 x3=1x3=0 x3=1x3=1x5=1x5=0 x5=1x5=0z=-3234.3 分配问题及匈牙利算法 一、问题的提出和数学模型例4-6 有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 24建立模型：设 xij=10译英文：x11+x12+x13+x14=1译日文：x21+x22+x23+x24=1译德文：x31+x32+x33+x34=1译俄文：x41+x42+x43+x44=1甲：x11+x21+x31+x41=1乙：x12+x22+x32+x42=1丙：x13+x23+x33+x43=1丁：x14+x24+x34+x44=1xij=0或1 (i=1,2,3,4;j=1,2,3,4)Min z=aijxij(aij-效率)i=1j=14 4若第i项工作交与第j个人完成若第i项工作不交与第j个人完成25分配问题一般数学模型结构：设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为 aij。规定每项工作只能交与其中的一个人完成，而每个人只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？Min z=aijxijst.xij=1xij=1i=1j=1j=1i=1m mm mxij=0或1 (i=1,2,m;j=1,2,m)(i=1,2,m)(j=1,2,m)26二、匈牙利法：基本思想：4 (0)5 6 5 4 (0)5 7 6 3 (0)(0)5 6 2 克尼格定理(konig)：如果从效率矩阵aij的每一行元素中分别减去(或加上)一个常数ui,从每列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵bij,其中bij=aij-ui-vj,则以bij为效率矩阵的最优解等价于以aij为效率矩阵的最优解.27证明:以aij为效率矩阵的目标函数值：z0=aijxij以bij为效率矩阵的目标函数值：z=bijxij m mi=1j=1i=1j=1 m mbij=aij-ui-vj z=(aij-ui-vj)xij=aijxij-uixij-vjxij=z0-uixij-vjxijm mm mm mm m m m =z0-ui-vj=z0-constantmmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1m m28三、步骤 使每行、每列都出现0元素方法每行减该行最小元素；2 10 9 715 4 14 813 14 16 114 15 13 9-2-4-11-4min0 8 7 511 0 10 42 3 5 00 11 9 5 min -0 -0 -5 -00 8 2 511 0 5 42 3 0 00 11 4 5-2-2-2+2 [phone] 11 2 3每列减该列最小元素。29寻找位于不同行不同列的0元素准则：A）从第一行开始，若只有一个0，则记（0），同时作直线覆盖该列的元素。否则，转下行；B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；C）重复A）、B）至再找不出这样的0元素，转D）D）可能出现三种情况：每行均有（0）元素，则在有（0）位置构成最优解中xij=1；多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路则沿回路顶点每间隔一个0记（0），同时作直线覆盖该列的元素；所有0元素均有直线覆盖，但记（0）的个数工作数时：假想工作数，使得与人数能够匹配,对应的效率设定为0值。当工作数人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。2若目标函数为求max z的处理：（如效益）max z=-min(-z)=-min(z)等价于求解 min z =(-aij)xiji=1 j=1 m m324 3 5 6 73 6 4 5 64 7 5 2 48 9 6 5 3甲 乙 丙 丁 戊A B C DE0 0 0 0 0ABCDE甲 乙 丙 丁 戊4 7 6 5 8 5 4 64 8 6 55 9 2 73 4 8 70 0 0 0 0-2 -8 -7 -6 -5 -7 -6 -4 -3 -6 -4 -3 -4 -9 -5 -433例4-7 机器安装选点问题 地点机器1234机器总数123410324 9413851576261111需求量111134例4-7的匈牙利解法(原理)35例4-8 有四项任务，分别由四个人去完成。他们每个人完成不同的工作所需时间如下表所示，求使总工作时间最少的任务安排。M J1234甲乙丙丁1055298437764875536第一步：求初始最优解检验是否找到最优解：在每行每列都有零元素后，要找出N个位于不同行不同列的零元素，如果能找到，其对应的位置即构成最优指派(如何尽快找到N个不同行不同列的零元素)37如何找到能覆盖所有零元素的最少直线？1.从第一行（列）开始，若该行（列）只有一个零元素，则给它标上圈，然后划去所在列（行）的其它零元素，标上，表明该列所代表的任务已经分派完，不必再考虑其它人了。若该行（列）有两个或两个以上零元素或者没有零元素（已标号的不计），则进行下一行（列），直到最后一行（列）。2.同样原则对列（行）进行标号383.重复（1），（2），直到下列三种情况之一出现为止：(1)若按（1）（2）标号已不能进行，但仍存在未标号的零元素，则可选其中任一个标上，并将其同行同列的其它零元素标上，返回1(2)若元素数目m等于矩阵的阶数n,则说明已经找到最优解。(3)若 元素的数目m小于矩阵的阶数n，则转入4。4.在未标 的行上标，然后在标有的行中，对标有的列标;在标有的列中，对标有 的行标，重复直到无法标为止。5.对所有标的列和未标的行画线，即得到能覆盖所有零元素的最少直线39第二步：找划去零的最少直线40第三步：找调整量，并调整 调整41回到第一步：圈零得新最优解最小的总工作时间：z=7+5+5+3=20。该问题有多个最优解，请求出其它的最优解。42工作分派问题的多重最优解：当分派问题的系数矩阵，经过变换得到了同行和同列都有两个或者两个以上的零元素时，则出现多重最优解可以任选一行（列）中某一个零元素，再划去同行（列）的其它零元素，这时会出现多重最优解见上述三种情况中的第一种情况43例4-9 求最大效率问题某港务局装卸队所属五个班组进行五条作业线的调度，已经某班组完成某作业的效率值如下，求最大效率的调度方案。作业线班组12345ABCDE400435505495450315295370310320220240320250310120220200180190145160165135100求最大值的匈牙利法44求最大值的工作指派问题45求效率最高的调度方案首先将效率最大问题转化为时间最小问题：用一个不比指派矩阵中最大元素小的数减去指派矩阵的所有元素。即令则有46问题转化，取M=50547用匈牙利法求最优解484950515253最大效率=145+220+370+495+310=1540544.4 整数规划模型的应用 例4-10：在未来四个月中，某制鞋厂必须按时完成下述合同要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋（以前的存货）和3名工人，每名工人的月薪为1500元，每月可工作160小时（正常工作时间）。一名工人最多还可有20小时的加班工作时间（规定），在加班工作时，每小时需付25元的加班费用。制作一双鞋需耗费4个工时和5元的原料费。在每月的开始，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月生产的产品可用于满足多个月的需求。试用ILP方法确定最佳的生产计划和用工政策。55问题分析：需要解决的问题：每月租进、解雇、使用的工人数 每月所需的加班时间 每月在正常时间、加班时间生产的鞋子的数量 每月开始和结束时库存鞋子的数量 费用明细：雇工费、解雇费、用工费、加班费、原料费56月初 人数本月雇用本月解雇本月使用用工过程图示：生产过程图示：正常生产加班生产月初库存月末库存交货数量工人数鞋子数57建模思路：每月可用工人0 每月库存鞋子0可用工人数=月初数+租进数-解雇数=月末数月末库存量=月初库存+正常生产+加班生产-交货量 目标函数=总费用 =月薪+雇用费+解雇费+加班费+原料费+库存费58例4-11 某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练基地中的一个进行训练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表1所示（单位：元）。每年在中心1征招1000名士兵，中心2征召600名，中心3征召700名。基地1可训练1000名，基地2可训练800名，基地3可训练700名。fromtoBase1 Base2 Base3 Center1 Center2 Center3 240 200 300 300 400 220 300 400 250 新兵受训后，要送到海军部队。运送时可采用小船或大船两种工具，共有7条小船和3条大船可供使用。若使用小船，则每条船要花费5000元加上每海里2元的费用；使用大船要花费10000元加上每海里3元的费用。一条小船可运送200人，沿途最多可经过2个训练基地；一条大船可运送500人，最多可经过3个训练基地。可能的航线如表2中所示。现问，应怎样决策，能使发生的总费用最少？表159途径训练基地 航程（海里）航线1234567 B1B 370 B12B 515 B23B 665 B2B 460 B3B 600 B13B 640B123B 720表2需要解决的问题：(1)Center iBase j运送的人数(2)Base j 实际训练人数(3)第i航线运送第j基地人数(4)第i航线使用小船数量(5)第i航线使用大船数量(6)征兵中心至训练基地运送费用(7)训练基地至海军部队运送费用(8)总费用60例4-12仓库位置问题 韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表1所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨产品到各成品库的费用如表2所示。由于某些因素，公司销售看淡，现只有四家客户，其需求量如表3所示。从各成品库运送成品到各客户的需求地的单位费用如表4所示。每个工厂和每个成品库运营的年固定费用如表5所示。公司想确定关闭那些工厂和仓库，会使总费用最低。表1 生产能力工 厂 1 2 3 4 5能力(吨)300 200 300 200 400表3 客户需求客 户 1 2 3 4需求(吨)200 300 150 250表2 工厂成品库运费表工厂仓库成品库1 成品库2 成品库312345800 1000 1200 700 500 700 800 600 500 500 600 700 700 600 500(元/吨)61表4 成品库客户运输费用（元/吨）成品库客户成品库1 成品库2 成品库3 1 2 3 440 80 90 50 70 40 60 80 80 30 50 60表5 年运营固定费用（元）工厂1 工厂2 工厂3 工厂4 工厂5 成品库1 成品库2 成品库335000 45000 40000 42000 40000 40000 20000 6000062建模思路xi0-1变量，第i厂是否开；yj0-1变量，第j库是否开。0-1规划与运输问题的混合模型。费用：工厂成品库运输费用+开工费；成品库客户运输费用+成品库运营费。63例4-13资产运作滚动计划 某养殖场饲养6头黑熊（资产），在未来三年内对该6头黑熊的预期收入如表中所示（以千元计）。为维持养殖场的正常的资金周转，该厂必须在第一年获取20000元的收入，第二年获取30000元的收入，第三年获取35000元的收入。试确定，该养殖场应采取怎样的销售计划，可使三年中获得的总收入最大？1 2 3 4 5 6year1 year2 year315 20 24 16 18 21 22 30 36 10 20 30 17 19 22 19 25 29黑熊建模提示：利用 0-1变量表示在某年出售与否的关系；三年内熊必须出售且只能出售一次；每年的销售收入必须能保证需求；每年的剩余资金可移作第二年使用。64例4-14 市政对四个建设项目招标，有三个建筑队投标，标底情况如表示。由于建筑队1力量所限，只能完成其中一个项目，而2和3最多都可承担两项。试确定，如何分配可使总费用最少？项目建筑队1 2 31 2 3 450 46 42 40 51 48 44 47 45 45单位：万元问题分析：可利用匈牙利方法求解分配问题解决 要考虑不能做的项目和可以多做项目的处理方式。如果要建立模型，该如何表示？65例4-15 校篮球队教练要确定比赛的首发阵容。全队共有7名球员，根据技术水平，对每名运动员的控球（ball-handing）、投篮（shooting）、蓝板（rebounding）、防守（defense）的能力都评出等级分，1分最低，3分最高。各球员的位置（position）及各项能力的等级分值如表示。五名出场队员应满足下述要求：（1）至少有3名队员能打后卫，至少有2名队员能打前锋，至少有1名队员能打中锋；（2）平均控球、投篮、蓝板能力在1.8分以上；（3）2号队员或3号队员必须在首发阵容中。目标是首发阵容中防守能力最强。1 2 3 4 5 6 7运动员位置（P）控球（B）投篮（S）蓝板（R）防守（D）Guard Center G/Forward F/C G/F F/C G/F3 3 1 3 2 1 3 2 2 3 2 2 1 3 3 1 1 3 1 2 3 1 2 3 3 2 2 166设 xj=1 0第j号队员入选第j号队员没入选Max z=djxj 防守能力总分j=17xj=5 上场队员数 j=17bjxj 9 控球能力总分sjxj 9 投篮能力总分rjxj 9 蓝板能力总分x1+x3+x5+x7 3 后卫人数x3+x4+x5+x6+x7 2 前锋人数x2+x4+x6 1 中锋人数j=1j=1j=1777xj=0或1 (j=1,7)St.x2+x3 12号、3号要求