运筹学课件：第5章 整数线性规划-第5节.ppt

第5章 整数线性规划第5节 指 派 问 题;例7 有一份中文说明书，需译成英、日、德、俄四种文字。分别记作E、J、G、R。现有甲、乙、丙、丁四人。他们将中文说明书翻译成不同语种的说明书所需时间如表5-7所示。问应指派何人去完成何工作，使所需总时间最少?;;当问题要求极小化时数学模型是： ;显然，解矩阵(xij)中各行各列的元素之和都是1。但这不是最优。;指派问题是0-1规划的特例，也是运输问题的特例；即n=m,aj=bi=1;;?;  以下用例7来说明指派问题的解法。第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素。(1) 从系数矩阵的每行元素减去该行的最小元素；(2) 再从所得系数矩阵的每列元素中减去该列的最小元素。若某行(列)已有0元素，那就不必再减了。例7的计算为;行列都有零元素;第二步：进行试指派，以寻求最优解。为此，按以下步骤进行。;;;现用例7的(bij)矩阵，按上述步骤进行运算。按步骤(1)，先给b22加圈，然后给b31加圈，划掉b11，b41；按步骤(2)，给b43加圈，划掉b44，最后给b14加圈，得到 ;可见m=n=4,所以得最优解为;例8?求表5-8所示效率矩阵的指派问题的最小解。;解 按上述第一步，将这系数矩阵进行变换。 ;再按上述步骤运算，得到;第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立元素数。为此按以下步骤进行：;;注意：矩阵中的 符号，即文中的√符号。;第四步：;;已具有n个独立0元素。这就得到了最优解，相应的解矩阵为;;以上讨论限于极小化的指派问题。对极大化的问题，即求;;有兴趣的读者可以进入以下网站;;