其实位势法检验的步骤例题的问题并不复杂，但是又很多的朋友都不太了解位势法，因此呢，今天小编就来为大家分享位势法检验的步骤例题的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！

本文目录

用闭回路法求检验数，需要对每一个非基变量（表上画“×”的地方）寻找闭回路，然后再去求检验数，当一个运输问题的产销点很多时，这种方法的计算工作量是很大的，不如位势法简单，下面通过实例简单介绍一下位势法。?简单的说，位势法就是通过与基变量的对应的单位运价把各行、各列对应的位势（可以先设成未知数）求出来，再利用它求出非基变量检验数的一种方法，这种方法的合理性来自于线性规划问题的对偶理论（有兴趣的同学可以参考文献（1）86页的内容）。

在线性规划问题的对偶理论和单纯型法，在基变量对应的检验数为零，所以有下面的方程组?u1?+?v3?=3

u1?+?v4?=10

u2?+?v1?=1

u2?+?v3?=2

u3?+?v2?=4

u3?+?v4?=5

由于是7个未知数6个方程，所以必须给某一变量初始值。一般是令u1=0，可以解出其它的位势如表上所示。?根据定理（课本上的定理5）?非基变量xij的检验数

给出最短路问题的数学模型，根据线性规划的对偶原理提出了最短路问题的两种位势法。这两种算法的计算思路均为：从确定一个起点势和标准势开始；再用标准势与已确定最短路的顶点势进行比较，按照势的由小到大顺序逐步得到其他顶点的势和路由，每次迭代要更新标准势；直到找到终点的势和路由为止。两种算法采用不同的标准势计算法。一种采用原标准势累加1的更新法，该算法仅适用于正整数费用网络；另一种利用弧割的概念寻找最小标准势来代替原标准势，该算法适用于正费用情形。证明了算法的正确性以及为说明算法的有效性给出了一个算例。最后通过与Dijkstra算法的比较分析了位势法的五条特点，得出结论：位势法是求解最短路问题的有效算法。系统稳定性。

原题:4．就上题中的初始方案,利用位势法对初始方案进行检验,并调整初始方案.

参考答案:

(鼠标形状为手柄时,点击观看下一步骤.)

利用位势法对上述的题目的初始方案进行检验：先做一个表,在表中,把原来运输方案中有数字的地方换上相应的运价,并在表的右边增加一列,在表的下方增加一行.并令横行为V行,纵行为U行.并令U1=0

与初始调运方案对应的运价表

需要地

供应地

B1

B2

B3

B4

Ui

A1

2

5

1

A2

3

A3

14

11

Vj

在新增的行和列中填上数字,使表中的运价数字正好等于它所在新增行和列的数字之和.随后,将原来表中空格位置通过UV相对应位置的计算出相应的数字,如下表：

位势表

需要地

供应地

B1

B2

B3

B4

Ui

A1

2

5

1

（2）

0

A2

（0）

3

（-1）

（0）

-2

A3

（11）

14

（10）

11

9

Vj

2

5

1

2

计算检验数：用单位运价表中的数字减去位势表对应格的数字,得检验数表.

检验数表

需要地

供应地

B1

B2

B3

B4

A1

8

A2

4

8

5

A3

1

3

检验数表中的数字都大于零,所以上述方案即为最优.总运费=3×2＋1×5＋6×1＋5×3＋3×14＋9×11=173（元）

文章到此结束，如果本次分享的位势法检验的步骤例题和位势法的问题解决了您的问题，那么我们由衷的感到高兴！