运筹学基解法（运筹学基础解）

接上一篇：

张敬信：【运筹学】最小元素法求运输问题初始基解的Matlab实现35 赞同 · 2 评论文章

三. Vogel法

Vogel法的思想是：既考虑最小元素，又考虑最小和次小的差额，相当于不只看眼前一步，多看一步，所以结果一般会好于最小元素法。

具体做法就是每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值，列差值），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案。

算法步骤:

Matlab实现:

functionB =Vogel(A,S,D)%实现按Vogel法生成运输问题的初始基可行解 %A为运价矩阵, S为供应向量, D为需求向量 %返回B为初始可行调运方案 M = 10000; %足够大数 [m,n] = size(A); B = zeros(m,n) * NaN; %存放结果 while true rA = sort(A); cA = sort(A,2); %最小差值向量 minD = [(cA(:,2) - cA(:,1)), rA(2,:) - rA(1,:)]; %前m个是最小行差, 后n个是最小列差 [~,I] = max(minD); %选出最大差值索引 %选出供应位置(Ir,Ic) if I > m Ic = I - m; [~,Ir] = min(A(:,Ic)); else Ir = I; [~,Ic] = min(A(Ir,:)); end %进行调运 if S(Ir) > D(Ic) %若供应大于需求 B(Ir,Ic) = D(Ic); S(Ir) = S(Ir) - D(Ic); D(Ic) = 0; A(:,Ic) = M; elseif S(Ir) < D(Ic) %若供应小于需求 B(Ir,Ic) = S(Ir); D(Ic) = D(Ic) - S(Ir); S(Ir) = 0; A(Ir,:) = M; else %若供应等于需求 B(Ir,Ic) = S(Ir); S(Ir) = 0; D(Ic) = 0; A(Ir,:) = M; A(:,Ic) = M; if min(min(A)) == M break else ind = find(isnan(B(:,Ic))); B(ind(1),Ic) = 0; %补0 end end end

注：后面调运部分的代码与最小元素法完全相同（所以，需要补 0 情况也没问题），只是在前期确定供应位置时，多了有关差额的操作。

测试代码：

A = [3 11 3 10; 1 9 2 8; 7 4 10 5]; %运价矩阵 S = [7 4 9]; %供应 D = [3 6 5 6]; %需求 Bv = Vogel(A,S,D) cv = sum(sum(A .* Bv, omitnan)) %总运费

运行结果：

主要参考文献

胡运全，运筹学基础及应用，第六版

百度文库，运输问题-表上作业法 https://wenku.baidu.com/view/1fb0f011640e52ea551810a6f524ccbff121caae.html

————————————————————

原创作品，版权所有，转载请注明，禁止出版盗用。