运筹学习题答案(第三章)

运筹学教程(第二版) 习题解答

运筹学教程

第三章习题解答3.1 与一般线性规划的数学模型相比，运输问 题的数学模型具有什么特征? 答： 1、运输问题一定有有限最优解。 2、约束系数只取0或1。 3、约束系数矩阵的每列有两个1, 而且只有两 个1。前m行中有一个1,或n行中有一个1。 4、对于产销平衡的运输问题，所有的约束都取 等式。

page 2 11 August 2013

2

School of Management

运筹学教程

第三章习题解答3.2 运输问题的基可行解应满足什么条件？将其 填入运输表中时有什么体现？并说明在迭代计算过程 中对它的要求。 解：运输问题基可行解的要求是基变量的个数等 于m+n-1。填入表格时体现在数字格的个数也应该等 于m+n-1。在迭代过程中，要始终保持数字格的个数 不变。

page 3 11 August 2013

3

School of Management

运筹学教程

第三章习题解答3.3 试对给出运输问题初始基可行解的西北角法、 最小元素法和Vogel法进行比较，分析给出的解之质 量不同的原因。 解：用西北角法可以快速得到初始解，但是由于 没有考虑运输价格，效果不好；最小元素法从最小的 运输价格入手，一开始效果很好，但是到了最后因选 择余地较少效果不好； Vogel法从产地和销地运价的 级差来考虑问题，总体效果很好，但是方法较复杂。

page 4 11 August 2013

4

School of Management

运筹学教程

第三章习题解答3.4 详细说明用位势法(对偶变量法)求检验数的原 理。 解：原问题的检验数也可以利用对偶变量来计 算： ij cij (ui v j )i 1,2, m; j 1,2, , n

其中，ui和vj就是原问题约束对应的对偶变量。由于 原问题的基变量的个数等于m+n-1。所以相应的检验 数就应该等于0。即有：cij (ui v j ) 0 i 1,2, m; j 1,2, , n

page 5 11 August 2013

5

School of Management

运筹学教程

第三章习题解答由于方程有m+n-1个， 而变量有m+n个。所以 上面的方程有无穷多个解。任意确定一个变量的值都 可以通过方程求出一个解。然后再利用这个解就可以 求出非基变量的检验数了。

page 6 11 August 2013

6

School of Management

运筹学教程

第三章习题解答3.5 用表上作业法求解运输问题时，在什么情况 下会出现退化解？当出现退化解时应如何处理？ 解：当数字格的数量小于m+n-1时，相应的解就 是退化解。如果出现了退化解，首先找到同时划去的 行和列，然后在同时划去的行和列中的某个空格中填 入数字0。只要数字格的数量保持在m+n-1个的水平 即可。

page 7 11 August 2013

7

School of Management

运筹学教程

第三章习题解答3.6 一般线性规划问题具备什么特征才能将其转 化为运输问题求解，请

举例说明。 解：如果线性规划问题有“供”和“需”的关系， 并且有相应的“费用”,就可以考虑将线性规划问题 转成运输问题求解。例如，生产满足需求的问题。

page 8 11 August 2013

8

School of Management

运筹学教程

第三章习题解答3.7 试判断表3-30和表3-31中给出的调运方案可 否作为表上作业法迭代时的基可行解?为什么? 答：都不是。数字格的数量不等于m+n-1。

表3-30销地 产地 A1 A2 A3page 9 11 August 2013

B1

B2

B3 15

B4 10 10

产量

05 5

15

1525 59

销量

15

15

School of Management

运筹学教程

第三章习题解答表3-31 销地 B1 B2 产地 A1 150 A2 A3 B3 B4 B5 产 量

250250

400500 50 300

200 300

A4A5

90 21080

30020 10010

销量page 10 11 August 2013

240 410 550 330 70School of Management

运筹学教程

第三章习题解答3.8 表3-32和表3-33分别给出了各产地和各销地 的产量和销量，以及各产地至各销地的单位运价，试 用表上作业法求最优解。

表3-32 销地 产地 A1 A2 A3page 11 11 August 2013

B1

B2

B3

B4

产量

4 5 1 3 4 6 6 1 2 5 2 0 3 7 3 5 1 16 5 6 3

88 4 2011

销量

School of Management

运筹学教程

第三章习题解答表3-33 销地 产地 A1 A2 A3 销量page 12 11 August 2013

B1

B2

B3

B4

产量 3 3 5 1112

9 3 3 8 7 1 4 9 2 4 5 5 7 6 5 21 3 2 5

School of Management

运筹学教程

第三章习题解答3.9 试求出表3-34给出的产销不平衡运输问题的 最优解。

表3-34

销地 产地 A1 A2A3 销量page 13 11 August 2013

B1

B2

B3

B4

产量

3 2 43 3

7 4 32

6 3 82

4 2 5

5

2613

School of Management

运筹学教程

第三章习题解答习题3.9的解答 销地 产 B 1 B2 B3 B4 B 5 量 产地 3 2 A1 7 6 0 5

3

4

A2A3page 14 11 August 2013

243 3

43

2

382 2

253

03

2614

3

0

销量

School of Management

运筹学教程

第三章习题解答3.10 某市有三个面粉厂，它们供给三个面食加 工厂所需的面粉。各面粉厂的产量、各面食加工厂加 工面粉的能力、各面食加工厂和各面粉厂之间的单位 运价，均表示于表3-35中。假定在第1,2和3面食加 工厂制作单位面粉食品的利润分别为12元、16元和 11元，试确定使总效益最大的面粉分配计划(假定面 粉厂和面食加工厂都属于同一个主管单位)。

page 15 11 August 2013

15

School of Management

运筹学教程

第三章习题解答表3-35

食品厂 面粉厂 Ⅰ Ⅱ Ⅲ 销量page 16 11 August 2013

1

2

3

产量

3 4 815

10 11 1125

2 8 420

20 30 20

16

School of Management

运筹学教程

第三章习题解答习题3.10的解答食品厂 面粉厂 Ⅰ Ⅱ Ⅲpage 17 11 August 2013

1

2

3 20

4

产量

315

105

4 8

1120

2 8 4

010

20 30 2017

11

0 0

School of Management

运筹学教程

第三章习题解答3.11 表3-36示出一个运输问题及它的一个解

:

表3-36 销地 产地 A1

B1

B2

B3

B4

产量8

A2A3 销量page 18 11 August 2013

4 5 1 3 4 6 8 1 6 2 1 2 1 7 3 5 1 18 5 6 3

104 2218

School of Management

运筹学教程

第三章习题解答试问： (1)表中给出的解是否为最优解？请用位势法进 行检验。 答：是最优解。 (2)如价值系数c24由1变为3,所给的解是否仍为 最优解？若不是，请求出最优解。 答：原来的解不是最优解。新的最优解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3, 其他变量为0 。 (3)若所有价值系数均增加1,最优解是否改变？ 为什么? 答：不会改变。因为检验数不变。page 19 11 August 2013 19

School of Management