运筹学教程课后答案第三章

运筹学教程（第二版）习题解答第三章习题解答3.1

与一般线性规划的数学模型相比，运输问题的数学模型具有什么特征?答：1、运输问题一定有有限最优解。2、约束系数只取0或1。3、约束系数矩阵的每列有两个1，而且只有两个1。前m行中有一个1，或n行中有一个1。4、对于产销平衡的运输问题，所有的约束都取等式。3.2运输问题的基可行解应满足什么条件？将其填入运输表中时有什么体现？并说明在迭代计算过程中对它的要求。解：运输问题基可行解的要求是基变量的个数等于m+n-1。填入表格时体现在数字格的个数也应该等于m+n-1。在迭代过程中，要始终保持数字格的个数不变。第三章习题解答3.3

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

详细说明用位势法(对偶变量法)求检验数的原理。解：原问题的检验数也可以利用对偶变量来计算：第三章习题解答=

cij

-

(u

i

+

v

j

)

i

=

1,2,

m

;

j

=

1,2,

,

ns

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

(u

i

+

v

j

)

=

0

i

=

1,2,

m

;

j

=

1,2,

,

n由于方程有m+n-1个，而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。第三章习题解答3.5用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？解：当数字格的数量小于m+n-1时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填入数字0。只要数字格的数量保持在m+n-1个的水平即可。第三章习题解答3.6

一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。解：如果线性规划问题有“供”和“需”的关系，并且有相应的“费用”，就可以考虑将线性规划问题

转成运输问题求解。例如，生产满足需求的问题。第三章习题解答3.7

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

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

13

468A26

1252

08A3373

51

14销量656320第三章习题解答表3-33销地产地B1B2B3B4产量A193

3873A21

492

453A35765

25销量132511第三章习题解答3.9

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

3762

405A2242

3202A343

3853

06销量332233.10

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

2020Ⅱ15

45

11810

030Ⅲ820

114020销量152520103.11

表3-36示出一个运输问题及它的一个解：表3-36销地产地B1B2B3B4产量A145

13

468A28

12

62

110A3173

51

14销量856322第三章习题解答试问：表中给出的解是否为最优解？请用位势法进行检验。答：是最优解。如价值系数c24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。答：原来的解不是最优解。新的最优解是：x12=3,x13=5,x21=8,x22=2,x33=1,x34=3，其他变量为0

。若所有价值系数均增加1，最优解是否改变？为什么?答：不会改变。因为检验数不变。第三章习题解答第三章习题解答u1

=

-1,

u

2

=

0,

u

3

=

0,v1

=

1,

v

2

=

2,

v3

=

5,

v

4

=

1i

j最优解是：u

,v

无约束,i

=1,2,

m

;j

=1,2,,n若所有价值系数均乘以2，最优解是否改变？为什么?答：最优解不变。因为检验数不变。写出该运输问题的对偶问题，并给出其对偶问题的最优解。解：对偶问题如下：m

nmax

Z

=

aiui

+

b

j

v

ji

=1

j

=1u

i

+

v

j

£

cij

i

=

1,2,

m

;

j

=

1,2,

,

n3.12

1，2，3三个城市每年需分别供应电力320，250和350单位，由I，Ⅱ两个电站提供，它们的最大供电量分别为400个单位和450个单位，单位费用如表3—37所示。由于需要量大于可供量，决定城市1的供应量可减少0～30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案(将可供电量用完)。表3-37城市电站123Ⅰ151822Ⅱ212516第三章习题解答第三章习题解答习题3.12的解答城市电站城市

1-1城市

1-2城市2城市

3-1城市

3-2产量Ⅰ150

1515250

182222400Ⅱ140

212125270

1640

16450ⅢM30

0MM40

070销量2903025027080第三章习题解答3.13

试写出本章例5转运问题的数学模型。解：已知a1＝10，a2＝40，a3

=a4

=a5

=0Q＝50b1=b2=b3＝0，b4＝30，b5＝20下面就是相应的模型：MIN

Z=4

X(1,1)+

5

X(1,2)+

3X(1,3)+

2

X(1,4)+

100X(1,

5)+

5

X(2,1)+

X(2,2)+2

X(2,3)+100

X(2,4)

+

4

X(2,

5)+

3

X(3,1)+2X(3,2)+3

X(3,3)+5

X(3,

4)

+

5

X(

3,

5)+

2

X(4,1)+100X(4,2)+5

X(4,3)+

3

X(4,4)+6

X(

4,

5)+

100X(5,1)+4X(5,2)+5X(5,3)+6

X(

5,

4)

+5

X(

5,

5)第三章习题解答2]-X(1,1)+X(1,2)+X(1,3)+X(1,4)+X(1,5)=103]X(2,1)-X(2,2)+X(2,3)+X(2,4)+X(2,5)=404]X(3,1)+X(3,2)-X(3,3)+X(3,4)+X(3,5)=05]X(4,1)+X(4,2)+X(4,3)-X(4,4)+X(4,5)=06]X(5,1)+X(5,2)+X(5,3)+X(5,4)-X(5,5)=07]-X(1,1)+X