4运筹学整数规划.ppt

第四章整数规划整数规划问题的求解要比一般的线性规划困难本章将着重讨论1。一类特殊的整数规划——指派问题，它的数学模型和求解。2。求解整数规划方法——分枝定界法。匈牙利法源于匈牙利数学家康尼(D.K?nig)一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数.1955年，库恩（W.W.Kuhn）引用了0元素的定理提出了匈牙利法，用于求解指派问题。定理一：分派问题的效率矩阵A的每一行的元素中分别减去（或加上）一个常数ui（称为该行的位势）；每一列的元素中分别减去（或加上）一个常数vi（称为该列的位势）。得到一个新的矩阵B。如果矩阵A的元素aij与矩阵B的元素bij满足：bij=aij-ui-vi,则，A与B的最优解等价。注：本定理解决了不同问题的等价转换。像我们提示------可以将复杂的问题转换为简单问题来解定理一的解释：

设效率矩阵为：定理三：若矩阵A的元素分为“0”与非“0”二部分，则覆盖0元素的最小直线数是位于不同行、不同列的“0”元素的最大个数。注：解决了如何找到解矩阵的“1”元素的位置。得到最优解。下面，请阅读教材P114—例5.15。尝试理解匈牙利法解指派问题的过程。第二步：进行试指派以寻求最优解。为此按如下5个分步骤进行：（1）从只有一个0元素的行（列）开始，给这个0元素加圈，记为?。然后划去?所在的列（行）的其它0元素，记为?。这表示该列所代表的任务已指派完，不必再考虑别人。（2）给只有一个0元素的列的0元素加圈，记为?；然后划去?所在行的0元素，记为?。解：按第一、二步将系数矩阵进行变换：例：一登山队员做登山准备，他需要携带的物品有：食品，氧气，冰镐，绳索，帐篷，照相机和通讯设备，每种物品的重要性系数和重量如下：假定登山队员可携带最大重量为25公斤课堂练习P1255.85.9(1)第三种方法：1。应用一般单纯形法求解线性规划问题，2。如最优解是非整数解，则把原问题可行域分解成几个互不相交的可行域，可行域分解边界为整数边界，形成不同的可行域上子问题。若不可分解转3。3。对各子问题应用单纯形法求解，如求得的最优解是非整数解，则转2。若子问题最优解是整数解，则保留整数解。4。直到各子问题均有整数解，或不可再分，比较各子问题的整数解对应的目标函数值，函数值最优的，即为原问题的最优解。P1的x1具有整数解，x2还不具有整数解，还需进一步分解。P2的x1具有整数解，x2还不具有整数解，还需进一步分解4。重复。依列，不考虑划去的0，只有一个0的对0打圈，划去行213421345。按算法处理行数据减去势值2，0。3，5行减2，1，2，4行减021346。按算法处理行数据减去势值2，0。3，5行减2，1，2，4行减0。得到21347。按算法处理列数据减去势值-2，0。1列减-2，2，3，4，5列减0。21348。按算法处理列数据减去势值-2，0。1列减-2，2，3，4，5列减0。得到9。按算法要求，得到一个新的矩阵。重新依行依列划圈，与划线，见下。1239。按算法要求，已无法划圈，与划线。有闭回路，间隔划圈12345这时我们已经找到了n个不同行不同列的0元素，也就得到了例8问题的最优解，具体如下：由解矩阵可得最优指派方案是：甲?B乙?C丙?E丁?D戊?A本例还可得出另一个最优解：最优指派方案是：甲?B乙?D丙?E丁?C戊?A所需总时间为32。求极大化指派问题，只要经如下变换，仍可利用匈牙利算法进行求解。极大化指派问题例子如下：104814181520重要系数42126255重量设备相机帐篷绳索冰镐氧气食品物品7654321序号解：如果令xi=1表示登山队员携带物品i，xi=0表示登山队员不携带物品i，则问题表示成0-1规划:MaxZ=20x1+15x2+18x3+14x4+8x5+4x6+10x7s.t.5x1+5x2+2x3+6x