运筹学总复习题(必做) .pdfVIP

1、有甲、乙、丙、丁四个人，要分别指派他们完成A、B、C、D不同的工作，每人

做各项工作所消耗的时间如下表所示：

ABCD

甲791012

乙13121517

丙15161415

丁11121516

问：应该如何指派，才能使总的消耗时间为最少？

指派问题匈牙利算法圈0，打钩，对没打钩的行划横线，对打钩的列打竖线

在打行各元素都减去这最小元素，在打列中各元素都加上这最小元素

2、某公司生产三种产品，各产品的重量和利润关系如下：

产品ⅠⅡⅢ

重量（t）456

利润（元）81113

现将三种产品运往市场出售，运输能力为总重量不超过10t，如何安排运输使总利

润最大。试建立此问题的动态规划模型（只建模，不求解）。

s=8x+11y+13z

4x+5y+6z=10

3、对下列线性规划问题

Maxz=2x+x+3x

123

x+x+2x≤5

123

s.t.2x+3x+4x＝12

123

x,x,x≥0

123

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

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

题的最优解；（10分）

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

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

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

w1+3w2=1w1=4w2=-1

2w1+4w2=3

w1=0

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

7985

61274

8796

67810

与1一样

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

销地

B1B2B3B4产量

产地

A11067124

A21610599

A35410104

销量5246

试用运用伏格尔法求出初始运输方案。

6、知下表是制订生产计划问题的一张LP最优单纯形表（极大化问题，约束条件均

为“≤”型不等式）其中