前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【运筹学】表上作业法 ( 最小元素法分析 | Vogel 方法 )

【运筹学】表上作业法 ( 最小元素法分析 | Vogel 方法 )

作者头像
韩曙亮
发布于 2023-03-28 12:46:53
发布于 2023-03-28 12:46:53
1.8K0
举报

文章目录

一、" 最小元素法 " 分析


在上一篇博客 【运筹学】表上作业法 ( 求初始基可行解 | 最小元素法 ) 中 , 按照 " 最小元素法 " 找到了初始基可行解 ,

使用 " 最小元素法 " , 属于贪婪算法 , 每次都找运费最小的优先供应 , 每个步骤的方案都是最优 , 局部最优 ,

每步最优不一定能使得全局最优 ;

二、Vogel 方法 ( 差额法 )


" Vogel 方法 " 的核心思想就是从运价表中 , 分别计算 各行 , 各列 的 最小运费 和 次最小运费 差额 , 填写到表的 最右列 和 最下行 ;

基于如下运输问题进行分析 : 下面的表格代表

3

个产地 ,

4

个销地 的运输规划问题 , 表格中的内容是 某产地运往某销地的运费 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

11 11 11

3 3 3

10 10 10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9 9 9

2 2 2

8 8 8

4 4 4

1 1 1

A 3 \rm A_3 A3​

7 7 7

4 4 4

10 10 10

5 5 5

9 9 9

1 1 1

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5 5 5

1 1 1

3 3 3

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
11
3
10
7
0
\rm A_2
1
9
2
8
4
1
\rm A_3
7
4
10
5
9
1

销量

3
6
5
6

列差额

2
5
1
3

列差额 :

1

列 列差额 : 最小运费

1

, 次最小运费

3

, 差额是

2

;

2

列 列差额 : 最小运费

4

, 次最小运费

9

, 差额是

5

;

3

列 列差额 : 最小运费

2

, 次最小运费

3

, 差额是

1

;

4

列 列差额 : 最小运费

5

, 次最小运费

8

, 差额是

3

;

行差额 :

1

行 行差额 : 最小运费

3

, 次最小运费

3

, 差额是

0

;

2

行 行差额 : 最小运费

1

, 次最小运费

2

, 差额是

1

;

3

行 行差额 : 最小运费

4

, 次最小运费

5

, 差额是

1

;

1

列 列差额 为例进行分析 , 最小运费

1

, 次最小运费

3

, 差额是

2

; 如果不能使用最小运费

1

, 那么退而求其次 , 使用次最小运费

3

; 最优方案无法使用 , 考虑次优方案 , 这两个方案的差距就是 列差额

2

, 次优方案比最优方案运费高 , 高

2

;

第二列的列差额是

5

, 如果不能使用最优方案 , 使用次优方案 , 每个都要增加运费

5

, 这个增加的就太多了 , 应该 优先满足差额较高的行列 优先安排运输 ;

" Vogel 方法 " 将全局的最优考虑了进去 , 不再追求局部最优 , 使用该方法得出的初始基可行解 , 距离最优解更近 , 可以迭代更少次数 ;

1

个基变量 :

从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是

\rm B_2

的列差额

5

;

\rm B_2

列最小运费 : 这里优先给

\rm B_2

销地的最小运费

4

安排运输 , 避免为其安排次小运费 , 对应表格第

3

行第

2

列 ,

\rm A_3

产地运往

\rm B_2

销地的运费 ;

产地分析 : 对于产地

\rm A_3

来说 , 其生产

9

个 , 已经安排了

0

个 , 还可以再安排

9

个 ;

销地分析 : 对于销地

\rm B_2

来说需求

6

个 , 已经安排了

0

个 , 还可以再安排

6

个 ;

最大安排最小运费运输 , 从

\rm A_3

\rm B_2

运输

6

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

10 10 10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8 8 8

4 4 4

1 1 1

A 3 \rm A_3 A3​

7 7 7

4̸ \not 4 ​4 , 6 6 6

10 10 10

5 5 5

9 9 9

1 1 1

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

3 3 3

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
10
7
0
\rm A_2
1
\not 9
2
8
4
1
\rm A_3
7
\not 4

,

6
10
5
9
1

销量

3
6
5
6

列差额

2
\not 5
1
3

此时

\rm B_2

的销量已经全部消耗完毕 , 该列就不需要安排其它产地向

\rm B_2

销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;

2

个基变量 :

划掉了

\rm B_2

行 , 这里重新计算行差与列差 ,

\rm B_1

,

\rm B_3

列最小运费 与 次小运费 没有变化 , 行差额不变 ;

\rm A_1

,

\rm A_2

行最小运费 与 次小运费 没有变化 , 行差额不变 ;

\rm A_3

行差额需要重新计算 , 最小运费被划掉了 , 此时最小运费是

5

, 次小运费是

7

, 行差额变为

2

;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

10 10 10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8 8 8

4 4 4

1 1 1

A 3 \rm A_3 A3​

7 7 7

4̸ \not 4 ​4 , 6 6 6

10 10 10

5 5 5

9 9 9

2 2 2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

3 3 3

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
10
7
0
\rm A_2
1
\not 9
2
8
4
1
\rm A_3
7
\not 4

,

6
10
5
9
2

销量

3
6
5
6

列差额

2
\not 5
1
3

从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是

\rm B_4

的列差额

3

;

\rm B_4

列最小运费 : 这里优先给

\rm B_4

销地的最小运费

5

安排运输 , 避免为其安排次小运费 , 对应表格第

3

行第

4

列 ,

\rm A_3

产地运往

\rm B_4

销地的运费 ;

产地分析 : 对于产地

\rm A_3

来说 , 其生产

9

个 , 已经安排了

6

个 , 还可以再安排

3

个 ;

销地分析 : 对于销地

\rm B_4

来说需求

6

个 , 已经安排了

0

个 , 还可以再安排

6

个 ;

最大安排最小运费运输 , 从

\rm A_3

\rm B_4

运输

3

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

10 10 10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8 8 8

4 4 4

1 1 1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2 2 2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

3 3 3

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
10
7
0
\rm A_2
1
\not 9
2
8
4
1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
2

销量

3
6
5
6

列差额

2
\not 5
1
3

此时

\rm A_3

的产量已经全部消耗完毕 , 该行就不需要安排其它销地运输了 , 可以划掉这一行 , 讨论其它列的运输问题 ;

3

个基变量 :

划掉了

\rm B_2

行 , 这里重新计算行差与列差 ,

\rm A_1

,

\rm A_2

行最小运费 与 次小运费 没有变化 , 行差额不变 ;

\rm B_1

,

\rm B_3

列最小运费 与 次小运费 没有变化 , 列差额不变 ;

\rm B_4

列差额需要重新计算 , 最小运费被划掉了 , 此时最小运费是

8

, 次小运费是

10

, 行差额变为

2

;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

10 10 10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8 8 8

4 4 4

1 1 1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2 2 2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
10
7
0
\rm A_2
1
\not 9
2
8
4
1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
2

从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是

\rm B_1

\rm B_4

的列差额

2

; 这两个任选一个都可以 ;

\rm B_4

列最小运费 : 这里优先给

\rm B_4

销地的最小运费

8

安排运输 , 避免为其安排次小运费 , 对应表格第

2

行第

4

列 ,

\rm A_2

产地运往

\rm B_4

销地的运费 ;

产地分析 : 对于产地

\rm A_2

来说 , 其生产

4

个 , 已经安排了

6

个 , 还可以再安排

4

个 ;

销地分析 : 对于销地

\rm B_4

来说需求

6

个 , 已经安排了

3

个 , 还可以再安排

3

个 ;

最大安排最小运费运输 , 从

\rm A_2

\rm B_4

运输

3

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1 1 1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
\not 10
7
0
\rm A_2
1
\not 9
2
\not 8

,

3
4
1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

此时

\rm B_4

的销量已经全部消耗完毕 , 该列就不需要安排其它产地向

\rm B_4

销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;

4

个基变量 :

划掉了

\rm B_4

行列 , 这里重新计算行差与列差 ,

\rm A_1

,

\rm A_2

行最小运费 与 次小运费 没有变化 , 行差额不变 ;

\rm B_1

,

\rm B_3

列最小运费 与 次小运费 没有变化 , 列差额不变 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1 1 1

9̸ \not 9 ​9

2 2 2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1 1 1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
\not 10
7
0
\rm A_2
1
\not 9
2
\not 8

,

3
4
1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是

\rm B_1

的列差额

2

;

\rm B_1

列最小运费 : 这里优先给

\rm B_1

销地的最小运费

1

安排运输 , 避免为其安排次小运费 , 对应表格第

2

行第

1

列 ,

\rm A_2

产地运往

\rm B_1

销地的运费 ;

产地分析 : 对于产地

\rm A_2

来说 , 其生产

4

个 , 已经安排了

3

个 , 还可以再安排

1

个 ;

销地分析 : 对于销地

\rm B_1

来说需求

3

个 , 已经安排了

0

个 , 还可以再安排

3

个 ;

最大安排最小运费运输 , 从

\rm A_2

\rm B_1

运输

1

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1̸ \not 1 ​1 , 1 1 1

9̸ \not 9 ​9

2̸ \not 2 ​2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1̸ \not 1 ​1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
\not 10
7
0
\rm A_2
\not 1

,

1
\not 9
\not 2
\not 8

,

3
4
\not 1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

此时

\rm A_2

的产量已经全部消耗完毕 , 该行就不需要安排其它销地运输了 , 可以划掉这一行 , 讨论其它列的运输问题 ;

5

个基变量 :

划掉了

\rm A_2

行 , 这里重新计算行差与列差 ,

\rm A_1

,

\rm A_2

行最小运费 与 次小运费 没有变化 , 行差额不变 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3

1̸1 \not 11 ​11

3 3 3

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1̸ \not 1 ​1 , 1 1 1

9̸ \not 9 ​9

2̸ \not 2 ​2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1̸ \not 1 ​1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3
\not 11
3
\not 10
7
0
\rm A_2
\not 1

,

1
\not 9
\not 2
\not 8

,

3
4
\not 1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 ,

\rm A_1

的行差额

0

;

\rm A_1

列最小运费 : 这里优先给

\rm A_1

销地的最小运费

3

安排运输 , 避免为其安排次小运费 , 对应表格第

1

行第

1

列 ,

\rm A_1

产地运往

\rm B_1

销地的运费 ; ( 次小运费 = 最小运费 , 任选一个即可 )

产地分析 : 对于产地

\rm A_1

来说 , 其生产

7

个 , 已经安排了

0

个 , 还可以再安排

7

个 ;

销地分析 : 对于销地

\rm B_1

来说需求

3

个 , 已经安排了

1

个 , 还可以再安排

2

个 ;

最大安排最小运费运输 , 从

\rm A_1

\rm B_1

运输

2

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3̸ \not 3 ​3 , 2 2 2

1̸1 \not 11 ​11

3 3 3

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1̸ \not 1 ​1 , 1 1 1

9̸ \not 9 ​9

2̸ \not 2 ​2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1̸ \not 1 ​1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
\not 3

,

2
\not 11
3
\not 10
7
0
\rm A_2
\not 1

,

1
\not 9
\not 2
\not 8

,

3
4
\not 1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

此时

\rm B_1

的销量已经全部消耗完毕 , 该列就不需要安排其它产地向

\rm B_1

销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;

6

个基变量 :

此时只剩下最后一个运费没有被安排 ,

\rm A_1

产地运往

\rm B_3

销地的运费 ;

产地分析 : 对于产地

\rm A_1

来说 , 其生产

7

个 , 已经安排了

2

个 , 还可以再安排

5

个 ;

销地分析 : 对于销地

\rm B_3

来说需求

5

个 , 已经安排了

0

个 , 还可以再安排

5

个 ;

最大安排最小运费运输 , 从

\rm A_1

\rm B_3

运输

5

个产品 ;

B 1 \rm B_1 B1​

B 2 \rm B_2 B2​

B 3 \rm B_3 B3​

B 4 \rm B_4 B4​

产量

行差额

A 1 \rm A_1 A1​

3 3 3 , 2 2 2

1̸1 \not 11 ​11

3 3 3 , 5 5 5

1̸0 \not 10 ​10

7 7 7

0 0 0

A 2 \rm A_2 A2​

1̸ \not 1 ​1 , 1 1 1

9̸ \not 9 ​9

2̸ \not 2 ​2

8̸ \not 8 ​8 , 3 3 3

4 4 4

1̸ \not 1 ​1

A 3 \rm A_3 A3​

7̸ \not 7 ​7

4̸ \not 4 ​4 , 6 6 6

1̸0 \not 10 ​10

5̸ \not 5 ​5 , 3 3 3

9 9 9

2̸ \not 2 ​2

销量

3 3 3

6 6 6

5 5 5

6 6 6

列差额

2 2 2

5̸ \not 5 ​5

1 1 1

2̸ \not 2 ​2

\rm B_1
\rm B_2
\rm B_3
\rm B_4

产量行差额

\rm A_1
3

,

2
\not 11
3

,

5
\not 10
7
0
\rm A_2
\not 1

,

1
\not 9
\not 2
\not 8

,

3
4
\not 1
\rm A_3
\not 7
\not 4

,

6
\not 10
\not 5

,

3
9
\not 2

销量

3
6
5
6

列差额

2
\not 5
1
\not 2

此时

\rm B_3

的销量已经全部消耗完毕 , 该列就不需要安排其它产地向

\rm B_3

销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;

至此 , 所有的产量与销量分配完毕 ;

上述初始基可行解方案总运费 :

\rm ( 2 \times 3 ) + ( 3 \times 5 ) + ( 1 \times 1 ) + ( 3 \times 8 ) + ( 4 \times 6 ) + ( 3 \times 5 ) = 85

最小元素法求出来的初始基可行解的 总运费是

86

, " Vogel 方法 " 比 " 最小元素法 " 能找出更近的初始基可行解 ;

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-01-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 文章目录
  • 一、" 最小元素法 " 分析
  • 二、Vogel 方法 ( 差额法 )
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档