《运筹学》习题(八)

班级 姓名

一、试画一图，使顶点的度数分别是： （1）2，3，4，5，6 （2）3，3，4，5，6，6 解：

e4 V5 e5 v1 v6 e3 e1 v3 e9 e6 e2 e8 v2 e7 v4 （ 图1 ） 二、针对图1，写出开链、闭链、初等链、回路各两条，并找出该图的两棵生成树。 解：

e1 v2 v3 e7

e2 e4 e5 v1 e6 v4 e3 v5 （ 图2）三、针对图2，写出链、初等链、路、路径、回

路各两条，并画出一棵以v1为根的有向树。解： 四、证明：在无圈图中，若任意两点间均有唯一链连通，则此图必是一棵树。 证明：

五、某仓库要存放10种化学药品a，b，c，d，e，f，g，h，i，j，其中有些药品彼此不能存放在一

起，已知不能存放在一起的药品为（a,g）,（a,c），（a,i）,（e,g）,（g,i），（c,d）,（f,j）,（b,g）,（b,e），（c,j）,（d,f）,（h,i）,（c,g）,（e,j）,问至少应将仓库分成多少个隔离区，才能确保安全。 解：

V2 v3 5 3 1 2 2 7 7 5 2 v1 2 5 1 v6 4 6 5 4 4 8 6 1 3 7 1 v4 3 v5

3

（图3） （图4） 六、求图3中从v1至各点的最短路。 七、求图4的最小生成树。 解： 解：

附：《运筹学》习题（七）答案

一、解：1、确定性的存贮模型，要求不允许缺货，订货时间很短的存贮策略问题。 2、确定性的存贮模型，要求不允许缺货，生产需要一定时间的存贮策略问题。 3、确定性的存贮模型，允许缺货，订货时间很短的存贮策略问题。

4、随机性的存贮模型，属于需求是随机离散的报童问题。 二、解：曲线图如下：

S 100 B 100 60 (22,56) 60 20 20 (12,24) （15,0） （50,0） O 10 20 30 40 50 60 T（天） 存贮量变化曲线 （15,0） （50,0） O 10 20 30 40 50 60 T（天） 缺货量变化曲线 1、 一年的第22天，72天，122天，172天，222天，272天存贮量最大； 2、 一年的第12天，62天，112天，162天，212天，262天缺货量最大； 3、 一个周期内缺货的时间为15天。

三、解：本题属于缺货需补足，订货时间很短的存贮问题。其中需求量R = 600, 订购费C3 = 900, C1 = 512 = 60, C2 = 180. 所以，最优订货量为

Q02RC3C1C224000155C1C2

四、解：设一个月该产品的订货量为Q，则需支出进货费8Q元。用R表示产品的需求量（它是一个随机变量），则R ~ N 150, 25。因此，实际的销量为min[R, Q ]，实际销售收入为15min[R, Q ]。当R  Q时，退货所得收入为5(QR)。所以，这一个月所获得利润为

R0 3Q WQ15R5QR8Q10R3Q 0RQ

15Q8Q7Q RQ 而期望的利润值为

EWQ3Qrdr10r3Qrdr7Qrdr0Q0Q 10rrdr7Q10Qrdr0QQ

其中 r1252er15022252，由微积分知识，当Q满足

*

Q0期望利润达到最大。rdr0.7时，

Q150查表得 0.525 即 Q163

25所以订货量应为163个。