《[管理学]整数规划20084》由会员分享，可在线阅读，更多相关《[管理学]整数规划20084（58页珍藏版）》请在金锄头文库上搜索。
1、 1. 整数规划的数学模型及解的特点 2. 分枝定界法 3. 0-型整数规划 4. 分派问题第四章 整数规划第一节 整数规划的数学模型及解的特点 例1 、某厂拟用集装箱托运甲、乙两种 货物，每箱的体积，重量，可获利润以 及托运所受限制如下表：一、整数规划问题的提出货物 体积（m3/箱） 重量（100斤/箱） 利润（百元/箱）甲 5 2 20乙 4 5 10托运限制 24 13 问：两种货物各托运多少箱，可使获 得利润为最大？max z = 20x1+10x2 5x1+4x224 2x1+5x213 x1,x20 x1,x2为整数解：先不考虑整数条件，解上述问题的松弛问题， 得最优解:x1=4.
2、8 , x2=0 , max z=968 -7 -6 -5 -4 -3 -2 -1 -1 2 3 4 5 6 7 8 9 10BXX1AC z = 20x1+10x20 整数规划是一类要求变量取整数值的数整数规划是一类要求变量取整数值的数 学规划，可分成线性和非线性两类。学规划，可分成线性和非线性两类。二、整数规划数学模型的一般形式 整数线性规划的一般形式为整数线性规划问题的类型： 1 1、纯整数线性规划、纯整数线性规划 2 2、混合整数线性规划、混合整数线性规划 3 3、0-10-1整数线性规划等。整数线性规划等。三、整数规划的例子四、解的特点例、例、 求下列问题：求下列问题：放弃整数要求放
3、弃整数要求 后，最优解后，最优解 B(9.2,2.4)B(9.2,2.4) Z0=58.8Z0=58.8O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)AD整数规划最整数规划最 优解优解I(2,4)I(2,4) Z0=58Z0=58B B附近四个整点附近四个整点 (9,2)(10,2)(9,3)(10,3)(9,2)(10,2)(9,3)(10,3)都不是都不是 原规划最优解原规划最优解O 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)ADE EF FGGH
4、HI IJ JO 1 2 3 4 5 6 7 8 9 105 4 3 2 1x x1 1x x2 2I(2,4)B(9.2,2.4)ADvv假如把可行域分解成五个互不相交的假如把可行域分解成五个互不相交的 子问题子问题P P1 1P P2 2 P P3 3 P P4 4 P P5 5之和之和, , P P3 3 P P5 5的的定义域定义域 都是空集都是空集, ,而放弃整数要求后而放弃整数要求后P P1 1最优解最优解 I(2,4),ZI(2,4),Z1 1=58=58 P P2 2最优解最优解(6,3),Z(6,3),Z2 2=57=57 P P4 4最最 优解优解(9,2),Z(9,2),
5、Z4 4=53=53 P P1 1P P2 2P P4 4X1 2X1 6X2 3X2 2X1 3X1 7X2 4X2 3P1P5P4P2P3 Pvv假如放弃整数要求后，用单纯假如放弃整数要求后，用单纯 形法求得最优解，恰好满足整数形法求得最优解，恰好满足整数 性要求，则此解也是原整数规划性要求，则此解也是原整数规划 的最优解。的最优解。第二节 分枝定界法一、分支定界法的步骤 1、求整数规划的松弛问题最优解，并定界； 2、若松弛问题的最优解满足整数要求，得到 整数规划的最优解，否则转下一步； 3、任意选一个非整数解的变量xi，在松弛问 题上加上约束组成两个新的松弛问题，称为 分支，再次定界；
6、4、检查所有分支的解的目标函数值，直到得 到最优解。例.求解下述整数规划问题。max z = 40x1+90x2 9x1+7x256 7x1+20x270 x1,x20 x1,x2为整数解：先不考虑整数条件，解上述问题的松弛问题，得最优解。x1=4.81 , x2=1.82 , z0=3568 -7 -6 -5 -4 -3 -2 -1 -1 2 3 4 5 6 7 8 9 10BXX1AC 9x1+7x2=56z = 40x1+90x27x1+20x2=700问题A的最优目标函数值z*即(下界)0 z* 356（上界）分解成子问题之和。现先考虑非整数分量x1（考虑x2当然也可以）。 由于 x=
7、4.81 ， 于是对原问题增加两个约束条件：x 4 , x 5 可将原问题分解为两个子问题B1和B2（即两枝）：B1max z = 40x1+90x2 9x1+7x256 7x1+20x270 x1,x20 x14 x1,x2为整数max z = 40x1+90x2 9x1+7x256 7x1+20x270 x1,x20 x15 x1,x2为整数B2-4 -3 -2 -1 -0 1 2 3 4 5 6 7 8 B1B2x2x1如下图所示给每枝增加一个约束条件，如上图所示。这并不影响问题的可行域。不考虑整数条件解问题1和2 ，得到各自的 最优解为：B1Z1=349 (x1,x2)T=(4, 2.
8、10)TB2Z2=341 (x1,x2)T=(5.00, 1.57)T得到Z*，并且Z*349 继续对B1,B2进行分解，分解B1为两枝，即 （B3,B4）B3 B4max z = 40x1+90x2 9x1+7x256 7x1+20x270 0 x1 4 0 x2 2 x1,x2为整数max z = 40x1+90x2 9x1+7x256 7x1+20x270 0 x1 4 x2 3 x1,x2为整数z3=340 x1=4 x2=2z4=327 x1=1.42 x2=3所以340Z*341之间有整数解。于是对B2分解为子问题，B5 和 B6B5 B6max z = 40x1+90x2 9x1
9、+7x256 7x1+20x270 x1 5 0 x2 1 x1,x2为整数max z = 40x1+90x2 9x1+7x256 7x1+20x270 x1 5 x2 2 x1,x2为整数得 x1=5.44 x2=1.00 z5=308无可行解Z*=340问题B3的解：x1=4.00，x2=2.00为最优整数解。这一分枝过程用枚举树表示如下：问题B x1 = 4.81 x2 = 1.82 z0 = 356z = 0 , z=356B1 x1=4.00 x2=2.10 z1=349x14x15 B2 x1=5.00 x2=1.57 z2=341z = 0 , z=349B3 x1 = 4.00
10、 x2 = 2.00 z3 = 340B4 x1 = 1.42 x2 = 3.00 z4 = 327x22x23Z=340,z=341x x21x22Z=340=Z*B5 x1 = 5.44 x2 = 1.00 z5 = 308B6 无可行解xx第三节 -整数规划 一、0-1变量及其应用 见P124例2、例3 二、0-1整数规划的解法 用隐枚举法求解0-1整数规划例1. 求解0-1整数规划问题解、列出变量取值0和1的组合，共23=8个序号（x1，x2，x3）Z值值约约束条件过滤过滤 条 件 abcd 1（0，0，0）0Z0 2（0，0，1）5Z5 3（0，1，0）-2 4（0，1，1）35（1
11、，0，0）3 6（1，0，1）8Z87（1，1，0）1 8（1，1，1）6例2. 求解0-1整数规划问题解：（1）第一个约束没有约束力， 可以去掉。按目标函数中各变量系数 的大小重新排列各变量。(2)列出变量取值0和1的组合，共24=16个序号（x1，x4，x3，x2） Z值值约约束条件过滤过滤 条 件 abc 1（1，1，1，1）16 2（1，1，1，0）14Z14 3（1，1，0，0）11 4（1，0，0，0）65（0，1，1，1）10 6（0，1，1，0）87（0，1，0，0）5 8（0，0，1，1）5第四节 指派（分派）问题一. 标准指派（分派）问题的数学模型。例 有一份资料需译成英、
12、日、俄三种文字，现有、 三个人，每人需完成其中的一种工作。因各人对不同文字 的熟悉程度不一样，所需工作时间也不同。问应分派哪一个 人去完成哪一项工作才能使花费的总时间最短。为了解决这个问题，我们引入变量xij,且令xij 1 当分派第 i 个人去完成第 j 项工作时； 否则 i, j = 1, 2 , 3 用表示3个人分别完成3项工作所消耗的总时间， 则可得出该问题的数学模型。译译英 译译日 译译俄A B C2 10 915 4 1413 14 16Min z = 2x11+15x12+13x13+10x21+4x22+14x22+9x31+14x32+16x33 x11+x12+x13=1
13、x21+x22+x23=1 x31+x32+x33=1 x11+x21+x31=1 x12+x22+x32=1 x13+x23+x33=1 xij = 0或1 i,j=1,2,3一般分派问题的数学模型：译译 英译译 日译译 俄人员员A 2 15 13 1B 10 4 14 1C 9 14 16 1工作1 1 1 3二 匈牙利法（一）、匈牙利法的条件是：问题求最小值、 人数与工作数相等就、价值系数非负； （二） 、指派（分派）问题最优解的一个性质 ： 假定C=（cij）为分派问题的价值系数 矩阵。现将它的某一行（或某一列）的各个 元素都减去一个常数k，得到一新矩阵C/=（ cij）。若以C/代替C作为原问题的价值系数 矩阵，而构成一新的
