1
运筹学试题及答案
填空 1. 线性规划问题MaxZ=CX；AX=b，X≥0（A为kxl的矩阵，且l>k）的基的最多个数为___，基的可行解的最多个数为_____.
2.指派问题的最优解的性质________________________________
3.线性规划问题的所有可行解构成的集合是__________,它们有有限个______________________,线性规划问题的每个基可行解对应可行域的___________,若线性规划问题有最优解，必在______________得到。
4影子价格的经济含义______.在完全市场经济的条件下，当某种资源的市场价格低于影子价格时，企业应_____该资源，而当某种资源的市场价格高于影子价格时，则企业应___该资源，可见影子价格对市场有____作用。
5. 运输问题的产销平衡表中有m个产地n个销地，其决策变量的个数有____个，其数值格有____个 答案1:Clk , Clk
2设指派问题的效率矩阵为C= (cij)n?n，若将该矩阵的某一行（或某一列）的各个元素都减去统一常数，得到新的效率矩阵B?(bij)n?n，则以B为效率矩阵的新的指派问题与原指派问题的最优解相同。 3 凸集，顶点，顶点，顶点
4其它条件不变的情况下，单位第i种资源变化所引起目标函数值的变化量。买进，卖出。 5 m?n，m?n?1
计算 1． 对下列线性规划问题 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分） 解：（1）（5分）写出其对偶问题； Minw=5y1+12y2 s.t. y1+2y2≥2 y1+3y2≥1 2y1+4y2≥3
y1≥0， y2 无约束
（2） （10分）已知（3，2，0）T是上述问题的最优解，根据互补松弛理论求出对偶问题的最优解； 由于原问题x1和x2为正，根据互补松弛理论，有对偶问题取最优解时 （1）、（2）取严格等式，即为
y1+2y2＝2
y1+3y2＝1
解得y2＝-1 y1＝4
故对偶问题最优解为Y*＝（4，－1），w*=8
2. （15分）运用单纯形法求解下面线性规划问题。
maxz?3x1?x2maxz?3x1?x2?3x1?5x2?x3?15?3x1?5x2?15 ? 解： ?
s.t?6x1?2x2?x4?24s.t?6x1?2x2?24?x,x?0?x,x?0?12?12（加入松弛变量x3,x4，上述模型可转化为上式）
2
CB 0 0 cj XB x3 x4 z x3 x1 z b 15 24 0 3 4 12 0 3 3 x1 3 [6] 3 0 1 0 1 x2 5 2 1 4 1/3 0 3 x3 1 0 0 1 0 0 0 x4 0 1 0 -0.5 1/6 -0.5 θ 5 4 1.2 - （2分）最优解x*?(4,0,0,0)T，最优值Z*?12
3． （15分）已知运输问题的产销平衡表与单位运价表如下表所示
销地 产地 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 试用运用沃格尔法求出初始运输方案。 解：（1） （7分）用最小元素法求得初始可行基如下
销地 B1 B2 B3 B4 产量 产地 A1 10 3 6 × 7 × 12 1 4 0 A2 16 × 10 × 5 4 9 5 9 -3 A3 5 2 4 2 10 × 10 × 4 -5
销量 5 10 2 9 4 8 6 12
（2） （8分）位势方程组为 Δ12＝6－（0＋9）＝-3
u1+v1=10 u1+v4=12 Δ13＝7－（0＋8）＝-1 u2+v3=5 u2+v4=9 Δ21＝16－（10－3）＝9 u3+v1=5 u3+v2=4 Δ22＝10－（9－3）＝4 令u1＝0，解得v1=10 v2=9 v3=8 Δ33＝10－（8－5）＝7 v4=12 u2 =-3 u3 =-5 Δ34＝10－（12－5）＝3 各非基变量检验数为 存在非基变量检验数为负，没有达到最优解
4． （15分）用匈牙利法求解下列分配问题，已知效益矩阵为
7 6 8 6
9 12 7 7
8 7 9 8
5 4 6 10
解：已知效益矩阵为
7 9 8 5
3
6 12 7 4 8 7 9 6 6 7 8 10
第一步（5分），把Cij转化为Cij’,
4 1 0
2 8 1 0 3 0 2 1 0 1 0 4
第二步（5分），求初始分配方案及寻找覆盖所有零元素的最少直线，
2 4 1 0 √
2 8 1 0 3 0 2 1 0 1 0 4
√
√
第三步（5分），调整，求最优解。
1
1 3 0 3 7 0 1
0 0 2 0 0 0 2 5
所以，最优解为x14*?x23*?x32*?x41*?1,其余xij*?0,z*?25
建模
1． 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：
班次 时间 所需人数
1 60 6：00 —— 10：00
2 70 10：00 —— 14：00 3 60 14：00 —— 18：00 4 50 18：00 —— 22：00 5 20 22：00 —— 2：00
6 30 2：00 —— 6：00
设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘 务人员，既能满足工作需要，又配备最少司机和乘务人员? （15分）解：设 xi 表示第i班次时开始上班的司机和乘务人员数, （2分）
这样我们建立如下的数学模型。
目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 （3分） 约束条件：s.t. x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50
4
x4 + x5 ≥ 20 x5 + x6 ≥ 30
x1,x2,x3,x4,x5,x6 ≥ 0（5分）
2. 某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，
问：应如何下料，可使所用原料最省？（15分） 解： 共可设计下列5 种下料方案，见下表（5分
设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5
约束条件： s.t. x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0
2.9 m 2.1 m 1.5 m 合计 剩余料头 方案1 1 0 3 7.4 0 方案2 2 0 1 7.3 0.1 方案3 0 2 2 7.2 0.2 方案4 1 2 0 7.1 0.3 方案5 0 1 3 6.6 0.8
选题 1 线性规划原问题中的变量个数与其对偶问题中的 约束条件 个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个 约束条件 ，从而对偶可行域将可能变 小 (小还是大)。
2 用表上作业法求解m个产地n个销地的平衡运输问题，其方案表上数字格的 个数为 m+n-1 个； 若已计算出某空格的检验数为-3，若从该空格出发进行调整，设调整量为2，则调整后可使总运费下降 6 。
3 下表中给出某线性规划问题计算过程中的一个单纯形表，约束条件为≤，目标函数为maxZ=28ⅹ4+ⅹ5 +2ⅹ6，表中ⅹ1，ⅹ2，ⅹ3为松弛变量，表中解的目标函数值Z=14。 CB XB b X1 X2 X3 X4 X5 X6 X6 a 3 0 -14/3 0 1 1 X2 5 6 d 2 0 5/2 0 X4 0 0 e f 1 0 0 -Z b c 0 0 -1 g
5
其中，a= 7 ，b= -6 ，c= 0 ，d= 1 ，e= 0 ，f= 1/3 ，g= 0 ；表中所给出的解 是 (是否）为最优解，如为最优解，解的情况是 无穷多最优解 (唯一最优解、无穷多最优解、无界解、无可行解)。
4 运输问题解的情况有四种：无可行解；无界解；唯一最优解；无穷多最优解。错 5 运输问题的所有结构约束条件都是等式约束。对
6 某建材厂生产四种型号的特用构件：Ⅰ型-、Ⅱ型、Ⅲ型、Ⅳ型。各型号每件所需组装时间、检验时间、销售收入及该厂组装调试能力如表1所示 Ⅰ型 Ⅱ型 Ⅲ型 Ⅳ型 工厂生产能力（h） 组装时间8 10 12 15 2000 (h) 检验时间2 2 4 5 500 （h） 售价（百元） 4 6 8 10 但现在因为某种特型材料比较紧张，每月最多只能进货180只（每件构件用一只），其中Ⅲ型、Ⅳ型用到的不超过100只。令х1、х2、х3、х4依次表示各型号每月计划产量。现工厂拟定使目标总销售收入z为最大的生产计划。
（1） 写出该问题的数学模型，对于约束条件依下列顺序：组装时间、检验时间、特种材料数、、Ⅲ型、
Ⅳ型用到的特种材料数，并引入松弛变量使之成为等式。
（2） 用单纯型法求解的终表入下表。 4 6 8 10 0 0 0 0 CB XB B-1b X1 X2 X3 X4 X5 X6 X7 X8 0 X8 50 -0.2 0 0.2 0 0.1 -0.5 0 1 -0.76 X2 125 0.5 1 0 0 0.25 0 0 5 -0.10 X7 5 0.3 0 0.2 0 0.25 1 0 5 10 X4 50 0.2 0 0.8 1 -0.1 0.5 0 0 -1 0 0 0 -0.5 -0.5 0 0 分别回答：
①最优生产计划是什么？x1=0,x2=125,x3=0,x4=50
是否还有其他的最优生产计划？是 为什么？因为非基变量的检验数为零 ②组装时间的影子价格是多少？0.5
③若外厂可调剂增加80h的检验时间，但每小时需付0.4百元，这样的调剂值得吗？值得 能增加多少收入？ 8
④设Ⅰ型构件售价由4百元增加到4.5百元，最优计划要改变吗？不要 如果增加到5.5百元呢？ 要 说明理由。
⑤写出本问题的对偶模型，并指出其最优解。y1=0.5,y2=0.5，y3=0,y4=0