运输问题的表上作业法（二）：利用位势法判断当前解的最优性 |
您所在的位置：网站首页 › python取火柴最优方案 › 运输问题的表上作业法（二）：利用位势法判断当前解的最优性 |
运输问题的表上作业法（二）：利用位势法判断当前解的最优性
|
上期谈到用Python实现求解运输问题 (Transportation Problem, TP) 的表上作业法的第一步——利用Vogel法寻找初始基可行解： 运输问题的表上作业法（一）：利用伏格尔 (Vogel) 法寻找初始基可行解 这期来讲讲找到初始基可行解之后怎样判断当前解是否是最优解。如果当前解已达到最优，那么无需再进行操作；如果当前解非最优，那么还要对当前解进行调整以达到最优。调整解的操作放到下一期再讲，本期先谈谈怎样判断最优性。 文章目录 位势法（对偶变量法）位势法应用实例位势法的Python语句通常判断TP问题解的最优性有两种方法：闭回路法和位势法。考虑到两种方法代码的复杂程度，我们重点讲讲更容易实现的位势法。位势法（Potentials）又称对偶变量法，是利用线性规划的对偶原理计算解的检验数，从而通过检验数判断最优性的方法。关于对偶原理，请参考运筹学相关书籍，这里不进行阐述，而只对位势法原理进行简单介绍。 位势法（对偶变量法）
下面通过一个运输问题的例题进一步说明位势法原理。 Example： 已知该TP问题的运输（成本）表如下（将中间3x4的成本表记为表1）：  把初始基可行解中非零元素对应位置的成本系数剥离出来，并添加上位势（图中u1-u3、v1-v4），记为表2：  构建位势方程组（需要注意的是，TP问题的可行解中非零变量个数为m+n-1，其中m、n分别是成本矩阵的行数和列数（本例中m=3,n=4），所以位势方程组应该含有m+n-1个方程；但是位势的个数为m+n，即方程组有m+n个未知量，多于方程的个数，可知方程组是解不出来的，因此我们随便令某个位势=0，即可求解这个方程组，并且此操作对最后检验数无影响）：  求出位势后，将ui+vj填入成本表中对应解变量为0的位置，记为表3：  表1-表3（σij=cij-(ui+vj)，对应位置元素相减），得到检验数表σ：  判断最优性：由于本例是极小化问题，如果检验数表中存在σij=0):
print('>>>TP已达到最优解>>TP未达到最优解>>位势方程组不可解 |
【本文地址】
今日新闻 |
推荐新闻 |