[三年级数学]教案_整数规划.pptVIP

第五节 指派问题 1指派问题的数学模型 在生活中经常遇到这样的问题，某单位需完成项任务，恰好有个人可以承担这些任务。由于每人的专长不同，各人完成任务不同（或所费时间），效率也不同。于是产生应指派哪个人去完成哪项任务，使完成项任务的总效率最高（或所需总时间最小）。这类问题称为指派问题或分派问题（assignment problem）。 例5-7 有一份中文说明书，需译成英、日、德、俄四种文字，分别记作E、J、G、R。现有甲、乙、丙、丁四人，他们将中文说明书翻译成不同语种的说明书所需时间如下表所示。问应指派何人去完成何工作，能使所需总时间最少？ 9 11 8 7 丁 13 16 14 9 丙 15 14 4 10 乙 4 13 15 2 甲 R G J E 任务 人员 类似有：有n项加工任务，怎样指派到n台机床上分别完成的问题：有n条航线，怎样指定n艘船去航行的问题…… 效率矩阵或系数矩阵 效率矩阵的元素 表示指派第i人去完成第j项任务时的效率（或时间、成本等）。 引入变量 ；其取值只能是1或0。并令 数学模型 可行解矩阵 第j项任务只能由1人完成 第i人只能完成1项任务 解矩阵中各行各列的元素之和都是1 指派问题是0-1规划的特例，也是运输问题的特例 2 匈牙利算法 指派问题最优解的性质：若从系数矩阵 的一行（列）各元素中分别减去该行（列）的最小元素，得到新矩阵 ，那么以 为系数矩阵求得的最优解和用原系数矩阵求解的最优解相同。 库恩（W. W.Kuhn）于1955年提出了指派问题的解法，他引用了匈牙利数学家康尼格（D.Konig）一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。这解法称为匈牙利法。 以例5-7为例说明指派问题的解法 第二步：进行试指派，以寻求最优解。按以下步骤进行。 经第一步变换后，系数矩阵中每行每列都已有了0元素；但需找出n个独立的0元素。若能找出，就以这些独立0元素对应解矩阵中的元素为1，其余为0，这就得到最优解。当n较小时，可用观察法、试探法去找出n个独立0元素；若n较大时，就必须按一定的步骤去找，常用的步骤为： （1）从只有一个0元素的行（列）开始，给这个0元素加圈，记作 。这表示对这行所代表的人，只有一种任务可指派。然后划去 所在列（行）的其他0元素，记作 。这表示这列所代表的任务已指派完，不必再考虑别人了。 （2）给只有一个0元素列（行）的0元素加圈，记作 ；然后划去 所在行（列）的0元素，记作 。 （3）反复进行（1），（2）两步，直到所有0元素都被圈出和划掉为止。 （4）若仍有没有划圈的0元素，且同行（列）的 0元素至少有两个（表示对这个可以从两项任务中指派其一）。这可用不同的方案去试探。从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈（表示选择性多的要“礼让”选择性少的），然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。 （5）若 元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到，若 ，则转入下一步。 * 第一节 问题的提出 例5-1：某工厂有资金13万元用于购置新机器，可在两种机器中任意选购。已知机器A每台购置费2万元，B为4万元。该厂维修能力只能维修7台机器B；若维修机器A，1台折算机器B 2台。已知一台A可增加年产值6万元，1台B可增加年产值4万元，问应购置A和B各多少台才能使年产值增加最多？ 第五章 整数规划（Integer Programming) 分类：1. 纯整数线性规划（Pure Integer Linear Programming） 2. 混合整数线性规划（Mixed Integer Linear Programming） 3. 0-1型整数线性规划（Zero-One Integer Linear Programming） 解：设x1，x2分别表示两种A、B两种机器的购置台数，根据实际机器台数应为整数，故该问题的优化模型为 上述规划问题是整数规划问题。 放松整数约束的整数规划就成为线性规划，此线性规划被称之为整数规划的线性规划松弛问题。这样，任何一个整数规划可以看成是一个线性规划再加上整数约束构成的。 整数规划问题的求解 以例5-1为例，图解法 最优解为 可行解