2.1.-运筹学匈牙利法-复习-xiao.pptVIP

0－1 整数规划是一种特殊形式的整数规划，这时的决策变量xi 只取两个值0或1， 通常用来表示逻辑性选择的决策。一般的解法为隐枚举法。 例 求解下列0－1 规划问题 0－1 整数规划的应用 √ √ √ √ 8 √ × √ √ × × √ √ √ × √ √ √ √ √ √ 3 √ √ √ √ -2 √ √ √ √ 5 √ √ √ √ 0 x1 . x2. x3 满足约束条件（是∨ 否×） Z 值 (1) (2) (3) (4) ( 0. 0. 0 ) ( 0. 0. 1 ) ( 0. 1. 0 ) ( 1. 0. 0 ) ( 0. 1. 1 ) ( 1. 0. 1 ) ( 1. 1. 0 ) ( 1. 1. 1 ) 一、0－1 整数规划——枚举法 √ √ √ √ 8 三、指派问题的匈牙利法 指派问题（The Assignment Problem） 1、指派问题的形式表述 给定了一系列所要完成的任务（tasks）以及一系列完成任务的被指派者（assignees），所需要解决的问题就是要确定出哪一个人被指派进行哪一项任务 2、指派问题的假设 被指派者的数量和任务的数量是相同的 每一个被指派者只完成一项任务 每一项任务只能由一个被指派者来完成 每个被指派者和每项任务的组合有一个相关成本 目标是要确定怎样进行指派才能使得总成本最小 设n 个人被分配去做n 件工作，每人只能完成一项任务，每项任务只能由一人完成。已知第i 个人去做第j 件工作的的效率为Cij(i=1.2…n;j=1.2…n)并假设Cij ≥0。问应如何分配才能使总效率（ 时间或费用）最高？ 3、指派问题模型 （The Model for Assignment Problem） 典型问题 例1：有一份说明书，要分别译成英、日、德、俄四种文字，交与甲、乙、丙、丁四个人去完成，因各人专长不同，他们完成翻译不同文字所需要的时间（小时）如表所示。规定每项工作只能交与其中的一个人完成，每个人只能完成其中的一项工作。 问：如何分配，能使所需的总时间最少？ 甲 乙 丙 丁 工作 人 译英文 译日文 译德文 译俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 建立模型 设 xij= 1 0 若第i项工作交与第j个人完成 若第i项工作不交与第j个人完成 译英文： x11+ x12 + x13 + x14 =1 译日文： x21+ x22 + x23 + x24 =1 译德文： x31+ x32 + x33 + x34 =1 译俄文： x41+ x42 + x43 + x44 =1 甲： x11+ x21 + x31 + x41 =1 乙： x12+ x22 + x32 + x42 =1 丙： x13+ x23 + x33 + x43 =1 丁： x14+ x24 + x34 + x44 =1 xij =0或1 (i=1,2,3,4; j=1,2,3,4) 甲 乙 丙 丁 工作 人 译英文 译日文 译德文 译俄文 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 4、指派问题的匈牙利解法 2 4 9 7 第1步：变换指派问题的系数矩阵（cij），使各行各列中都出现0元素 (1) 从（cij）的每行元素都减去该行的最小元素； (2)再从所得新系数矩阵无零元素的列中减去该列的最小元素。 4 2 在变化后的效率矩阵中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。 第2步：进行试指派，即确定独立零元素 （1）从有唯一的零元素