在运筹学中，运输问题是一种经典的线性规划问题，主要用于解决如何将货物从多个供应点高效地运送到多个需求点，以达到总运输成本最低或运输效率最高的目标。在众多求解运输问题的方法中，“最小元素法”是一种常用的初始基可行解的求解方法，它基于“优先满足单位运价最低的供需关系”的原则进行分配。
下面通过一个具体的例题来说明如何使用“最小元素法”求解运输问题。
一、问题描述
某公司有三个仓库（A、B、C），四个销售点（D、E、F、G）。各仓库的供应量和各销售点的需求量如下表所示：
| | D | E | F | G | 供应量 |
|---|---|---|---|---|--------|
| A | 3 | 1 | 4 | 2 | 10 |
| B | 5 | 6 | 7 | 8 | 15 |
| C | 9 | 8 | 7 | 6 | 20 |
| 需求量 | 8 | 7 | 12 | 10 | 37|
其中，数字表示从对应仓库到销售点的单位运价（即每单位货物的运输费用）。
我们的目标是：根据上述数据，采用“最小元素法”确定一个初始的运输方案，并计算其总运输成本。
二、最小元素法的步骤
1. 找出当前表格中所有未被分配的最小单位运价。
2. 将该运价对应的供应量与需求量中较小的一个尽可能多地分配给该单元格。
3. 调整相应的供应量和需求量，并划去已满足的行或列。
4. 重复以上步骤，直到所有的供应量和需求量都被满足。
三、具体计算过程
我们首先列出完整的运输表：
| | D (8) | E (7) | F (12) | G (10) | 供应量 |
|---|-------|-------|--------|--------|--------|
| A (10) | 3 | 1 | 4| 2| 10 |
| B (15) | 5 | 6 | 7| 8| 15 |
| C (20) | 9 | 8 | 7| 6| 20 |
| 需求量 | 8 | 7 | 12| 10 | 37 |
第一步：找到最小的单位运价
当前表格中最小的运价是 1（位于A→E），所以优先分配A→E。
- A的供应量为10，E的需求量为7。
- 所以，分配7个单位从A到E。
更新后表格：
| | D (8) | E (0) | F (12) | G (10) | 供应量 |
|---|-------|-------|--------|--------|--------|
| A (3) | 3 | - | 4| 2| 3|
| B (15) | 5 | 6 | 7| 8| 15 |
| C (20) | 9 | 8 | 7| 6| 20 |
| 需求量 | 8 | 0 | 12| 10 | 37 |
划去E列。
第二步：再次寻找最小运价
此时，未被分配的最小运价是 2（位于A→G）。
- A的剩余供应量为3，G的需求量为10。
- 分配3个单位从A到G。
更新后表格：
| | D (8) | E (0) | F (12) | G (7) | 供应量 |
|---|-------|-------|--------|-------|--------|
| A (0) | - | - | 4| - | 0|
| B (15) | 5 | 6 | 7| 8 | 15 |
| C (20) | 9 | 8 | 7| 6 | 20 |
| 需求量 | 8 | 0 | 12| 7 | 37 |
划去A行。
第三步：继续寻找最小运价
当前最小运价为 4（位于B→F），但B的供应量为15，F的需求量为12。
- 分配12个单位从B到F。
更新后表格：
| | D (8) | E (0) | F (0) | G (7) | 供应量 |
|---|-------|-------|-------|-------|--------|
| A (0) | - | - | - | - | 0|
| B (3) | 5 | 6 | - | 8 | 3|
| C (20) | 9 | 8 | 7 | 6 | 20 |
| 需求量 | 8 | 0 | 0 | 7 | 37 |
划去F列。
第四步：继续寻找最小运价
当前最小运价为 5（位于B→D），B剩余供应量为3，D需求量为8。
- 分配3个单位从B到D。
更新后表格：
| | D (5) | E (0) | F (0) | G (7) | 供应量 |
|---|-------|-------|-------|-------|--------|
| A (0) | - | - | - | - | 0|
| B (0) | - | - | - | 8 | 0|
| C (20) | 9 | 8 | 7 | 6 | 20 |
| 需求量 | 5 | 0 | 0 | 7 | 37 |
划去B行。
第五步：继续寻找最小运价
当前最小运价为 6（位于C→G），C的供应量为20，G的需求量为7。
- 分配7个单位从C到G。
更新后表格：
| | D (5) | E (0) | F (0) | G (0) | 供应量 |
|---|-------|-------|-------|-------|--------|
| A (0) | - | - | - | - | 0|
| B (0) | - | - | - | - | 0|
| C (13) | 9 | 8 | 7 | - | 13 |
| 需求量 | 5 | 0 | 0 | 0 | 37 |
划去G列。
第六步：最后分配
剩余需求为D（5），剩余供应为C（13）。
- 分配5个单位从C到D。
最终运输方案如下：
| | D | E | F | G | 供应量 |
|---|---|---|---|---|--------|
| A | 0 | 7 | 0 | 3 | 10 |
| B | 3 | 0 | 12 | 0 | 15 |
| C | 5 | 0 | 0 | 7 | 20 |
| 需求量 | 8 | 7 | 12 | 10 | 37|
四、总运输成本计算
- A→E: 7 × 1 = 7
- A→G: 3 × 2 = 6
- B→F: 12 × 7 = 84
- B→D: 3 × 5 = 15
- C→G: 7 × 6 = 42
- C→D: 5 × 9 = 45
总成本 = 7 + 6 + 84 + 15 + 42 + 45 = 199
五、总结
通过“最小元素法”，我们得到了一个初始的运输方案，并计算了其总运输成本。虽然该方法并不一定得到最优解，但它为后续的优化提供了良好的起点。在实际应用中，通常会结合“位势法”或“闭回路法”进一步优化方案。
此例题展示了如何利用“最小元素法”求解运输问题的基本思路和操作步骤，适用于教学与实践中的初步分析。
