题目
三、(15分)已知某运输问题如下(单位:百元/吨):单位运价 销地产地B1B2B3供应量(吨)A137218A2581012A394515需求量(吨)161217求:(1)使总运费最小的调运方案和最小运费。(12分)(2)该问题是否有多个最优调运方案?若没有,说明为什么;若有,请再求出一个最优调运方案来。(3分)
三、(15分)已知某运输问题如下(单位:百元/吨):
单位运价 销地
产地
B1
B2
B3
供应量(吨)
A1
3
7
2
18
A2
5
8
10
12
A3
9
4
5
15
需求量(吨)
16
12
17
求:(1)使总运费最小的调运方案和最小运费。(12分)
(2)该问题是否有多个最优调运方案?若没有,说明为什么;若有,请再求出一个最优调运方案来。(3分)
题目解答
答案
解:(1)用伏格尔法确定初始调运方案为:
B1 | B2 | B3 | 供 | |
A1 | 1 | 17 | 18 | |
A2 | 12 | 12 | ||
A3 | 3 | 12 | 15 | |
需 | 16 | 12 | 17 |
12=9;
22=0;
23=6;
33=-3 (5分)
有
ij
0,所以需要调整为:
B1 | B2 | B3 | 供 | |
A1 | 4 | 14 | 18 | |
A2 | 12 | 12 | ||
A3 | 12 | 3 | 15 | |
需 | 16 | 12 | 17 |
12=6;
22=5;
23=6;
31=3 (5分)
因为
ij
0, 所以为最优方案。
Min Z=3*4+2*14+12*5+12*4+3*5=163 为唯一最优解。 (2分)
(2)无,因为
ij>0,所以该题仅有唯一最优方案。 (3分)
评分标准:1. 得运输表5分。2. 运输问题求解8分。3.得出最终结论2分4. 其他情况酌情给分。
解析
运输问题的核心是通过合理调配资源,使得总运费最小。本题需掌握以下关键点:
- 伏格尔法:用于确定初始可行解,通过计算各行、列的机会成本(罚数),优先满足罚数最大的行或列。
- 闭回路调整法:通过调整非基变量(检验数为负)的运量,逐步优化方案。
- 最优性检验:若所有非基变量的检验数均非负,则为最优解;若存在检验数为零,则存在多个最优解。
第(1)题
步骤1:用伏格尔法确定初始调运方案
- 计算罚数:每行、每列中最小运价与次小运价的差值。
- 选择罚数最大行/列:优先满足该方向的需求。
- 分配运量:在选定行/列中,尽可能多地分配运量,直至满足需求或耗尽供应量。
步骤2:闭回路调整
- 选择检验数最小的非基变量(本题为$u_{23}=-3$)。
- 构造闭回路:调整路径为$A_2 \to B_3 \to A_3 \to B_1 \to A_2$。
- 调整运量:沿闭回路增减运量,确保供需平衡。
步骤3:最优性检验
计算所有非基变量的检验数,若均非负,则为最优解。本题检验数均为正,故为最优。
第(2)题
若存在检验数为零的非基变量,则有多个最优解。本题所有检验数均正,故唯一最优解。