【运筹学】表上作业法 ( 示例 | 使用 “ 最小元素法 “ 找初始基可行解 )

2023-03-28 20:48:06 浏览数 (1)

文章目录

  • 一、运输规划问题
  • 二、找初始基可行解

一、运输规划问题

运输规划问题 :

​

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

rm B_1
rm B_1
rm B_1
rm B_1

产量

rm A_1
3
11
4
4
7
rm A_1
7
7
3
8
4
rm A_1
1
2
10
6
9

销量

3
6
5
6
20

二、找初始基可行解

可以使用 " 最小元素法 " 或 " Vogel 方法 " 找初始基可行解 , 这里使用 最小元素法 ;

【运筹学】表上作业法 ( 求初始基可行解 | 最小元素法 ) 博客中有详细的 " 最小元素法 " 的分析过程 , 这里只进行简要分析 ;

基变量个数 是

rm m n - 1 = 4 3 - 1 = 6

最小元素法找初始基可行解:

①

rm x_{31}

运费为

1

最小 , 安排

3

个 ,

rm B_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̸ not 3 ​3

11 11 11

4 4 4

4 4 4

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7 7 7

3 3 3

8 8 8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

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

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
11
4
4
7
rm A_2
not 7
7
3
8
4
rm A_3
not 1

,

3
2
10
6
9

销量

3
6
5
6
20

②

rm x_{32}

运费为

2

最小 , 安排

6

个 ,

rm B_2

销地满足 ,

rm A_3

产量也满足 , 这里注意除了最后一个基变量之外 , 不能同时删除一行一列 , 每次只能删除一行 , 或者删除一列 ; 这里选择划掉

rm B_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

1̸1 not 11 ​11

4 4 4

4 4 4

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7̸ not 7 ​7

3 3 3

8 8 8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

2̸ not 2 ​2 , 6 6 6

10 10 10

6 6 6

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

20 20 20

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
not 11
4
4
7
rm A_2
not 7
not 7
3
8
4
rm A_3
not 1

,

3
not 2

,

6
10
6
9

销量

3
6
5
6
20

③

rm x_{23}

运费为

3

最小 , 安排

4

个 ,

rm A_3

产量满足 , 划掉

rm A_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̸ not 3 ​3

1̸1 not 11 ​11

4 4 4

4 4 4

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7̸ not 7 ​7

3̸ not 3 ​3 , 4 4 4

8̸ not 8 ​8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

2̸ not 2 ​2 , 6 6 6

10 10 10

6 6 6

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

20 20 20

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
not 11
4
4
7
rm A_2
not 7
not 7
not 3

,

4
not 8
4
rm A_3
not 1

,

3
not 2

,

6
10
6
9

销量

3
6
5
6
20

④

rm x_{13}

运费为

4

最小 , 安排

1

个 ,

rm B_3

销量满足 , 划掉

rm B_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̸ not 3 ​3

1̸1 not 11 ​11

4̸ not 4 ​4 , 1 1 1

4 4 4

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7̸ not 7 ​7

3̸ not 3 ​3 , 4 4 4

8̸ not 8 ​8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

2̸ not 2 ​2 , 6 6 6

1̸0 not 10 ​10

6 6 6

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

20 20 20

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
not 11
not 4

,

1
4
7
rm A_2
not 7
not 7
not 3

,

4
not 8
4
rm A_3
not 1

,

3
not 2

,

6
not 10
6
9

销量

3
6
5
6
20

⑤

rm x_{14}

运费为

4

最小 , 安排

6

个 ,

rm A_1

产量满足 , 划掉

rm A_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̸ not 3 ​3

1̸1 not 11 ​11

4̸ not 4 ​4 , 1 1 1

4̸ not 4 ​4 , 6 6 6

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7̸ not 7 ​7

3̸ not 3 ​3 , 4 4 4

8̸ not 8 ​8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

2̸ not 2 ​2 , 6 6 6

1̸0 not 10 ​10

6 6 6

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

20 20 20

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
not 11
not 4

,

1
not 4

,

6
7
rm A_2
not 7
not 7
not 3

,

4
not 8
4
rm A_3
not 1

,

3
not 2

,

6
not 10
6
9

销量

3
6
5
6
20

⑥ 剩下最后一个变量

rm x_{34}

, 安排

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̸ not 3 ​3

1̸1 not 11 ​11

4̸ not 4 ​4 , 1 1 1

4̸ not 4 ​4 , 6 6 6

7 7 7

A 2 rm A_2 A2​

7̸ not 7 ​7

7̸ not 7 ​7

3̸ not 3 ​3 , 4 4 4

8̸ not 8 ​8

4 4 4

A 3 rm A_3 A3​

1̸ not 1 ​1 , 3 3 3

2̸ not 2 ​2 , 6 6 6

1̸0 not 10 ​10

6̸ not 6 ​6 , 0 0 0

9 9 9

销量

3 3 3

6 6 6

5 5 5

6 6 6

20 20 20

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
not 3
not 11
not 4

,

1
not 4

,

6
7
rm A_2
not 7
not 7
not 3

,

4
not 8
4
rm A_3
not 1

,

3
not 2

,

6
not 10
not 6

,

0
9

销量

3
6
5
6
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

rm B_1
rm B_2
rm B_3
rm B_4

产量

rm A_1
3
11
4

,

1
4

,

6
7
rm A_2
7
7
3

,

4
8
4
rm A_3
1

,

3
2

,

6
10
6

,

0
9

销量

3
6
5
6
20
变量 博客

0 人点赞