【运筹学】表上作业法 ( 示例 | 使用 “ 闭回路法 “ 计算检验数判定最优解 )
一、运输规划问题
运输规划问题 :
| B 1 \rm B_1 B1 | B 1 \rm B_1 B1 | B 1 \rm B_1 B1 | B 1 \rm B_1 B1 | 产量 | |
|---|---|---|---|---|---|
| A 1 \rm A_1 A1 | 3 3 3 | 11 11 11 | 4 4 4 | 4 4 4 | 7 7 7 |
| A 1 \rm A_1 A1 | 7 7 7 | 7 7 7 | 3 3 3 | 8 8 8 | 4 4 4 |
| A 1 \rm A_1 A1 | 1 1 1 | 2 2 2 | 10 10 10 | 6 6 6 | 9 9 9 |
| 销量 | 3 3 3 | 6 6 6 | 5 5 5 | 6 6 6 | 20 20 20 |
使用最小元素法找到的初始基变量与基可行解 :
| 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 | 4 4 4 , 1 1 1 | 4 4 4 , 6 6 6 | 7 7 7 |
| A 2 \rm A_2 A2 | 7 7 7 | 7 7 7 | 3 3 3 , 4 4 4 | 8 8 8 | 4 4 4 |
| A 3 \rm A_3 A3 | 1 1 1 , 3 3 3 | 2 2 2 , 6 6 6 | 10 10 10 | 6 6 6 , 0 0 0 | 9 9 9 |
| 销量 | 3 3 3 | 6 6 6 | 5 5 5 | 6 6 6 | 20 20 20 |
二、使用 " 闭回路法 " 计算检验数判定最优解
计算检验数 判定上述 初始基可行解 是否是 最优解 ;
每个非基变量 , 都要计算一次检验数 ;
1. 计算 σ 11 \sigma_{11} σ11 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 11 = 3 − 1 + 6 − 4 = 4 ≥ 0 \sigma_{11} = 3 - 1 + 6 - 4 =4 \geq 0 σ11=3−1+6−4=4≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 4 4 4 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
2. 计算 σ 12 \sigma_{12} σ12 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 12 = 11 − 2 + 6 − 4 = 11 ≥ 0 \sigma_{12} = 11 - 2 + 6 - 4 =11 \geq 0 σ12=11−2+6−4=11≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 11 11 11 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
3. 计算 σ 21 \sigma_{21} σ21 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 21 = 7 − 1 + 6 − 4 + 4 − 3 = 9 ≥ 0 \sigma_{21} = 7 - 1 + 6 - 4 + 4 - 3 =9 \geq 0 σ21=7−1+6−4+4−3=9≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 9 9 9 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
4. 计算 σ 22 \sigma_{22} σ22 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 22 = 7 − 2 + 6 − 4 + 4 − 3 = 8 ≥ 0 \sigma_{22} = 7 - 2 + 6 - 4 + 4 - 3 =8 \geq 0 σ22=7−2+6−4+4−3=8≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 8 8 8 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
5. 计算 σ 24 \sigma_{24} σ24 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 24 = 8 − 4 + 4 − 3 = 5 ≥ 0 \sigma_{24} = 8 - 4 + 4 - 3 =5 \geq 0 σ24=8−4+4−3=5≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 5 5 5 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
6. 计算 σ 33 \sigma_{33} σ33 检验数
使用 闭回路法 计算检验数 , 首先要确定闭回路 ; 以非基变量为起点 , 然后构造回路 , 只能在基变量对应的格子位置拐弯 ;
σ 33 = 10 − 6 + 4 − 4 = 4 ≥ 0 \sigma_{33} = 10 - 6 + 4 - 4 =4 \geq 0 σ33=10−6+4−4=4≥0
该检验数 ≥ 0 \geq 0 ≥0 , 如果按照这个回路调整运费会增加 , 每调整一个产品都会增加 4 4 4 个单位运费 ;
计算检验数时 , 只计算拐弯的基变量的运费 , 经过的基变量运费不计算 ;
经过上述运算 , 所有的非基变量检验数都 ≥ 0 \geq 0 ≥0 , 当前的基可行解就是最优解 ;
文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。
原文链接：hanshuliang.blog.csdn.net/article/details/112306909
- 点赞
- 收藏
- 关注作者
评论（0）