运筹学总复习题（必做）

1、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人做各项工作所消耗的时间如下表所示：

甲 乙 丙 丁 A 7 13 15 11 B 9 12 16 12 C 10 15 14 15 D 12 17 15 16 问：应该如何指派，才能使总的消耗时间为最少？

指派问题匈牙利算法 圈0，打钩，对没打钩的行划横线，对打钩的列打竖线 在打?行各元素都减去这最小元素，在打?列中各元素都加上这最小元素 2、某公司生产三种产品，各产品的重量和利润关系如下：

产品 重量（t） 利润（元） Ⅰ 4 8 Ⅱ 5 11 Ⅲ 6 13 现将三种产品运往市场出售，运输能力为总重量不超过10t，如何安排运输使总利润最大。试建立此问题的动态规划模型（只建模，不求解）。 s=8x+11y+13z 4x+5y+6z<=10

3、对下列线性规划问题 Max z=2x1+x2+3x3 x1+ x2+2x3 ≤5 s.t. 2x1+3x2+4x3＝12

x1, x2, x3≥0

（1） 写出其对偶问题；（5分）

（2） 已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问

题的最优解；（10分）

试卷A 共（4）页 第（1）页

对偶：min=5w1+12w2 （2）w1+2w2=2

w1+2w2 >=2 w1+3w2=1

w1+3w2>=1 w1=4 w2=-1 2w1+4w2>=3 w1>=0

4、用匈牙利法求解下列分配问题，已知效益矩阵为

7 6 8 6

9 12 7 7

8 7 9 8

5 4 6 10

与1一样

5、已知运输问题的产销平衡表与单位运价表如下表所示

销地 产地 A1 A2 A3 销量 B1 10 16 5 5 B2 6 10 4 2 B3 7 5 10 4 B4 12 9 10 6 产量 4 9 4

试用运用伏格尔法求出初始运输方案。 6、知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均为“≤”型不等式）其中X4,X5,X6为松驰变量。 XB b X1 X2 X3 X4 X5 X1 2 1 1 0 2 0 X3 2/3 0 0 1 1 0 X5 1 0 -2 0 1 1 Cj-Zj 0 0 0 -4 0 问：(1)对偶问题的最优解： （2）写出B-1

试卷A 共（4）页 第（2）页

X6 1 4 6 -9

7、已知运输问题的调运和运价表如下，求最优调运方案和最小总费用。（共15分）。 销地 B1 B2 B3 产量 产地 A1 5 9 2 15 A2 3 1 7 11 A3 6 2 8 20 销量 18 12 16 8、某公司要把4个有关能源工程项目承包给4个互不相关的外商投标者，规定每个承包商只能且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？各承包商对工程的报价如表2所示： 项目 投标者 甲 乙 丙 丁

A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17 试卷A 共（4）页 第（3）页