在上一篇博客 【运筹学】表上作业法 ( 求初始基可行解 | 最小元素法 ) 中 , 按照 " 最小元素法 " 找到了初始基可行解 ,
使用 " 最小元素法 " , 属于贪婪算法 , 每次都找运费最小的优先供应 , 每个步骤的方案都是最优 , 局部最优 ,
每步最优不一定能使得全局最优 ;
" Vogel 方法 " 的核心思想就是从运价表中 , 分别计算 各行 , 各列 的 最小运费 和 次最小运费 差额 , 填写到表的 最右列 和 最下行 ;
基于如下运输问题进行分析 : 下面的表格代表
个产地 ,
个销地 的运输规划问题 , 表格中的内容是 某产地运往某销地的运费 ;
| 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 | | |
产量行差额
销量
列差额
列差额 :
第
列 列差额 : 最小运费
, 次最小运费
, 差额是
;
第
列 列差额 : 最小运费
, 次最小运费
, 差额是
;
第
列 列差额 : 最小运费
, 次最小运费
, 差额是
;
第
列 列差额 : 最小运费
, 次最小运费
, 差额是
;
行差额 :
第
行 行差额 : 最小运费
, 次最小运费
, 差额是
;
第
行 行差额 : 最小运费
, 次最小运费
, 差额是
;
第
行 行差额 : 最小运费
, 次最小运费
, 差额是
;
以 第
列 列差额 为例进行分析 , 最小运费
, 次最小运费
, 差额是
; 如果不能使用最小运费
, 那么退而求其次 , 使用次最小运费
; 最优方案无法使用 , 考虑次优方案 , 这两个方案的差距就是 列差额
, 次优方案比最优方案运费高 , 高
;
第二列的列差额是
, 如果不能使用最优方案 , 使用次优方案 , 每个都要增加运费
, 这个增加的就太多了 , 应该 优先满足差额较高的行列 优先安排运输 ;
" Vogel 方法 " 将全局的最优考虑了进去 , 不再追求局部最优 , 使用该方法得出的初始基可行解 , 距离最优解更近 , 可以迭代更少次数 ;
第
个基变量 :
从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是
的列差额
;
列最小运费 : 这里优先给
销地的最小运费
安排运输 , 避免为其安排次小运费 , 对应表格第
行第
列 ,
产地运往
销地的运费 ;
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
销量
列差额
此时
的销量已经全部消耗完毕 , 该列就不需要安排其它产地向
销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;
第
个基变量 :
划掉了
行 , 这里重新计算行差与列差 ,
,
列最小运费 与 次小运费 没有变化 , 行差额不变 ;
,
行最小运费 与 次小运费 没有变化 , 行差额不变 ;
行差额需要重新计算 , 最小运费被划掉了 , 此时最小运费是
, 次小运费是
, 行差额变为
;
| 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 | | |
产量行差额
,
销量
列差额
从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是
的列差额
;
列最小运费 : 这里优先给
销地的最小运费
安排运输 , 避免为其安排次小运费 , 对应表格第
行第
列 ,
产地运往
销地的运费 ;
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
,
销量
列差额
此时
的产量已经全部消耗完毕 , 该行就不需要安排其它销地运输了 , 可以划掉这一行 , 讨论其它列的运输问题 ;
第
个基变量 :
划掉了
行 , 这里重新计算行差与列差 ,
,
行最小运费 与 次小运费 没有变化 , 行差额不变 ;
,
列最小运费 与 次小运费 没有变化 , 列差额不变 ;
列差额需要重新计算 , 最小运费被划掉了 , 此时最小运费是
, 次小运费是
, 行差额变为
;
| 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 | | |
产量行差额
,
,
销量
列差额
从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是
和
的列差额
; 这两个任选一个都可以 ;
列最小运费 : 这里优先给
销地的最小运费
安排运输 , 避免为其安排次小运费 , 对应表格第
行第
列 ,
产地运往
销地的运费 ;
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
,
,
销量
列差额
此时
的销量已经全部消耗完毕 , 该列就不需要安排其它产地向
销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;
第
个基变量 :
划掉了
行列 , 这里重新计算行差与列差 ,
,
行最小运费 与 次小运费 没有变化 , 行差额不变 ;
,
列最小运费 与 次小运费 没有变化 , 列差额不变 ;
| 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 | | |
产量行差额
,
,
,
销量
列差额
从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 , 是
的列差额
;
列最小运费 : 这里优先给
销地的最小运费
安排运输 , 避免为其安排次小运费 , 对应表格第
行第
列 ,
产地运往
销地的运费 ;
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
,
,
,
销量
列差额
此时
的产量已经全部消耗完毕 , 该行就不需要安排其它销地运输了 , 可以划掉这一行 , 讨论其它列的运输问题 ;
第
个基变量 :
划掉了
行 , 这里重新计算行差与列差 ,
,
行最小运费 与 次小运费 没有变化 , 行差额不变 ;
| 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 | | |
产量行差额
,
,
,
,
销量
列差额
从所有 没有被划掉 的并且 没有被安排 的的运费中找到差额最大的 ,
的行差额
;
列最小运费 : 这里优先给
销地的最小运费
安排运输 , 避免为其安排次小运费 , 对应表格第
行第
列 ,
产地运往
销地的运费 ; ( 次小运费 = 最小运费 , 任选一个即可 )
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
,
,
,
,
销量
列差额
此时
的销量已经全部消耗完毕 , 该列就不需要安排其它产地向
销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;
第
个基变量 :
此时只剩下最后一个运费没有被安排 ,
产地运往
销地的运费 ;
产地分析 : 对于产地
来说 , 其生产
个 , 已经安排了
个 , 还可以再安排
个 ;
销地分析 : 对于销地
来说需求
个 , 已经安排了
个 , 还可以再安排
个 ;
最大安排最小运费运输 , 从
向
运输
个产品 ;
| 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 | | |
产量行差额
,
,
,
,
,
,
销量
列差额
此时
的销量已经全部消耗完毕 , 该列就不需要安排其它产地向
销地运输了 , 可以划掉这一列 , 讨论其它列的运输问题 ;
至此 , 所有的产量与销量分配完毕 ;
上述初始基可行解方案总运费 :
最小元素法求出来的初始基可行解的 总运费是
, " Vogel 方法 " 比 " 最小元素法 " 能找出更近的初始基可行解 ;
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有