运筹学精品课件之整数规划

运筹学

Operations

ResearchChapter4整数规划IntegerProgramming1.整数规划的数学建模2.整数规划的求解算法

3.案例分析29一月2023第四章整数规划第一节整数规划的数学模型及解的特点第二节解纯整数规划的割平面法第三节分枝定界法第四节0-1型整数规划第五节指派问题29一月2023

在求解线性规划问题时，得到的最优解可能是分数或小数，但许多实际问题要求得到的解为整数才行。这种要求线性规划有整数解的问题，称为整数线性规划(IntegerlinearProgramming)。第一节整数规划的数学模型及解的特点29一月2023

例1

某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定服务员连续工作8小时为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。时段12345678服务员最少数目10891113853

设xi表示第i时段开始上班的人数29一月2023例2现有资金总额为B，可供选择的投资项目n个，项目j所需投资额和预期收益分别为aj和cj，此外，由于种种原因，有三个附加条件：（1）若选择1，则必须选择2，反之则不一定；（2）项目3和4至少选择一个；（3）项目5、6、7中恰好选择2个。应该如何选择项目，才能使总预期收益最大？设第i个项目为xi，则其有两种状态，选择投资（记为1）和不选择投资（记为0）。29一月2023例3工厂A1和A2生产某种物资。由于该种物资供不应求，故需再建一家工厂，相应的方案有A3和A4两个。这种物资的需求地有B1~B4四个。各工厂的生产能力、各地年需求量、各厂至各需求地的单位运费cij见下表。工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要决定应该建设A3还是A4，才能使每年的总费用（即全部物资运费和新工厂生产费用之和）最少。B1B2B3B4生产能力A12934400A28357600A37612200A44525200需求量35040030015029一月2023设xij表示第i个工厂供应给第j个需求的地的产量，y表示是否建设A3工厂（取1表示建设A3工厂，取0表示不建设A3工厂）29一月2023【例4】指派问题或分配问题。人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表5－3所示，如何安排他们的工作使总成绩最好。表5－3工作人员ABCD甲85927390乙95877895丙82837990丁8690808829一月2023

【解】此工作分配问题可以采用枚举法求解，即将所有分配方案求出，总分最大的方案就是最优解。本例的方案有4！＝4×3×2×1＝24种，当人数和工作数较多时，方案数是人数的阶乘，计算量非常大。用0－1规划模型求解此类分配问题显得非常简单。设数学模型如下：目标函数为29一月2023每项工作只能安排一人，约束条件为变量约束：要求每人做一项工作，约束条件为29一月2023引例

某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：货物集装箱体积(米3)重量(百斤)利润(百元) 甲5220乙4510托运限制2413问两种货物各装运多少箱，可使获得利润最大？29一月2023

是不是可通过把不考虑整数要求求得的最优解经过“化整”得到满足整数要求的最优解呢？设甲、乙两种货物装运箱数分别为x1和x2。显然，x1、x2都要求为整数,于是可建立整数规划模型：

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

x1,x2≥0(4)

x1,x2为整数(5)29一月2023

此例可解得x1=4.8,x2=0，凑整为x1=5,x2=0，这就破坏了条件(2)，因而不是可行解；如截断小数变为x1=4,x2=0，这当然满足所有约束条件，但不是最优解，因为对x1=4,x2=0有z＝80，而对x1=4,x2=1（也是可行解）有z＝90。29一月2023整数规划的数学模型若要求所有xj的解为整数，称为纯整数规划若要求部分xj的解为整数，称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的，最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解29一月2023第二节割平面法29一月2023考虑纯整数规划问题：设其中aij和bi皆为整数（若不为整数时，可乘上一个倍数化为整数）。29一月2023割平面法是R.E.Gomory于1958年提出的一种方法，它主要用于求解纯整数规划。割平面法是用增加新的约束来切割可行域，增加的新约束称为割平面方程或切割方程。其基本思路为：

若其松弛问题的最优解X*不满足整数约束，则从X*的非整分量中选取一个，用以构造一个线性约束条件，将其加入原松弛问题中，形成一个新的线性规划，然后求解之。若新的最优解满足整数要求，则它就是整数规划的最优解；否则重复上述步骤，直到获得整数最优解为止。29一月2023为最终获得整数最优解，每次增加的线性约束条件应当满足两个基本性质：（1）已获得的不符合整数要求的LP最优解不满足该线性约束条件，从而不可能在以后的解中出现；（2）凡整数可行解均满足该线性约束条件，因而整数最优解始终被保留在每次剩余的线性规划可行域中。

29一月2023例1用割平面法求解整数规划问题步骤1：标准化其松弛问题B029一月2023Cj1100CBXBbx1x2x3x411x2x17/43/401103/4-1/41/41/4cj-zj00-1/2-1/2引进一个割平面来缩小可行域，割平面要切去松弛问题的非整数最优解而又不要切去问题的的任一个整数可行解。用单纯形法求解：29一月2023步骤2：求一个割平面方程

1）在最终表上任选一个含有不满足整数条件基变量的约束方程。如选x1，则含x1的约束方程为

2）将所选择的约束方程中非基变量的系数及常数项进行拆分处理。具体规则是：将上述系数和常数项均拆分成一个整数加上一个非负真分数（纯小数）之和。则（3）式变为：29一月2023

3）将上述约束方程（4）重新组合。组合的原则是：将非负基变量系数及常数项中的非负真分数移到等号右端，将其他部分移到等号左端，即得：

等式左端实际上由三部分组成，常数项的整数部分，基变量及非基变量（含松弛变量或剩余变量），前两部分都是整数或应取整数，而松弛变量x3、x4由松弛问题标准型知，也应取非负整数（对于这一点，当原问题的约束方程组中的系数或常数项中有非整数时，要求将约束方程先化为成整数系数及整数常数项，然后再标准化，就可满足）。29一月2023很明显，（5）左端为整数，右端<3/4，则有其右端0，即4）将割平面方程加到松弛问题的约束方程中，构成新的松弛问题并求解（对偶单纯形法）。

29一月2023割平面方程

Cj11000CBXBbx1x2x3x4x5110x2x1x57/43/4-3/40101003/4-1/4-3/41/41/4-1/4001cj-zj00-1/2-1/20110x2x1x311101010000101/31/31-1/3-4/3cj-zj000-1/3-2/329一月20231、本题注只用一次割平面就求得了最优解，但大多数问题中不是只用一、二次割平面就能求得整数最优解。若一次割平面不能求得整数最优解，则按步骤2中的4个步骤，在松弛问题的最终单纯形表中找出第二个割平面方程，将此割平面方程加到伴随规划中，过程伴随规划，再用对偶单纯形法(单纯形法)求解。若求得了整数最优解，则停止计算，否则继续再作割平面，缩小可行域，直到求得整数最优解为止。注意：29一月20232、实际解题时，经验表明若从最终单纯形表中选择具有最大分数部分的非整分量所在行构造割平面约束，往往可以提高“切割”效果，减少“切割”次数。3、在用割平面法解整数规划时，常会遇到收敛很慢的情形，因此实际中通常不单独使用。29一月2023第三节分枝定界法29一月2023

分枝定界法(branchandboundmethod)是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数规划问题，也可用于混合整数规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。分枝定界法的主要思路是：首先求解整数规划的松弛问题，如果求得的最优解不符合整数条件，则增加新约束——缩小可行域；将原整数规划问题分枝——分为两个子规划，再解子规划的松弛规划┅通过求解一系列子规划的伴随规划及不断地定界，最后得到原整数规划问题的整数最优解。29一月2023分枝定界法的思路：

1.求整数规划的松弛问题最优解；

2.若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步；

3.任意选一个非整数解的变量xi，在松弛问题中加上约束xi≤[xi]及xi≥[xi]+1组成两个新的松弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界；29一月2023分枝定界法的思路：

4.

检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于（max）整数解的目标值，需要继续分枝，再检查，直到得到最优解。29一月2023

步骤1：用单纯形法求解松弛问题，得到最优解及最优值。

步骤2：分枝。例2解整数规划问题41/9>10/3,优先选择B1分枝。29一月2023无可行解61/14(B12)>10/3(B2),优先选择B12分枝。29一月20234>10/3，所以B2无需分枝。29一月2023【例3】用分枝定界法求解【解】先求对应的松弛问题（记为LP0）：用图解法得到最优解X＝（3.57,7.14）,Z0=35.7,如下图所示。29一月20231010松弛问题LP0的最优解X=(3.57,7.14),Z0=35.7x1x2oABC29一月20231010x1x2oABCLP1LP234LP1:X=(3,7.6),Z1=34.8LP2:X=(4,6.5),Z2=35.5①②29一月20231010x1x2oABCLP1LP334LP3:X=(4.33,6),Z3=35.336①②29一月20231010x1x2oACLP1346①②LP4:X=(4,6),Z4=34LP5:X=(5,5),Z5=355LP329一月2023尽管LP1的解中x1不为整数，但Z5>Z因此LP5的最优解就是原整数规划的最优解。分枝过程如图表示：LP0:X=(3.57,7.14),Z0=35.7LP1:X=(3,7.6)Z1=34.8LP2:X=(4,6.5)Z2=35.5x1≤3x1≥4LP3:X=(4.33,6)Z3=35.33x2≤6LP4:X=(4,6)Z4=34LP5:X=(5,5)Z5=35x1≤4x1≥5无可行解x2≥729一月2023

(1)用观察法求整数规划原问题R的一个可行解，其目标值便是R的最优目标值z*的一个下界z。

(2)求解松弛问题R0，若R0无可行解，则R也无可行解，结束；若得到R0的最优解x(0)和最优值z0。若x(0)符合R的整数条件，则显然x(0)也是R的最优解，结束；否则，以R0作为一个分枝标明求解的结果，z0是问题R的最优目标值z*的一个上界z。

分支定界法的步骤29一月2023

(3)分枝。取目标函数值最大的一个枝Rs，在Rs的解中任选一不符合整数条件的变量xj，其值为bj，构造两个约束条件xj≤[bj]和xj≥[bj]+1。将两个约束条件分别加入问题Rs，得两个后继规划问题Rs1和Rs2。不考虑整数条件求解这两个后继问题，以每个后继问题为一分枝标明求解的结果。分支定界法的步骤29一月2023

(4)定界。在各分枝中找出目标函数值最大者作为新的上界z；从已符合整数要求的各分枝中，找出目标函数值最大者作为新的下界z。

(5)比较与剪枝。各分枝的最优目标函数值中如果有小于z者，则剪掉这一枝（用打×表示），即以后不再考虑了。若已没有大于z的分枝，则已得到R的最优解，结束；否则，转(3)。29一月2023第四节0-1整数规划29一月2023

0-1型整数规划是整数规划的一种特殊形式，它的变量xj仅取值0或1。这种只能取0或1的变量称为0-1变量或二进制变量。29一月2023例1(含有互斥约束条件的问题)：设工序B的每周时约束条件为：0.3x1+0.5x2150，现还有一种新的加工方式,对应约束为：0.2x1+0.4x2120，两种加工方式只能选一种。互斥29一月2023如果有m个互相排斥的约束条件(≤型)：αi1x1+αi2x2+…+αinxn≤bi，i=1，2，…,m

为保证这m个约束条件只有一个起作用，我们引入m个0-1变量yi(i=1,2,…，m)和一个充分大的常数M，将约束条件改为如下形式：

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

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

y1+y2+…+ym=m−

1(5-14)显然，在m个yi中只有一个能取0值，设yi*=0，就只有i=i*这个约束条件起作用，而别的式子都是多余的。29一月2023例2(固定费用问题)：三种资源被用于生产三种产品，资源量、单件可变费用、售价、资源单耗量以及固定成本见右表，制定一个生产计划使总收益最大。产品1产品2产品3资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价8101229一月2023

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

(1)只要发现某个变量组合不满足其中一个约束条件时，就不必再去检验其他约束条件是否可行。

(2)若已发现一个可行解，则可根据它的目标函数值产生一个过滤条件，对于目标函数值比它差的变量组合就不必再去检验它的可行性；在以后的求解中每当发现更好的可行解就替换原来的过滤条件。0-1型整数规划的解法29一月2023例3求解0－1整数规划(x1，x2，x3)z值约束条件（1）

（3）

（4）

（5）过渡条件（0，0，0）（0，0，1）（0，1，0）（0，1，1）（1，0，0）（1，0，1）（1，1，0）（1，1，1）05-233816√√√√√√√√√√√√z0z5z8若将目标函数系数按小到大排列：maxz=-2x2+3x1+5x3，计算量大减。29一月2023第五节指派问题29一月2023指派问题的标准形式及其数学模型匈牙利解法求解指派问题一般的指派问题29一月2023有n项任务，恰好n个人承担，第i人完成第j项任务的花费(时间或费用等)为cij，要求确定人和事之间的一一对应的指派方案，使总花费最省？一、指派问题的标准形式及其数学模型指派问题的系数矩阵如下：Cij的含义可以不同，如费用、成本、时间等。29一月2023为建立标准指派问题的数学模型，引入n×n个0-1变量：指派问题的数学模型可写成如下形式：1若派第i人做第j事0若不派第i人做第j事（ij=1，2,…，n）第j项工作由一个人做第i人做一项工作29一月2023指派问题的每个可行解，可用矩阵表示如下：矩阵X中，每行各元素中只有1个元素为1，其余各元素等0；每列各元素中也只有1个元素为1，其余各元素等0。指派问题有n！个可行解。29一月2023例4有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表。问应指派何人去完成何工作，使所需总时间最少？29一月2023指派问题的数学模型如下：29一月2023已知条件可用系数矩阵（效率矩阵）表示为：其可行解也可用每行仅有一个1，每列也仅有一个1的矩阵表示，如：29一月2023二、匈牙利法解题步骤

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

标准指派问题是一种特殊的整数规划问题，又是特殊的0-1规划问题和特殊的运输问题。29一月2023

匈牙利解法的关键是利用了指派问题最优解的如下性质：若从指派问题的系数矩阵C的某行（或某列）各元素分别减去一个常数k，得到一个新的矩阵C’，则以C’和C为系数矩阵的两个指派问题有相同的最优解。（系数矩阵的变化并不影响数学模型的约束方程组，而只是目标函数值减少了常数k，所以最优解不变）二、匈牙利法解题步骤29一月2023-2-4-9-7

若某行(列)已有0元素，那就不必再减了。例1的计算为：1.使系数矩阵各行、各列出现零元素作法：系数矩阵各行元素减去所在行的最小元素，再从所得矩阵的各列减去所在列最小元素。(因一行中xij

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

同时减去一常数不影响xij取值)。匈牙利法解题步骤如下：29一月2023-4-2这就保证每行每列至少有一个0元素，同时不出现负元素。29一月2023

2.试求最优解作法：由独立0元素的行（列）开始，独立0元素处右上角画“*”标记，在有“*”

的行列中划去其它0元素；再在剩余的0元素中重复此做法，直至不能标记

“*”为止。29一月2023（1）当遇到在所有的行和列中，0元素都不止一个时（存在0元素的闭回路），可任选其中一个0元素加圈，同时划去同行和同列中其他0元素。（2）如能找出n个位于不同行不同列的零元素，令对应的xij=1，其余xij=0，得最优解，结束；否则，看下面的例题转第3步。29一月2023例5求表中所示效率矩阵的指派问题的最小解。

任务人ABCDE甲127979乙89666丙71712149丁