【运筹学】表上作业法 ( 找初始基可行解 | 计算检验数 | 调整运量 )

韩曙亮

发布于 2023-03-28 20:47:51

4420

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、运输规划问题

运输规划问题 :

二、找初始基可行解

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

	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}

三、计算检验数

计算检验数 :

使用闭回路法 , 逐个计算每个非基变量的检验数 ,

以非基变量为起点 , 出发的格子使用加号

+

, 第二个格子使用减号

-

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

+-

符号 ;

计算上述闭回路的运费代数和 ,

如果代数和大于等于

0

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

0

就是最优选择 ;

如果代数和小于

0

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

0

不是最优选择 ;

这里以计算

\rm \sigma_{24}

检验数为例 :

\rm A_{24} +

,

\rm A_{23} -

,

\rm A_{13} +

,

\rm A_{14} -

\rm \sigma_{24} = ( 1 \times 8 ) - ( 1 \times 2 ) + ( 1 \times 3 ) - ( 1 \times 10 ) = -1

检验数小于

0

;

计算出的非基变量检验数使用蓝色括号字体写在表格中 :

	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) (1)	11 11 11 , ( 2 ) (2) (2)	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 , ( 1 ) (1) (1)	2 2 2 , 1 1 1	8 8 8 , ( − 1 ) (-1) (−1)	4 4 4
A 3 \rm A_3 A3	7 7 7 , ( 10 ) (10) (10)	4 4 4 , 6 6 6	10 10 10 , ( 12 ) (12) (12)	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

,

(1)

11

,

(2)

3

,

4

10

,

3

7

\rm A_2

1

,

3

9

,

(1)

2

,

1

8

,

(-1)

4

\rm A_3

7

,

(10)

4

,

6

10

,

(12)

5

,

3

9

销量

3

6

5

6

四、调整运量 ( 换基 )

上述检验数中 ,

\rm \sigma_{24}

为负数 , 需要进行换基 , 该非基变量就是入基变量 ;

该检验数的闭合回路如下 :

\rm A_{24} +

,

\rm A_{23} -

,

\rm A_{13} +

,

\rm A_{14} -

;

在

-

符号的基变量中挑选一个最小的 , 作为出基变量 ;

换基之后的结果如下 :

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

	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

计算检验数验证 , 是最优解 ;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-01-07，如有侵权请联系 cloudcommunity@tencent.com 删除

变量

表格

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

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

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

变量

表格

登录后参与评论

0 条评论

热度