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

1、4、整数规划与分配问题2010/10/84.1 整数规划的特点及作用 在线性规划问题中,它的解都假设为具有连续型数值.但是在许多实际问题中,决策变量仅仅在取整数值时才有意义,比如变量表示的是工人的数量,机器的台数,货物的箱数等。实际问题中经过“四舍五入”处理得到的解可能不是原问题的可行解,有的虽是原问题的可行解,但却不是整数最优解.因而有必要研究整数规划问题的解法.例1 某厂拟用火车装运甲、乙两种货物集装箱，每箱的体积、重量、可获利润以及装运所受限制如下：问两种货物各装运多少箱，可使获得利润最大？货物集装箱 体积()重量(百斤)利润(百元)甲 5 220乙 4 510托运限制 24 133米

2、设甲、乙两种货物装运箱数分别为x1和x2。显然，都要求为整数,于是可建立整数规划模型如下：1212121212max201054242513,0,zxxxxxxs txxxx为 整 数整数规划的一般模型 如何求解整数规划问题？如何求解整数规划问题？1 12 21 12 21 12 21 12 2O 1 2 3 4 5 6 7 8 9 105 4 3 2 1I(2,4)B(9.2,2.4)AD4.2 分配问题与匈牙利法4.2.1 问题的提出与数学模型 在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每个人的专长不同，各人完成任务不同（或所费时间），效率不同。于是

3、产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（Assignment problem）。效率矩阵甲 乙 丙 丁译成英文译成日文译成德文译成俄文2 10 9 715 4 14 813 14 16 114 15 13 9 4.2.2 匈牙利法甲 乙 丙 丁译成英文译成日文译成德文译成俄文2 10 9 715 4 14 813 14 16 114 15 13 95 Z=9+4+11+4=28例例4:4:4个工人分派做4项工作，规定每人只能做1项工作，每项工作只能1个人做。现设每个工人做每项工作所消耗的时间如表所示，求总耗时最少的分派方案。工作 工作时间/h 工人 1234115182124219232218326171619419212317