运筹学整数规划与分配问题课件.ppt

1、整数规划的特点及作用整数规划的特点及作用分配问题与匈牙利法分配问题与匈牙利法分枝定界法分枝定界法割平面法割平面法应用举例应用举例在实际问题中，全部或部分变量取值必须是整数。比如人在实际问题中，全部或部分变量取值必须是整数。比如人或机器是不可分割的，选择地点可以设置逻辑变量等。或机器是不可分割的，选择地点可以设置逻辑变量等。在一个线性规划问题中要求全部变量取整数值的，称纯整在一个线性规划问题中要求全部变量取整数值的，称纯整数线性规划或简称数线性规划或简称纯整数规划纯整数规划；只要求一部分变量取整；只要求一部分变量取整数值的，称为数值的，称为混合整数规划混合整数规划。对整数规划问题求解，有人认为可

2、以不考虑对变量的整数对整数规划问题求解，有人认为可以不考虑对变量的整数约束，作为一般线性规划问题求解，当解为非整数时，用约束，作为一般线性规划问题求解，当解为非整数时，用四舍五入或凑整方法寻找最优解。四舍五入或凑整方法寻找最优解。当变量取值较小时，得到的解可能与实际整数最优解差别当变量取值较小时，得到的解可能与实际整数最优解差别很大。很大。若问题中整数变量的数目很大，则凑整方法的组合数目很若问题中整数变量的数目很大，则凑整方法的组合数目很多。多。例例1.求下述整数规划问题的最优解求下述整数规划问题的最优解且均取整数值 ,0,5.45.0 143 223max21212121xxxxxxxxz解

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

4、以表示为：个约束条件可以表示为：),1(1mibxainjjij定义逻辑变量定义逻辑变量个约束条件起作用，假定第个约束条件不起作用，假定第 0 1iiyi又设又设 M 为任意大的正数，则约束条件可以改写为：为任意大的正数，则约束条件可以改写为：kmyyyMybxamiinjjij211定义逻辑变量：定义逻辑变量：，其它，假定约束右端项为01iiby此时约束条件可以改写为：此时约束条件可以改写为：12111rriiinjjijyyyybxa2.约束条件的右端项可能是约束条件的右端项可能是 r 个值中的某一个个值中的某一个rnjjijbbbxa或或或211即即3.两组条件满足其中一组两组条件满足其

5、中一组 若若 x14，则，则 x21（第一组条件第一组条件）；否则当）；否则当 x14 时，时，x23（第二组条件第二组条件）.定义逻辑变量：定义逻辑变量：）（组条件起作用，第组条件不起作用，第2,1 0 1iiiyi又设又设 M 为任意大正数，则问题可表达为：为任意大正数，则问题可表达为：134142122211211yyMyxMyxMyxMyx需注意，当约束需注意，当约束为大于时，右端为大于时，右端项中用减号。项中用减号。4.用以表示含固定费用的函数用以表示含固定费用的函数 用用 xj 代表产品代表产品 j 的生产数量，其生产费用函数表示为的生产数量，其生产费用函数表示为)0(0)0()(

6、jjjjjjjxxxcKxC其中其中 Kj 是同产量无关的生产准备费用，问题的目标是使是同产量无关的生产准备费用，问题的目标是使所有产品的总生产费用为最小，即所有产品的总生产费用为最小，即njjjxCz1)(max定义逻辑变量（表示是否生产产品定义逻辑变量（表示是否生产产品 j）0001jjjxxy，又设又设 M 为任意大正数，为了表示上述定义，引入约束：为任意大正数，为了表示上述定义，引入约束：jjMyx 显然，当显然，当 xj 0 时，时，yj=1。将目标函数与约束条件合起来考虑有：将目标函数与约束条件合起来考虑有：1 00min1或jjjnjjjjjyMyxyKxcz由此看出，当由此看出

7、，当 xj=0 时，为使时，为使 z 极小化，应有极小化，应有 yj=0一、问题的提出与数学模型 分配问题分配问题也称也称指派问题指派问题（assignment problem），是一），是一种特殊的整数规划问题。假定有种特殊的整数规划问题。假定有 m 项任务分配给项任务分配给 m 个人个人去完成，并指定每人完成其中一项，每项只交给其中一个去完成，并指定每人完成其中一项，每项只交给其中一个人去完成，应如何分配使总的效率为最高。人去完成，应如何分配使总的效率为最高。如果完成任务的效率表现为资源消耗，考虑的是如何分配如果完成任务的效率表现为资源消耗，考虑的是如何分配任务使得目标极小化；如果完成任务

8、的效率表现为生产效任务使得目标极小化；如果完成任务的效率表现为生产效率的高低，则考虑的是如何分配使得目标函数极大化。率的高低，则考虑的是如何分配使得目标函数极大化。在分配问题中，利用不同资源完成不同计划活动的效率常在分配问题中，利用不同资源完成不同计划活动的效率常用表格形式表示为效率表，表格中数字组成用表格形式表示为效率表，表格中数字组成效率矩阵效率矩阵。例例2.有一份说明书，要分别翻译成英、日、德、俄有一份说明书，要分别翻译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，使这四个人分别完成四项任务总的时间为最小。效不同

9、，使这四个人分别完成四项任务总的时间为最小。效率表如下：率表如下：效率矩阵用效率矩阵用aij 表示，为表示，为9131541116141381441579102ija定义逻辑变量定义逻辑变量）；（项任务个人去完成第，不分配第项任务个人去完成第，分配第mjmijijixij,1,1 0 1则分配问题的数学模型写为：则分配问题的数学模型写为：),1;,1(1 0),1(1),1(1min1111mjmixmjxmixxazijmiijmjijmimjijij或二、匈牙利法用表上作业法来求解分配问题时，单位运价表即效率表，用表上作业法来求解分配问题时，单位运价表即效率表，产销平衡表中产量和销量都设为

10、产销平衡表中产量和销量都设为 1 即可。即可。匈牙利数学家克尼格（匈牙利数学家克尼格（Konig）求解分配问题的计算方法）求解分配问题的计算方法被称为被称为匈牙利法匈牙利法，原理是原理是如果效率矩阵所有元素如果效率矩阵所有元素aij=0，而其中存在一组位于不同行不同列的零元素，则只要令对而其中存在一组位于不同行不同列的零元素，则只要令对应于这些零元素位置的应于这些零元素位置的xij=1即为最优解。即为最优解。0149392002323038012140 定理定理1 如果从分配问题效率矩阵如果从分配问题效率矩阵 aij 的每一行元素中的每一行元素中分别减去（或加上）一个常数分别减去（或加上）一个

11、常数 ui(被称为该行的位势被称为该行的位势)，从，从每一列分别减去（或加上）一个常数每一列分别减去（或加上）一个常数 vj（被称为该列的位（被称为该列的位势），得到一个新的效率矩阵势），得到一个新的效率矩阵 bij，若其中，若其中 bij=aij-ui-vj，则则 bij 的最优解等价于的最优解等价于 aij 的最优解。的最优解。定理定理2 若矩阵若矩阵 A 的元素可分成的元素可分成“0”与非与非“0”两部两部分，则覆盖分，则覆盖“0”元素的最少直线数等于位于不同行不同元素的最少直线数等于位于不同行不同列的列的“0”元素的最大个数。元素的最大个数。AB甲35乙42AB甲02乙20AB甲03乙

12、10 结合例结合例2 说明说明匈牙利法的计算步骤匈牙利法的计算步骤 第一步：找出效率矩阵每行的最小元素，并分别第一步：找出效率矩阵每行的最小元素，并分别从每行中减去。从每行中减去。5911005324100115780411429131541116141381441579102min 第二步：找出矩阵每列的最小元素，分别从各列中减第二步：找出矩阵每列的最小元素，分别从各列中减去。去。0 5 0 0 min5411000324501152805911005324100115780 第三步：经过上述两步变换后，矩阵的每行每列至少第三步：经过上述两步变换后，矩阵的每行每列至少都有了一个零元素。下面确

13、定能否找出都有了一个零元素。下面确定能否找出 m 个位于不同行个位于不同行不同列的零元素的集合（该例中不同列的零元素的集合（该例中 m=4），也就是看要覆），也就是看要覆盖上面矩阵中的所有零元素，至少需要多少条直线。盖上面矩阵中的所有零元素，至少需要多少条直线。1.从第一行开始，若该行只有一个零元素，就对这从第一行开始，若该行只有一个零元素，就对这个零元素打上（个零元素打上（），对打括号的零元素所在的列画一条），对打括号的零元素所在的列画一条线，若该行没有零元素或者有两个以上零元素（已划去的线，若该行没有零元素或者有两个以上零元素（已划去的不算在内），则转下一行，依次进行到最后一行。不算在内）

14、，则转下一行，依次进行到最后一行。2.从第一列开始，若该列只有一个零元素，就对这个从第一列开始，若该列只有一个零元素，就对这个零元素打上（零元素打上（）（同样不考虑已划去的零元素），再对）（同样不考虑已划去的零元素），再对打括号的零元素所在行画一条直线。若该列没有零元素或打括号的零元素所在行画一条直线。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为有两个以上零元素，则转下一列，依次进行到最后一列为止。止。3.重复上述步骤重复上述步骤 1、2，可能出现三种情况：，可能出现三种情况：效率矩阵每行都有打括号的零元素，只要对应这些效率矩阵每行都有打括号的零元素，只要对应这些元素令

15、元素令 xij=1 就找到了最优解。就找到了最优解。打括号的零元素个数少于打括号的零元素个数少于 m，但未被划去的零元，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素打一个括号，然后对所有打括号的零元素所在行的零元素打一个括号，然后对所有打括号的零元素所在行（或列）画一条直线，同样得到最优解。（或列）画一条直线，同样得到最优解。矩阵中所有零元素或被划去，或打上括号，但打括矩阵中所有零元素或被划去，或打上括号，但打括号的零元素少于号的零元素少于 m，这时转入第四步。，这时转入第四步。第四步：按定理第四步：按定理 1 进

16、行如下变换进行如下变换 1.从矩阵未被直线覆盖的数字中找出一个最小的从矩阵未被直线覆盖的数字中找出一个最小的 k；2.对矩阵中的每行，当该行有直线覆盖时，令对矩阵中的每行，当该行有直线覆盖时，令 ui=0，无，无直线覆盖的，令直线覆盖的，令 ui=k；3.对矩阵中有直线覆盖的列，令对矩阵中有直线覆盖的列，令 vj=-k，对无直线覆盖的，对无直线覆盖的列，令列，令 vj=0；4.从原矩阵的每个元素从原矩阵的每个元素 aij中分别减去中分别减去 ui 和和 vj。第五步：回到第三步，反复进行，直到矩阵的每一行第五步：回到第三步，反复进行，直到矩阵的每一行都有一个打括号的零元素为止，即找到最优分配方

17、案。都有一个打括号的零元素为止，即找到最优分配方案。由于调整后的矩阵中新出现了一个零，因此对打括号由于调整后的矩阵中新出现了一个零，因此对打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号的元素重新进行调整，得到如下矩阵，这时只要把打括号元素所对应的决策变量取值为元素所对应的决策变量取值为1，就得到最优解。，就得到最优解。该问题中，最优值为：该问题中，最优值为：4+4+9+11=28hABCDE甲127979乙89666丙71712149丁15146610戊4107109课堂练习课堂练习 三、两点说明1.分配问题中人数和工作任务不相等时分配问题中人数和工作任务不相等时 当人数多于工作任务

18、数时，可以添加假想任务使得人当人数多于工作任务数时，可以添加假想任务使得人数与工作任务数相同，因为工作任务是假想的，因此完成数与工作任务数相同，因为工作任务是假想的，因此完成这些任务的时间是零。当任务数多于人数时，可添加假想这些任务的时间是零。当任务数多于人数时，可添加假想的人。这样的方法和运输问题中处理的方法类似。的人。这样的方法和运输问题中处理的方法类似。2.当问题目标变为求极大时当问题目标变为求极大时mimjijijxaz11max可改写为可改写为mimjijijxaz11)(min 此时效率矩阵中元素都变为了负值，可利用定理此时效率矩阵中元素都变为了负值，可利用定理1，使效率矩阵中全部

19、元素都变为非负的，就可以利用匈牙利使效率矩阵中全部元素都变为非负的，就可以利用匈牙利法进行求解。法进行求解。分枝定界法分枝定界法(branch and bound method)是为了求解同整数是为了求解同整数规划具有类似性质的一大类问题而设计的一种较好的方法。规划具有类似性质的一大类问题而设计的一种较好的方法。结合例一来说明分枝定界法的思路和解题步骤：结合例一来说明分枝定界法的思路和解题步骤：例例1.求下述整数规划问题的最优解求下述整数规划问题的最优解且均取整数值 ,0,5.45.0 143 223max21212121xxxxxxxxz第一步：第一步：寻找替代问题并求解。寻找替代问题并求解

20、。放宽或取消原问题的某放宽或取消原问题的某些约束，找出一个替代问题。若替代问题的最优解是原问些约束，找出一个替代问题。若替代问题的最优解是原问题的可行解，这个解就是原问题的最优解，否则是源问题题的可行解，这个解就是原问题的最优解，否则是源问题最优解的上界最优解的上界(求极大值求极大值)或下界或下界(求极小值求极小值)。例例1对应的松弛问题对应的松弛问题 L0:max.,012121212 322314 0 54 50 Lzxxxxxxx x其最优解为：其最优解为：5.2 ,25.321xx最优值为：最优值为：75.14z第二步：第二步：分枝与定界。分枝与定界。将替代问题分成若干子问题，对子将替

21、代问题分成若干子问题，对子问题也要容易求解，且各子问题的解的集合要包含原问题问题也要容易求解，且各子问题的解的集合要包含原问题的解集。然后对每个子问题求最优解，若满足原问题的约的解集。然后对每个子问题求最优解，若满足原问题的约束，则找到原问题的可行解，否则该解为所属分枝的边界束，则找到原问题的可行解，否则该解为所属分枝的边界值；如果所有子问题的最优解均非原问题可行解，则选取值；如果所有子问题的最优解均非原问题可行解，则选取边界值最大边界值最大(求极大值求极大值)或最小或最小(求极小值求极小值)的子问题再进一的子问题再进一步细分子问题求解。分枝过程一直进行下去，直到找到一步细分子问题求解。分枝过

22、程一直进行下去，直到找到一个原问题的可行解为止。如果计算中同时出现两个以上可个原问题的可行解为止。如果计算中同时出现两个以上可行解，则选取其中行解，则选取其中最大最大(求极大值求极大值)或最小或最小(求极小值求极小值)的的一个保留。一个保留。将线性规划问题将线性规划问题 L0 分为两枝。分为两枝。在在 L0 的最优解中，任选一个非整数变量，如的最优解中，任选一个非整数变量，如 x2=2.5；因因 x2 的最优整数解只可能是的最优整数解只可能是 x22 或或 x23，故在，故在 L0中分中分别增加约束条件：加上约束条件别增加约束条件：加上约束条件 x22，记为，记为 L1；加上约；加上约束条件束

23、条件 x23，记为，记为 L2。:max.,1121212212 3223140 54 5 20 Lzxxxxxxxx x:max.,2121212212 3223140 54 5 30 Lzxxxxxxxx xL1 的最优解为：的最优解为：x1=3.5 ,x2=2 ,z=14.5L2 的最优解为：的最优解为：x1=2.5 ,x2=3 ,z=13.5由于两个子问题的最优解仍非原问题的可行解，故选取最由于两个子问题的最优解仍非原问题的可行解，故选取最优值较大的子问题优值较大的子问题L1进行分枝，将分解为进行分枝，将分解为 L11和和 L12 两个两个子问题。子问题。:max.,111212122

24、112 3223140 54 5 230 Lzxxxxxxxxx x:max.,121212122112 3223140 54 5 240 Lzxxxxxxxxx x L11和和 L12 两个子问题的可行域为：两个子问题的可行域为：L11 的最优解为：的最优解为：x1=3,x2=2,z=13L12 的最优解为：的最优解为：x1=4 ,x2=1 ,z=14这时两个问题获得的均为可行解，保留可行解中较大的一这时两个问题获得的均为可行解，保留可行解中较大的一个个z14第三步：剪枝，将各子问题边界值与保留的可行第三步：剪枝，将各子问题边界值与保留的可行解的值进行比较，把边界值劣于可行解的分枝解的值进行

25、比较，把边界值劣于可行解的分枝剪去，如果除保留下来的可行解外，其余分枝剪去，如果除保留下来的可行解外，其余分枝均被剪去，则该可行解就是原问题的最优解，均被剪去，则该可行解就是原问题的最优解，否则回到第二步，选取边界值最优的一个继续否则回到第二步，选取边界值最优的一个继续分枝。如果计算又出现新的可行解，则与原可分枝。如果计算又出现新的可行解，则与原可行解比较，保留最优的，并重复上述步骤。行解比较，保留最优的，并重复上述步骤。通过剪枝，求解得最优解为（通过剪枝，求解得最优解为（4,1），最优解为），最优解为14。用分枝定界法可求解纯整数规划问题和混合整数规用分枝定界法可求解纯整数规划问题和混合整数

26、规划问题，比穷举法优越，但若变量数目很大，其计划问题，比穷举法优越，但若变量数目很大，其计算量也相当客观。算量也相当客观。割平面法是求解整数规划问题最早提出的一割平面法是求解整数规划问题最早提出的一种方法，种方法，1958年由年由Gomory提出，其基本提出，其基本思想是在整数规划问题的松弛问题中依次引思想是在整数规划问题的松弛问题中依次引进线性约束条件，称为进线性约束条件，称为(Gomory约束约束)，使，使问题的可行域逐步缩小，但每次切割只割去问题的可行域逐步缩小，但每次切割只割去问题的部分非整数解，直到使问题的最优目问题的部分非整数解，直到使问题的最优目标函数点成为缩小后可行域的一个顶点

27、。标函数点成为缩小后可行域的一个顶点。例例1.求下述整数规划问题的最优解求下述整数规划问题的最优解且均取整数值 ,0,5.45.0 143 223max21212121xxxxxxxxz第一步：把约束条件的系数化成整数，不考虑变量的第一步：把约束条件的系数化成整数，不考虑变量的整数约束整数约束:max.,012121212322 314290Gzxxxxstxxx x 加松弛变量，用单纯形法求解得最终单纯加松弛变量，用单纯形法求解得最终单纯形表：形表：x1x2x3x42x25/2011/2-1/23x113/410-1/43/4cj-zj00-1/4-5/4 第二步：找出非整数解变量中分数部分

28、最第二步：找出非整数解变量中分数部分最大的一个基变量，并写下该行约束：大的一个基变量，并写下该行约束：xxx2341112222将常数写成整数与一个正的分数值的和；将常数写成整数与一个正的分数值的和；)()()xxx 2341110+1+2222（xxxx24341112222将整数项移到等式左端：将整数项移到等式左端：,243434345211111222211102211102(Gomory)222xxxxxxxxx由于为整数，故因此加上松弛量得：约束变,123124123414239222111012122xxxxxxxxxx由于代入得：相当于原约束条件加上该新约束条件 新约束条新约束条

29、件只割去件只割去可行域部可行域部分非整数分非整数解，原有解，原有的整数解的整数解全部保留全部保留 将将Gomory约束加到约束加到G0得到新的线性规划得到新的线性规划问题问题G1，如下：，如下：:max.,11212312434512345322314291112220Gzxxxxxxxxstxxxx x x x x 第四步：重复第一至第三步一直到找出问第四步：重复第一至第三步一直到找出问题的整数最优解为止题的整数最优解为止 由于得到的解仍为非整数解，重复第二步由于得到的解仍为非整数解，重复第二步5145145556110(G11322113221102omor2y)22xxxxxxxxxx约

30、束:max.,21212312434556123453223142911122211220Gzxxxxxxxxstxxxxxx x x x x 最终的整数规划解最终的整数规划解(4,1)已经成为经已经成为经过两次切割后可行过两次切割后可行域上的一个顶点，域上的一个顶点，因此可以用单纯型因此可以用单纯型法找出最优解法找出最优解 清远市下设八个区，下表给出救护车从一清远市下设八个区，下表给出救护车从一个区至另一个区的车程时间个区至另一个区的车程时间(min)，该市，该市拟建救护中心，要求各区离救护中心的车拟建救护中心，要求各区离救护中心的车程时间必须在程时间必须在8min以内，问该市至少应建以内，

31、问该市至少应建多少个救护中心，建于何处？多少个救护中心，建于何处？234567818911131481521012131117143778121048710958141661077128min覆盖区域1127212334564345653456634568717868 根据上表则对于每个区，距离其8min的区至少应该建一个救护站，因此有：,10jx=该区设救护中心设否则min.(,.,)jzxxxxxxxxxstxxxxxxxxxxj8jj 1127123456345681768x1111110118或.(,.,)jxxxxxxstxxxxxj123456176811110118或 某钻井队要从10个可供选择的井位中确定5个钻井探油，使总的钻探费用最小。若10个井位的代号为S1S10，相应的钻探费用为C1C10，并且井位选择要满足以下条件：或选择S1和S7，或选择S8；选择了S3或S4，就不能选择S5，反之亦然；在S5，S6，S7，S8中最多只能选两个；试建立该问题的整数规划模型。j10jji 110ji 1187835455678i1Sjx0min Zc xx5xx1xx1s.t.xx1xx1xx+xx2x01 选择钻探井位设决策变量否则取 或