运筹学讲义第4章

2010/03--第4章整数规划----1--IntegerProgramming整数规划AllIntegerProgramming全整数规划MixedProgramming混合整数规划第四章整数规划2010/03--第4章整数规划----2--4.1一般整数规划问题的特点及分枝定界法一、引例某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙22331214米39吨托运限制2010/03--第4章整数规划----3--建模：解：设托运甲货物x1箱，乙货物x2箱Maxz=3x1+2x2st.2x1+3x2142x1+x29x10，x20，且为整数2010/03--第4章整数规划----4--24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=602010/03--第4章整数规划----5--24624(3.5,2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)02010/03--第4章整数规划----6--24624(4,1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5,3)(3,2)02010/03--第4章整数规划----7--分枝定界法: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=12010/03--第4章整数规划----8--LINDO软件及EXCEL求解：1）LINDO程序软件：输入同求解LP模型时的输入；在END之前，对整数变量给予说明。命令格式：GIN变量名。EXCEL求解：2010/03--第4章整数规划----9--4.20-1规划问题及模型一、0-1规划问题的概念•在整数规划问题中，若变量取值为0或者1，则为0-1规划问题。•0-1变量通常用来表示逻辑性选择的决策。2010/03--第4章整数规划----10--二、0-1变量的应用例1：某油田在10个有油气构造处要选择若干个钻探采油，设第j个构造开采时需投资aj元，投产后预计年收益为cj元，若该油田投资的总限额为b元，问：应选择哪几个构造开采最为有利？设xj=10---选择开采第j个构造---不选择开采第j个构造maxz=Σcjxjj=110∑ajxjbxj＝0或1(j=1,2,---,10)j=110-----年总收益----投资额限制1、表示选择性决策2010/03--第4章整数规划----11--2.表示选择性约束例2：上述例题中，如果在开采中需用电力，解决的方案或由电网供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度，电网每天供电量限制为f度。当使用自备柴油机发电时，每度电平均耗油0.3公斤，而柴油供应量限额为每天p公斤。试在模型中表示出该限制条件。采用电网供电：∑djxjf采用自备柴油机发电：∑0.3djxjpj=110j=110+(1－y1)M+(1－y2)My1+y2=1y1,y2=0或1M-----非常大的正数2010/03--第4章整数规划----12--3.表示条件性约束例3：若在开采时还需满足下述条件：（a）若开采8号，则必须同时开采6号；（b）若开采5号，则不许开采3号；（c）2号和4号至少开采一个；（d）8号与7号必须同时开采；（e）1号、4号、6号、9号开采时不能超过两个，试表示上述约束条件。2010/03--第4章整数规划----13--（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22010/03--第4章整数规划----14--4.两组条件满足其中一组若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或12010/03--第4章整数规划----15--5.分段函数线性表示设有f(xj)=Kj+cjxj当xj00当xj=0，将minf(xj)表示成线性函数。设yj=10当xj0当xj=0Minf(xj)=kjyj+cjxjst.xjyjMxj0,yj=0或1M—非常大的正常数则f(xj)=kjyj+cjxjxjyjMyjxjMxj0,yj=0或1或为：2010/03--第4章整数规划----16--三、隐枚举法步骤：①化标准形(隐枚举法)：1)目标函数极小化；2)约束条件化成；3)使目标函数系数皆为非负,若xj系数为负值,则令xj=1-xj；4)使目标函数按变量系数由小→大顺序排列，约束条件变量排列的顺序要与之对应。②令所有变量xj=0，计算边界目标函数值z，检查是否满足所有约束条件，若满足，即为最优解；否则，分枝计算。③分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值，然后检查是否满足所有约束，若满足，转下步；否则继续分枝。④剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。(a)对可行解，保留边界值最小的一枝zmin，其余全剪掉；(b)zmin分枝，剪掉；(c)能判断出为无可行解的分枝，剪掉；(d)非上述情况，继续分枝。2010/03--第4章整数规划----17--例：求解下述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)2010/03--第4章整数规划----18--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)2010/03--第4章整数规划----19--求解图示：1234567891011z=-10z=-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x3=1z=-3√×××××2010/03--第4章整数规划----20--4.3分配问题及匈牙利算法(AssignmentProblem)一、问题的提出和数学模型例：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。问：如何分配，能使所需的总时间最少？甲乙丙丁工作人译英文译日文译德文译俄文21097154148131416114151392010/03--第4章整数规划----21--建立模型：设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个人完成2010/03--第4章整数规划----22--分配问题一般数学模型结构：设有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)2010/03--第4章整数规划----23--二、匈牙利法：基本思想：4(0)5654(0)5763(0)(0)562克尼格定理(konig)：如果从效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui,从每列中分别减去(或加上)一个常数vj,得到一个新的效率矩阵[bij],其中bij=aij-ui-vj,则以[bij]为效率矩阵的最优解等价于以[aij]为效率矩阵的最优解.2010/03--第4章整数规划----24--证明:以[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=1mm2010/03--第4章整数规划----25--三、步骤⑴使每行、每列都出现0元素方法：每行减该行最小元素；2109715414813141611415139-2-4-11-4min0875110104235001195min-0-0-5-0082511054230001145-2-2-2+2+2080311032450001123每列减该列最小元素。2010/03--第4章整数规划----26--⑵寻找位于不同行不同列的0元素准则：A）从第一行开始，若只有一个0，则记（0），同时作直线覆盖该列的元素。否则，转下行；B）从第一列开始，若只有一个0，则记（0），同时作直线覆盖该行的元素。否则，转下列；C）重复A）、B），至再找不出这样的0元素，转D）D）可能出现三种情况：①每行均有（0）元素，则在有（0）位置构成最优解中xij=1；②多于两行和两列存在未被直线覆盖的0元素，即存在0元素的闭回路，则沿回路顶点每间隔一个0记（），同时作直线覆盖该列的元素；③所有0元素均有直线覆盖，但记（0）的个数m个，转⑶。2010/03--第4章整数规划----27--000000⑶迭代，寻找新的位于不同行不同列的0元素a）从未被直线覆盖的元素中找出一个最小的元素amin；b）对行，若无直线覆盖，则-amin；c）对列，若有直线覆盖，则+amin；⑷转⑵。2010/03--第4章整数规划----28--特殊问题处理：1．人数与工作数不等的处理：当人数工作数时：假想工作数，使得与人数能够匹配,对应的效率设定为0值。当工作数人数时：假想人数，使得与工作数能够匹配,对应的效率设定为0值。2．若目标函数为求maxz的处理：（如效益）∵maxz=-min(-z)=-min(z)∴等价于求解minz=∑∑(-aij)xiji=1j=1mm2010/03--第4章整数规划----29--43567364564752489653甲