第五章 整数规划

第五 整数规第一节ProgrammingProgrammingProgramming0-1010-1例1 以及托运所受限制如表5-1：5-货体每箱重每箱（百斤利每箱（百元都是非负整数。这是一个（纯）Maxz=20x1+10 5x14x2 2x5x

x,x x1=4.8，x2=0，maxz=0条件②（关于体积的限制，因而它不是可行解；如将（x1=4.8x2=0）舍去=0x1=4x2=0时，zx1=4x2=1时（这也是可行解）时，z=905-1C（4.8，0）点达Cz的等值线必须zz=96z=90，它们的差值△z表示利润的降低，这是由于变量的不可分性（装箱）第二 分解（1）R(pi)R(P)（2）R(pi)R(pj)

成立，则称问题（P）被分解为子问题p1、p2、…、pm)之和。最常xi是问题（P）0-1变量，则问题（P）xi=0xi=1”分解为两个子问题之和。衍生松弛， ~。由此易知松弛问题有如下三个有用的R(P性质 若松弛问题没有可行解，则原问题也一定没有可行解性质 松弛问题目标函数的最优值给出原问题目标函数最优值的一个（P）极大（小）值不大（小）于（P）目标函数的极大（小）性质3 13132，通过求解第三节分枝定界法（BranchandBoundMethod）是通过有系统的“分枝”和“定例 求解下述整数规maxz4x1 4x1x2 2x13x2

x1,x2 x1x2 X(0)11

6

问题（4.3）624.1另一方面，(0,0)T显然是（4.3）0，

11,

6x2（x1当然也可以

6x2=1x2=2，故可把原问题（4.3）分解（即所谓进行分枝）为如下两个子问maxz4x1 4x1x2 2x13x2

x1,x2 x2 x1x2maxz4x1 4x1x2 2x13x2

x1,x2 x2 x1x2X(1)

;

X(2)1,2T;z2X(2)1,2T已是问题（4.5）的可行解从而也是其最优解，故此解为原问题（4.3）z2=10＞0，可知原问题（4.3）目标函数最优值010z2z1z0，故4.2所示。（4.4

9,

1

9，按上面所说的同样方法，将问题（4.4）

maxz4x1 4x1x2 2x13x2

0x 0x1 x1x2maxz4x1 4x1x2 2x13x2

0x x1 x1x24.3：

z3此解已是整数解，故为原问题（4.3）z3=11＞10z2，z311作为原问题（4.3）最优目标值的新上界。此时，问题（4.3）的目标函数最优值的上界和下界相等，均为11z311，相应的XnX(3)(2,1)T。用分枝定界法进行求解的过程常表示成树状图，并称之为枚举树Treez。然后，解该整数规划对应的线性规划2，规划即其松弛问题zznz。（1）xj≤[bj（2）xj≥[bj其中，bj]为数值不大于bj2继续进行分枝。第四节个有整数坐标的极点恰好是问题的最优解为止。这个方法是由R．E．Gomory1958Gomory割平面法。例2 maxzx1x x1x2 3x1x2

x1,x2 x1x2

x3

x c—5/24.1x3x4分别4.5A点。x24.1x2所在这一行相当于x3x1x4 4

03x01x1 3 4 4

14

3(1x 4

14

3 34

1x4

为了用原来的变量（而不是用松弛变量）表示，现将x31x1x2x443x1x2代入式（4.9）x2 （4.10，得maxzx1 x1x2 3x1x2

x1,x2A点在内的一个三角形（4.6。（4.11（4.9，而不用（4.10x1x2=1z=2。这就是原整数规划问题（4.8）的最优解。迭代过程于表4.2中，最优点为图4.6B点。cc3M M 3M 2 B1B

B1b, B1bi个分量bxiaijxj

现将系数aij和右侧常数bi分为整数和非负真分数两部分，即

[bi]f(bif（）f(aij)xjf(bi)[bi]xi[aij]xj

当要求解为非负整数时，式（4.15）的右端为整数，注意到0f(bi＜1f(aij)xj≥0，故上式右端为非负整数，从而应有f(aij)xj现引入剩科变量sif(aij)xjsi

ff

si

式（4.16）和（4.17）Gomory约束，称式（4.17）Gomory切割方由于在切割方程中sif(bi常常为正，故在把它加入松弛问性质 证假定问题（4.1） B1b(b,b,,b)T,

(aij)0 f(bi)

f（4.161表明，切割方程（4.17）对可行域进行了切割，它把非整数最优解性质2 足（4.162成立。（4.2则（4.1）也没有可行解，停止；若（4.2）XnXn即为

xiaijxj

出的最优解为整数解，则它就是问题（4.1）2例3

z6x1 2x14x2 2x1x2 x1,x2 x1x2解先不考虑整数条件，解此问题的松弛问题。为此，在两个约束不等式4.3cx5x x1 6

2x3 6

23

x5 56

23

4.4cj/都不是整数，我们取bi的分数部分最大者所对应的变量为退出变量，因为max4,634x4.4x10

x3 5

2x5 25 2

252

5 5 cxxx至此，我们已得到了原问题的（整数）Xnx1x2)T3(3,1)Tzn=224.7第五节0-1xi01这量0-1xi01这个条件可由约束条xi≥0xi≤1xi为整数来代替，这和一般整数规划的约束条件形式是一0-10-1变量，可以把有各种情况0-10-1变量还可把多种非线性规0-10-1规划的一些简0-1=1，2，…，ncj均是整数。试问为使所得利润最大，应选取哪些项目进行投资？0-1xjx

jmaxcjj ajxj j x

0或1j0-1背包问题nm个可供选择的厂址，每个厂址只能建一个工厂，在iDi，单位时间的固定成本为aij的需求量为bj，从厂址ij的单位运费为cij设在单位时间内，从厂址ijxij0-1yi

minzcijxijai

j

xijDiyi j xij

i1,2,,j1,2,,

yi0或0-1变量后，就可以适应种种“二中选一”或“多抉择”设有rA(1)XA(2)Xb(A(r)Xb(rq组约束得到满足，而其它rq组约束可满足，也可以不不同）A(kXb(k)M(k对于与所考虑问题有关Xyk0-1变量，则约束A(k)Xb(k)yM(k在

=0时相应于约束A(kX

；在

=1时相应于约束A(kXb(k)M(k，注意前面对M(kX不起约束作用。为（k=12rA(k)Xb(k)

M(k)

k1,2,,ykrxj0xjTj，Tj是它的一个有限的上界。于0 2 x 2x220 2 x（i=0，1，…，r）0-1变量，r是由不等式确定的整数。实际上，式（4.20xj

T2r11，就得到Tj0-1变量的通常意xj的又一表达形式。二、0-10-1规划时，一种自然的想法是用枚举法01的例

z2x1x2

x3 4x2x3

x3 x14x2x3 xi0或1,i 解（xxx）共有23=8 4.6约束（x1x2x3 0（001（100（1011max（0，－1，2，1）=2maxz2Xn1,0,0)T大（n＞10）2n相当大。全枚举法0-101组合，满足所有约束条件并使目标函数值最优的组合就是0-1规划的最优解。

zcjxjj1j

aijx

bi,i1,2,, cj≥0bi0，所有约束条件方程必须是“≤”

z2x13x2

z2x13(1x2)

z2x13x23x3z2x13x2xj=0xj=1xj=1xj=010值，检验解是否可行。若可01，将此子域再分成两个子域。如此继续第一步xj0值，检验解是否可行。若可行，第二步10，使问题分成两个zz值大，不会是最优解；如不可行， 式左端的自由变量当系数为负时取值为1，系数为正时取值为0，这就是左端所第七步检查有无自由变量。若有，转第二步；若没有，计算停止。目标1值的一切可能组合都被隐含地考虑过了，不必再一一列举。所以这种方法称例 minz8x12x24x37x43x13x2x32x43x5 5x3x2xxx

7-8所示。经过第一、二、三步，进行第四步，子域的1的解[1，0，0，0，0]可z1=82z2=0z1，进234。3的解[0，1，0，0，0]z3=2z1，不可行，但能通过两个不等4进行检验计算。4的解[0，0，0，0，0]z4=0z1，不可行，进行x1=0x2=0x3x4x5=0，求出左356。5的解[0，1，1，0，0]，z64x2=01x3=01，这样计算速度可能快一些。第六 nn个人（或呢？这一类问题就称为分派问题或指派问题（AssignmentProblem。例 4.8所示。问应分派哪个人去完成哪项工作，可使总的消耗时间 工作0—1xijxij

i，jz55项工作所消耗的总时间，则可得出该问题的数学

z5x116x128x134x143x214x226x236x245x315x327x339x346x417x425x437x447x414x526x532x54

xij

j

xijj

i

4.8称为该问题的价值系数表，它给出了这个问题目标函数中的各个系现假定一般分派问题的价值系数矩阵的元素为cij，它表示由第i个人去完j项工作的资源消耗（价值或效率 minzcij

j j

1,j

0—1规划的特例，也是运输问题的特例（即mn，aibjj种有效算法：匈牙利法（HungarianAlgorithm。性质假定Ccij为分派问题（4.21）C作为（4.21）的价值系数矩阵，而构成一新的分派问题，则这个新分派问Ccijlk，记由此所得的新矩阵为C(cij)。则机关报的分派问题的目标函数 n z(X)cijxijcijxij(cilk)xij

j

j j cijxijkxili1j cijxijk

j

cijxijk·1z(X)i1j通过上述变换，即可使新价值系数矩阵Ccij)nnxij≥0和cij≥0对所有ij都成立，这样的解就是新分派问题的最优解，它同时也是于不同行不同列的nxij=1，xij=0，这个解就是问题的最优解。因此，问题的关键就在于寻求产Konig发展并证明了设已给定一个初始的nnCcij，运用匈牙利法求最优分找出(cij每行（或每列）的最小元素，将(cij的每行（或每列）的所有m条直线（水平的或竖直的）去覆盖（或说划去）简约化价m=n，停止；可从上述简约化的价值矩阵的零元中找到一组位于不xij=1xij=0，m＜nm条直线覆盖的元素中找出最小元素，从所有未被覆盖3步。C0

找出价值系数矩阵C0每行的最小元素，各个元素分别减去相应的最小元素后得新的价值系数矩阵C1：

5 1

1 C0

85C1

6

C1

11，得新矩阵C2 C1

10

C2

C2C2

(1)

5*

8

0(

6 8

x11x25x32x43x541xij最后回到原问题中，其最优目标函数值为5+1+5+5+2=18；即让甲去干工18。

zcij

j

1,j1,2,,

j

可令cijMcijM（如选cijM即可显然cij≥0

zcij

j

1,j1,2,,

j

cijxij(Mcij Mxijcij MMxijcij M1cij n·Mcij nM为常数，故cijxijcijxi