东北农业大学理学院经济数学方法与模型课件 第五章精选.ppt

一、目标函数为求极大值的问题 当目标函数为： 时，记 得到一新矩阵 ．由最优解的性质知，以 为价值 系数矩阵的指派问题与以 为价值系数矩阵的指派问 题同时达到最优，且有相同的最优解．经过上述转换， 即可将极大化问题变为极小化问题． * 二、价值系数矩阵中存在负元素 若价值系数矩阵 的第 行（或第 列）存在负元 素，则第 行（或第 列）每个元素都减去该行的最小元 素，即可使价值系数矩阵 满足非负条件，然后可以用 匈牙利法求解． * 例1　求价值系数矩阵为如下所示的指派问题的最小 解． * 解： * * 于是最优解为： 最优值为： * 三、价值系数矩阵不是方阵 若记人员（或设备）数为 ，任务（或加工件）数 为 ，所谓价值系数矩阵不是方阵，即 ，此时，需 分情况讨论： * 1、 （1） 且 项任务又都必须完成时：此时，必有 某个（些）人完成一项以上的任务，这类问题可按例2的 方法处理． * 例2　有三人分配去完成四项任务，且四项任务都必 须完成，假定每个人至多完成2项任务．试求使完成任务 的总时间为最少的分配方案． * 解： 其中 、 为虚拟任务． * 用匈牙利法求得最优解为： 即甲完成工作 、 ；乙完成工作 ；丙完成工作 ，可使 完成任务所需时间为最少，此时 * （2）若 ，但每人只能完成一项任务．此时一定 有某个（些）任务没有人去完成，这类问题可按例3的方 法处理． * 例3　某设备公司有3台设备，可租给 、 、 、、 五 项工程使用，各设备用于各项工程创造的利润如表所示。 问将哪一台设备租给哪一项工程，才能使创造的总利润 为最大？ * 解：先把极大化问题变为极小化问题，记 得到新价值系数矩阵： * 因设备台数比工程数少两个，故增加两台虚拟设备 、 ，并把价值系数矩阵写为： * 用匈牙利法求解 * 最优解为： 故将设备 分给工程 ， 分给工程 ， 分给工程 ， 工程 、 没有分到设备．这时，可创最高利润，利润值 为： * 另外，如果人数少于任务数，而某项任务又必须完 成，则在增加虚拟人时，将虚拟人完成此项任务的系数 设为 ，而虚拟人完成其他任务的系数设为0即可；如果 某人就能力而言可完成某项任务，而由于某种原因不允 许该人完成某项任务，则可将相应的系数改为 即可． * 2、 可参照 的情况处理，一般是增加虚拟工作，使 系数矩阵为方阵，然后用匈牙利法求解． * 第五章 匈牙利法与最佳指派问题 什么是最佳指派问题？ 最佳指派（或分配）问题是经济计划工作中经常遇到 的一个问题．比如，当某一个部门或某一个企业的生产任 务已经确定，如何分配给它们所属的单位，使得完成这些 任务所需费用最小（或效益最大）．分配问题是较简单的 线性规划问题，也是运输问题的一个特例，当然可以用线 性规划的单纯形法加以求解．然而，使用本章介绍的方法 ——匈牙利法去求解，效果会更好，该方法的得名是因为 匈牙利数学家狄·考尼格（D·Konig）为发展这个方法证 明了主要定理． * 本章主要内容 第一节 最佳指派问题的线性规划模型 第二节 标准指派问题的匈牙利法 第三节 非标准指派问题 * 第一节 最佳指派问题的LP模型 例1　有一份资料需从汉语译成英、日、俄三种文字 ，现有A、B、C三人，每人需完成且只完成其中的一种 工作．因各人对不同文字的熟悉程度不一样，所需工作 时间（单位：天）也不同（见下表）．问应指派哪一个 人去完成哪一项工作才能使花费的总时间最短？ * 解：对于某个人来讲，要么做某项工作，比如“译 英”要么不做，二者必居其一，换句话说，每个人与每 项工作之间只有两种状态：“做”或“不做”为此我们 设变量： 此时 称为0-1变量． * 由于每个人只能完成一项工作，因而有： 又由于每项工作只能由一个人完成，因而又有： * 上述6个方程以及 为0-1变量就构成了本问题的约束 条件，而目标为所消耗的总时间最少，因而目标函数为： 这是依本例实际问题而建立的线性规划模型． *