运筹学考试题

北京交通大学考试试卷。

本卷共九题，请仔细检查，必要时向监考老师申请调换试卷。

1) 最小元素法是用来解决哪类问题的？若不用最小元素法法还可用哪种方法？（6分）

2) 已知线性规划问题 max z = 2x1+4x2+6x3+8x4

x1+2x2+2x3+3x4≤90 2x1+x2+3x3+2x4≤90 xi≥0 其对偶问题的最优解为y1 =2.4, y2=0.4 ，根据对偶理论求出原问题的最优解。（8分）

3) 拟分派五人去做五项竞赛，各人做预期竞赛分数见表。如何分派，使预期总分最高？（12分）

4) 解下列左端线性规划问题，max z= 2 x－x＋x，约束条件。

2 x＋x 4，－4 x－2 x＋3 x 7， x－2 x＋x 9，

x 0, =1, 2, 3并写出最优基矩阵b及其逆矩阵；，试用对偶单纯形法求解(19)

5) 求解下列运输问题并回答是否有多重最优解。 (15)

6) 某厂可在同一生产线上生产 a, b, c 三种产品，生产时耗费设备台时分别为 6小时，8小时和10小时。该生产线每月正常工作200小时。三种产品每种单件可获利5000元，6500元和8000元。

每月预计销售量为12件、10件和8件。该厂经营目标为：1.

利润尽量不低于160000元；2. 尽可能充分利用生产能力；3. 若有加班尽量不超过 24小时；4.

产量尽可能接近预计销售量。请建立目标规划模型。（8）

7) 在下图中，除已经标明方向的弧其方向均为从左至右，仅四条上下方向的弧为从上至下。以上各弧对应数对左边数字即是该弧的容量，右边数字是单位量的流流经该弧时的费用，右边数字同时为一给定的流f，求该网络（a是源，f是汇）对给定流f的增流网络。(10)

b 6-2c

defa2-18-2 1-1

g 7-3h

8) 在上图中，若右边数字是该弧的权，求该图的最小支撑树。(7)

9) 在上图中，若左边数字是该弧的权，求a到f的最短路。(8)

10) 利用求鞍点方法求解如下矩阵对策。(7)