《整数规划(学时)》由会员分享，可在线阅读，更多相关《整数规划(学时)（43页珍藏版）》请在金锄头文库上搜索。
1、1-第4章 整数规划-第四章 整数规划 （6学时） ExcelORM1.0下载地址: ExcelORM 密码:123456课时：6学时 1 整数规划的特点及应用 2 分配问题与匈牙利法 3 分支定界法 4 割平面法 5 应用案例2-第4章 整数规划-4.1 一般整数规划问题的特点及分枝定界法一、引例某厂拟用集装箱托运甲、乙两种货物，每箱的体 积、重量、可获利润及托运时所受的限制如下表所示 ，问如何托运能使总收益最大？货物体积(米3/箱) 重量(吨/箱) 利润(千元/箱)甲乙2 2 33 1 214米39 吨托运限制3-第4章 整数规划-建模：解：设 托运甲货物x1箱，乙货物x2箱Max z=3
2、 x1 +2 x2 st . 2 x1+3 x2142 x1 + x29x10，x20，且为整数4-第4章 整数规划-24624(3.25, 2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6 5-第4章 整数规划-24624(3.5, 2)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5, 3)6-第4章 整数规划-24624(4, 1)x1x22x1+3x2=142x1+x2=93x1+2x2=6(2.5, 3)(3, 2)7-第4章 整数规划-分枝定界法:L0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L
3、3：z3=13L4：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x22x23x13x148-第4章 整数规划-LINDO软件及EXCEL求解：LINDO程序软件：同求解LP模型时的输入及编辑修改过 程，在使用 GO 命令求解之前，对整数变量给予说明。 命令格式：GIN 。EXCEL求解：9-第4章 整数规划-4.2 0-1规划问题及模型一、0-1规划问题的概念 在整数规划问题中，若变量取值为0或者1，则为0-1 规划问题。 0-1变量通常用来表示逻辑性选择的决策。10-第4章 整数规划-二、0-1变量的应用例1：某油田在10个有油气构造处要选择若干
4、个钻探 采油，设第j个构造开采时需投资aj元，投产后预计年收 益为cj元，若该油田投资的总限额为b元，问：应选择哪 几个构造开采最为有利？设 xj=1 0- 选择开采第j个构造 -不选择开采第j个构造max z=cjxj j=110ajxj bxj0或1 (j=1,2,-,10)j=110-年总收益-投资额限制1、表示选择性决策11-第4章 整数规划-2. 表示选择性约束例2：上述例题中，如果在开采中需用电力，解决的方案或由电网 供电或由自备的柴油机发电。已知第j个构造开采时每天耗电量为dj度 ，电网每天供电量限制为f 度。当使用自备柴油机发电时，每度电平均 耗油0.3公斤，而柴油供应量限额为
5、每天p公斤。试在模型中表示出该限 制条件。采用电网供电： djxj f采用自备柴油机发电： 0.3djxj pj=110j=110+(1y1)M+(1y2)My1+y2=1 y1, y2 =0或1M-非常大的正数12-第4章 整数规划-3. 表示条件性约束例3：若在开采时还需满足下述条件： （ a）若开采8号，则必须同时开采6号； （b ）若开采5号，则不许开采3号； （c） 2 号和4号至少开采一个； （d） 8 号与7号必须同时开采； （e）1号 、4号、6号、9号开采时不能超过两个，试表示 上述约束条件。13-第4章 整数规划-（a）当x8=1x6=1，x60当x8=0x6=1，x6=0
6、 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 214-第4章 整数规划-4. 两组条件满足其中一组若x1 4，则x21，否则(x14)，则x2 3。设 yi= 1 0第 i 组条件起作用第 i 组条件不起作用则i=1,2x1 4(1-y1) M x2 1(1-y1) M M充分大正数x1 4(1-y2) M x2 3(1-y2) My1y2=1 y1，y2=0或115-第4章 整数规划-5. 分段函数线性表示设有 f(xj)=Kj+cjxj
7、当xj00 当xj=0 ，将min f (xj) 表示成 线性函数。设 yj=10当xj0当xj=0Min f(xj) = kjyj+cjxj st. xjyjMxj0, yj=0或1M非常大的正常数则f(xj) = kjyj+cjxj xjyjM yjxjM xj0, yj=0或1或为：16-第4章 整数规划-三、隐枚举法步骤： 化标准形(隐枚举法)：1) 目标函数极小化 2) 约束条件化成 3) 使目标函数系数皆为非负, 若xj系数为负值, 则令xj=1-xj 4) 使目标函数按变量系数由小大顺序排列，约束条件变量排列的顺序要与之对应。 令所有变量xj=0，计算边界目标函数值z，检查是否满
8、足所有约 束条件，若满足，即为最优解；否则，分枝计算。 分枝：按变量次序依次令各变量取“1”和“0”值，计算边界值， 然后 检查是否满足所有约束，若满足，转下步；否则继续分枝。 剪枝：在得到一个可行解后，分枝过程中要进行剪枝工作。 (a) 对可行解，保留边界值最小的一枝zmin，其余全剪掉； (b) zmin分枝，剪掉； (c) 能判断出为无可行解的分枝，剪掉； (d) 非上述情况，继续分枝。 17-第4章 整数规划-例：求解下述 0-1规划问题：Max z=8x1+2x2-4x3-7x4-5x5 st. 3x1+3x2+x3+2x4+3x5 4 5x1+3x2- 2x3 - x4+ x5 4
9、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)18-第4章 整数规划-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=
10、0或1 (j=3,4,5)4) 变量按顺序排列：min z= 2 x2 +4x3 +5x5 +7x4+8 x1 -10st. 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)19-第4章 整数规划-求解图示：1234567891011z=-10z =-8z=-4z=-6z=-5z=-1z=1z=-5z=-3z=-6x2=1x2=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z=-320-第4章 整数规划-4.4 分配问题及匈牙利算法(Assignment Prob
11、lem)一、问题的提出和数学模型例：有一份说明书，要分别译 成英、日、德、俄四种文字， 交与甲、乙、丙、丁四个人去 完成，因各人专长不同，他们 完成翻译不同文字所需要的时 间（小时）如表所示。规定每 项工作只能交与其中的一个人 完成，每个人只能完成其中的 一项工作。问：如何分配，能使所需的 总时间最少？甲 乙 丙 丁工作人译英文译日文译德文译俄文2 10 9 715 4 14 813 14 16 114 15 13 9 21-第4章 整数规划-建立模型：设 xij=10译英文：x11+ x12 + x13 + x14 =1译日文：x21+ x22 + x23 + x24 =1译德文：x31+
12、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个人完成22-第4章 整数规划-分配问题一般数学模型结构：设有m项工作要交与m个人完成，其中第i项工作交与 第j个人完成时所需花费的时
13、间为 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)23-第4章 整数规划-二、匈牙利法：基本思想：4 (0) 5 6 5 4 (0) 5 7 6 3 (0) (0) 5 6 2 克尼格定理(konig)：如果从效率矩阵aij的每一 行元素中分别减去(或加上)一个常数ui,从每列中分别减 去(或加上)一个常数vj,得到一个新的效率矩阵bij,
14、其 中bij=aij-ui-vj,则以bij为效率矩阵的最优解等价于以 aij为效率矩阵的最优解.24-第4章 整数规划-证明:以aij为效率矩阵的目标函数值： z0= aijxij以bij为效率矩阵的目标函数值： z=bijxijm mi=1j=1i=1j=1m m bij=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 m25-第4章 整数规划-三、步骤 使每行、每列都出现0元素方法：每行减该行最小元素；2 10 9 7 15 4 14 8 13 14 16 11 4 15 13
