【运筹学】表上作业法 ( 最优解判别

在上两篇博客 【运筹学】表上作业法 ( 求初始基可行解 | 最小元素法 ) , 【运筹学】表上作业法 ( 最小元素法分析 | Vogel 方法 ) 中 , 分别给出了表上作业法如何找初始基可行解 , 两种方法 " 最小元素法 " 和 " Vogel 方法 ( 差额法 ) " , 其中 Vogel 方法 得到的初始基可行解更靠近最优解 ;

下面开始判断该 初始基可行解 是否是 最优解 ;

最优解判别 : 得到一组 基可行解 之后 , 使用 检验数 判定该解是否是最优解 ;

检验数符号 : 变量 x i j \rm x_{ij} xij​ 的检验数记作 λ i j \rm \lambda_{ij} λij​ ;

检验数判定原则 : 运输规划的 目标函数求最小值 时 , 所有的 非基变量检验数 λ i j \rm \lambda_{ij} λij​ 都非负 , 该基可行解就是最优解 , 该运输方案是最优方案 ;

求检验数的方法 : ① 闭回路法 , ② 位势法 ;

使用最小元素法求得的初始基可行解 :

使用 最小元素法, 得到初始基可行解 : { x 13 = 4 x 14 = 3 x 21 = 3 x 23 = 1 x 32 = 6 x 34 = 3 \begin{cases} \rm x_{13} = 4 \\\\ \rm x_{14} = 3 \\\\ \rm x_{21} = 3 \\\\ \rm x_{23} = 1 \\\\ \rm x_{32} = 6 \\\\ \rm x_{34} = 3 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x13​=4x14​=3x21​=3x23​=1x32​=6x34​=3​

使用 Vogel 方法求得初始基可行解 :

使用 Vogel 方法, 得到初始基可行解 : { x 11 = 2 x 13 = 5 x 21 = 1 x 24 = 3 x 32 = 6 x 34 = 3 \begin{cases} \rm x_{11} = 2 \\\\ \rm x_{13} = 5 \\\\ \rm x_{21} = 1 \\\\ \rm x_{24} = 3 \\\\ \rm x_{32} = 6 \\\\ \rm x_{34} = 3 \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧​x11​=2x13​=5x21​=1x24​=3x32​=6x34​=3​

推荐使用 Vogel 方法计算初始基可行解 ;

以最小元素法获得的初始基可行解为例 :

当前的初始基可行解的总运费计算如下 :

( 3 × 4 ) + ( 10 × 3 ) + ( 1 × 3 ) + ( 2 × 1 ) + ( 4 × 6 ) + ( 3 × 5 ) = 86 \rm ( 3 \times 4 ) + ( 10 \times 3 ) + ( 1 \times 3 ) + ( 2 \times 1 ) + ( 4 \times 6 ) + ( 3 \times 5 ) = 86 (3×4)+(10×3)+(1×3)+(2×1)+(4×6)+(3×5)=86

提出问题 :

在上述运输规划表格中 , A 2 \rm A_2 A2​ 没有向 B 4 \rm B_4 B4​ 运输产品 , 如果想要增加该项的运输 ;

A 2 \rm A_2 A2​ 的产量是固定的 , 不能凭空多出来 , 如果想要多给 B 4 \rm B_4 B4​ 运输一部分 , 一定要减少其它销地的运输 ;

这里 A 2 \rm A_2 A2​ 可以减少向 B 1 \rm B_1 B1​ 或 B 3 \rm B_3 B3​ 销地运输产品的个数 ;

假如想要减少 A 2 \rm A_2 A2​ 产地运往 B 1 \rm B_1 B1​ 销地的产品数量 , 但对于 B 1 \rm B_1 B1​ 销地来说 , 从 A 2 \rm A_2 A2​ 产地获取的产品少了 , 需要从其它产地获取更多产品 , 而此时其它的产地的产品运输都是饱和的 , 多不出来 ;

运量变化规则 :

单纯形法中每次迭代中 , 要选出一个 出基变量 , 和一个 入基变量 , 这两个成对出现 ;

同理在运输规划中 , 也有类似的概念 ; 增加某个方向的运量 , 需要立刻体现出 减少了某个方向的运量 , 增加一个 , 减少一个 ; 增加和减少交替出现 ;

不可行的修改方案 :

如果想要增加一个销地的运量 , 就需要减少另外一个销地的运量 , 但是注意 , 减少另外销地的运量不能影响其它的运输问题 , 上述情况下 增加 A 2 \rm A_2 A2​ 向 B 4 \rm B_4 B4​ 的运量 , 此时如果要 减少 A 2 \rm A_2 A2​ 对 B 1 \rm B_1 B1​ 的运量 , 会引起 B 1 \rm B_1 B1​ 销地供货不足 , 导致另外的连锁反应 , 需要增加另外产地的向 B 1 \rm B_1 B1​ 供货 , 但是 A 1 , A 3 \rm A_1 , A_3 A1​,A3​ 都没有可以增加供货的空间 ;

这样无法形成一个闭合回路 ;

可行的修改方案 :

增加 A 2 \rm A_2 A2​ 向 B 4 \rm B_4 B4​ 的运量 , 如果 减小 A 2 \rm A_2 A2​ 向 B 3 \rm B_3 B3​ 运输的产品数 , B 3 \rm B_3 B3​ 得到的物资从 A 2 \rm A_2 A2​ 减少 , 那么相应 A 1 \rm A_1 A1​ 向 B 3 \rm B_3 B3​ 供货需要增加 , A 2 \rm A_2 A2​ 向 B 3 \rm B_3 B3​ 的运输量最多减少 1 1 1 个 , 对于 A 1 \rm A_1 A1​ 来说 , 向 A 3 \rm A_3 A3​ 运输增加了 , 一定需要减少运往某个销地的运量 , 只能 减少 A 1 \rm A_1 A1​ 到 B 4 \rm B_4 B4​ 的运量 , 此时发现产销又平衡了 ;

A 2 \rm A_2 A2​ 到 B 4 \rm B_4 B4​ 最多能增加 1 1 1 个单位 , 此时 A 2 \rm A_2 A2​ 到 B 3 \rm B_3 B3​ 减少 1 1 1 个单位 , A 1 \rm A_1 A1​ 到 B 3 \rm B_3 B3​ 增加 1 1 1 个单位 , A 1 \rm A_1 A1​ 到 B 4 \rm B_4 B4​ 减少 1 1 1 个单位 ;

是否采取上述可行的修改方案 , 要看修改后的总运费是否小于修改前的总运费 , 如果修改后总费用减小 , 则进行修改 , 反之则不修改 ;

经过上述计算后的运费表格如下 :

计算当前的总运费 :

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

总费用确实减少了 , 比之前的减少了 1 1 1 的总费用 , 需要采取修改后的方案 ;

与之前的总运费表格对比 :

此时 x 24 \rm x_{24} x24​ 是新增加的基变量 , 这是 入基变量 , 由非基变量变为基变量 ;

原来的基变量 x 23 \rm x_{23} x23​ 变成了非基变量 , 这是 出基变量 ;

闭回路法 :

上述示例中找了一个 A 2 \rm A_2 A2​ 到 B 4 \rm B_4 B4​ 的格子对应的非基变量 x 24 \rm x_{24} x24​ 找闭回路 , 实际上任意一个非基变量都存在一个闭回路 ;

此时找到了针对最优解的判定方案 , 是针对 非基变量 进行判断 , 对于 任意一个非基变量 , 都可以找到这样的闭回路 ,

出发的格子中 增加运输量 , 然后某个格子需要 减少运输量 , 增加 与 减少 依次交替 , 最终能回到初始的格子, 达到产销平衡 ;

出发的格子使用加号 + + + , 第二个格子使用减号 − - − , 之后的歌词依次使用 加号减号交替 + − +- +− 符号 ;

让其运费做一个 " + − + − ⋯ +-+-\cdots +−+−⋯ " 运算 , 最终看代数和 ;

如果代数和 大于等于 0 0 0 , 说明当前的非基变量格子取 0 0 0 就是 最优选择 ;

如果代数和 小于 0 0 0 , 说明当前的非基变量格子取 0 0 0 不是最优选择 ;