9、某奶牛站希望通过投资来扩大牛群数，开始只有5000元资金，现在已知可购入A或者B两个品种的奶牛，对于A种牛每投入1000元，当年及以后每年可以获得500元和2头小牛，对B种牛每投入1000元，当年及以后每年可以获得200元和3头小牛。问：
（1）在今后的四年内应该如何分配投资使奶牛群最大 （2）到第四年底奶牛站将有多少头奶牛。 答案：状态S为阶段n可利用的资金；
n决策d为阶段n向A种牛投入的资金数；
nS?dnn为阶段n向B种牛投入的资金数；
则转移函数为Sn?1?0.2Sn?0.3dn 递推函数：
f(Sn)?rn(dn)?nf?n?1(Sn?1)
rn?rnn(3?); 1000Sndn表示在阶段n出生的小牛数
?5000；
S4第四年末牧场主应拥有的牛的头数为70头
10. 求下面容量网络的最大流，弧边上括号内第一个数为容量，第二个数为流量。 （1）、根据标号过程找出增广链，确定流量修正量ε； （2）、调整流量，画出最大流图，说明最大流量是多少； （3）、根据标号和求解过程确定最小割并算出最小割容量； V2 V4
(3,2) (4,1)
V1 (3,1) (1,1) (3,1) V6 (2,0)
(2,2) (3,1) (2,2) V3 V5
、解：
1.增广链： + + +
V1 V2 V4 V6
2 1 3 ?1?min?2,1,3??1
?（V1V,2） 2
（-,∞） V1
（3,2）
(1,1)
（V2? V,14 ）（4,2） （3,3） （V?,3）
4 （2,0） （3,1）V6
（2,2）
2.
增广链
V3 (V2?,1)
（3,1）
图1
V5
(V3?,2)
（2,2）
(V4?,2)（V2?,2）
（V1?,1）
V2
（-,∞） V1
（3,3） （2,2）
(1,1) V3
（V5?,1）
（3,3）
V4
（4,3）
（V4?,2）
V6
（2,1） （3,0）
V5
（2,2）
（3,1）
图2
（V2?,2）
V1
+ 1
V2
+ 2
V5
- 1
V4
+ 2
V6
?2?min?1,2,1,2??1
标号过程中，图2为最大流图，最大流量fmax?3?2?5
3.S??V1? 其节点均属S
则最小割为(S,S)??(V1,V2),(V1,V3)?，最小割容量为3+2=5
11、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小时到达25件。试求： ⑴ 该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？
⑵ 每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？ ⑶ 一个工件从送达到研磨完，时间超过20分钟的概率？ ⑷ 等待研磨的工件在8～10件的概率。 答案：
模型：M/M/1
参数：λ＝25件/小时，μ＝件/分钟＝30件/小时， ρ＝λ/μ = 5/6； 1） P0 ＝ 1／6 ， P6 ＝ ；
2）加工前平均等待时间 wq = 10分钟，平均等待的工件数 Lq = 件； 3）P( T > 20 ) = e = 104）P7 ＋ P8 ＋ P9 ＝ + + =
-20 (
- )
- 44
；
12、一台研磨机对某种工件进行加工，研磨一个工件的时间服从负指数分布，平均需要2分钟。工件的到达服从泊松分布，平均每小时到达25件。试求： （1）该研磨机空闲的概率和恰巧有5件工件等待研磨的概率？
（2）每件工件在加工前平均等待的时间是多少？平均等待的工件有多少件？ （3）一个工件从送达到研磨完，时间超过20分钟的概率？ （4）等待研磨的工件在8～10件的概率。
答案：
模型：M/M/1
参数：λ＝25件/小时，μ＝件/分钟＝30件/小时， ρ＝λ/μ = 5/6； 1） P0 ＝ 1／6 ， P6 ＝ ；
2）加工前平均等待时间 wq = 10分钟，平均等待的工件数 Lq = 件； 3）P( T > 20 ) = e-20 ( - ) = 10- 44 ； 4）P7 ＋ P8 ＋ P9 ＝ + + = 。
运筹学复习题
