本
文
摘
要
接前两篇：
张敬信：【运筹学】最小元素法求运输问题初始基解的Matlab实现35 赞同 · 2 评论文章张敬信：【运筹学】Vogel法求运输问题初始基解的Matlab实现17 赞同 · 7 评论文章得到初始基可行解后，下一步需要判断是否为最优解，这就需要计算非基变量的检验数 σij\sigma_{ij} .
通常有两种方法：闭回路法、位势法。
闭回路法代码实现比较麻烦，先不考虑。
四. 位势法
算法原理：
由单纯形法的检验数公式，可得
σij=cij−CBB−1Pij=cij−(u1,⋯,um,v1,⋯,vn)Pij=cij−(ui+vj)\begin{align} \sigma_{ij} & = c_{ij} - C_B B^{-1} P_{ij} \\ & = c_{ij}-(u_1, \cdots, u_m, v_1, \cdots, v_n) P_{ij} \\ &= c_{ij} - (u_i+v_j) \end{align}
与每一行对应的数 uiu_i 称为是行位势，与每一列对应的 vjv_j 称为列位势。由于基变量的检验数为 0, 代入上式就得到关于 ui,vju_i,\,v_j 的方程组:
cij=ui+vj,i=1,⋯,m;j=1,⋯,nc_{ij}= u_i + v_j, \quad i =1 , \cdots, m; \; j = 1, \cdots, n
其中， ui,vju_i , \, v_j 取正、负、0均可。
对于 mm 个产地、 nn 个销地的运输问题，有 mm 个行位势、 nn 个列位势，即该方程组有 m+nm+n个未知数；而基变量的个数只有 m+n−1m+n-1 个，即该方程组只有 m+n−1m+n-1 个方程。
所以需要任意假定一个未知数的值，一般假定 u1=0u_1 =0 , 再求解该方程组即可得到所有 ui,vju_i, \, v_j 。再代入 σi,j=ci,j−(ui+vj)\sigma_{i,j} = c_{i,j} - (u_i+v_j) 就能求出非基变量的检验数 σij\sigma_{ij} .
算法步骤:
（1）与当前解每一个基变量 xijx_{ij} 对应，令
cij=ui+vj,i=1,⋯,m;j=1,⋯,nc_{ij}= u_i + v_j, \quad i =1 , \cdots, m; \; j = 1, \cdots, n
得到 m+nm+n 个未知数， m+n−1m+n-1 个方程的方程组，假定 u1=0u_1 =0 , 求解该方程组得到所有 ui,vju_i, \, v_j 。
（2）再用公式 σi,j=ci,j−(ui+vj)\sigma_{i,j} = c_{i,j} - (u_i+v_j) 求出非基变量对应的检验数 σij\sigma_{ij} .
Matlab实现：
functionSigma =Potential(C,B)%实现用位势法计算检验数Sigma %输入参数C为运价矩阵, B为初始调运方案矩阵 %返回检验数矩阵Sigma [m,n] = size(C); [I,J] = find(~isnan(B)); %找到基变量的位置 b = [0; C(sub2ind([m,n],I,J))]; A = zeros(m+n); A(1,1) = 1; for i=1:n+m-1 A(i+1,[I(i),J(i)+m]) = 1; end x = A \ b; %解方程组 u = x(1:m); v = x(m+1:end); %计算Sigma [nI,nJ] = find(isnan(B)); %找到非基变量的位置 Sigma = zeros(m,n) * NaN; for i=1:length(nI) Sigma(nI(i),nJ(i)) = C(nI(i),nJ(i)) - (u(nI(i)) + v(nJ(i))); end测试代码：
A = [3 11 3 10; 1 9 2 8; 7 4 10 5]; %运价矩阵 S = [7 4 9]; %供应 D = [3 6 5 6]; %需求 Bm = MinElement(A,S,D); %用最小元素法求初始调运方案 Bv = Vogel(A,S,D); %用Vogel法求初始调运方案 %用位势法计算检验数 SigmaM = Potential(A, Bm) SigmaV = Potential(A, Bv)运行结果：
主要参考文献
胡运全，运筹学基础及应用，第六版
百度文库，运输问题-表上作业法 https://wenku.baidu.com/view/1fb0f011640e52ea551810a6f524ccbff121caae.html
————————————————————
原创作品，版权所有，转载请注明，禁止出版盗用。
