4运筹学整数规划课件.ppt

第四章 整数规划;整数规划 线性规划问题中，所有的解都假设为具有连续型的数值，即解可以是整数、分数或带有小数点的实 数。 但对于某些具体的问题，常要求最优解是整数的 情形。 例如：机器台数 完成工作的人数 装货的车数等等。 分数或小数的解，不符合实际要求，要求整数解。; 直观上用看起来，似乎对线性规划最优解“舍入化整” 可以求得解，但这常常得不到可行的解，即使得到可行的解，也不一定是最优解。 称求解是整数的规划问题为整数规划 (Integer Programming)，简称为 I P 。 因此，对整数规划问题，需要另行研究。 整数规划中，如果所有的变量都要求是（非负）整数,就称为纯整数规划(Pure Integer Programming);全整数规划(All Integer Programming)； 如果其中一部分变量取值为整数，则称为混合整数规划( Mixed Integer Programming )。; 整数规划问题的求解要比一般的线性规划困难 本章将着重讨论 1。一类特殊的整数规划——指派问题，它的数学模型和求解。 2。求解整数规划方法——分枝定界法。 ;一、指派问题的数学模型 1。数学模型 某单位需要指派 n 个人去完成 n 项任务，每个人只做一项工作，同时，每项工作只由一个人完成。由于各人的专长不同，每个人完成各项任务的效率也不同。于是产生了应指派哪一个人去完成哪一项任务，使完成 n 项任务的总效率最高（如所用的时间为最少）。我们把这类问题称之为指派问题或分派问题(Assignment Problem)。 ;例 :有一份中文说明书,需要译成英、日、德、俄四 种文字，分别记作 E、J、G、R 。现有 甲、乙、丙、丁四人，他们将中文说明书翻译成不同文字说明书所 需要的时间如表4—1所示。问应指派何人去完成哪一 项工作，使所需的总时间最少？; 对应每个指派问题, 都有类似的表格，我们称之为效率矩阵或系数矩阵，某元素 cij ( i , j = 1,2, ······, n ) 表示指派第 i 个人去完成 第 j 项任务时的效率(或时间、成本等)。解题时需要引入变量 xij ；其取值只能是 1 或 0，并令 ：; 当问题是要求极小化时的数学模型是：;二、匈牙利法 指派问题的效率矩阵的每一个元素aij≥0 解矩阵是每行或每列只能有一个元素为1，其余均为 0 的 n 阶方阵。如：; 匈牙利法源于匈牙利数学家康尼(D.K?nig) 一个关于矩阵中 0 元素的定理： 系数矩阵中独立 0 元素的最多个数等于能覆盖所有 0 元素的最少直线数. 1955年，库恩（W.W.Kuhn）引用了0 元素的定理提出了匈牙利法，用于求解指派问题。;定理一：分派问题的效率矩阵A的每一行的元素中分别减去（或加上）一个常数ui （称为该行的位势）；每一列的元素中分别减去（或加上）一个常数vi （称为该列的位势）。得到一个新的矩阵B。如果矩阵A的元素aij与矩阵B的元素bij满足 ： bij = aij - ui - vi , 则， A与B的最优解等价。 注：本定理解决了不同问题的等价转换。像我们提示------可以将复杂的问题转换为简单问题来解;定理一的解释： 设效率矩阵为：; 定理二： 设 (aij)是指派问题的系数矩阵， aij ? 0，i , j = 1 , 2, ······, n 。若从(aij)的某一行（列）各元素中分别减去该行（列）的最小元素而得到的新矩阵 (bij) ，那么, 以新矩阵 (bij) 为系数矩阵的指派问题与原问题具有相同的最优解。;定理三： 若矩阵A的元素分为“0”与非“0”二部分，则覆盖0元素的最小直线数是位于不同行、不同列的“0”元素的最大个数。 注：解决了如何找到解矩阵的“1”元素的位置。得到最优解。;下面，请阅读教材P114 — 例5.15。 尝试理解匈牙利法解指派问题的过程。;指派问题的解法: 第一步：使指派问题的系数矩阵，经变换，在各行各 列中都出现 0 元素。为此分如下两步进行： （1）将系数矩阵的每行元素减去该行的最小元素； （2）再从所得的系数矩阵中，将每列减去该列的最 小元素。（若该行或列已有 0 元素，则就不必计算） ;第二步：进行试指派以寻求最优解。为此按如下 5