整数线性规划

整数规划是数学规划的一个重要分支,可分为:纯整数规划(所有变量都限制为整数)、混合整数规划(一部分变量限制为整数)、0-1规划(所有变量都限制取0或1).

本章讨论纯整数线性规划(ILP)及解此规划的割平面法和分枝定界法；分配问题(0-1规划)与匈牙利算法.4.1整数规划的特点及作用4.2分配问题与匈牙利算法4.3割平面法4.4分枝定界法第4章整数规划与分配问题1§4.1整数规划的特点及作用4.1.1整数规划的模型分类

纯整数规划模型

0-1整数规划模型

混合整数规划模型4.1.2逻辑变量在建模中的作用4.1.3实例

投资决策问题

背包问题4.1.4解整数线性规划的困难性2纯整数规划模型0-1整数规划模型混合整数规划模型4.1.1整数规划的模型分类34.1.2逻辑变量在建模中的作用1.m个约束条件中只有k个起作用

m个约束条件可表为

定义又M为任意大的正数，则在约束条件≤的右端+M(即yi=1),此条件不起作用42.约束条件的右端项可能是r个值(b1,b2,…,br)中的某一个,

定义上述约束条件(*)可表示为即53.两组条件中满足其中一组

定义又M为任意大的正数，则问题可表述为在约束条件≤的右端+M(即yi

=1),此条件不起作用在约束条件≥的右端-M(即yi

=1)，此条件不起作用64.用以表示含有固定费用的函数若将(1)(2)表达为7【例1】试引入0－1变量将下列各题分别表达为一般线性约束条件（1）x1+x2≤6或4x1+6x2≥10或2x1+4x2≤20（2）若x1≤5，则x2≥0，否则x2≤8（3）x2取值0，1，3，5，7【解】（1）3个约束只有1个起作用或yi=1此条件不起作用yi=0此条件不起作用8（3）右端常数是5个值中的1个（2）两组约束只有一组起作用或或9

(1)投资组合问题1.问题某财团有B万元的资金,经出其考察有n个项目可供投资,其中第j个项目需投资金额为bj万元,预计5年后获利cj万元,问应如何选择项目使得5年后总收益最大？变量约束目标2.分析3.数学模型4.1.3实例0-1整数线性规划—总金额不超过限制—总收益最大101.背景旅行背包容量一定的背包里装尽可能多的物品(2)背包问题某人出国留学打点行李,现有三个旅行包,容积大小分别为1000毫升、1500毫升和2000毫升,根据需要列出需带物品清单,其中一些物品是必带物品共有7件,其体积大小分别为400、300、150、250、450、760、190、(单位毫升).尚有10件可带可不带物品,如果不带将在目的地购买,通过网络查询可以得知其在目的地的价格(单位美元).这些物品的容量及价格分别见下表,试给出一个合理的安排方案把物品放在三个旅行包里.

物品12345678910体积200350500430320120700420250100价格15451007050752009020302.问题113.问题分析变量—对每个物品要确定是否带,同时还要确定放在哪个包裹里，设变量xij为第i个物品是否放在第j个包裹中约束包裹容量限制必带物品限制选带物品限制目标函数未带物品购买费用最小12模型13特征—变量为整数来源—问题本身的要求;引入的逻辑变量的需要性质—可行域是离散集合4.1.4解整数线性规划的困难性与线性规划的关系：整数规划前者的可行解是松弛问题的可行解前者的最优值小于等于松弛问题的最优值松弛的线性规划问题对于min问题,前者的最优值大于等于松弛问题的最优值14最优解不一定在顶点上达到.最优解不一定是松弛问题最优解的邻近整数解.整数可行解的个数远多于松弛问题的顶点,枚举法不可取.解ILP问题要远难于解松弛的LP问题.若松弛的LP问题无解,则原ILP问题无解.反之,不一定成立.结论15§4.2分配问题与匈牙利算法4.2.1分配问题的数学模型4.2.2匈牙利算法164.2.1分配问题的数学模型分配问题(指派问题)

假定有m项任务分配给m个人去完成,并指定每人完成其中一项,每项只交给其中一个人去完成,应如何分配使总的效率最高.效率矩阵：利用不同资源完成不同计划活动的效率通常用表格形式表示，表格中的数字组成效率矩阵.举例有一份说明书,要分别译成英、日、德、俄四种文字,交甲乙丙丁四个人去完成.因各人专长不同,他们完成翻译不同文字所需的时间如表所示.应如何分配,使这四人分别完成这四项任务总的时间最小.效率矩阵

译成英文译成日文译成德文译城俄文甲21097乙154148丙13141611丁415139工作人一一对应17人工作a1a2aiamb1b2bjbmxi1

xi2

xij

xim-1

xim

x1jxij

x2jxm-1jxmj

分配问题的数学模型:第i人完成一项任务第j项任务由一人完成184.2.2匈牙利算法事实：若效率矩阵的所有元素,而其中存在一组位于不同行其余的逻辑变量xij=0,

得到的就是问题的最优解(最优分配方案).例效率矩阵为令问题：如何产生并寻找这组位于不同行不同列的零元素？不同列的零元素，则只要令对应于这些零元素位置的逻辑变量xij=1,

，其余的xij=019匈牙利数学家克尼格(Konig)基础：两个基本定理定理1如果从分配问题效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数ui(被称为该行的位势),从每一列分别减去(或加上)一个常数vj(被称为该列的位势),得到一个新的效率矩阵[bij],其中bij=aij-ui-vj

,则[bij]的最优解等价于[aij]的最优解。作用：构造含有零元素的等价效率矩阵。定理2若矩阵A的元素分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数.作用：判别效率矩阵中有多少个不同行不同列的零元素。20匈牙利算法的步骤：第一步：找出效率矩阵每行的最小元素,并分别从每行中减去最小元素.minmin产生含零的等价效率矩阵每行至少一个0元素每列也至少一个0元素第二步：再找出矩阵每列的最小元素,再分别从各列中减去.21第三步：判定由前两步得到的效率矩阵中有多少个不同行不同列的零元素.按照以下准则进行：

(1)从第一行开始,若该行只有一个零元素,就对这个零元素打上()号,对打()号零元素所在列画一条直线.

(2)从第一列开始,若该列只有一个零元素就对这个零元素打上()号(同样不考虑已划去的零元素),对打()号零元素所在行画一条直线.若该行没有零元素或有两个以上零元素(已划去的不计在内),则转下一行,依次进行到最后一行.若该列没有零元素或有两个以上零元素(已划去的不计在内),,则转下一列,依次进行到最后一行.

(3)重复(1)、(2)两个步骤,直至不能进行为止，()()()22231效率矩阵每行(或每列)都有一个打()号的零元素,令对应打()号零元素的xij=1,就找到了问题的最优解.打()号的零元素个数小于m,但未被划去的零元素之间存在闭回路,打()号的零元素个数小于m,但矩阵中所有零元素被划去或打上()号.()()()

(3)重复(1)、(2)两个步骤,直至不能进行为止，可能出现三种情况:然后对所有打()号的零元素,或所在行,或所在列，画一条直线.重复(1)、(2)两个步骤，直至不能进行为止。这时可顺着闭回路的走向,对每个间隔的零元素打()号,此时转第四步。23第四步：为设法使每一行都有一个打()号的零元素，需要继续按定理1对矩阵进行变换：

(1)从矩阵未被直线覆盖的数字中找出一个最小的数字k;

(2)对矩阵的每行,当该行有直线覆盖时令ui=0,无直线覆盖的令ui=k

(3)对矩阵的每列,当该列有直线覆盖时令vj=-k,无直线覆盖的令vj=0.

(4)从原矩阵的每个元素aij中分别减去ui和vj,得到一个新的矩阵,转第五步。第五步：返回到第三步,反复进行,一直到矩阵的每一行都有一个打号的零元素为止,即找到了最优分配方案.()()()()()()()24说明：1)第三步中的第二种结果2打()号的零元素个数小于m,但未被划去的零元素之间存在闭回路,这时可顺着闭回路的走向,对每个间隔的零元素打一()号,然后对所有打()号的零元素,或所在行,或所在列画一条直线.()()()()()()或()()()()()()()()或()25例()()()()()(1)(2)()()()()()()()()()()()()()()得到答案()()()()26说明：2.分配问题中如果人数和任务数不相等时的处理方法.(2)人数<任务数(1)人数>任务数工作人IIIIII13252746336345355652仍规定每人完成一项工作,每项工作只交给一个人去完成

增添两项假想的工作任务,每个人完成这两项任务时间为零.IVV0000000000工作人IIIIIIIV1325227463336354000027minmin()()()()()3.目标函数为的处理方法.minmin284.3Gomory割平面法

割平面法是求解整数规划的一个最早提出的方法,1958年由高莫雷(Gomory)提出.

基本思想是在与整数规划相对应的线性规划中逐步增加线性约束条件(称为割平面),使线性规划的可行域缩小,同时保持整数规划的可行解集合不变;

然后求解增加约束后的线性规划,如果得到整数的最优解则停止;如果没有找到整数最优解,就再增加割平面,一直到得到或证明线性规划无整数最优解为止.29割平面法的解题步骤：第一步：把问题中所有约束条件的系数均化为整数,解该问题的松弛问题G0.若得到的是整数解,得到了原问题的最优解，否则转第二步.构造Gomory约束.第二步：将Gomory约束加到G0中得到新的线性规划问题G1.第三步：重复第一至第三步直到找出问题的整数最优解为止.第四步：30例用割平面法求下述整数规划的最优解解：替代问题最终单纯形表cj

→3200CB基bx1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj

-zj

00-1/4-5/4

找出非整数解变量中分数部分最大的一个基变量，并写下这一行的约束

将上式中所有常数分写成整数与一个正分数之和得，31将整数、分数进行分离,得因左端为整数,故右端也需取整数，故又,故加上松弛变量后得(I)或(II)就是要寻找的Gomory约束因将(III)代入(I)并化简得(I)和(IV)等价32cj

→3200CB基bx1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj

-zj

00-1/4-5/40x500100x5-1/200-1/2-1/2[]2x22010-113x17/21001-1/20x310011-2cj-zj000-1-1/2得到新的Gomory约束加上松弛变量后得33320000x1x2x3x4x5x62x22010-1103x17/21001-1/200x310011-200x6-1/20000-1/21cj-zj000-1-1/20[]2x21010-1023x1410010-10x3300110-40x5100001-2cj-zj000-10-1344.4分枝定界法分枝定界法是一种隐枚举法，是借助于一种“巧妙”地枚举整数规划问题的可行解的思想来设计算法的，其关键步骤是分枝和定界。分枝定界法可用于解纯整数或混合的整数规划问题。上世纪六十年代初由LandDoig

和Dakin等人提出。由于这种方法灵活且便于用计算机求解，所以现在它是解整数规划的主要方法。35分枝定界法的解题步骤：第一步：寻找替代问题并求解.放宽或取消原问题的某些约束若替代问题的最优解是原问题的可行解,则此解就是原问题的最优解.寻找替代问题的方法：替代问题的要求：易求解;包含原问题的解.否则,此解的目标函数值就是原问题最优值的上界(求极大)或下界(求极小).例求下述整数规划的最优解替代问题L0的最优解(3.25,2.5),不是原问题的可行解,转第二步.原问题对替代问题的解进行判定36第二步：分枝与定界若子问题的最优解满足原问题的约束，则该解是原问题的可行解.(1)替代问题的最优解不是原问题的可行解时，将替代问题分成两个子问题(分枝)。子问题的要求：易求解;各子问题解的集合包含原问题的解否则,该解对应的目标值为所属分枝的边界值(对求极大问题为上界或对求极小问题为下界).(2)若所有子问题的最优解均非原问题的可行解，则取边界值最大(求极大)或最小(求极小)的子问题进一步细分求解,直到找到一个原问题的可行解为止.出现下述三种情况时需要分枝：概念：(3)存在子问题的边界值大于可行解的目标值时，需要对该子问题进行分枝。可行解的目标值确定了一个上界，即待剪去子问题的一个上界。37(3.25,2.5),z=14.75(3.5,2),z=14.5(2.5,3),z=13.5(3,2),z=13(4,1),z=1438第三步：定界与剪枝

如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解.(1)分枝后出现一个可行解时，将边界值与可行解的目标值进行比较，把边界值劣于可行解的分枝剪去。(2)分枝后出现两个以上的可行解，选取其中目标值最大的一个可行解保留，其余分枝剪去。然后将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去.第四步：判断是否最优解否则，返回第二步，选取边界值最优的一个继续分枝，定界，剪枝，判断。需要剪枝的两种情况：39(3.25,2.5),z=14.75(3.5,2),z=14.5(2.5,3),z=13.5(3,2),z=13(4,1),z=1440【例1】

用分枝定界法求下述混合整数规划的最优解解：(3.25,2.5),z=14.75(3