资源描述
Integer Programming 整数规划All Integer Programming 全整数规划Mixed Programming 混合整数规划第4章 整数规划4.1 普通整数规划问题的特点及分枝定界法一、引例 某厂拟用集装箱托运甲、乙两种货物，每箱的体积、分量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)分量(吨/箱)利润(千元/箱)甲乙 2 2 3 3 1 2 14米3 9 吨托运限制建模：解：设 托运甲货物x1箱，乙货物x2箱 Max z=3 x1+2 x2 st.2 x1+3 x214 2 x1+x29 x10，x20，且为整数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)分枝定界法: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=1x22x23x13x14LINDO软件及EXCEL求解：LINDO程序软件：同求解LP模型时的输入及编辑修正正程，在运用 GO 命令求解之前，对整数变量给予阐明。命令格式：GIN 。EXCEL求解：4.2 0-1规划问题及模型一、0-1规划问题的概念 在整数规划问题中，假设变量取值为0或者1，那么为0-1规划问题。0-1变量通常用来表示逻辑性选择的决策。二、0-1变量的运用 例1：某油田在10个有油气构造处要选择假设干个钻探采油，设第j个构造开采时需投资aj元，投产后估计年收益为cj元，假设该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设 xj=10-选择开采第j个构造 -不选择开采第j个构造max z=cjxjj=110ajxj bxj0或1 (j=1,2,-,10)j=110-年总收益-投资额限制1、表示选择性决策2.表示选择性约束 例2：上述例题中，假设在开采中需用电力，处理的方案或由电网供电或由自备的柴油机发电。知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f 度。当运用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：djxj f采用自备柴油机发电：0.3djxj pj=110j=110+(1y1)M+(1y2)My1+y2=1y1,y2=0或1M-非常大的正数3.表示条件性约束例3：假设在开采时还需满足下述条件：a假设开采8号，那么必需同时开采6号；b假设开采5号，那么不许开采3号；c 2 号和4号至少开采一个；d 8 号与7号必需同时开采；e 1号、4号、6号、9号开采时不能超越两个，试表示上述约束条件。a当x8=1x6=1，x60当x8=0 x6=1，x6=0 x8 x6b当x5=1x3=0，x3 1当x5=0 x3=0，x3=1 x5+x3 1c x2+x4 1d x8=x7e x1+x4+x6+x9 24.两组条件满足其中一组假设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或15.分段函数线性表示设有 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或为：三、隐枚举法步骤：化规范形(隐枚举法)：1)目的函数极小化 2)约束条件化成 3)使目的函数系数皆为非负,假设xj系数为负值,那么令xj=1-xj 4)使目的函数按变量系数由小大顺序陈列，约束条件变 量陈列的顺序要与之对应。令一切变量xj=0，计算边境目的函数值z，检查能否满足一切约 束条件，假设满足，即为最优解；否那么，分枝计算。分枝：按变量次序依次令各变量取“1和“0值，计算边境值，然后 检查能否满足一切约束，假设满足，转下步；否那么继续分枝。剪枝：在得到一个可行解后，分枝过程中要进展剪枝任务。(a)对可行解，保管边境值最小的一枝zmin，其他全剪掉；(b)zmin分枝，剪掉；(c)能判别出为无可行解的分枝，剪掉；(d)非上述情况，继续分枝。例：求解下述 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)3)使目的函数系数皆为正：令 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)求解图示：1234567891011z=-10z=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0 x3=1x3=0 x3=1x3=1x5=1x5=0 x5=1x5=0z=-34.3 分配问题及匈牙利算法(Assignment Problem)一、问题的提出和数学模型例：有一份阐明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需求的时间小时如表所示。规定每项任务只能交与其中的一个人完成，每个人只能完成其中的一项任务。问：如何分配，能使所需的总时间最少？甲 乙 丙 丁任务人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 建立模型：设 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个人完成分配问题普通数学模型构造：设有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)二、匈牙利法：根本思想：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为效率矩阵的最优解.证明:以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 m三、步骤 使每行、每列都出现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 +20 8 0 311 0 3 24 5 0 00 11 2 3每列减该列最小元素。寻觅位于不同行不同列的0元素准那么：A从第一行开场，假设只需一个0，那么记0，同时作直线覆盖该列的元素。否那么，转下行；B从第一列开场，假设只需一个0，那么记0，同时作直线覆盖该行的元素。否那么，转以下；C反复A、B，至再找不出这样的0元素，转DD能够出现三种情况：每行均有0元素，那么在有0位置构成最优解中xij=1；多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路，那么沿回路顶点每间隔一个0记，同时作直线覆盖该列的元素；一切0元素均有直线覆盖，但记0的个数任务数时：假想任务数，使得与人数可以匹配,对应的效率设定为0值。当任务数人数时：假想人数，使得与任务数可以匹配,对应的效率设定为0值。2假设目的函数为求max z的处置：如效益 max z=-min(-z)=-min(z)等价于求解 min z =(-aij)xiji=1 j=1 m m4 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 -44.4 整数规划模型的运用例1：在未来四个月中，某制鞋厂必需按时完成下述合同要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋以前的存货和3名工人，每名工人的月薪为1500元，每月可任务160小时正常任务时间。一名工人最多还可有20小时的加班任务时间规定，在加班任务时，每小时需付25元的加班费用。制造一双鞋需耗费4个工时和5元的原料费。在每月的开场，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月消费的产品可用于满足多个月的需求。试用ILP方法确定最正确的消费方案和用工政策。问题分析：需求处理的问题：每月租进、解雇、运用的工人数 每月所需的加班时间 每月在正常时间、加班时间消费的鞋子的数量 每月开场和终了时库存鞋子的数量 费用明细：雇工费、解雇费、用工费、加班费、原料费月初 人数本月雇用本月解雇本月运用用工过程图示：消费过程图示：正常消费加班消费月初库存月末库存交货数量工人数鞋子数建模思绪：每月可用工人0 每月库存鞋子0可用工人数=月初数+租进数-解雇数=月末数月末库存量=月初库存+正常消费+加班消费-交货量 目的函数=总费用 =月薪+雇用费+解雇费+加班费+原料费+库存费例2：某海军部队在三个征兵中心征招新兵。新兵必需送到三个海军训练基地中的一个进展训练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表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中所示。现问，应怎样决策，能使发生的总费用最少？表1途径训练基地 航程海里航线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)总费用例3：仓库位置问题 韩德公司有五个消费番茄酱的工厂，每个工厂的消费才干如表1所示。消费出来的番茄酱可储存在三个废品库中，每个废品库的库存才干为500吨。从各工厂运送一吨产品到各废品库的费用如表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(元/吨)表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 60000建模思绪xi0-1变量，第i厂能否开；yj0-1变量，第j库能否开。0-1规划与运输问题的混合模型。费用：工厂废品库运输费用+开工费；废品库客户运输费用+废品库运营费。例4：资产运作滚动方案 某养殖场豢养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变量表示在某年出卖与否的关系；三年内熊必需出卖且只能出卖一次；每年的销售收入必需能保证需求；每年的剩余资金可移作第二年运用。例5：市政对四个建立工程招标，有三个建筑队招标，标底情况如表示。由于建筑队1力量所限，只能完成其中一个工程，而2和3最多都可承当两项。试确定，如何分配可使总费用最少？工程建筑队1 2 31 2 3 450 46 42 40 51 48 44 47 45 45单位：万元问题分析：可利用匈牙利方法求解分配问题处理 要思索不能做的工程和可以多做工程的处置方式。假设要建立模型，该如何表示？例6：校篮球队教练要确定竞赛的首发阵容。全队共有7名球员，根据技术程度，对每名运发动的控球ball-handing、投篮shooting、蓝板rebounding、防守defense的才干都评出等级分，1分最低，3分最高。各球员的位置position及各项才干的等级分值如表示。五名出场队员应满足下述要求：1至少有3名队员能打后卫，至少有2名队员能打前锋，至少有1名队员能打中锋；2平均控球、投篮、蓝板才干在1.8分以上；32号队员或3号队员必需在首发阵容中。目的是首发阵容中防守才干最强。1 2 3 4 5 6 7运发动位置P 控球B 投篮S 蓝板R 防守DGuard 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 1设 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号要求
展开阅读全文