必威体育精装版物流运筹学课件-整数规划问题及数学模型.ppt

在实际中经常会遇到这样的问题，有n 项不同的任务，需要n 个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成 n 项任务的总效率最高（或所需时间最少），这类问题称为分配问题或指派问题。 一、指派问题及数学模型 第五节 指派问题与匈牙利法 指派问题举例 甲、乙、丙、丁四个人，A、B、C、D四项任务，不同的人做不同的工作效率不同，如何指派不同的人去做不同的工作使效率最高，即花费的总时间最短？ 解：对于这个问题，很容易建立一个数学模型的， 引入0-1变量 ， 当 =1时，表示分配第i个人完成第j项任务 当 =0时，表示不分配第i个人完成第j项任务 第五节 指派问题与匈牙利法 一项任务只由一个人完成，有如下约束 一人只能完成一项任务，有如下约束 第五节 指派问题与匈牙利法 例： 人事部门欲安排四人到四个不同岗位工作，每个岗位一个人。经考核四人在不同岗位的成绩（百分制）如表所示，如何安排他们的工作使总成绩最好。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 第五节 指派问题与匈牙利法 设 数学模型如下： 要求每人做一项工作，约束条件为： 第五节 指派问题与匈牙利法 每项工作只能安排一人，约束条件为： 变量约束： 第五节 指派问题与匈牙利法 第五节 指派问题与匈牙利法 指派问题的数学模型: 工作任务 效率 工人 要求每个工人有一项工作,每项工作只有一个工人来作.如何安排使总的效益最好. 第五节 指派问题与匈牙利法 第五节 指派问题与匈牙利法 二、指派问题的解法—匈牙利法 匈牙利法(1955年W.W.Kuhn求解分配问题,使用了匈牙利数学家Kuhn的两个定理,故称匈牙利解法. 定理1 第五节 指派问题与匈牙利法 第二步，用单纯形法求松弛问题，得最终单纯形表。 cj → 8 5 0 0 CB 基 b x1 x2 x3 x4 0 x3 12 2 3 1 0 0 x4 6 [2] －1 0 1 cj－zj 8 5 0 0 0 x3 6 0 [4] 1 －1 8 x1 3 1 －1/2 0 1/2 cj－zj 0 9 0 －4 5 x2 3/2 0 1 1/4 －1/4 8 x1 15/4 1 0 1/8 3/8 cj－zj 0 0 －9/4 －7/4 松弛问题的最优解 ， ，非整数规划的可行解。 第三节 割平面法 第三步，引进割平面 在最终单纯形表中选择分数部分最大的基变量 列出该行约束： 将所有系数分成整数与一个正的分数之和： 将分数部分移至右端： 分析右边的分数项，其取值小于1，即得到了Gomory约束： 第三节 割平面法 第四节 0-1规划与隐枚举法 如果线性规划中的所有决策变量的取值只能取0、1，则这类线性规划问题是一种特殊的整数规划问题称之为0-1规划，把只能取0或1值的变量称为0-1变量。0-1变量是一种逻辑变量。 第四节 0-1规划与隐枚举法 其数学模型如下： 第四节 0-1规划与隐枚举法 本节先介绍引入0-1变量的实际问题： ① 投资场所（项目）的选定 ②相互排斥的约束条件 ③关于固定费用的问题 然后，再研究0-1规划问题的一般解法---隐枚举法。 第四节 0-1规划与隐枚举法 一、引入0-1变量的实际问题 投资场所的选定——相互排斥的计划 例 : 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai (i=1，2，…，7)可供选择。规定： 在东区，由A1，A2，A3三个点中至多选两个； 在西区，由A4，A5两个点中至少选一个； 在南区，由A6，A7两个点中至少选一个。 如选用Ai点，设备投资估计为bi元， 每年可获利润估计为ci元， 但投资总额不能超过B元。 问应选择哪几个点可使年利润为最大? 解题时先引入0-1变量xi (=1,2，…，7) 问题建模： 2. 相互排斥的约束条件 设运货有车运和船运两种方式， 用车运的体积限制条件为： 5x1+4x2≤24 用船运的体积限制条件为： 7x1+3x2≤45 这两条件是互相排斥的。 为了统一在一个问题中，引入0-1变量y，令 （