【运筹学】表上作业法 ( 最优解判别 | 初始基可行解 | 运费修改可行性方案 | 闭回路法 )

2023-03-28 20:47:12 浏览数 (1)

文章目录

  • 一、最优解判别
  • 二、初始基可行解
  • 三、运费修改可行性方案
  • 四、闭回路法

一、最优解判别

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

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

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

检验数符号 : 变量

rm x_{ij}

的检验数记作

rm lambda_{ij}

;

检验数判定原则 : 运输规划的 目标函数求最小值 时 , 所有的 非基变量检验数

rm lambda_{ij}

都非负 , 该基可行解就是最优解 , 该运输方案是最优方案 ;

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

二、初始基可行解

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

​

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 , 4 4 4

10 10 10 , 3 3 3

7 7 7

A 2 rm A_2 A2​

1 1 1 , 3 3 3

9 9 9

2 2 2 , 1 1 1

8 8 8

4 4 4

A 3 rm A_3 A3​

7 7 7

4 4 4 , 6 6 6

10 10 10

5 5 5 , 3 3 3

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

​

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
3
11
3

,

4
10

,

3
7
rm A_2
1

,

3
9
2

,

1
8
4
rm A_3
7
4

,

6
10
5

,

3
9

销量

3
6
5
6

使用 最小元素法, 得到初始基可行解 :

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}

使用 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 , 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

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

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}

推荐使用 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 , 4 4 4

10 10 10 , 3 3 3

7 7 7

A 2 rm A_2 A2​

1 1 1 , 3 3 3

9 9 9

2 2 2 , 1 1 1

8 8 8

4 4 4

A 3 rm A_3 A3​

7 7 7

4 4 4 , 6 6 6

10 10 10

5 5 5 , 3 3 3

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

​

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
3
11
3

,

4
10

,

3
7
rm A_2
1

,

3
9
2

,

1
8
4
rm A_3
7
4

,

6
10
5

,

3
9

销量

3
6
5
6

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

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

提出问题 :

在上述运输规划表格中 ,

rm A_2

没有向

rm B_4

运输产品 , 如果想要增加该项的运输 ;

rm A_2

的产量是固定的 , 不能凭空多出来 , 如果想要多给

rm B_4

运输一部分 , 一定要减少其它销地的运输 ;

这里

rm A_2

可以减少向

rm B_1

或

rm B_3

销地运输产品的个数 ;

假如想要减少

rm A_2

产地运往

rm B_1

销地的产品数量 , 但对于

rm B_1

销地来说 , 从

rm A_2

产地获取的产品少了 , 需要从其它产地获取更多产品 , 而此时其它的产地的产品运输都是饱和的 , 多不出来 ;

运量变化规则 :

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

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

不可行的修改方案 :

如果想要增加一个销地的运量 , 就需要减少另外一个销地的运量 , 但是注意 , 减少另外销地的运量不能影响其它的运输问题 , 上述情况下 增加

rm A_2

向

rm B_4

的运量 , 此时如果要 减少

rm A_2

对

rm B_1

的运量 , 会引起

rm B_1

销地供货不足 , 导致另外的连锁反应 , 需要增加另外产地的向

rm B_1

供货 , 但是

rm A_1 , A_3

都没有可以增加供货的空间 ;

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

可行的修改方案 :

增加

rm A_2

向

rm B_4

的运量 , 如果 减小

rm A_2

向

rm B_3

运输的产品数 ,

rm B_3

得到的物资从

rm A_2

减少 , 那么相应

rm A_1

向

rm B_3

供货需要增加 ,

rm A_2

向

rm B_3

的运输量最多减少

1

个 , 对于

rm A_1

来说 , 向

rm A_3

运输增加了 , 一定需要减少运往某个销地的运量 , 只能 减少

rm A_1

到

rm B_4

的运量 , 此时发现产销又平衡了 ;

rm A_2

到

rm B_4

最多能增加

1

个单位 , 此时

rm A_2

到

rm B_3

减少

1

个单位 ,

rm A_1

到

rm B_3

增加

1

个单位 ,

rm A_1

到

rm B_4

减少

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

11 11 11

3 3 3 , 5 5 5

10 10 10 , 2 2 2

7 7 7

A 2 rm A_2 A2​

1 1 1 , 3 3 3

9 9 9

2 2 2

8 8 8 , 1 1 1

4 4 4

A 3 rm A_3 A3​

7 7 7

4 4 4 , 6 6 6

10 10 10

5 5 5 , 3 3 3

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

​

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
3
11
3

,

5
10

,

2
7
rm A_2
1

,

3
9
2
8

,

1
4
rm A_3
7
4

,

6
10
5

,

3
9

销量

3
6
5
6

计算当前的总运费 :

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

总费用确实减少了 , 比之前的减少了

1

的总费用 , 需要采取修改后的方案 ;

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

此时

rm x_{24}

是新增加的基变量 , 这是 入基变量 , 由非基变量变为基变量 ;

原来的基变量

rm x_{23}

变成了非基变量 , 这是 出基变量 ;

四、闭回路法

闭回路法 :

上述示例中找了一个

rm A_2

到

rm B_4

的格子对应的非基变量

rm x_{24}

找闭回路 , 实际上任意一个非基变量都存在一个闭回路 ;

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

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

出发的格子使用加号

, 第二个格子使用减号

-

, 之后的歌词依次使用 加号减号交替

-

符号 ;

让其运费做一个 "

- -cdots

" 运算 , 最终看代数和 ;

如果代数和 大于等于

0

, 说明当前的非基变量格子取

0

就是 最优选择 ;

如果代数和 小于

0

, 说明当前的非基变量格子取

0

不是最优选择 ;

变量 表格 博客 产品 函数

0 人点赞