《整数规划学时》PPT课件.ppt

《《整数规划学时》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《整数规划学时》PPT课件.ppt（43页珍藏版）》请在三一办公上搜索。

1、2006/3,-第4章 整数规划-,-1-,WELCOME TO MY LECTURE!,2006/3,-第4章 整数规划-,-2-,第四章 整数规划（6学时）,ExcelORM1.0下载地址:密码:123456,课时：6学时1 整数规划的特点及应用2 分配问题与匈牙利法3 分支定界法4 割平面法5 应用案例,2006/3,-第4章 整数规划-,-3-,4.1 一般整数规划问题的特点及分枝定界法,一、引例,某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？,货物,体积(米3/箱),重量(吨/箱),利润(千元/箱),甲,乙,2 2

2、 3,3 1 2,14米3 9 吨,托运限制,2006/3,-第4章 整数规划-,-4-,建模：,解：设 托运甲货物x1箱，乙货物x2箱,Max z=3 x1+2 x2 st.2 x1+3 x214 2 x1+x29 x10，x20，且为整数,2006/3,-第4章 整数规划-,-5-,2,4,6,2,4,(3.25,2.5),x1,x2,2x1+3x2=14,2x1+x2=9,3x1+2x2=6,2006/3,-第4章 整数规划-,-6-,2,4,6,2,4,(3.5,2),x1,x2,2x1+3x2=14,2x1+x2=9,3x1+2x2=6,(2.5,3),2006/3,-第4章 整数规

3、划-,-7-,2,4,6,2,4,(4,1),x1,x2,2x1+3x2=14,2x1+x2=9,3x1+2x2=6,(2.5,3),(3,2),2006/3,-第4章 整数规划-,-8-,分枝定界法:,L0：z0=14.75,x1=3.25，x2=2.5,L1：z1=14.5,L2：z2=13.5,L3：z3=13,L4：z4=14,x1=3.5，x2=2,x1=2.5，x2=3,x1=3，x2=2,x1=4，x2=1,x22,x23,x13,x14,2006/3,-第4章 整数规划-,-9-,LINDO软件及EXCEL求解：,LINDO程序软件：同求解LP模型时的输入及编辑修改过程，在使用

4、 GO 命令求解之前，对整数变量给予说明。命令格式：GIN。,EXCEL求解：,2006/3,-第4章 整数规划-,-10-,4.2 0-1规划问题及模型,一、0-1规划问题的概念,在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。,0-1变量通常用来表示逻辑性选择的决策。,2006/3,-第4章 整数规划-,-11-,二、0-1变量的应用,例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？,设 xj=,10,-选择开采第j个构造-不选择开采第j个构造,max

5、z=cjxj,j=1,10,ajxj b,xj0或1(j=1,2,-,10),j=1,10,-年总收益,-投资额限制,1、表示选择性决策,2006/3,-第4章 整数规划-,-12-,2.表示选择性约束,例2：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f 度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。,采用电网供电：djxj f,采用自备柴油机发电：0.3djxj p,j=1,10,j=1,10,+(1y1)M,+(1y2)M,y1+

6、y2=1,y1,y2=0或1,M-非常大的正数,2006/3,-第4章 整数规划-,-13-,3.表示条件性约束,例3：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2 号和4号至少开采一个；（d）8 号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。,2006/3,-第4章 整数规划-,-14-,（a）当x8=1,x6=1，x60,当x8=0,x6=1，x6=0,x8 x6,（b）当x5=1,x3=0，x3 1,当x5=0,x3=0，x3=1,x5+x3 1,（c）x2+x4 1,（d）x8=

7、x7,（e）x1+x4+x6+x9 2,2006/3,-第4章 整数规划-,-15-,4.两组条件满足其中一组,若x1 4，则x21，否则(x14)，则x2 3。,设 yi=,1 0,第 i 组条件起作用,第 i 组条件不起作用,则,i=1,2,x1 4(1-y1)M x2 1(1-y1)M,M充分大正数,x1 4(1-y2)M x2 3(1-y2)M,y1y2=1 y1，y2=0或1,2006/3,-第4章 整数规划-,-16-,5.分段函数线性表示,设有 f(xj)=,Kj+cjxj 当xj0 0 当xj=0，,将min f(xj)表示成线性函数。,设 yj=,10,当xj0当xj=0,M

8、in f(xj)=kjyj+cjxjst.xjyjM xj0,yj=0或1,M非常大的正常数,则,f(xj)=kjyj+cjxj xjyjM yjxjM xj0,yj=0或1,或为：,2006/3,-第4章 整数规划-,-17-,三、隐枚举法,步骤：,化标准形(隐枚举法)：1)目标函数极小化 2)约束条件化成 3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj 4)使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。,令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约 束条件，若满足，即为最优解；否则，分枝计算。,分枝：按变量次序依次令各变量取“1”

9、和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。,剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。(a)对可行解，保留边界值最小的一枝zmin，其余全剪掉；(b)zmin分枝，剪掉；(c)能判断出为无可行解的分枝，剪掉；(d)非上述情况，继续分枝。,2006/3,-第4章 整数规划-,-18-,例：求解下述 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+4x

10、3+7x4+5x5,化标准形：,2)约束条件：,-3x1-3x2-x3-2x4-3x5-4,-5x1-3x2+2x3+x4-x5-4,xj=0或1(j=1,2,3,4,5),2006/3,-第4章 整数规划-,-19-,3)使目标函数系数皆为正：,令 x1=1-x1，x2=1-x2,min z=-8+8 x1-2+2 x2+4x3+7x4+5x5,st.-3+3 x1-3+3 x2-x3-2x4-3x5-4,-5+5 x1-3+3 x2+2x3+x4-x5-4,x1,x2,xj=0或1(j=3,4,5),4)变量按顺序排列：,min z=2 x2+4x3+5x5+7x4+8 x1-10,st.

11、3 x2-x3-3x5-2x4+3 x1 2,3 x2+2x3-x5+x4+5 x1 4,x1,x2,xj=0或1(j=3,4,5),2006/3,-第4章 整数规划-,-20-,求解图示：,1,2,3,4,5,6,7,8,9,10,11,z=-10,z=-8,z=-4,z=-6,z=-5,z=-1,z=1,z=-5,z=-3,z=-6,x2=1,x2=0,x3=1,x3=0,x3=1,x3=1,x5=1,x5=0,x5=1,x5=0,z=-3,2006/3,-第4章 整数规划-,-21-,4.4 分配问题及匈牙利算法(Assignment Problem),一、问题的提出和数学模型,例：有一

12、份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？,甲 乙 丙 丁,工作,人,译英文译日文译德文译俄文,2 10 9 715 4 14 813 14 16 114 15 13 9,2006/3,-第4章 整数规划-,-22-,建立模型：,设 xij=,1,0,译英文：,x11+x12+x13+x14=1,译日文：,x21+x22+x23+x24=1,译德文：,x31+x32+x33+x34=1,译俄文

13、：,x41+x42+x43+x44=1,甲：,x11+x21+x31+x41=1,乙：,x12+x22+x32+x42=1,丙：,x13+x23+x33+x43=1,丁：,x14+x24+x34+x44=1,xij=0或1(i=1,2,3,4;j=1,2,3,4),Min z=aijxij(aij-效率),i=1j=1,4 4,若第i项工作交与第j个人完成,若第i项工作不交与第j个人完成,2006/3,-第4章 整数规划-,-23-,分配问题一般数学模型结构：,设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为 aij。规定每项工作只能交与其中的一个人完成，而每个人

14、只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？,Min z=aijxij,st.xij=1,xij=1,i=1j=1,j=1,i=1,m m,m,m,xij=0或1(i=1,2,m;j=1,2,m),(i=1,2,m),(j=1,2,m),2006/3,-第4章 整数规划-,-24-,二、匈牙利法：,基本思想：,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为效

15、率矩阵的最优解等价于以aij为效率矩阵的最优解.,2006/3,-第4章 整数规划-,-25-,证明:,以aij为效率矩阵的目标函数值：z0=aijxij,以bij为效率矩阵的目标函数值：z=bijxij,m m,i=1j=1,i=1j=1,m m,bij=aij-ui-vj,z=(aij-ui-vj)xij,=aijxij-uixij-vjxij,=z0-uixij-vjxij,m m,m m,m m,m,m,m,m,=z0-ui-vj,=z0-constant,m,m,i=1j=1,i=1j=1,i=1j=1,i=1j=1,i=1,j=1,j=1,i=1,i=1,j=1,m m,2006/

16、3,-第4章 整数规划-,-26-,三、步骤,使每行、每列都出现0元素,方法：每行减该行最小元素；,2 10 9 7,15 4 14 8,13 14 16 11,4 15 13 9,-2-4-11-4,min,0 8 7 5,11 0 10 4,2 3 5 0,0 11 9 5,min-0-0-5-0,0 8 2 5,11 0 5 4,2 3 0 0,0 11 4 5,-2-2-2,+2+2,0 8 0 3,11 0 3 2,4 5 0 0,0 11 2 3,每列减该列最小元素。,2006/3,-第4章 整数规划-,-27-,寻找位于不同行不同列的0元素,准则：,A）从第一行开始，若只有一个0

17、，则记（0），同时作直线覆盖该列的元素。否则，转下行；,B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；,C）重复A）、B），至再找不出这样的0元素，转D）,D）可能出现三种情况：每行均有（0）元素，则在有（0）位置构成最优解中xij=1；,多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路，则沿回路顶点每间隔一个0记（），同时作直线覆盖该列的元素；,所有0元素均有直线覆盖，但记（0）的个数m个，转。,2006/3,-第4章 整数规划-,-28-,0 0,0 0,0 0,迭代，寻找新的位于不同行不同列的0元素,a）从未被直线覆盖的元素中找出一个最小

18、的元素amin；b）对行，若无直线覆盖，则-amin；c）对列，若有直线覆盖，则+amin；,转。,2006/3,-第4章 整数规划-,-29-,特殊问题处理：,1人数与工作数不等的处理：,当人数工作数时：假想工作数，使得与人数能够匹配,对应的效率设定为0值。,当工作数人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。,2若目标函数为求max z的处理：（如效益）,max z=-min(-z)=-min(z),等价于求解 min z=(-aij)xij,i=1 j=1,m m,2006/3,-第4章 整数规划-,-30-,4 3 5 6 7,3 6 4 5 6,4 7 5 2 4,

19、8 9 6 5 3,甲 乙 丙 丁 戊,A B C D,E,0 0 0 0 0,ABCD,E,甲 乙 丙 丁,戊,4 7 6 5,8 5 4 6,4 8 6 5,5 9 2 7,3 4 8 7,0 0 0 0 0,-2-8-7-6-5-7-6-4-3-6-4-3-4-9-5-4,2006/3,-第4章 整数规划-,-31-,4.5 整数规划模型的应用,例1：在未来四个月中，某制鞋厂必须按时完成下述合同要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋（以前的存货）和3名工人，每名工人的月薪为1500元，每月可工作160小时（正常工作时间）。

20、一名工人最多还可有20小时的加班工作时间（规定），在加班工作时，每小时需付25元的加班费用。制作一双鞋需耗费4个工时和5元的原料费。在每月的开始，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月生产的产品可用于满足多个月的需求。试用ILP方法确定最佳的生产计划和用工政策。,2006/3,-第4章 整数规划-,-32-,问题分析：,需要解决的问题：每月租进、解雇、使用的工人数 每月所需的加班时间 每月在正常时间、加班时间生产的鞋子的数量 每月开始和结束时库存鞋子的数量 费用明

21、细：雇工费、解雇费、用工费、加班费、原料费,2006/3,-第4章 整数规划-,-33-,月初 人数,本月雇用,本月解雇,本月使用,用工过程图示：,生产过程图示：,正常生产,加班生产,月初库存,月末库存,交货数量,工人数,鞋子数,2006/3,-第4章 整数规划-,-34-,建模思路：,每月可用工人0,每月库存鞋子0,可用工人数=月初数+租进数-解雇数=月末数,月末库存量=月初库存+正常生产+加班生产-交货量,目标函数=总费用=月薪+雇用费+解雇费+加班费+原料费+库存费,2006/3,-第4章 整数规划-,-35-,例2：,某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练基地中的一

22、个进行训练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表1所示（单位：元）。,每年在中心1征招1000名士兵，中心2征召600名，中心3征召700名。基地1可训练1000名，基地2可训练800名，基地3可训练700名。,from,to,Base1 Base2 Base3,Center1 Center2 Center3,240 200 300 300 400 220 300 400 250,新兵受训后，要送到海军部队。运送时可采用小船或大船两种工具，共有7条小船和3条大船可供使用。若使用小船，则每条船要花费5000元加上每海里2元的费用；使用大船要花费10000元加上每海里3元的费用。一

23、条小船可运送200人，沿途最多可经过2个训练基地；一条大船可运送500人，最多可经过3个训练基地。可能的航线如表2中所示。现问，应怎样决策，能使发生的总费用最少？,表1,2006/3,-第4章 整数规划-,-36-,途径训练基地 航程（海里）,航线,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)征兵中心至训练基

24、地运送费用,(7)训练基地至海军部队运送费用,(8)总费用,2006/3,-第4章 整数规划-,-37-,例3：仓库位置问题,韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表1所示。生产出来的番茄酱可储存在三个成品库中，从各工厂运送一吨产品到各成品库的费用如表2所示。由于某些因素，公司销售看淡，现只有四家客户，其需求量如表3所示。从各成品库运送成品到各客户的需求地的单位费用如表4所示。每个工厂和每个成品库运营的年固定费用如表5所示。公司想确定关闭那些工厂和仓库，会使总费用最低。,表1 生产能力,工 厂 1 2 3 4 5,能力(吨)300 200 300 200 400,表3 客户需求,

25、客 户 1 2 3 4,需求(吨)200 300 150 250,表2 工厂成品库运费表,工厂,仓库,成品库1 成品库2 成品库3,12345,800 1000 1200 700 500 700 800 600 500 500 600 700 700 600 500,(元/吨),2006/3,-第4章 整数规划-,-38-,表4 成品库客户运输费用,（元/吨）,成品库,客户,成品库1 成品库2 成品库3,1 2 3 4,40 80 90 50 70 40 60 80 80 30 50 60,表5 年运营固定费用,（元）,工厂1 工厂2 工厂3 工厂4 工厂5 成品库1 成品库2 成品库3,35

26、000 45000 40000 42000 40000 40000 20000 60000,2006/3,-第4章 整数规划-,-39-,建模思路,xi0-1变量，第i厂是否开；yj0-1变量，第j库是否开。,0-1规划与运输问题的混合模型。,费用：工厂成品库运输费用+开工费；成品库客户运输费用+成品库运营费。,2006/3,-第4章 整数规划-,-40-,例4：资产运作滚动计划,某养殖场饲养6头黑熊（资产），在未来三年内对该6头黑熊的预期收入如表中所示（以千元计）。为维持养殖场的正常的资金周转，该厂必须在第一年获取20000元的收入，第二年获取30000元的收入，第三年获取35000元的收入

27、。试确定，该养殖场应采取怎样的销售计划，可使三年中获得的总收入最大？,1 2 3 4 5 6,year1 year2 year3,15 20 24 16 18 21 22 30 36 10 20 30 17 19 22 19 25 29,黑熊,建模提示：,利用 0-1变量表示在某年出售与否的关系；,三年内熊必须出售且只能出售一次；,每年的销售收入必须能保证需求；,每年的剩余资金可移作第二年使用。,2006/3,-第4章 整数规划-,-41-,例5：,市政对四个建设项目招标，有三个建筑队投标，标底情况如表示。由于建筑队1力量所限，只能完成其中一个项目，而2和3最多都可承担两项。试确定，如何分配可

28、使总费用最少？,项目,建筑队,1 2 3,1 2 3 4,50 46 42 40 51 48 44 47 45 45,单位：万元,问题分析：,可利用匈牙利方法求解分配问题解决,要考虑不能做的项目和可以多做项目的处理方式。,如果要建立模型，该如何表示？,2006/3,-第4章 整数规划-,-42-,例6：,校篮球队教练要确定比赛的首发阵容。全队共有7名球员，根据技术水平，对每名运动员的控球（ball-handing）、投篮（shooting）、蓝板（rebounding）、防守（defense）的能力都评出等级分，1分最低，3分最高。各球员的位置（position）及各项能力的等级分值如表示。五

29、名出场队员应满足下述要求：（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/F,3 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,2006/3,-第4章 整数规划-,-43-,设 xj=,1 0,第j号队员入选,第j号队员没入选,Max z=djxj 防守能力总分,j=1,7,xj=5 上场队员数,j=1,7,bjxj 9 控球能力总分,sjxj 9 投篮能力总分,rjxj 9 蓝板能力总分,x1+x3+x5+x7 3 后卫人数,x3+x4+x5+x6+x7 2 前锋人数,x2+x4+x6 1 中锋人数,j=1,j=1,j=1,7,7,7,xj=0或1(j=1,7),St.,x2+x3 1,2号、3号要求,