第4章线性整数规划指派问题.ppt

* 匈牙利法 我们用方阵进行匈牙利算法的运算，找出完整分配方案的最优解。若所得的结果中某一1元素在虚行或虚列上，这个结果可以不考虑，而其他行和列的结果就是最优解。 具体算法步骤如下： 第1步：如果是求目标函数S＝f(X)的极大值，则应将所有 效应矩阵的元素改为负值，然后进行第2步。 如果求目标函数S＝f(X)的极小值，则直接进行第2步。 第2步：若第i行的最小元素不是0，则从该行的每个元素中减去此最小元素。(i＝1～m)。 第4章线性整数规划指派问题 * 匈牙利法 第3步：若第j列的最小元素不是0，则从该列的每个元素中减去此最小元素。(j=1～n)。 第4步：逐个检查每一行，看是否每一行只有一个未标注的0，如只有一个0存在，则在此元素上注以符号△，表示一种分配，同时，对同一列的0元素打×，以便下一个分配不落在此列上。重复这一过程，直到所有行上没有未标注△的0或至少有两个0。 第5步：逐个检查每一列，查出单一的未标注的0，打上△，对同一行的0元素打×。重复这一过程，直到所有列上没有未标注△的0或至少有两个0。 第4章线性整数规划指派问题 * 匈牙利法 第6步：反复进行第4、5步，直到下面三种情况之一发生为止： (a) 每行均标注有△； (b) 至少有两个未标注的0在各行或各列中； (c) 没有剩下未标注的0，但还未形成一完整的分配。 第7步：如果上述(a)发生，则得一完整的分配方案；且是一最优分配方案，可停机。如果是(b)发生，可任意作一分配记号△到一个0上，而将同行或同列的另一个0打×，然后转到第4步。如果是(c)发生，则转到第8步。 第4章线性整数规划指派问题 * 匈牙利法 第8步：对所有没有标注△的行打√。 第9步：在打√的行中如包含一个0元素，则给该元素所对应的(没有打√的)列打上√。 第10步：在打√的列上，如有△记号，则这些△记号的对应的行均打√。 第11步：重复第9、10步；直到所有能打√的行和列都打完。 第12步：对所有未打√的行和已打√的列划线，这些线至少有一次盖过每一个0元素，这是覆盖0元素所需的最少线数。 第4章线性整数规划指派问题 * 匈牙利法 第13步：检查所有没有线通过的元素，选择出其中最小者。在未完全划线的行中，对每一元素减去此最小数，再在有线通过的列上，对每一元素加上此最小数，得一新矩阵，再回到第4步。 第4章线性整数规划指派问题 * 三、匈牙利法的FORTRAN程序 该程序用于解n个资源、n个活动对象的分配问题，要求使目标函数f(X)为最优。可用以求目标函数的极大值；也可用以求目标函数的极小值。但要求其效应矩阵C的各元素cij必须是整数。 该程序由主程序和子程序组成。主程序包括数据输入、输出。子程序即为匈牙利算法，称为HUNGRY。 使用下面所列程序至多可解决15个资源、15个对象的问题。若所要求解的问题中资源的个数、对象的个数大于15，即n＞15，只需改变主程序中DIMENSION语句中的维数即可。 第4章线性整数规划指派问题 * 匈牙利法的FORTRAN程序 使用该程序时，应输入下列数据： N──资源、对象的个数。 KODE──对于最小化问题，KODE =0；对于最大化问题，KODE =1。 MATRIX(I,J)──初始效应矩阵。 该程序将计算并打印出： IASMAT──分配矩阵(ASSIGNMENT MATRIX)。 NCOST──目标函数的最优值。 第4章线性整数规划指派问题 * 匈牙利法的FORTRAN程序 具体程序如下： CCCC 用于求解资源分配问题的匈牙利算法程序 CCCC 需要输入的数据为： CCCC N──资源、对象的个数。 CCCC KODE──对于极小值问题，KODE =0；对于极大值问题，KODE =1。 CCCC MATRIX(I,J)──初始效应矩阵，按行输入。 DIMENSION MATRIX(15,15),IASMAT(15) OPEN(21,FILE=HUN.IN) OPEN(22,FILE=HUN.OUT) READ(21,*) N,KODE DO 2 I=1,N 2 READ(21,*) (MATRIX(I,J),J=1,N) CLOSE(21) WRITE(22,*) 初始效应矩阵为： DO 6 I=1,N 6 WRITE(22,5)(MATRIX(I,J),J=1,N) 第4章线性整数规划指派问题 * 5 FORMAT(1X,10I8) CALL HUNGRY(N,MATRIX,IASMAT,NCOST,KODE) WRITE(22,120) NCOST 120 FORMAT(/1X,最优目