数学建模中的分枝定界法.docVIP

利用匈牙利算法与分枝定界法解决调色问题张颖 摘要： 关键词： 0 引言 研究实际课题时，建立模型不是最终目的，总会遇到设计求解算法的问题。NP完全问题一方面不可能找到求解的有效算法，另一方面枚举所有可能情况的办法对规模较大的例子仍无法实现。出于实际需要，人们以枚举为基础，选用一些减少计算量的技巧或规则，以增大算法实用效果。例如，求解线性规划的单纯形法从理论上讲是指数算法，但在实际应用时它又表现得出奇地好（其平均计算量仅为。这一实例鼓舞人们去对其余的问题寻找类似的算法。本文通过对数学建模中的一道调色问题两种算法的研究比较，提出解决最小哈密尔顿圈问题的一种设想。 1 算法 1.1 匈牙利算法 基本思想一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵则以或为系数矩阵的指派问题具有相同的最优指派。系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。 1.12算法特征 第一步：变换指派问题的系数矩阵（）为()，使在()的各行各列中都出现0元素 第二步：进行试指派，以寻求最优解。在()中找尽可能多的独立0元素记作，若能找出n个元素，就以这n个元素对应解矩阵()中的元素为1，其余为0，这就得到最优解。若元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m n, 则转入下一步。第三步：作最少的直线覆盖所有0元素。应等于m，若不相等，说明试指派过程有误，回到第二步；若l＝m n，须再变换当前的系数矩阵，以找到n个元素，为此转第四步。第四步：变换矩阵()以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。 1.21基本思想：对有约束条件的最优化问题的所有可行解（数目有限）空间进行有哪些信誉好的足球投注网站。具体执行时，把全部可行的解空间不断分割为越来越小的子集（称为分枝），并为每个子集内的解的值计算一个下界或上界（称为定界）。在每次分枝后，对凡是界限超出已知可行解值那些子集不再做进一步分枝。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。 1.22 算法 第一步，先不考虑原问题的整数限制，求解相应的松弛问题，若求得最优解，符合整数约束条件，即转下一步。 第二步，定界。在各分枝问题中，找出目标函数值最大者作为整数规划最优值的上界记为，从已符合整数条件的分枝中，找出目标函数值最大者作为下界，记为。即。 第三步，分枝。在最优解中选择一个不符合整数条件的，令 ，(不为整数)则用下列两个约束条件：其中表示不超过的最大整数，分别加入问题形成两个子问题。 第四步，应用对目标函数估界的方法，或对某一分枝重要性的了解，确定出首先要解的某一分枝的后继问题，并解此问题。若所获得的最优解符合整数条件，则就是原问题的解，若不符合整数条件，再回到第二步，并参照第四步终止后继问题。 当求解某子问题的松弛问题时，只要出现情况之一，该问题就已探明 算例分析 要调配红、蓝、白、黑、黄五种颜色的油漆。清洗调配工具所需花费的时间既和原来调配什么颜色有关又和拟调配什么颜色有关，各种情况下所需的时间见表1所示。问应当如何调配较好（要求先建立模型）。表1现调 原调 红 蓝 白 黑 黄 红 / 6 18 4 8 蓝 7 / 17 3 7 白 4 5 / 4 5 黑 20 19 24 / 22 黄 8 8 16 6 / 理解：一个油漆工每天都要使用上述五种颜料，从而他应当在完成工作后清洗好工具，以便第二天开始同样顺序的调色。如果该工人只需调配一次而不必考虑以后的工作，问题可以作类似的讨论。考察五种颜色间的指派问题，将甲色指派给乙色理解为“用完甲色清洗工具，其后使用乙色”。相应的费用矩阵为 在变换过程中，的值可能改变，它们均表示充分大的正整数，为简便起见，不妨仍用表示。从最后一个矩阵不难求得此调色问题一个最优顺序：红蓝黑白黄（黄红）。 但是我们发现，利用匈牙利算法求得的解纯系巧合。它是多项式时间算法，不可能用来解的每一例。如果将此例的费用矩阵改为 ——共计减20 相应的指派不构成一个哈密顿圈，它含有两个子圈和。 试用分枝定界法。如对矩阵，由于从其相应的等价问题中可找到费用为0的最优指派，故可知20是其总费用的一个下界。现作如下两个分枝：（1）取；（2）不取。（1）如取，即2指派给1（简记（21）），则不能再有，将矩阵中位于第一行及第二列的元素0改写成，在不允许取（12）的限下两问题的最优指派相同，作变换： 此时再做如下分枝： （情况1）取（14） （情况2）不取（14）（简记为） 情况1中位于第四行第二列的元素改为是因为此时不能取，否则将