最优化理论-第3章-整数规划

第3章整数规划哈尔滨工程大学理学院戴运桃Email:peach0040@126.com3.1整数规划定义规划中的变量（部分或全部）限制为整数时，称为整数规划。若在线性规划模型中，变量限制为整数，则称为整数线性规划。目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。整数规划的数学模型若要求所有xj

的解为整数，称为纯整数规划若要求部分xj

的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的最优解不会优于其松弛问题的最优解引例

某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：货物集装箱体积(米3)重量(百斤)利润(百元) 甲5220乙4510

托运限制2413问两种货物各装运多少箱，可使获得利润最大？返回设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型如下：

Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)

x1,x2≥0(4)

x1,x2为整数

(5)是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？容易求得相应的线性规划问题的最优解为

x1=4.8，x2=0，maxz=96现在来分析上述线性规划问题的最优解是否是整数规划问题的最优解因为x1表示的是托运甲种货物的箱数，目前得到的最优解不是整数，所以不合条件⑤的要求。是不是可以把所得的非整数最优解经过“化整”就可得到合于条件⑤的整数最优解呢?如将(x1=4.8，x2=0)凑整为(x1=5，x2=0)，这样就破坏了条件②(关于体积的限制)，因而它不是可行解；如将(x1=4.8，x2=0)舍去尾数0.8，变为(x1=4，x2=0)，这当然满足各约束条件，因而是可行解，但不是最优解，因为当x1=4，x2=0,时z=80；而当x1=4，x2=1(这也是可行解)时，z=90。

图中画(+)号的点表示可行的整数解。凑整得到的(5，0)点不在可行域内，而C点又不合于条件⑤。为了满足题中要求，表示目标函数的z的等值线必须向原点平行移动，直到第一次遇到带“+”号B点(x1=4，x2=1)为止。这样，z的等值线就由z=96变到z=90，它们的差值为Δz=96-90=6，表示利润的降低，这是由于变量的不可分性(装箱)所引起的。由上例看出，将其相应的线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。因此有必要对整数线性规划的解法进行专门研究。在求解整数线性规划时，如果可行域是有界的，首先容易想到的方法就是穷举所有可行的整数解，即列出图中所有标有“+”的整数点，然后比较它们的目标函数值，从而确定最优解。对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。如在例1中，变量只有x1和x2。由条件②，x1所能取的整数值为0、1、2、3、4共5个；由条件③，x2所能取的整数值为0、1、2共3个。因此所有可能的整数组合(不都是可行的)数是3×5=15个，穷举法还是勉强可用的。对于大型问题，可行的整数组合数会很大。例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20，超过2×1018。显然，穷举法是不可取的。应寻找仅检查可行的整数组合的一部分，就能定出最优的整数解的方法。分支定界解法就是其中之一。分枝定界法可用于解纯整数或混合整数线性规划问题。20世纪60年代初由LandDoig和Dakin等提出，是解整数线性规划的重要方法之一。分枝定界法继续求解定界，重复下去，直到得到最优解为止。基本思想例

求解问题Aminz=-10x1-20x25x1+8x2≤60 x1≤8 x2≤4x1，x2≥0x1，x2整数例题演示问题A对应的松弛问题Bminz=-10x1-20x25x1+8x2≤60 x1≤8 x2≤4x1，x2≥0B1minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≤5

分枝B2minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

B21minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3分枝B22minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≥4

B211minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3x1≤7分枝B212minz=-10x1-20x25x1+8x2≤60 x1≤8x2≤4x1，x2≥0

x1≥6

x2≤3

x1≥8x1≤5x1≥6问题B的解为:z0=-136x1=5.6x2=4问题B2为:z1=-135x1=6.00x2=3.75问题B1为:z1=-130x1=5.00x2=4.00-136<=Z*<=-130-136<=Z*<=0-135<=Z*<=-130问题B21为:z1=-132x1=7.2x2=3.00问题B22为:无可行解x2≤3x2≥4问题B211为:z1=-130x1=7.00x2=3.00问题B212为:z1=-130x1=8.00x2=2.50x1≤7x1≥8-132<=Z*<=-130-130<=Z*<=-130分枝定界法一般步骤问题(B)无可行解，则(A)也无可行解，停止；

0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。3.20-1整数规划

例：某公司拟在市东、西、南三区建立门市部。拟议中有7个位置Ai（i=1，2,…,7）可供选择规定在东区，由A1，A2，A3三个点中至多选两个；在西区，由A4，A5，两个点中至少选一个；在南区，由A6，A7，两个点中至少选一个。如果选择Ai点，设备投资估计为bi元，每年可获利润ci元，但投资总额不能超过B元。问应选择哪几个点可使年利润为最大？则该问题的数学模型为：

在整数规划中，如果变量xi仅取0或1，这时变量xi称为0—1变量，这时的整数规划称为0—1型整数规划。28在本章开始的例1中，关于运货的体积限制为

5x1+4x2≤24(1)

今设运货有车运和船运两种方式，上面的条件系用车运时的限制条件，如用船运时关于体积的限制条件为

7x1+3x2≤45(2)

这两个条件是互相排斥的。为了统一在一个问题中，引入0-1变量y，令含有互斥约束条件的问题Maxz＝20x1+10x2(1)5x1+4x2≤24(2)2x1+5x2≤13(3)

x1,x2≥0(4)

x1,x2为整数(5)29

于是，(1)式和(2)式可由下述条件(3)式和(4)式来代替：

5x1+4x2≤24+yM(3)

7x1+3x2≤45+(1−y)M(4)

其中M是充分大的数。可以验证:当y=0时，(3)式就是(1)式，而(4)式自然成立，因而是多余的。当y=1时，(4)式就是(2)式，而(3)式是多余的。引入的变量y不必出现在目标函数内，即认为在目标函数内y的系数为0。

30如果有m个互相排斥的约束条件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

为了保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，且下面这一组m+1个约束条件

αi1x１+αi2x2+…+αinxn≤bi+yiM

i=1,2,…，m(5)

y1+y2+…+ym=m−

1(6)

就合乎上述的要求。这是因为，由于(6)式，m个yi中只有一个能取0值，设yi*=0，代入(5)式，就只有i=i*这个约束条件起作用，而别的式子都是多余的。

对于0-1型整数规划，一般采用隐枚举法，而不必采用完全枚举法。包括:

(1)只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。(2)若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中每当发现更好的可行解就替换原来的过滤条件。0-1型整数规划的解法

例:用隐枚举法求解下列0—1型整数规划该条件称为过滤条件解：先通过试探找一个可行解，所有可能的可行解约束条件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1)

0

5

-1

1

0

1

√

5

-2

3

1

1

1

0

√

5

3

1

5×

8

0

2

1

1

√

8

1

6

2

6

×所有可能的可行解约束条件可行解否Z值(0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1)

0

√

5

-1

1

0

1

√

5

-2

3

3

8

0

2

1

1

√

8

1

6

0

0

0

0

0所有可能的可行解约束条件可行解否Z值(1，0，1)(1，1，1)(0，1，1)(1，0，0)(0，1，1)(1，1，0)(0，0，0)(0，1，0)

8

√

6

5

3

3

1

0

-2

0

2

1

1

836注意：一般常重新排列xi的顺序使目标函数中xi的系数是递增(不减)的，在上例中，改写

z=3x1−2x2+5x3=−2x2+3x1+5x3

因为−2，3，5是递增的序，变量(x2，x1，x3)也按下述顺序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)，…，这样，最优解容易比较早的发现。再结合过滤条件的改进，更可使计算简化。37z=3x1−2x2+5x3=−2x2+3x1+5x3指派问题指派问题的标准形式及其数学模型匈牙利解法求解指派问题一般的指派问题

有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij，要求确定人和事之间的一一对应的指派方案，使总花费最省？指派问题的标准形式及其数学模型

例4

有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？指派问题的标准形式及其数学模型指派问题的系数矩阵如下：Cij的含义可以不同，如费用、成本、时间等。为建立标准指派问题的数学模型，引入n×n个0-1变量：指派问题的数学模型可写成如下形式：若派第i人做第j事0若不派第i人做第j事

（ij=1，2,…，n）第j项工作由一个人做第i人做一项工作指派问题的每个可行解，可用矩阵表示如下：矩阵X中，每行各元素中只有1个元素为1,其余各元素等0；每列各元素中也只有1个元素为1,其余各元素等0。指派问题有n！个可行解。匈牙利法解题步骤

1955年，库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理，提出了解指派问题的一种算法，称为匈牙利解法。

标准指派问题是一种特殊的整数规划问题，又是特殊的0-1规划问题。

匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C的某行（或某列）各元素分别减去该行（或列）的最小元素，得到一个新的矩阵C’，则以C’和C为系数矩阵的两个指派问题有相同的最优解。

（系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）匈牙利法-2-4-9-7若某行(列)已有0元素，那就不必再减了。例1的计算为：1.使系数矩阵各行、各列出现零元素

作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij

取值一个1，其余为0，cij

同时减去一常数不影响xij取值)。匈牙利法解题步骤如下：-4-2

这就保证每行每列至少有一个0元素，同时不出现负元素。2.试求最优解。作法：由独立0元素的行（列）开始，独立0元素处画标记，在有的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记为止。（1）当遇到在所有的行和列中，0元素都不止一个时（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中其他0元素。（2）如能找出n个位于不同行不同列的零元素，令对应的xij=1，其余xij=0，得最优解，结束；否则，看下面的例题转第3步。例

求表中所示效率矩阵的指派问题的最小解。

任务人ABCDE甲127979乙89666丙71712149丁15146610戊4107109经行运算即可得每行每列都有0元素的系数矩阵。

再按上述步骤运算，得到：所画0元素少于n，未得到最优解。

3.作能覆盖所有0元素的最少直线数的直线集合(1)对没有的行打号；(2)对已打号的行中所有0元素的所在列打号；(3)再对打有号的列中0元素的所在行打号；(4)重复(2),(3)直到得不出新的打号的行(列)为止；(5)对没有打号的行画一横线，对打号的列画一纵线，这就得到覆盖所有0元素的最少直线数

4.未被直线覆盖的最小元素为cij0,在打号行中各元素都减去cij0,打号列中的各元素都加上cij0。Cij=2

解为5.返回步骤2，重复上述步骤。一般的指派问题在实际应用中，常会遇到各种非标准形式的指派问题。通常的处理方法是先将它们转化为标准形式，然后用匈牙利解法求解。最大化指派问题设最大化指派问题系数矩阵C中最大元素为m。令矩阵B=(bij)=(m-cij),则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同的最优解。人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”。这些虚拟的人作各事的费用系数可取0，理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”。这些虚拟的事被各人做的费用系数同样也取0。一个人可做几件事的指派问题若某个人可做几件事，则可将该人看做相同的几个人来接受指派。这几个人作同一件事的费用系数当然都一样。某事一定不能由某人作的指派问题若某事一定不能由某个人做，则可将相应的费用系数取做足够大的数M。例

：某大型工程有五个工程项目，决定向社会公开招标，建设公司A1，A2，A3参加招标承建，根据实际情况，可允许每家建设公司承建一项或二项工程。求使总费用最少的指派方案。上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚拟的事B6，使之成为标准指派问题的系数矩阵：解：由于每家建筑公司最多可以承建两项，因此可把每家建筑公司看成两家建筑公司，其系数矩阵为然后，用匈牙利解法求解。可得费用最省为4+7+9+8+7=35（百万元）1.

用图解法和单纯形法求解线性规划问题

作业：2.

用单纯形法求解线性规划问题

3.

求解整数规划问题maxz=3x1+2x2①2x1+3x2≤14②

2x1+x2≤9③

x1，x2≥0④

x1，x2整数⑤

4.设有A、B、C、D四人去完成甲、乙、丙、丁四项任务，不同的人完成不同的任务时间不同，资料如下，求总时间最小的分配方案。ABCD甲乙丙丁

5.设有A、B、C、D四人去完成甲、乙、丙、丁四项任务，不同的人完成不同的任务赢得不同，资料如下，求总赢得最大的分配方案。ABCD甲乙丙丁

6.设有A、B、C、D、E五人去完成甲、乙、丙、丁四项任务，每人完成各项工作如表所示。规定每项工作只能有一个人去完成，每人最多承担一项工作，又假定D因某种原因决定不承担丁项目，问应该如何分配，才能使4项工作总得花费时间最少？ABCDE甲乙丙丁例

求解整数规划问题Amaxz=3x1+2x2①2x1+3x2≤

70

②2x1+x2≤70③x1，x2≥0④x1，x2整数⑤解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图，得最优解x1=4.81，x2=1.82，z0=356

可见它不符合整数条件⑤。这时z0是问题A的最优目标函数值z*的上界，记作z0=。而在x1=0，x2=0时，显然是问题A的一个整数可行解，这时z=0，是z*的一个下界，记作=0，即0≤z*≤356。分枝因为当前均为非整数，故不满足整数要求，任选一个进行分枝。设选进行分枝，把可行集分成2个子集：因为4与5之间无整数，故这两个子集内的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划求解如下：问题B1为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x1,x2≥0问题B2为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≥5x1,x2≥

068

x1≤4，x1≥5B1:z1=349x1=4.00x2=2.10B2:z2=341x1=5.00x2=1.5769显然，仍没有得到全部变量是整数的解。因z1＞z2，故将改为349，那么必存在最优整数解，得到z*，并且

0≤z*≤349继续对问题B1和B2进行分解。因z1＞z2，故先分解B1为两支。增加条件x2≤2，称为问题B11；增加条件x2≥3，称为问题B21。相当于在图中再去掉x2＞2与x2＜3之间的区域，进行第二次迭代。问题B11为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≤2x1,x2≥0问题B12为:Maxz=40x1+90x29x1+7x2≤567x1+20x2≤

70x1≤4x2≥3x1≥

0z11=340x1=4.00x2=2.00z12=327x1=1.42x2=3.00对问题B1再进行分枝得问题B11和B12，它们的最优解为:

再定界：，并将B12剪枝。

340≤z*≤34971继续对问题B2