题目
给出如下运输问题 运 销价 产 B1 B2 B3 B4产量 Al 5 3 10 4 90 A2 1 6 9 6 40 A3 20 10 5 7 70销量 30 50 80 40 200(1) 应用最小元素法求其初始方案;(2)应用位势法求初始方案的检验数,并检验该方案是否为最优方案
给出如下运输问题
运 销
价
产
B1
B2
B3
B4
产量
Al
5
3
10
4
90
A2
1
6
9
6
40
A3
20
10
5
7
70
销量
30
50
80
40
200
(1) 应用最小元素法求其初始方案;
(2)应用位势法求初始方案的检验数,并检验该方案是否为最优方案
题目解答
答案
解: (1)初始方案
B1 | B2 | B3 | B4 | 产量 | |
A1 | 50 | 40 | 90 | ||
A2 | 30 | 10 | 40 | ||
A3 | 70 | 70 | |||
销量 | 30 | 50 | 80 | 40 |
(2)检验表
B1 | B2 | B3 | B4 | ui | |
A1 | 6 | 3 | -1 | ||
A2 | 1 | ||||
A3 | 23 | 9 | 5 | -3 | |
vj | 4 | 8 | 5 |
非基变量检验数全部非负,该方案为最优方案。
解析
步骤 1:应用最小元素法求初始方案
最小元素法是一种求解运输问题初始方案的方法,其基本思想是优先选择单位运输费用最小的运输方案。具体步骤如下:
1. 从运输表中找出单位运输费用最小的单元格,将该单元格的产量和销量中较小的一个作为该单元格的运输量,然后划去该单元格所在的行或列。
2. 重复上述步骤,直到所有行和列都被划去,得到一个初始方案。
步骤 2:应用位势法求初始方案的检验数
位势法是一种检验运输问题初始方案是否最优的方法,其基本思想是通过计算非基变量的检验数来判断初始方案是否最优。具体步骤如下:
1. 为每个产地和销地分别赋予一个位势,记为u和v。
2. 根据初始方案中的基变量,利用位势的定义计算出u和v的值。
3. 利用u和v的值计算非基变量的检验数,检验数的计算公式为:σij = cij - (ui + vj),其中cij为非基变量的单位运输费用。
4. 如果所有非基变量的检验数都非负,则初始方案为最优方案;否则,需要进行调整。
步骤 3:检验初始方案是否为最优方案
根据位势法计算出的非基变量检验数,判断初始方案是否为最优方案。如果所有非基变量的检验数都非负,则初始方案为最优方案;否则,需要进行调整。
最小元素法是一种求解运输问题初始方案的方法,其基本思想是优先选择单位运输费用最小的运输方案。具体步骤如下:
1. 从运输表中找出单位运输费用最小的单元格,将该单元格的产量和销量中较小的一个作为该单元格的运输量,然后划去该单元格所在的行或列。
2. 重复上述步骤,直到所有行和列都被划去,得到一个初始方案。
步骤 2:应用位势法求初始方案的检验数
位势法是一种检验运输问题初始方案是否最优的方法,其基本思想是通过计算非基变量的检验数来判断初始方案是否最优。具体步骤如下:
1. 为每个产地和销地分别赋予一个位势,记为u和v。
2. 根据初始方案中的基变量,利用位势的定义计算出u和v的值。
3. 利用u和v的值计算非基变量的检验数,检验数的计算公式为:σij = cij - (ui + vj),其中cij为非基变量的单位运输费用。
4. 如果所有非基变量的检验数都非负,则初始方案为最优方案;否则,需要进行调整。
步骤 3:检验初始方案是否为最优方案
根据位势法计算出的非基变量检验数,判断初始方案是否为最优方案。如果所有非基变量的检验数都非负,则初始方案为最优方案;否则,需要进行调整。