2012级运筹学A卷

2、（共10分）已知某运输问题的产销量、单位运价以及初始调运方案如下表所示。 （1）用表上作业法求最优调运方案。

（2）A2到B1的单位产品运费在什么范围之内变动时，最优方案不变。 销地 产地 A1 A2 A3 销量

3、（共9分）用匈牙利法求解如下最小值的指派问题 10 10 4 2 8 C= 7 11 10 14 12 5 6 9 12 14 13 15 11 10 7

4、（共11分）用动态规划方法求出下述问题的最优解。

共 7 页 第 5 页

B1 3 3 3 2 4 3 B2 7 4 3 3 0 2 B3 6 3 8 2 2 0 B4 4 2 5 2 B5（虚销地） 产量 3 3 0 0 0 5 2 6 maxz=x1x2x3

2x1+4x2+x3≤10x1,x2,x3≥0

5、（共11分）

（1）求下图所示的网络的最大流（每个弧旁的数字表示该弧的容量和流量）。 （2）该网络的最小割集是什么？

(6,6) v4 v1

(6,2) (7,5) (16,10)

(3,3) (6,5) v2 (7,7) vs vt (6,5)

(5,5) (3,2) (12,12) (14,12)

共 7 页 第 6 页

v3 v5 (5,5)

共 7 页 第 7 页