运筹学的运输问题最小元素法（运筹学基础运输问题）

一. 运输问题

设有 mm 个产地 A1,⋯,AmA_1, \, \cdots,\, A_m 其产量（供应量）分别为 SiS_i；nn 个销地 B1,⋯,BnB_1, \, \cdots , \, B_n , 其销量（需求量)分别为DjD_j ；从产地 AiA_i 运往销地 BjB_j 的运费为 cijc_{ij} . 假设产销平衡，问如何安排运输方案能使总运费最小？

这就是经典的运输问题，设从 AiA_i 运往 BjB_j 的运量为xijx_{ij} (决策变量），则建立运输模型：minf=∑i=1m∑j=1ncijxijs.t.∑j=1nxij=Si,i=1,⋯m∑i=1mxij=Dj,j=1,⋯,nxij≥0,i=1,⋯,m;j=1,⋯n\min ~~ f=\sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} x_{i j} \\ s.t. \quad \sum_{j=1}^{n} x_{i j}=S_{i}, \quad i=1, \cdots m \\ \qquad ~~~\sum_{i=1}^{m} x_{i j}=D_{j}, \quad j=1, \cdots, n \\ \qquad \qquad ~~~~~~ x_{i j} \geq 0, \quad i=1, \cdots, m; \; j=1, \cdots n

其中，约束条件 1 表示从 ii 地运出量等于 ii 地的供应量；约束条件 2 表示运往jj 地的运量等于 jj 地的需求量。

运输问题是特殊的线性规划问题，笔算适合用变种的单纯形法—表上作业法。

表上作业法，首先要求出初始可行解（即满足约束条件的初始调运方案），这通常有两种算法：最小元素法、Vogel法。

二. 最小元素法

最小元素法的基本思想是就近供应，即从运价表中最小的运价开始确定产销关系，依此

类推，一直到给出基本方案为止。

算法步骤：

Matlab实现：

functionB =MinElement(A,S,D)%实现按最小元素法生成运输问题的初始基可行解 %A为运价矩阵, S为供应向量, D为需求向量 %返回B为初始可行调运方案 M = 10000; %足够大数, 大于所有运价 [m,n] = size(A); B = zeros(m,n) * NaN; %存放结果 while true [~,I] = min(A(:)); [Ir,Ic] = ind2sub([m,n],I); %最小元索引, 确定供应位置 %进行调运 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 有时候也是基解元素，故用NaN表示非基空格；另外，该函数对于计算过程中，同时划去一行一列需要补 0 的情形也能实现。

代码测试：

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) cm = sum(sum(A .* Bm, omitnan)) %总运费

运行结果：

再测试一组需要补 0 的：

A = [4 10 4 4; 7 7 3 8; 1 2 10 6]; %运价矩阵 S = [20; 15; 15]; %供应 D = [5 10 25 10]; %需求 Bm0 = MinElement(A,S,D) cm0 = sum(sum(A .* Bm0, omitnan)) %总运费

运行结果：

主要参考文献

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

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

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

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