[管理学]整数规划与分配问题.ppt

4、整数规划与分配问题 2010/10/8 4.1 整数规划的特点及作用 在线性规划问题中,它的解都假设为具有连续型数值.但是在许多实际问题中,决策变量仅仅在取整数值时才有意义,比如变量表示的是工人的数量,机器的台数,货物的箱数等。 实际问题中经过“四舍五入”处理得到的解可能不是原问题的可行解,有的虽是原问题的可行解,但却不是整数最优解.因而有必要研究整数规划问题的解法. 例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下： 问两种货物各装运多少箱，可使获得利润最大？ 因此用图解法或单纯形法都无法找出整数规划的最优解，这就要研究整数规划问题的特殊方法。 4.2 分配问题与匈牙利法 4.2.1 问题的提出与数学模型 在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，各人完成任务不同（或所费时间），效率不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（Assignment problem）。 4.2.2 匈牙利法 匈牙利算法基本思想： 对同一工作i来说，所有人的效率都提高或降低同一常数，不会影响最优分配；同样，对同一人j来说,做所有工作的效率都提高或降低同一常数，也不会影响最优分配。 例4: 4个工人分派做4项工作，规定每人只能做1项工作，每项工作只能1个人做。现设每个工人做每项工作所消耗的时间如表所示，求总耗时最少的分派方案。 * 13 24 托运限制 10 5 4 乙 20 2 5 甲 利润(百元) 重量(百斤) 体积( ) 货物集装箱 设甲、乙两种货物装运箱数分别为x1和x2。显然，都要求为整数,于是可建立整数规划模型如下： 整数规划的一般模型 此模型与一般线性规划的模型很相似，区别在于除变量的非负条件外，还加了整数解的要求。 如何求解整数规划问题？ 例2： 求下列问题： Max Z=3x1+13x2 s.t. 2x1+9x2 ? 40 11x1-8x2 ? 82 x1,x2 ? 0,且取整数值 O 1 2 3 4 5 6 7 8 9 10 5 4 3 2 1 x1 x2 I(2,4) B(9.2,2.4) A D 可行域OABD内整数点，放弃整数要求后，最优解B(9.2,2.4) Z0=58.8，而原整数规划最优解I(2,4) Z0=58，实际上B附近四个整点(9,2)(10,2)(9,3)(10,3)都不是原规划最优解。 例3 有一份中文说明书，需翻译成英、日、德、俄四种文字，现有甲、乙、丙、丁四人，他们将中文说明书翻译成英、日、德、俄四种文字所需时间如下，问应该如何分配工作，使所需总时间最少？ 效率矩阵 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 译成英文 译成日文 译成德文 译成俄文 甲 乙 丙 丁 引入0-1变量xij=1分配第i人去完成第j 项任务，xij=0不分配第i人去完成第j 项任务。 ? xij =1 (j=1,2……n)表示 第j 项任务只能由一人去完成。 ? x ij =1 (i=1,2……n) 第i人只能完成一项任务。 分配问题的数学模型： Min Z=? ? cijxij ? xij =1 (j=1,2……n) ? xij =1 (i=1,2……n) xij = 0或1(i=1,2…..m; j=1,2……n) 满足约束条件的解称为可行解可写成矩阵形式： X= 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 称为解矩阵其各行各列元素之和为1。 分配问题性质： 分配问题的最优解有这样的性质，若从系数矩阵C的一行（列）各元素中分别减去该行（列）的最小元素得到的新矩阵B，那么B