运筹学-整数规划与分配问题PPT

第四章整数规划与分配问题整数规划的特点及作用分配问题与匈牙利法分枝定界法割平面法应用举例1ppt课件1整数规划的特点及应用在实际问题中，全部或部分变量取值必须是整数。比如人或机器是不可分割的，选择地点可以设置逻辑变量等。在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称纯整数规划；只要求一部分变量取整数值的，称为混合整数规划。2ppt课件对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解。当变量取值较小时，得到的解可能与实际整数最优解差别很大。若问题中整数变量的数目很大，则凑整方法的组合数目很多。3ppt课件

例1.

求下述整数规划问题的最优解解：如果不考虑整数约束（松弛问题）用图解法得考虑到整数约束，用凑整法求解时，比较四个点(4,3),(4,2),(3,3),(3,2)，前三个都不是可行解，第四个虽然是可行解，但z=13不是最优。实际问题的最优解为（4,1）这时z*=14。最优解为(3.25,2.5)。4ppt课件逻辑（0-1）变量在建立数学模型中的作用1.m个约束条件中只有k

个起作用设

m

个约束条件可以表示为：定义逻辑变量又设

M

为任意大的正数，则约束条件可以改写为：5ppt课件定义逻辑变量：此时约束条件可以改写为：2.约束条件的右端项可能是r个值中的某一个即6ppt课件3.两组条件满足其中一组

若x1≤4，则x2≥1（第一组条件）；否则当x1>4时，x2≤3（第二组条件）.

定义逻辑变量：又设M

为任意大正数，则问题可表达为：需注意，当约束为大于时，右端项中用减号。7ppt课件4.用以表示含固定费用的函数

用xj

代表产品j

的生产数量，其生产费用函数表示为其中

Kj

是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即8ppt课件定义逻辑变量（表示是否生产产品j）又设M

为任意大正数，为了表示上述定义，引入约束：显然，当xj>0时，yj=1。9ppt课件将目标函数与约束条件合起来考虑有：由此看出，当

xj=0时，为使z极小化，应有yj=010ppt课件2分配问题与匈牙利法一、问题的提出与数学模型

分配问题也称指派问题（assignmentproblem），是一种特殊的整数规划问题。假定有m项任务分配给m个人去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。在分配问题中，利用不同资源完成不同计划活动的效率常用表格形式表示为效率表，表格中数字组成效率矩阵。11ppt课件

例2.有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效率表如下：效率矩阵用[aij]表示，为12ppt课件定义逻辑变量则分配问题的数学模型写为：13ppt课件二、匈牙利法用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为1即可。匈牙利数学家克尼格（

Konig）求解分配问题的计算方法被称为匈牙利法，原理是如果效率矩阵所有元素aij>=0，而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的xij=1即为最优解。14ppt课件

定理1

如果从分配问题效率矩阵[aij]的每一行元素中分别减去（或加上）一个常数ui(被称为该行的位势)，从每一列分别减去（或加上）一个常数vj（被称为该列的位势），得到一个新的效率矩阵[bij]，若其中bij=aij-ui-vj，则[bij]的最优解等价于[aij]的最优解。

定理2

若矩阵A

的元素可分成“0”与非“0”两部分，则覆盖“0”元素的最少直线数等于位于不同行不同列的“0”元素的最大个数。AB甲35乙42AB甲02乙20AB甲03乙1015ppt课件

结合例2说明匈牙利法的计算步骤

第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。

第二步：找出矩阵每列的最小元素，分别从各列中减去。16ppt课件

第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确定能否找出

m

个位于不同行不同列的零元素的集合（该例中m=4），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。1.从第一行开始，若该行只有一个零元素，就对这个零元素打上（），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。17ppt课件2.从第一列开始，若该列只有一个零元素，就对这个零元素打上（）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。18ppt课件3.重复上述步骤1、2，可能出现三种情况：①效率矩阵每行都有打括号的零元素，只要对应这些元素令

xij=1就找到了最优解。②打括号的零元素个数少于

m

，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。19ppt课件③矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于

m

，这时转入第四步。

第四步：按定理1进行如下变换1.从矩阵未被直线覆盖的数字中找出一个最小的k

；2.对矩阵中的每行，当该行有直线覆盖时，令

ui=0，无直线覆盖的，令ui=k

；3.对矩阵中有直线覆盖的列，令vj=-k，对无直线覆盖的列，令vj=0；4.从原矩阵的每个元素aij中分别减去ui和vj。20ppt课件

第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方案。

由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为1，就得到最优解。

该问题中，最优值为：4+4+9+11=28h21ppt课件求下面所示效率矩阵的指派问题的最小解ABCDE甲127979乙89666丙71712149丁15146610戊4107109课堂练习22ppt课件

三、两点说明1.分配问题中人数和工作任务不相等时

当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。2.当问题目标变为求极大时可改写为

此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。23ppt课件§3分枝定界法分枝定界法(branchandboundmethod)是为了求解同整数规划具有类似性质的一大类问题而设计的一种较好的方法。结合例一来说明分枝定界法的思路和解题步骤：

例1.

求下述整数规划问题的最优解24ppt课件第一步：寻找替代问题并求解。放宽或取消原问题的某些约束，找出一个替代问题。若替代问题的最优解是原问题的可行解，这个解就是原问题的最优解，否则是源问题最优解的上界(求极大值)或下界(求极小值)。

例1对应的松弛问题L0其最优解为：最优值为：25ppt课件第二步：分枝与定界。将替代问题分成若干子问题，对子问题也要容易求解，且各子问题的解的集合要包含原问题的解集。然后对每个子问题求最优解，若满足原问题的约束，则找到原问题的可行解，否则该解为所属分枝的边界值；如果所有子问题的最优解均非原问题可行解，则选取边界值最大(求极大值)或最小(求极小值)的子问题再进一步细分子问题求解。分枝过程一直进行下去，直到找到一个原问题的可行解为止。如果计算中同时出现两个以上可行解，则选取其中最大(求极大值)或最小(求极小值)的一个保留。26ppt课件

将线性规划问题L0

分为两枝。

在L0

的最优解中，任选一个非整数变量，如x2=2.5；因x2

的最优整数解只可能是x2≤2或x2≥3，故在

L0中分别增加约束条件：加上约束条件x2≤2，记为L1；加上约束条件x2≥3，记为L2。27ppt课件L1

的最优解为：x1=3.5,x2=2,z=14.5L2

的最优解为：x1=2.5,x2=3,z=13.528ppt课件由于两个子问题的最优解仍非原问题的可行解，故选取最优值较大的子问题L1进行分枝，将分解为L11和L12

两个子问题。29ppt课件L11和L12

两个子问题的可行域为：L11

的最优解为：x1=3,x2=2,z=13L12

的最优解为：x1=4,x2=1,z=14这时两个问题获得的均为可行解，保留可行解中较大的一个30ppt课件第三步：剪枝，将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝剪去，如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解，否则回到第二步，选取边界值最优的一个继续分枝。如果计算又出现新的可行解，则与原可行解比较，保留最优的，并重复上述步骤。31ppt课件32ppt课件通过剪枝，求解得最优解为（4,1），最优解为14。用分枝定界法可求解纯整数规划问题和混合整数规划问题，比穷举法优越，但若变量数目很大，其计算量也相当客观。33ppt课件§4割平面法割平面法是求解整数规划问题最早提出的一种方法，1958年由Gomory提出，其基本思想是在整数规划问题的松弛问题中依次引进线性约束条件，称为(Gomory约束)，使问题的可行域逐步缩小，但每次切割只割去问题的部分非整数解，直到使问题的最优目标函数点成为缩小后可行域的一个顶点。34ppt课件

例1.

求下述整数规划问题的最优解第一步：把约束条件的系数化成整数，不考虑变量的整数约束35ppt课件加松弛变量，用单纯形法求解得最终单纯形表：x1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj-zj00-1/4-5/436ppt课件第二步：找出非整数解变量中分数部分最大的一个基变量，并写下该行约束：将常数写成整数与一个正的分数值的和；将整数项移到等式左端：37ppt课件38ppt课件39ppt课件

新约束条件只割去可行域部分非整数解，原有的整数解全部保留40ppt课件将Gomory约束加到G0得到新的线性规划问题G1，如下：41ppt课件第四步：重复第一至第三步一直到找出问题的整数最优解为止42ppt课件由于得到的解仍为非整数解，重复第二步43ppt课件44ppt课件45ppt课件