《运筹学》 课件 第4章-整数规划

7/16/2024第4章整数规划1CONTENTS目录7/16/20244.1

问题及其数学模型4.2

分支定界法4.3

割平面法4.4

整数规划4.5

指派问题4.6

整数规划案例24.1问题及数学模型4.1.1整数规划问题引例货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲19542乙273403托运限制1365（立方英尺）140（百千克）

例4.1某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量，可获利润以及托运所受限制如表4.1所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。表4.1单位货物体积、重量及利润7/16/20244

4.1.1整数规划问题引例7/16/20245纯整数规划：所有决策变量为非负整数；全整数规划：所有变量、系数和常数均为整数；混合整数规划：只有一部分决策变量为非负整数，其余变量可为非负实数；0-1整数规划：所有决策变量只能取0获1两个整数。4.1.2整数规划的数学模型7/16/20246例4.2

设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。4.1.3整数规划与线性规划的关系7/16/20247用图解法求出最优解x1＝3/2,x2=10/3且有z=29/6现求整数解（最优解）：如用“舍入取整法”可得到4个点，即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。4.1.3整数规划与线性规划的关系7/16/202484.2分枝定界法

基本思路4.2分支定界法7/16/2024101）先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：分支定界法的步骤如下：4.2分支定界法7/16/2024112）定界：记(IP)的目标函数最优值为Z*,以Z(0)

作为Z*

的上界，记为＝Z(0)

。再用观察法找的一个整数可行解X′，并以其相应的目标函数值Z′作为Z*

的下界，记为Z＝Z′，也可以令Z＝－∞，则有：Z≤Z*≤3）分枝：

在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以

表示不超过的最大整数。构造两个约束条件

xr≤和xr≥＋1将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4.2分支定界法7/16/202412如此反复进行，直到得到Z＝Z*＝为止，即得最优解X*

。4）修改上、下界：按照以下两点规则进行。⑴.在各分枝问题中，找出目标函数值最大者作为新的上界；

⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5）比较与剪枝各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。4.2分支定界法7/16/202413分支定界法是一种隐枚举方法（implicitenumeration）或部分枚举方法，它不是一种有效的算法，是枚举方法基础上的改进。其关键是分支和定界。例4.3MaxZ=X1+X214X1+9X2

≤51-6X1+3X2

≤1X1

，X2

≥0X1

，X2

取整数s.t.4.2分支定界法7/16/202414分支定界法图解整数规划例4.3分支定界求解过程（一）松弛问题

MaxZ=X1+X2

14X1

+9X2≤51

-6X1+3X2≤1

X1

，X2≥0该整数规划松弛问题的解为：（X1

，X2）=

（3/2，10/3）Z0=29/64.2分支定界法7/16/202415松弛问题

MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1

，X2≥0（3/2，10/3）Z0=29/6LP1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥2X1

，X2≥0LP2MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤1X1

，X2≥0LP2：解（1，7/3）Z2=10/3LP1：解（2，23/9）Z1=41/9例4.3分支定界求解过程（二）4.2分支定界法7/16/202416（3/2，10/3）Z0=29/6LP1MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X1

，X2≥0LP2：解（1，7/3）Z2=10/3LP1：解（2，23/9）Z1=41/9LP11MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≥3X1

，X2≥0LP12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2

X2≤2X1

，X2≥0LP12：解（33/14，2）Z12=61/14例4.3分支定界求解过程（三）4.2分支定界法7/16/202417（3/2，10/3）Z0=29/6LP2：解（1，7/3）Z2=10/3LP12MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1X1≥2X2≤2X1

，X2≥0LP12：解（33/14，2）Z12=61/14LP121MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≥3X2≤2X1

，X2≥0LP122MaxZ=X1+X214X1+9X2≤51-6X1+3X2≤1

X1≤2X2≤2X1

，X2≥0LP121：解（3，1）Z121=4LP122：解（2，2）Z122=4LP1：解（2，23/9）Z1=41/9例4.3分支定界求解过程（四）4.2分支定界法7/16/202418LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11

无可行解LP122（2，2）Z122=4LP121

（3，1）Z121=4#LP22（1，2）Z22=3LP21

无可行解####例4.3分支搜索法流程4.2分支定界法7/16/202419LP（3/2，10/3）Z0=29/6LP2（1，7/3）Z2=10/3LP1（2，23/9）Z1=41/9LP12（33/14，2）Z12=61/14LP11

无可行解LP122（2，2）Z122=4LP121

（3，1）Z121=4#例4.3分支定界法流程4.2分支定界法7/16/2024203200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例4.4

用分支定界法求解整数规划问题（单纯形法）4.2分支定界法7/16/202421

x1=13/4x2=5/2Z(0)=59/4≈14.75

选x2进行分枝，即增加两个约束，2≥x2≥3有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:4.2分支定界法7/16/20242232000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=14.5继续分枝，加入约束3≥x1≥4LP14.2分支定界法7/16/20242332000CB

XB

bx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3Z(2)=13.5∵Z(2)<Z(1)∴先不考虑分枝7/16/202424接(LP1)继续分枝，加入约束4≤x1≤3，有下式：分别引入松弛变量x7和x8，然后进行计算。4.2分支定界法7/16/202425CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算。LP37/16/202426CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1x1=4x2=1Z(4)=14找到整数解，问题已探明，停止计算。LP47/16/202427树形图如下：LP1x1=7/2,x2=2Z(1)＝29/2=14.5LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)＝13LP4x1=4,x2=1Z(4)＝14x2≤2x2≥3x1≤3x1≥4###4.2分支定界法7/16/2024284.3割平面法4.3.1基本思想7/16/2024301）用单纯形法求解(IP)对应的松弛问题(LP)：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。2）从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：4.3.2求解步骤7/16/2024313）将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。4.3.2求解步骤7/16/202432例4.5

用割平面法求解整数规划问题解：增加松弛变量x3和x4

，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/44.3.2求解步骤7/16/202433此题的最优解为：X＊

(1,3/2)，Z=3/2

。以x2为源行生成割平面，由于1/4=0+1/4,3/2=1+1/2,我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为:也即：4.3.2求解步骤7/16/202434将x3=6-3x1-2x2,x4=3x1-2x2,代入中，得到等价的割平面条件：x2≤1

见下图。x1x2⑴⑵33第一个割平面4.3.2求解步骤7/16/202435Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40现将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-17/16/202436此时，X1

＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：用上表的约束解出x4和s1，将它们带入上式得到等价的割平面条件：x1≥x2，见图：x1x2⑴⑵33第一个割平面第二个割平面4.3.2求解步骤7/16/202437将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/27/16/202438CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10

至此得到最优表，其最优解为X＊=(1,1),Z=1,这也是原问题的最优解。

有以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。7/16/202439例4.6

用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100CBXBbx1x2x3x41x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6初始表最优表4.3.2求解步骤7/16/202440在松弛问题最优解中，x1,x2均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和4.3.2求解步骤7/16/202441以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。4.3.2求解步骤7/16/202442Cj11000CBXBbx1x2x3x4s11x15/3105/6－1/601x28/301－2/31/300s1－2/300－1/3－1/31－Z－13/300－1/6－1/601x10100－101x240101－20x320011－3－Z－40000－1/2﹡得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X＊=(0,4),Z=4,或X＊=(2,2),Z=4。4.3.2求解步骤7/16/2024434.40-1整数规划7/16/202444例4.8

求解下列0－1

规划问题4.4.1建模与求解思想7/16/202445解：对于0－1规划问题，由于每个变量只取0，1两个值，一般会用穷举法来解，即将所有的0，1组合找出，使目标函数达到极值要求就可求得最优解。但此法太繁琐，工作量相当大。而隐枚举法就是在此基础上，通过加入一定的条件，就能较快的求得最优解。x1.x2.x3约束条件满足条件Z值(1)(2)(3)(4)是∨否×(0.0.0)0000∨0(0.0.1)

－1101∨5(0.1.0)2414∨－2(1.0.0)1110∨3(0.1.1)15 ×(1.0.1)0211∨8(1.1.0)3×(1.1.1)26×4.4.1建模与求解思想7/16/202446由上表可知，问题的最优解为X*=(x1=1x2=0x3=1)由上表可知：x1=0x2=0x3=1是一个可行解，为尽快找到最优解，可将3x1－2x2＋5x3≥5作为一个约束，凡是目标函数值小于5的组合不必讨论，如下表。x1.x2.x3约束条件满足条件Z值(0)(1)(2)(3)(4)是∨否×(0.0.0)00000∨0(0.0.1)5－1101∨5(0.1.0)-2×(0.1.1)3×(1.0.0)3×(1.0.1)80211∨8(1.1.0)1×(1.1.1)4×4.4.1建模与求解思想7/16/202447以下讨论一般形式的0－1规划如何化为标准形式：4.4.2标准0-1整数规划的隐枚举法求解步骤7/16/202448例4.9

求解下列0－1规划问题解：令

y1=x5,y2=x4,y3=x2,y4=x3,y5=x1

得到下式4.4.2标准0-1整数规划的隐枚举法求解步骤7/16/202449y1.y2.y3.y4.y5约束条件满足条件Z值(1)(2)是∨否×(0.0.0.0.0)00×(1.0.0.0.0)1-1×(0.1.0.0.0)-11×(0.0.1.0.0)-21×(0.0.0.1.0)4-4∨8(1.1.0.0.0)00×(1.0.1.0.0)-10×所以，

Y*=（0.0.0.1.0），原问题的最优解为：X*

＝（0.0.1.0.0），Z*=84.4.2标准0-1整数规划的隐枚举法求解步骤7/16/2024504.5指派问题7/16/2024514.5.1指派问题模型7/16/2024524.5.1指派问题模型7/16/2024534.5.1指派问题模型7/16/202454

指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法，即系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。第一步：变换指派问题的系数矩阵（cij）为(bij)，使在(bij)的各行各列中都出现0元素，即

(1)从（cij）的每行元素都减去该行的最小元素；

(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。4.5.2匈牙利法7/16/202455第二步：进行试指派，以寻求最优解。

在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎。然后划去◎所在列(行)的其它0元素，记作Ø；这表示这列所代表的任务已指派完，不必再考虑别人了。

(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎所在行的0元素，记作Ø．

(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。4.5.2匈牙利法7/16/202456(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。第三步：作最少的直线覆盖所有0元素。

(1)对没有◎的行打√号；

(2)对已打√号的行中所有含Ø元素的列打√号；

(3)再对打有√号的列中含◎元素的行打√号；4.5.2匈牙利法7/16/202457(4)重复(2)，(3)直到得不出新的打√号的行、列为止；

(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若l＝m<n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。4.5.2匈牙利法7/16/202458例4.11

有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁59824.5.2匈牙利法7/16/202459第一步，变换系数矩阵：－5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3<n=44.5.2匈牙利法7/16/202460第三步，作最少的直线覆盖所有0元素：◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；

第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：4.5.2匈牙利法7/16/202461000000得到4个独立零元素，所以最优解矩阵为：◎◎◎ØØ√√√◎◎◎ØØ◎◎◎ØØ◎Z=154.5.2匈牙利法7/16/202462在实际应用中，常会遇到各种非标准形式的制派问题。一般的处理方法是先将其转化为标准形式，然后再用匈牙利法求解。最大化指派问题——设最大化指派问题系数矩阵C=(cij)，其中最大元素为m。令矩阵B=(bij)=(m-cij)，则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同最优解。人数和事数不等的指派问题——若人少事多，则添加一些虚拟的“人”，其费用系数取0，若人多事少，则添加一些虚拟的“事”，其费用系数取0。一个人可做几件事的指派问题——若某个人可以做几件事，则将该人化作几个“人”来接受指派。这几个“人”做同一件事的费用系数当然都一样。某事一定不能由某人做的指派问题——若某事一定不能由某人做，则可将相应的费用系数取为足够大的数M。4.5.3非标准形式的指派问题7/16/202463例4.12

从甲、乙、丙、丁、戊五人中选四人去完成四项任务，每人完成各项任务的时间如下表。规定每人只能完成一项任务。由于某种原因，甲必须被分配一项任务，丁不承担第4项任务，试确定总花费时间最少的分派方案。人任务甲乙丙丁戊11023159251015243155147154201513684.5.3非标准形式的指派问题7/16/202464解：增加虚设任务5，各人该项任务时间为0，某人不完成某任务时，取时间M（充分大的时间）：人任务甲乙丙丁戊110231