1、2006/08,-第4章 整数规划-,-1-,Integer Programming 整数规划All Integer Programming 全整数规划Mixed Programming 混合整数规划,第4章 整数规划,2006/08,-第4章 整数规划-,-2-,4.1 一般整数规划问题的特点及分枝定界法,一、引例,某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？,货物,体积(米3/箱),重量(吨/箱),利润(千元/箱),甲,乙,2 2 3,3 1 2,14 米3 9 吨,托运限制,2006/08,-第4章 整数规划-,-3
2、-,建模：,解：设 托运甲货物x1箱，乙货物x2箱,Max z=3 x1 +2 x2 st . 2 x1+3 x214 2 x1 + x29 x10，x20，且为整数,2006/08,-第4章 整数规划-,-4-,2,4,6,2,4,(3.25, 2.5),x1,x2,2x1+3x2=14,2x1+x2=9,3x1+2x2=6,2006/08,-第4章 整数规划-,-5-,2,4,6,2,4,(3.5, 2),x1,x2,2x1+3x2=14,2x1+x2=9,3x1+2x2=6,(2.5, 3),2006/08,-第4章 整数规划-,-6-,2,4,6,2,4,(4, 1),x1,x2,2x
3、1+3x2=14,2x1+x2=9,3x1+2x2=6,(2.5, 3),(3, 2),2006/08,-第4章 整数规划-,-7-,分枝定界法:,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/08,-第4章 整数规划-,-8-,LINDO软件及EXCEL求解：,LINDO程序软件：同求解LP模型时的输入及编辑修改过程，在使用 GO 命令求解之前，对整数变量给予说明。命令格式：G
4、IN 。,EXCEL求解：,2006/08,-第4章 整数规划-,-9-,4.2 0-1规划问题及模型,一、0-1规划问题的概念,在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。,0-1变量通常用来表示逻辑性选择的决策。,2006/08,-第4章 整数规划-,-10-,二、0-1变量的应用,例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？,设 xj=,10,- 选择开采第j个构造 -不选择开采第j个构造,max z=cjxj,j=1,10,ajxj b,xj
5、0或1 (j=1,2,-,10),j=1,10,-年总收益,-投资额限制,1、表示选择性决策,2006/08,-第4章 整数规划-,-11-,2. 表示选择性约束,例2：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f 度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。,采用电网供电： djxj f,采用自备柴油机发电： 0.3djxj p,j=1,10,j=1,10,+(1y1)M,+(1y2)M,y1+y2=1,y1, y2 =0或1,M
6、-非常大的正数,2006/08,-第4章 整数规划-,-12-,3. 表示条件性约束,例3：若在开采时还需满足下述条件： （a）若开采8号，则必须同时开采6号； （b）若开采5号，则不许开采3号； （c） 2 号和4号至少开采一个； （d） 8 号与7号必须同时开采； （e） 1号、4号、6号、9号开采时不能超过两 个，试表示上述约束条件。,2006/08,-第4章 整数规划-,-13-,（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
7、1,（d） x8 = x7,（e） x1 + x4 + x6 + x9 2,2006/08,-第4章 整数规划-,-14-,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/08,-第4章 整数规划-,-15-,5. 分段函数线性表示,设有 f(xj)=,Kj+cjxj 当xj00 当xj=0，,将min f (xj) 表示
8、成线性函数。,设 yj=,1 0,当xj0 当xj=0,Min f(xj) = kjyj+cjxj st. xjyjM xj0, yj=0或1,M非常大的正常数,则,f(xj) = kjyj+cjxj xjyjM yjxjM xj0, yj=0或1,或为：,2006/08,-第4章 整数规划-,-16-,三、隐枚举法,步骤：, 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj 4) 使目标函数按变量系数由小大顺序排列，约束条件变 量排列的顺序要与之对应。, 令所有变量xj=0，计算边界目标函数值z，检查是否满
9、足所有约 束条件，若满足，即为最优解；否则，分枝计算。, 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。, 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。,2006/08,-第4章 整数规划-,-17-,例：求解下述 0-1规划问题：,Max z=8x1+2x2-4x3-7x4-5x5 st. 3x1+3x2+x3+2x4+3x5 4 5x1+3x2-
10、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 -4,xj=0或1 (j=1,2,3,4,5),2006/08,-第4章 整数规划-,-18-,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+
11、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. 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/08,-第4章 整数规划-,-19-,求解图示：,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=
12、1,x3=0,x3=1,x3=1,x5=1,x5=0,x5=1,x5=0,z=-3,2006/08,-第4章 整数规划-,-20-,4.3 分配问题及匈牙利算法(Assignment Problem),一、问题的提出和数学模型,例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？,甲 乙 丙 丁,工作,人,译英文 译日文 译德文 译俄文,2 10 9 7 15 4 14 8 13 14 16 1
13、1 4 15 13 9,2006/08,-第4章 整数规划-,-21-,建立模型：,设 xij=,1,0,译英文：,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 =1,xij =0或1 (i=1,2,3,4; j=
14、1,2,3,4),Min z= aijxij (aij-效率),i=1j=1,4 4,若第i项工作交与第j个人完成,若第i项工作不交与第j个人完成,2006/08,-第4章 整数规划-,-22-,分配问题一般数学模型结构：,设有m项工作要交与m个人完成，其中第i项工作交与第j个人完成时所需花费的时间为 aij。规定每项工作只能交与其中的一个人完成，而每个人只能完成其中的一项工作。问：如何分配，可使所需的总时间最少？,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,
15、m),(j=1,2,m),2006/08,-第4章 整数规划-,-23-,二、匈牙利法：,基本思想：,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为效率矩阵的最优解.,2006/08,-第4章 整数规划-,-24-,证明:,以aij为效率矩阵的目标函数值： z0= aijxij,以bij为效率矩阵的目标函数值： z=bijxij
16、,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/08,-第4章 整数规划-,-25-,三、步骤, 使每行、每列都出现0元素,方法：每行减该行最小元素；,2 10 9 7,15 4 14 8,13 14 16 11,4 15 1
17、3 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/08,-第4章 整数规划-,-26-, 寻找位于不同行不同列的0元素,准则：,A）从第一行开始，若只有一个0，则记（0），同时作直线覆盖该列的元素。否则，转下行；,B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；,C）重复
18、A）、B），至再找不出这样的0元素，转D）,D）可能出现三种情况： 每行均有（0）元素，则在有（0）位置构成最优解中xij=1；, 多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路， 则沿回路顶点每间隔一个0记（ ），同时作直线覆盖该列的元素；, 所有0元素均有直线覆盖，但记（0）的个数m个，转。,2006/08,-第4章 整数规划-,-27-,0 0,0 0,0 0, 迭代，寻找新的位于不同行不同列的0元素,a）从未被直线覆盖的元素中找出一个最小的元素amin； b）对行，若无直线覆盖，则- amin； c）对列，若有直线覆盖，则+ amin；, 转 。,2006/08,-第4章
19、 整数规划-,-28-,特殊问题处理：,1人数与工作数不等的处理：,当人数工作数时：假想工作数，使得与人数能够匹配, 对应的效率设定为0值。,当工作数人数时：假想人数，使得与工作数能够匹配, 对应的效率设定为0值。,2若目标函数为求max z的处理：（如效益）, max z= - min (-z ) = - min ( z), 等价于求解 min z =(-aij)xij,i=1 j=1,m m,2006/08,-第4章 整数规划-,-29-,4 3 5 6 7,3 6 4 5 6,4 7 5 2 4,8 9 6 5 3,甲 乙 丙 丁 戊,A B C D,E,0 0 0 0 0,ABCD,E
20、,甲 乙 丙 丁,戊,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/08,-第4章 整数规划-,-30-,4.4 整数规划模型的应用,例1：在未来四个月中，某制鞋厂必须按时完成下述合同要求，第一个月300双，第二个月500双，第三个月100双，第四个月100双。在一月初，工厂已有50双鞋（以前的存货）和3名工人，每名工人的月薪为1500元，每月可工作160小时（正常工作时间）。一名工人最多还可有20小时的加班工作时间（规定），在加班工作
21、时，每小时需付25元的加班费用。制作一双鞋需耗费4个工时和5元的原料费。在每月的开始，可以租用和解雇工人。每雇用一名工人需支付1600元的费用，每解雇一名工人需支付2000元的解雇费用。在每月末，要为留在仓库里未交货的每双鞋支付30元的保管维护费用。一个月生产的产品可用于满足多个月的需求。试用ILP方法确定最佳的生产计划和用工政策。,2006/08,-第4章 整数规划-,-31-,问题分析：,需要解决的问题：每月租进、解雇、使用的工人数每月所需的加班时间每月在正常时间、加班时间生产的鞋子的数量每月开始和结束时库存鞋子的数量费用明细：雇工费、解雇费、用工费、加班费、原料费,2006/08,-第4
22、章 整数规划-,-32-,月初 人数,本月雇用,本月解雇,本月使用,用工过程图示：,生产过程图示：,正常生产,加班生产,月初库存,月末库存,交货数量,工人数,鞋子数,2006/08,-第4章 整数规划-,-33-,建模思路：,每月可用工人0,每月库存鞋子0,可用工人数=月初数+租进数- 解雇数=月末数,月末库存量=月初库存+正常生产+加班生产-交货量,目标函数=总费用 =月薪+雇用费+解雇费+加班费+原料费+库存费,2006/08,-第4章 整数规划-,-34-,2006/08,-第4章 整数规划-,-35-,例2：,某海军部队在三个征兵中心征招新兵。新兵必须送到三个海军训练基地中的一个进行训
23、练，从每个征兵中心运送一个新兵至某一个训练基地的费用如表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元的费用。一条小船
24、可运送200人，沿途最多可经过2个训练基地；一条大船可运送500人，最多可经过3个训练基地。可能的航线如表2中所示。现问，应怎样决策，能使发生的总费用最少？,表1,2006/08,-第4章 整数规划-,-36-,途径训练基地 航程（海里）,航线,1 2 3 4 5 6 7,B1B 370B12B 515B23B 665B2B 460B3B 600B13B 640 B123B 720,表2,需要解决的问题：,(1) Center iBase j运送的人数,(2) Base j 实际训练人数,(3) 第i航线运送第j基地人数,(4) 第i航线使用小船数量,(5) 第i航线使用大船数量,(6) 征兵
25、中心至训练基地运送费用,(7) 训练基地至海军部队运送费用,(8) 总费用,2006/08,-第4章 整数规划-,-37-,例3：仓库位置问题,韩德公司有五个生产番茄酱的工厂，每个工厂的生产能力如表1所示。生产出来的番茄酱可储存在三个成品库中，每个成品库的库存能力为500吨。从各工厂运送一吨产品到各成品库的费用如表2所示。由于某些因素，公司销售看淡，现只有四家客户，其需求量如表3所示。从各成品库运送成品到各客户的需求地的单位费用如表4所示。每个工厂和每个成品库运营的年固定费用如表5所示。公司想确定关闭那些工厂和仓库，会使总费用最低。,表1 生产能力,工 厂 1 2 3 4 5,能力(吨) 30
26、0 200 300 200 400,表3 客户需求,客 户 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/08,-第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
27、工厂3 工厂4 工厂5 成品库1 成品库2 成品库3,35000 45000 40000 42000 40000 40000 20000 60000,2006/08,-第4章 整数规划-,-39-,建模思路,xi0-1变量，第i厂是否开； yj0-1变量，第j库是否开。,0-1规划与运输问题的混合模型。,费用：工厂成品库运输费用+开工费； 成品库客户运输费用+成品库运营费。,2006/08,-第4章 整数规划-,-40-,例4：资产运作滚动计划,某养殖场饲养6头黑熊（资产），在未来三年内对该6头黑熊的预期收入如表中所示（以千元计）。为维持养殖场的正常的资金周转，该厂必须在第一年获取20000元
28、的收入，第二年获取30000元的收入，第三年获取35000元的收入。试确定，该养殖场应采取怎样的销售计划，可使三年中获得的总收入最大？,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/08,-第4章 整数规划-,-41-,例5：,市政对四个建设项目招标，有三个建筑队投标，标底情况如表示。由于建筑队1
29、力量所限，只能完成其中一个项目，而2和3最多都可承担两项。试确定，如何分配可使总费用最少？,项目,建筑队,1 2 3,1 2 3 4,50 46 42 40 51 48 44 47 45 45,单位：万元,问题分析：, 可利用匈牙利方法求解分配问题解决, 要考虑不能做的项目和可以多做项目的处理方式。, 如果要建立模型，该如何表示？,2006/08,-第4章 整数规划-,-42-,例6：,校篮球队教练要确定比赛的首发阵容。全队共有7名球员，根据技术水平，对每名运动员的控球（ball-handing）、投篮（shooting）、蓝板（rebounding）、防守（defense）的能力都评出等级分
30、，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/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/08,-第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号要求,
