2009级《运筹学》试卷（A 卷）参考答案及评分标准
一.设A 、B 产品的产量为x 1，x 2，用于销售的C 产品的产量为x 3，需处理的C 产品的产量为x 4. 1.
⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤=--≤+≤+-++=-0
13000217003211002..273max 413432212
14321x x x x x x x x x t s x x x x z 2.
1234125126
234
3717max 37221100231700..201300
-=++-++
=⎧⎪
++=⎪⎪--=⎨⎪+=⎪⎪≥⎩z x x x x x x x x x x s t x x x x x x
3.
12412
123
3431243min 10001700130023232721,,0,=+++≥⎧⎪
++≥⎪⎪
-+≥⎨
⎪-≥-⎪⎪≥⎩w y y y y y y y y y y y y y y y 无约束
4．在2中引入人工变量x 8,则有
12348
12
512
623483718max 37221100231700..2013000
-=++--++=⎧⎪
++=⎪⎪
--+=⎨⎪+=⎪⎪≥⎩z x x x x Mx x x x x x x s t x x x x x x x 于是得到初始基可行解为：0(0,0,0,0,1100,1700,1300,0)=X ，则初始单纯形表为： 二．（1）本运输
c j 3 7
2 -1 0 0 -M 0 x 1 x 2 x
3 x
4 x
5 x
6 x 8 x
7 C B X B b 0 x 4 1100 1 2 1 0 0 0 0 x 5 1700 2 3 0 1 0 0 -M x 7 0 2 -1 -1 0 0 1 0 0 x
8 1300
1 0 0 0 1
σj
3
2M +7
-M +2
-M-1
问题的线性规划模型为：
⎪⎪⎪
⎪⎪⎩⎪⎪
⎪⎪⎪⎨
⎧==≥=++=++=++=++=+++=+++=++++++++++++++=4,3,2,1;3,2,1,010
1414121515
20.16141712206781115410min 3424143323133222123121113433323124232221
14131211343332312423222114131211j i x x x x x x x x x x x x x x x x x x x x x x x x x t s x x x x x x x x x x x x z ij
（5分）
（2）用最小元素法确定初始调运方案，如下表 （5分）
（3）用位势法计算非基变量的检验数，结果如下表 （5分）
（4）因为非基变量x 14检验数小于0，所以当前解不是最优解。
（2分）
用闭回路法进行解的调整。
取非基变量x 14，其闭回路
x 14
x 11=6 x 14=6
x 11
及调整过程如右图， 得新的调运方案如下表 （3分）
三.1构造最大流模型，并设初始可行流0f 为0流。
如图1.(10分)
图1
2.用标号法求最大流 （10分）
(1)①对f 0进行标号，得一可增广链s-s 1-v 1-t 1-t 。
如图2
图2
②调整流量，得新的可行流f 1，如图3。
图3
(2) ①对f1进行标号，得一可增广链s-s1-t1-t。
见图3。
②调整流量，得新的可行流f2，如图4。
图4
(3) ①对f2进行标号得一可增广链s-s1-t2-t。
见图4。
②调整流量，得新的可行流f3，如图5。
1
图5
(4) ①对f3进行标号得一可增广链s-s1-v2-t2-t。
见图5。
②调整流量，得新的可行流f4，如图6。
2
图6
(5) ①对f4进行标号得一可增广链s-s2-v2-t2-t。
见图6。
②调整流量，得新的可行流f5，如图7。
图7
(6) ①对f5进行标号得一可增广链s-s2-t2-t。
见图7。
②调整流量，得新的可行流f6，如图8。
图8
(7) ①对f6进行标号得一可增广链s-s2-t2-t。
见图8。
②调整流量，得新的可行流f7，如图9。
图92
(8) ①对f 7进行标号, 当标到s 1时，标号不能继续进行，即不存在可增广链。
则f 7就是最大流。
其流量为：20)812(1010=+=+=W 。
四．由题意，本问题属于M/M/1/∞/∞/FCFS 的排队问题，已知8,6==μλ，所以
175.08
6
<==
ρ （2分） （1）空闲概率为：
25.010=-=ρP （2分）
（2）平均逗留时间：
小时）(5.06
81
1=-=-=
λμs W （2分） （3）修车铺内平均逗留车辆数，即平均队长为：
（辆）375
.0175
.01=-=
-=
ρ
ρ
s L （2分）
（4）∑∑=∞
=-=2
03
2P 1P
P n n n n
＝
＞，而
1875.0)1(1=-=ρρP ，1406.0)1(22=-=ρρP ，所以
4219.0P 1P 2
02=-=∑=n n ＞ （2分）
五．
六.证明：
必要性：由定理3，若),(*
*
y x 是G 的解，则必有
),(),(),(****j x E y x E y i E ≤≤，因此，在（1）（2）中，只需取),(*
*y x E v =即可。
充分性：设有v y x ,,*
*满足条件（1）（2），则有
∑∑∑=≥n
j
j n j
m i
i
ij
v v y x a
y j
***
（3）
∑∑∑=≤m
i
j m i
n j
i
ij
v v x y a
x j
***
（4）
（3）（4）表明，),(*
*
y x E v =，则（1）（2）中的第一式即为定理3的条件，则),(*
*
y x 为G 的解。
证毕。