整数规划PPT演示文稿

运筹学5讲课教师：赵晋都太原理工大学经济管理学院第四章整数规划与分配问题4.1一般整数规划问题及分枝定界法4.20-1规划问题及模型4.3分配问题及匈牙利法4.4整数规划模型的应用4.1一般整数规划问题及分枝定界法一、引例4-1某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙22331214米39吨托运限制二、建模解：设托运甲货物x1箱，乙货物x2箱Maxz=3x1+2x2st.2x1+3x2142x1+x29x10，x20，且为整数24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=624624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)三、分枝定界法:1.解原问题的替代问题L0Maxz=3x1+2x2st.2x1+3x2142x1+x29x10，x20L0的最优解为(3.25;2.5),不是原问题的可行解。2.分枝与定界选择X2进行分枝,L0变为二个子问题L1Maxz=3x1+2x2L2Maxz=3x1+2x2st.2x1+3x214st.2x1+3x2142x1+x292x1+x29x22x23x10，x20;x10，x20;x1(3.5;2)Z1=14.5x2(2.5;3)Z2=13.5L1和L2的最优解仍不是原问题的可行解,继续分枝与定界,因为L1的边界值较大,所以选择L1L11Maxz=3x1+2x2L12Maxz=3x1+2x2st.2x1+3x214st.2x1+3x2142x1+x292x1+x29x22x22x13x14x10，x20;x10，x20;x11(3;2)Z1=13x12(4;1)Z12=14x11和x12都是原问题的可行解;选择x123.剪枝确定最优解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=1x2≤2x2≥3x1≤3x1≥4XX12是原问题的可行解,也是最优解。∴原问题最优解为:X(4;1);maxZ=144.20-1规划问题及模型一、0-1规划问题的概念在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。0-1变量通常用来表示逻辑性选择的决策。二、0-1变量的应用例4-2：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制1、表示选择性决策2.表示选择性约束例4-3：上述例题中，如果在开采中需用电力，解决的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数3.表示条件性约束例4-4：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2号和4号至少开采一个；（d）8号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。（a）当x8=1x6=1，x6≠0当x8=0x6=1，x6=0∴x8x6　（b）当x5=1x3=0，x3≠1当x5=0x3=0，x3=1∴　x5+x31（c）x2+x41（d）x8=x7（e）x1+x4+x6+x924.两组条件满足其中一组若x14，则x21，否则(x14)，则x23。设yi=10第i组条件起作用第i组条件不起作用则i=1,2x14＋(1-y1)Mx21－(1-y1)MM——充分大正数x14－(1-y2)Mx23＋(1-y2)My1＋y2=1y1，y2=0或15.分段函数线性表示设有f(xj)=Kj+cjxj当xj>00当xj=0，将minf(xj)表示成线性函数。设yj=10当xj>0当xj=0Minf(xj)=kjyj+cjxjst.xjyjMxj0,yj=0或1M—非常大的正常数则f(xj)=kjyj+cjxjxjyjMyjxjMxj0,yj=0或1或为：三、隐枚举法步骤：①化 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形(隐枚举法)：1)目标函数极小化2)约束条件化成3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj4)使目标函数按变量系数由小→大顺序排列，约束条件变量排列的顺序要与之对应。②令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约束条件，若满足，即为最优解；否则，分枝计算。③分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后检查是否满足所有约束，若满足，转下步；否则继续分枝。④剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。(a)对可行解，保留边界值最小的一枝zmin，其余全剪掉；(b)>zmin分枝，剪掉；(c)能判断出为无可行解的分枝，剪掉；(d)非上述情况，继续分枝。例4-5：求解下述0-1规划问题：Maxz=8x1+2x2-4x3-7x4-5x5st.3x1+3x2+x3+2x4+3x545x1+3x2-2x3-x4+x54xj=0或1(j=1,2,3,4,5)1)目标函数极小化:minz=-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)3)使目标函数系数皆为正：令x1=1-x1，x2=1-x2minz=-8+8x1-2+2x2+4x3+7x4+5x5st.-3+3x1-3+3x2-x3-2x4-3x5-4-5+5x1-3+3x2+2x3+x4-x5-4x1,x2,xj=0或1(j=3,4,5)4)变量按顺序排列：minz=2x2+4x3+5x5+7x4+8x1-10st.3x2-x3-3x5-2x4+3x123x2+2x3-x5+x4+5x14x1,x2,xj=0或1(j=3,4,5)求解图示：1234567891011z=-10z=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z=-3√×××××4.3分配问题及匈牙利算法一、问题的提出和数学模型例4-6有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文2109715414813141611415139建立模型：设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)Minz=aijxij(aij---效率)i=1j=144若第i项工作交与第j个人完成若第i项工作不交与第j个人完成分配问题一般数学模型结构：设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为aij。规定每项工作只能交与其中的一个人完成，而每个人只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？Minz=aijxijst.xij=1xij=1i=1j=1j=1i=1mmmmxij=0或1(i=1,2,···,m;j=1,2,···,m)(i=1,2,···,m)(j=1,2,···,m)二、匈牙利法：基本思想：4(0)5654(0)5763(0)(0)562克尼格定理(konig)：如果从效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui,从每列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵[bij],其中bij=aij-ui-vj,则以[bij]为效率矩阵的最优解等价于以[aij]为效率矩阵的最优解.证明:以[aij]为效率矩阵的目标函数值：z0=aijxij以[bij]为效率矩阵的目标函数值：z=bijxijmmi=1j=1i=1j=1mm∵　bij=aij-ui-vj∴z=(aij-ui-vj)xij=aijxij-uixij-vjxij=z0-uixij-vjxijmmmmmmmmmm=z0-ui-vj=z0-constantmmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm三、步骤⑴使每行、每列都出现0元素方法：每行减该行最小元素；2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2-2+2+2080311032450001123每列减该列最小元素。⑵寻找位于不同行不同列的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．若目标函数为求maxz的处理：（如效益）∵maxz=-min(-z)=-min(z)∴　等价于求解minz=∑∑(-aij)xiji=1j=1mm43567364564752489653甲乙丙丁戊ABCDE00000ABCDE甲乙丙丁戊4765854648655927348700000-2-8-7-6-5-7-6-4-3-6-4-3-4-9-5-4例4-7机器安装选点问题地点机器1234机器总数1234103249413851576261111需求量1111例4-7的匈牙利解法(原理)例4-8有四项任务，分别由四个人去完成。他们每个人完成不同的工作所需时间如下表所示，求使总工作时间最少的任务安排。MJ1234甲乙丙丁10552984377648755第一步：求初始最优解检验是否找到最优解：在每行每列都有零元素后，要找出N个位于不同行不同列的零元素，如果能找到，其对应的位置即构成最优指派(如何尽快找到N个不同行不同列的零元素)如何找到能覆盖所有零元素的最少直线？1.从第一行（列）开始，若该行（列）只有一个零元素，则给它标上圈◎，然后划去◎所在列（行）的其它零元素，标上×，表明该列所代表的任务已经分派完，不必再考虑其它人了。若该行（列）有两个或两个以上零元素或者没有零元素（已标号的不计），则进行下一行（列），直到最后一行（列）。2.同样原则对列（行）进行标号3.重复（1），（2），直到下列三种情况之一出现为止：(1)若按（1）（2）标号已不能进行，但仍存在未标号的零元素，则可选其中任一个标上◎，并将其同行同列的其它零元素标上×，返回1(2)若◎元素数目m等于矩阵的阶数n,则说明已经找到最优解。(3)若◎元素的数目m小于矩阵的阶数n，则转入4。4.在未标◎的行上标√，然后在标有√的行中，对标有×的列标√;在标有√的列中，对标有◎的行标√，重复直到无法标√为止。5.对所有标√的列和未标√的行画线，即得到能覆盖所有零元素的最少直线第二步：找划去零的最少直线第三步：找调整量，并调整调整回到第一步：圈零得新最优解最小的总工作时间：z=7+5+5+3=20。该问题有多个最优解，请求出其它的最优解。工作分派问题的多重最优解：当分派问题的系数矩阵，经过变换得到了同行和同列都有两个或者两个以上的零元素时，则出现多重最优解可以任选一行（列）中某一个零元素，再划去同行（列）的其它零元素，这时会出现多重最优解见上述三种情况中的第一种情况例4-9求最大效率问题某港务局装卸队所属五个班组进行五条作业线的调度，已经某班组完成某作业的效率值如下，求最大效率的调度方案。求最大值的匈牙利法作业线班组12345ABCDE400435505495450315295370310320220240320250310120220200180190145160165135100求最大值的工作指派问题求效率最高的调度方案首先将效率最大问题转化为时间最小问题：用一个不比指派矩阵中最大元素小的数减去指派矩阵的所有元素。即令则有问题转化，取M=505用匈牙利法求最优解最大效率=145+220+370+495+310=15404.4整数规划模型的应用例4-10：在未来四个月中，某制鞋厂必须按时完成下述 合同 劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载 要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋（以前的存货）和3名工人，每名工人的月薪为1500元，每月可工作160小时（正常工作时间）。一名工人最多还可有20小时的加班工作时间（规定），在加班工作时，每小时需付25元的加班费用。制作一双鞋需耗费4个工时和5元的原料费。在每月的开始，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月生产的产品可用于满足多个月的需求。试用ILP方法确定最佳的生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 和用工政策。问题分析：需要解决的问题：每月租进、解雇、使用的工人数每月所需的加班时间每月在正常时间、加班时间生产的鞋子的数量每月开始和结束时库存鞋子的数量费用明细：雇工费、解雇费、用工费、加班费、原料费月初人数本月雇用本月解雇本月使用用工过程图示：生产过程图示：正常生产加班生产月初库存月末库存交货数量工人数鞋子数建模思路：每月可用工人≥0每月库存鞋子≥0可用工人数=月初数+租进数-解雇数=月末数月末库存量=月初库存+正常生产+加班生产-交货量目标函数=总费用=月薪+雇用费+解雇费+加班费+原料费+库存费例4-11某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练基地中的一个进行训练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表1所示（单位：元）。每年在中心1征招1000名士兵，中心2征召600名，中心3征召700名。基地1可训练1000名，基地2可训练800名，基地3可训练700名。fromtoBase1Base2Base3Center1Center2Center3240200300300400220300400250新兵受训后，要送到海军部队。运送时可采用小船或大船两种工具，共有7条小船和3条大船可供使用。若使用小船，则每条船要花费5000元加上每海里2元的费用；使用大船要花费10000元加上每海里3元的费用。一条小船可运送200人，沿途最多可经过2个训练基地；一条大船可运送500人，最多可经过3个训练基地。可能的航线如表2中所示。现问，应怎样决策，能使发生的总费用最少？表1途径训练基地航程（海里）航线1234567B—1—B370B—1—2—B515B—2—3—B665B—2—B460B—3—B600B—1—3—B640B—1—2—3—B720表2需要解决的问题：(1)Centeri→Basej运送的人数(2)Basej实际训练人数(3)第i航线运送第j基地人数(4)第i航线使用小船数量(5)第i航线使用大船数量(6)征兵中心至训练基地运送费用(7)训练基地至海军部队运送费用(8)总费用例4-12仓库位置问题韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表1所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨产品到各成品库的费用如表2所示。由于某些因素，公司销售看淡，现只有四家客户，其需求量如表3所示。从各成品库运送成品到各客户的需求地的单位费用如表4所示。每个工厂和每个成品库运营的年固定费用如表5所示。公司想确定关闭那些工厂和仓库，会使总费用最低。表1生产能力工厂12345能力(吨)300200300200400表3客户需求客户1234需求(吨)200300150250表2工厂—成品库运费表工厂仓库成品库1成品库2成品库31234580010001200700500700800600500500600700700600500(元/吨)表4成品库—客户运输费用（元/吨）成品库客户成品库1成品库2成品库31234408090507040608080305060表5年运营固定费用（元）工厂1工厂2工厂3工厂4工厂5成品库1成品库2成品库33500045000400004200040000400002000060000建模思路xi——0-1变量，第i厂是否开；yj——0-1变量，第j库是否开。0-1规划与运输问题的混合模型。费用：工厂——成品库运输费用+开工费；成品库——客户运输费用+成品库运营费。例4-13资产运作滚动计划某养殖场饲养6头黑熊（资产），在未来三年内对该6头黑熊的预期收入如表中所示（以千元计）。为维持养殖场的正常的资金周转，该厂必须在第一年获取20000元的收入，第二年获取30000元的收入，第三年获取35000元的收入。试确定，该养殖场应采取怎样的销售计划，可使三年中获得的总收入最大？123456year1year2year3152024161821223036102030171922192529黑熊建模提示：⑴利用0-1变量表示在某年出售与否的关系；⑵三年内熊必须出售且只能出售一次；⑶每年的销售收入必须能保证需求；⑷每年的剩余资金可移作第二年使用。例4-14市政对四个建设项目招标，有三个建筑队投标，标底情况如表示。由于建筑队1力量所限，只能完成其中一个项目，而2和3最多都可承担两项。试确定，如何分配可使总费用最少？项目建筑队123123450464240514844—474545单位：万元问题分析：⑴可利用匈牙利方法求解分配问题解决⑵要考虑不能做的项目和可以多做项目的处理方式。☆如果要建立模型，该如何表示？例4-15校篮球队教练要确定比赛的首发阵容。全队共有7名球员，根据技术水平，对每名运动员的控球（ball-handing）、投篮（shooting）、蓝板（rebounding）、防守（defense）的能力都评出等级分，1分最低，3分最高。各球员的位置（position）及各项能力的等级分值如表示。五名出场队员应满足下述要求：（1）至少有3名队员能打后卫，至少有2名队员能打前锋，至少有1名队员能打中锋；（2）平均控球、投篮、蓝板能力在1.8分以上；（3）2号队员或3号队员必须在首发阵容中。目标是首发阵容中防守能力最强。1234567运动员位置（P）控球（B）投篮（S）蓝板（R）防守（D）GuardCenterG/ForwardF/CG/FF/CG/F3313213223221331131231233221设xj=10——第j号队员入选——第j号队员没入选Maxz=∑djxj——防守能力总分j=17∑xj=5——上场队员数j=17∑bjxj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号要求