运筹学-第四章 整数规划与分配问题

1、4.整数规划和分配问题，4.1整数规划的特点和功能。在线性规划问题中，假设其解具有连续的数值。然而，在许多实际问题中，决策变量只有在取整数值时才有意义，例如工人数量、机器数量和货物箱数量。实际问题中“舍入”得到的解可能不是原问题的可行解，虽然有些解是原问题的可行解，但它们不是整数最优解。因此，有必要研究整数规划问题的解法。例1一家工厂计划用火车装运两种货物集装箱，每种集装箱的体积、重量、利润和装运限制如下：问一问这两种货物有多少集装箱被装运，以使利润最大化。假设货物A和货物B的装运箱数量分别为x1和x2。很明显，它们都要求是整数，所以整数规划模型可以建立如下：(1)整数规划的一般模型，它非常类

2、似于一般线性规划的模型，不同之处在于除了变量的非负条件外，还增加了整数解的要求。如何解决整数规划问题？例2:找出以下问题：最大z=3x 1 13 x2 s . t . 2x 1 9x 2 40 11 x1-8x 282 x1，x20，OABD取整数值、o 1 234 56 7 8 9 10，543 21，x1，x2，I (2，4)，b (9.2，4)放弃整数要求后，最优解B(9.2，2.4) Z0=58.8，而最优解I(2，4) Z0=58事实上，靠近B的四个整点(9，2)(10，2)(9，3)(10，3)不是原规划的最优解。因此，用图解法或单纯形法都不可能找到整数规划的最优解，因此有必要研究

3、整数规划的特殊方法。4.2分配问题和匈牙利定律，4.2.1问题和数学模型在生活中经常遇到这样的问题，某个单位需要完成N个任务，而只有N个人可以承担这些任务。因为每个人都有不同的专长，每个人都有不同的任务(或花费的时间)和不同的效率。因此，应该指派哪个人来完成哪个任务，这样完成N个任务的总效率最高(或者所需的总时间最小)。这种问题称为指派问题或指派问题。有一本中文手册需要翻译成英文、日文、德文和俄文。有四个人：甲、乙、丙和丁。将中文手册翻译成英文、日文、德文和俄文所需的时间如下。应该如何分配工作以最大限度地减少所需的总时间？效率矩阵，引入0-1变量xij=1来分配第I个人来完成第j个任务，xij

4、=0来分配第I个人来完成第j个任务。Xij=1 (j=1，2n)意味着第j个任务只能由一个人完成。X ij=1 (i=1，2n)第六个人只能完成一项任务。分布问题的数学模型是最小z=111=1(j=1，2n)1=1 (I=1，2n)1=0或1(I=1，2.m；J=1，2n)满足约束条件的解称为可行解，可以写成矩阵形式：4.2.2匈牙利法，匈牙利算法的基本思想：对于同一作业I，每个人的效率增加或减少相同的常数，这不会影响最优分配；同样，对于同一个人J，做所有工作的效率将增加或减少相同的常数，并且它不会影响最优分配。分配问题的本质：分配问题的最优解具有这样的性质：如果通过从系数矩阵C的每个元素中减

5、去行(列)的最小元素来获得新的矩阵B，则由B获得的系数矩阵的最优解与由原始系数矩阵C获得的最优解相同。匈牙利算法：如果系数矩阵中的元素可以被分为“0”和非“0”， 覆盖“0”元素的直线的最小数量等于不同行和列中“0”元素的最大数量。 匈牙利算法步骤：步骤1:转换分配问题的系数矩阵，每行和每列出现0个元素：从系数矩阵的每行元素中减去每行的最小元素。然后从系数矩阵的元素中减去每列的最小元素。如果一行已经有一个0元素，就没有必要减少它。(cij)=2 4 11 4，5，2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9，步骤2:尝试分配以找到最佳解决方案从只有一个0元素的行(或列)开始，圈出这个0元素，记住它，然后划掉它所在的列(或行)中的其他0元素，并将其写成。用一个0元素圈出列(或行)的0元素，写下来，然后划掉行(或列)的其他0元素，并记为。重复上述两个步骤，直到所有0个元素都被圈出并划掉。如果有0个元素没有被圈起来，并且在同一行(或列)中至少有两个0元素，则从最少剩下0个元素的行(或列)开始，比较该列中每个0元素所在的列中0元素的数量，在该列中选择0个元