运筹学胡运权第五版课件

第4章整数规划与分配问题IntegerProgrammingandAssignmentProblem§4.1整数规划的特点与作用例

某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获利润及托运时所受的限制如下表所示，问如何托运能使总收益最大？货物体积(米3/箱)重量(吨/箱)利润(千元/箱)甲乙2 2 33 1 214（米3）9（吨）托运限制解：建模如下设托运甲货物x1箱，乙货物x2箱2、整数规划的一般形式1、整数规划（IntegerProgramming）决策变量部分或全部取值为整数的线性规划问题，称为整数线性规划或简称整数规划，常记为IP。纯整数规划

所有决策变量要求取非负整数。混合整数规划

只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。3、整数规划的分类例如该问题是纯整数规划.在整数规划IP中去掉变量取整限制得到的线性规划问题称为松弛问题，常用L0表示。4、整数规划的松弛问题例求解下列整数线性规划。解：其松弛问题为先求松弛问题的最优解；再用四舍五入的方法求整数规划的最优解24624(3.25,2.5)x1x22x1+3x2=142x1+x2=93x1+2x2=6松弛问题的最优解ABCD取整得到4个整数解：A(3,2)B(4,2)C(4,3)D(3,3)不可行可行解,此时z=13但A不是该整数规划的最优解！P该问题共有19个整数可行解,注意：可行域不是凸集！其中P(4,1)是最优解

zmax=145、整数规划IP与其松弛问题L0的关系若L0无可行解，则IP无可行解；若L0有整数最优解，则IP有相同的最优解；若L0有非整数最优解，则IP的最优解不能确定。注意：求解IP时，不能通过先解L0再通过凑整的方法进行；

IP的可行域不再是凸集。6、0-1变量（逻辑变量）取值只能为0或者1的决策变量。注意：0-1变量通常用来表示只有两种结果的选择性决策。7、0-1变量在实际问题中的应用管理问题整数线性规划引入0-1变量

0－1规划所有决策变量只能取0-1变量。（1）表示选择性约束例用0-1变量将表示成一般线性约束条件。8、0-1变量在表示线性约束条件中的应用一般的，已知m个约束条件若只有k个起作用，则（2）表示选择性取值例用0-1变量将表示成一般线性约束条件。一般的，若约束条件的右端项（或变量x）只能取r个值b1,b2,…,br中的一个值（3）表示两组条件中仅有一组满足例用0-1变量将表示成一般线性约束条件。§4.2分配问题及匈牙利法2-1问题的提出与数学模型例有一份说明书，要分别翻译成英、日、德、俄四种文字，交给甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交给其中一个人完成，每个人只能完成其中一项工作。问：如何分配，能使所需的总时间最少？译英译日译德译俄甲215134乙1041415丙9141613丁78119人工作解:建立如下模型设

xij=10甲：x11+x12+x13+x14=1乙：x21+x22+x23+x24=1丙：x31+x32+x33+x34=1丁：x41+x42+x43+x44=1译英：x11+x21+x31+x41=1译日：x12+x22+x32+x42=1译德：x13+x23+x33+x43=1译俄：x14+x24+x34+x44=1xij

=0或1(i=1,2,3,4;j=1,2,3,4)minz=aijxij i=1j=144第i个人完成第j项工作第i个人不完成第j项工作用aij表示第

i个人完成第j项任务的时间

有m项工作要交给m个人完成，规定每项工作只能交给其中一个人完成，而每个人只能完成其中一项工作。问：如何分配，可使所需的总时间最少？（或总效率最高？）1、分配问题或指派问题（AssignmentProblem）2、分配问题的已知条件m个人，用i=1,2,…,m表示；

m项工作，用j=1,2,…,m表示；

aij为第i个人完成第j项工作所需花费的资源（即时间或效率）将m阶矩阵（aij）称为该分配问题的效率矩阵（此处效率也包括时间），此时该问题称为m阶分配问题。3、分配问题的表格形式

工作人12…m1a11a12…a1m2a21a22…a2m......mam1am2…amm4、标准分配问题求目标函数的极小值效率矩阵的元素全非负aij≥05、标准分配问题的数学模型第i个人完成一项工作第j项工作由一个人完成分配问题是0-1整数规划的特例，也是运输问题的特例。分配问题一定有最优解。2-2匈牙利法4(0)5654(0)5763(0)(0)562例已知某分配问题的效率矩阵如右：1、特殊情况在标准形式的分配问题中，若m阶效率矩阵中存在m个不同行不同列的0元素（称之为独立的0元素），则令这些0元素对应位置上的变量的值为1，其他变量的值为0，得到该问题的最优解。2、基本原理（1）如果从效率矩阵[aij]的每一行元素中分别减去(或加上)一个常数（称之为行位势，记做ui

）,或者从每一列中分别减去(或加上)一个常数（称之为列位势，记做vj）,得到一个新的效率矩阵[bij],其中bij=aij-ui-vj,则以[bij]为效率矩阵的最优解等价于以[aij]为效率矩阵的最优解.（2）系数矩阵中独立0元素的最多个数=能够覆盖所有0元素的最少直线数。定理（1）的证明以[aij]为效率矩阵的目标函数值：z0=aijxij以[bij]为效率矩阵的目标函数值：

z=bijxijmmi=1j=1i=1j=1mm∵

bij=aij-ui-vj∴z=(aij-ui-vj)xij=aijxij-uixij

-vjxij

=z0-uixij-

vjxijmmmmmmmmmm=z0-ui-vj=z0-常数mmi=1j=1i=1j=1i=1j=1i=1j=1i=1j=1j=1i=1i=1j=1mm故以[bij]为效率矩阵的分配问题的最优解等价于以[aij]为效率矩阵的分配问题的最优解.3、匈牙利法由匈牙利数学家克尼格（Konig）建立的用于求解分配问题的计算方法。4、匈牙利法的步骤第一步造0：变换效率矩阵，使每行每列至少有一个0找出每行最小元素（即该行的行位势ui），从该行各元素中减去ui找出每列最小元素（即该列的列位势vj），从该列各元素中减去vj

第二步划直线：计算独立0元素的个数②、逐列检查若该列只有一个未标记的0，对其加()标记（表明这项工作必须由对应的人完成），同时划一条直线覆盖该行的所有元素（表明此人不能再完成其他工作）。否则轮空，转下一列检查，直到所有列检查完；①、逐行检查若该行只有一个未标记的0，对其加()标记（表明这个人必须对应的工作），同时划一条直线覆盖该列的所有元素（表明此项工作不能再由其他人完成）。否则轮空，转下一行检查，直到所有行检查完；③、在未被直线覆盖的元素中重复①②，直至再划不出这样的直线，转入④。④、可能出现三种情况： 情况1：打（0）的个数=m，即每行均有（0），则令（0）对应的变量xij=1，其他变量=0，得到该问题的最优解，计算总时间，结束。 情况2：打（0）的个数<m，且未被直线覆盖的0元素构成闭回路，则沿该回路对每个间隔的0打（），同时划去该0所在的一列。情况3：打（0）的个数<m，且所有0元素均被直线划去。出现僵局，转入第三步。000000第三步

打破僵局：使未划去的元素中出现新的0元素①

从未被直线覆盖的元素中找出一个最小的元素，用k表示； ②逐行检查，若该行有直线覆盖，则令行位势ui=0，否则令ui=k； ③逐列检查，若该列有直线覆盖，则令列位势vj=-k,否则令vj=0；④在现有效率矩阵中减去行位势和列位势，得到新的效率矩阵，转入第二步。“横线为0”“竖线负k”21513410414159141613781192497ui01311260101105740142vj

004201370606905320100例用匈牙利法求解下列分配问题。（1）最优分配甲乙丙丁译俄译日译英译德减去ui减去vj总时间zmin=4+4+9+11=28小时210971541481314161141513924114ui0875110104235001195vj

00500825110542300011452202-2-200080311032450001123（2）减去ui减去vj出现僵局，取K=2减去ui减去vj最优分配人1234工作3241总时间zmin=9+4+11+4=28例已知分配问题的效率矩阵如下，试求总效率最高的分配方案。

工作人一二三136227143365例求解下列分配问题。

工作人一二三四136262714433658464375524365762解：∵人数>工作数∴增加假想的工作，建立标准分配问题如下：

工作人一二三四五六136260027144003365800464370055243006576200最优分配人123456工作三二一四总时间zmin=2+1+3+2=8（1）任务E必须完成,其他4项任务可任选3项完成.（2）其中有1人完成2项,其他每人完成1项.（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲或乙或丁完成，且规定4人中丙或丁完成2项任务，其它每人完成1项。（1）任务E必须完成,其他4项任务可任选3项完成.其中有1人完成2项,其他每人完成1项.（3）任务A由甲或丙完成，任务C由丙或丁完成，任务E由甲或乙或丁完成，且规定4人中丙或丁完成2项任务，其它每人完成1项。例已知分配问题的效率矩阵如下，试求总效率最高的分配方案。

工作人一二三1362271433652-3两点说明1．人数与工作数不等的处理

当人数>工作数时：增加假想的工作，使得工作数与人数能够匹配,对应的效率设定为0。

当工作数>人数时：增加假想的人，使得人数与工作数能够匹配,对应的效率设定为0或M或其它。2．若目标函数为求max

z的处理（例如已知每个人完成各项工作的效率）令z=-z

等价于求解

minz

=∑∑(-aij)xiji=1j=1mm再利用第1个基本原理减去行（列）位势，化为效率矩阵非负的情形。§4.3分枝定界法二、分枝定界法用来求解整数线性规划的方法。一、整数线性规划（IP）的特征

1、可行域不是凸集；

2、可行解的个数是有限的；

3、当可行解个数不多时，可以用穷举法求解。三、原理

在求解某问题时，先放宽或取消其中某些约束，求解一个较简单的替代问题，而且总是保证原问题的可行域包含在替代问题的可行域中。四、步骤以纯整数规划为例，已知其松弛问题为：

第一步求解松弛问题（L0）先不考虑整数约束，解(

IP)的松弛问题(L0)，可能得到以下情况之一：①若(L0)无可行解，则(IP)也无可行解，结束。②若(L0)有最优解，并符合(IP)的取整条件，则(L0)的最优解即为(IP)的最优解，结束。③若(L0)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(L0)的最优解为：

第二步分枝与定界记(

IP)的目标函数最优值为Z*。以松弛问题（L0）的最优解X（0）对应的目标函数值Z0作为Z*

的上界。

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

（不为整数），以表示不超过的最大整数。构造两个约束条件

xr≤和xr≥＋1

将这两个约束条件分别加入问题(

L0

)，形成两个子问题(L1)和(L2)。注意：（L1）和（L2）的可行域之并集包含（IP)的全部可行解。

依次求解两个子问题（L1）和（L2），将出现两种情况：①某个子问题的最优解满足变量取整的要求，即为原（IP）的整数可行解，进入第三步；②两个子问题的最优解均非整数可行解，则选目标函数值较大的子问题继续分枝求解，直至出现某个子问题的最优解满足变量取整要求，即为原（IP）的整数可行解，进入第三步。

第三步比较与剪枝若出现两个或更多整数可行解，则仅保留目标函数值较大的一个。将各分枝的目标函数值与保留的整数可行解进行比较，并把目标函数值小于整数可行解的目标函数值的分枝剪去，将出现两种情况：①仅保留整数可行解，其他分枝均被剪去，则该整数可行解即为原（IP）的最优解，结束；②除保留整数可行解外，还有其他未被剪去的分枝，则取目标函数值最大的继续分枝，直至出现新的整数可行解，重复第三步。例用分枝定界法求解下列IP问题

图解法x1x2012345678910123456782x1+x2=72x1+4x2=13X（0）=(5/2,2)z0=23X（1）=(2,9/4)Z1=21X（2）=(3,1)Z2=22原IP的最优解原IP的松弛问题L0：

松弛问题的最优解为：x（0）=(5/2,2)T,Z0=23x12x13L0：z0=23x1=2.5，x2=2L1：z1=21L2：z2=22x1=2，x2=2.25x1=3，x2=1x1≤2x1≥3取原IP的最优解为舍松弛问题：

当存在若干变量有取整约束时，分枝既广且深，在最坏的情况下相当于组合所有可能的整数解。一般整数规划问题属于一类未解决的难题，称为NP-complete，只有少数特殊问题有好的算法，例如分配问题。

注意：

例求解下列整数线性规划。解：其松弛问题为24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解松弛问题：选x2=2.5分枝，引入条件x2≤2,x2≥3,得到两个子问题：24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解AB点A（3.5,2）为L1的最优解，此时z=14.5点B（2.5,3）为L2的最优解，此时z=13.5都不是原IP的可行解，取边界值较大的z=14.5，对x1=3.5继续分枝。选x1分枝，引入条件x1≤3,x1≥4,得到两个子问题：24624(3.25,2.5)x1x22x1+3x2=142x1+x2=9松弛问题的最优解AB点C（3,2）为L11的最优解，此时z=13点D（4,1）为L12的最优解，此时z=14都是原IP的可行解，取边界值较大的z=14，开始剪枝。CDL0：z0=14.75x1=3.25，x2=2.5L1：z1=14.5L2：z2=13.5L11：z3=13L12：z4=14x1=3.5，x2=2x1=2.5，x2=3x1=3，x2=2x1=4，x2=1x2≤2x2≥3x1≤3x1≥4舍舍取综上，原IP的最优解为L0：z0=14.75x1=3.25，x2=2.5L1：z1=43/3L2：z2=14L11：z3=13L12：z4=38/3x1=3，x2=8/3x1=4，x2=1x1=3，x2=2x1=2，x2=10/3x1≤3x1≥4x2≤2x2≥3舍舍取综上，原IP的最优解为本例也可以先对x1=3.25分枝：例用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取约束条件x1≤1，x1≥2将（IP）划分为（IP1）和（IP2）相应的，将（LP）划分为（LP1）和（LP2）x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是（IP）最小值的下限。即有：

下面求（LP1）和（LP2）的最优解。x1x2⑴⑵33(18/11,40/11)⑶

先求（LP1）,如图所示。此时B

在点取得最优解。x1＝1,x2=3,Z(1)＝－16找到整数解，问题已探明，此枝停止计算。11再求（LP2）

,如图所示。在C

点取得最优解。即x1＝2,x2=10/3,Z(2)

＝－56/3≈－18.7∵Z2<Z1＝－16∴原问题有比（－16）更小的最优解，但x2不是整数，故利用

3≤10/3≤4

加入条件。BAC加入条件：x2≤3,x2≥4有下式：下面求（LP3）和（LP4）的最优解。x1x2⑴⑵33(18/11,40/11)⑶11BAC先求（LP3）,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4<Z≈-19.8但x1＝12/5不是整数，可继续分枝。即2≤x1≤3。D再求（LP4），如图所示。无可行解，不再分枝。

在（LP3）的基础上继续分枝。加入条件x1≤2，x1≥3有：再求（LP5）和（LP6）的最优解。x1x2⑴⑵33(18/11,40/11)⑶11BACD先求（LP5）,如图所示。此时E

在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时F在点取得最优解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F

如对Z(6)

继续分解，其最小值也不会低于－15.5，问题探明,剪枝。

至此，原问题（IP）的最优解为：

x1=2，

x2=3,

Z*=Z(5)=－17以上的求解