福建农林大学考试试卷 （ A ）卷
2012 ——2013 学年第 一 学期
课程名称： 运筹学 考试时间 120分钟
应数、信科 专业 10 年级 班 学号 姓名 题号 得分 评卷人签字 得分 一、填空题（每空2分，共20分）
一 二 三 复核人签字 四 总得分
1、线性规划问题中的基可行解与基解的区别是 基本可行解的分量≥0 。
?1??2?2、设K是凸集，x?K，若x不能用不同的两点x?K和x?K的线性组合表示为
x??x?1???1???x?2?,0???1，则称x为K的 顶点（极点） 。
3、产销平衡的运输问题一定存在 最优 解，当某个非基变量（空格）的检验数为0时，该问题有 无穷多最优 解。
4、产销平衡的运输问题，用闭合回路法对最优解进行判别时，从每一空格出发找一条闭合回路的方法是用水平或垂直直线向前划，当碰到一个数字格时可以转90°的一倍或两倍。
5、指派问题中，系数矩阵中 独立0元素 的最多个数等于能覆盖所有0元素的最少直线数。 6、在确定性存储模型中，不允许缺货，备货时间很短的经济批量公式是Q?2C3R。 C17、排队系统中，系统的状态指的是 系统中的顾客数 。 8、动态规划中，定义状态应满足 无后效性 性质。
9、线性规划问题中，如果在约束条件中出现等式约束，我们通常用增加 人工变量 的方法来产生初始可行基。 得分
第1页（共6页）
二、判断题（每小题2分，共14分）（对打√，错打×）
1、用单纯形法求解标准型的线性规划问题时，当所有检验数Cj?Zj?0时，既可判别表中解 为最优解。（×）
m2、对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cn个。（×）
3、单纯形法求解中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的 值为负。（√）
4、已知yi*为线性规划的对偶问题的最优解，若yi*>0，说明在最优生产计划中第i种资源已经 完全耗尽。（√）
5、指派问题效率矩阵的每一个元素都乘上同一常数k，将不影响最优指派方案。（×） 6、在允许发生短缺的存贮模型中，订货批量的确定应使由于存贮量减少带来的节约能抵消缺货 时造成的损失。（√）
7、假如到达排队系统的顾客来自两个方面，分别服从普阿松分布，则这两部分顾客合起来的顾 客流仍为普阿松分布。（√） 得分
1、设线性规划的目标函数是maxZ，在用标准的单纯形法求解的过程中，得下表（其中a，d是常数，部分数据有缺失）：
三、计算题（每题10分，共60分）
cj?CB 0 5 0 x6x2x4 b 20 d 8 2 x15 x28 x30 x40 x50 x6XB 0 0 3 -1 -2 0 0 1/2 1 0 a -2 cj?zj
第2页（共6页）
（1）在所有的空格中填上适当的数（此数可含参数a，d） （2）当a，d在什么范围取值时，此解为最优解。
2??2?5a?0?a? 解：?，即?5；解为最优解。
d?0???d?0（3）若不是最优解，下一步迭代时的主元素为哪个？
解：若不是最优解，下一步迭代时的主元素为a（0?a?（4）c3?8在什么范围变化时，最优解不变？ (8??c3)?10?0,即?c3?2。
2、已知线性规划问题：maxz=2x1+x2+5x3?6x4
2 5?2x1????????x3??x4?8s.t ??2x1?2x2?x3?2x4?12
??x?0 (j?1,…,4)?j（1）写出其对偶问题；
**（2）已知对偶问题最优解为y1?4,y2?1，试用对偶问题的性质，求原问题的最优解。
解：（1）原问题的对偶问题为
min??8y1?12y2 ①?2y1?2y2 ?2 ②??2y1?1 ③??y1?y2?5 ④?y+2y?6 ⑤2?1??y1,y2?0
（2）将对偶问题最优解为y1?4,y2?1代入对偶问题约束条件可知：
①②式为严格不等式 则有 x1?x2?0 因 y1?0,y2?0
第3页（共6页）
******则有
?x3?x4?8 ??x3?x4?12 因原问题的最优解X*?(0,0,4,4)。 3、求解指派问题，并求出最小费用
minz???cijxij
i?1j?144(cij)4?4?20?17???24??1781222241816212522??23? 21??19?0524470814??6? 列约简?5?2?解：用“匈牙利法”求解。效率矩阵表示为：
?20?17 ??24??1781222241816212522??12??023? 行约简 ??821???19??0?12??(0)?8??0*?(0)524010047(0)8100012??4? 3??(0)??00100??0? 0??1???至此已得最优解： ????∴最小费用W=8+17+16+19=60
4、每月需要某种机构零件2000件,每件成本150元,每年的存储费用为成本的16%,每次订购费100元,求E.O.Q和最小费用。如允许缺货，单位缺货费为200元，求库存量和最大缺货量。 解：（1）用“不允许缺货，生产时间很短”的模型求解
已知C3?100,R?2000?12?24000,C1?150?0.16?24，故 最佳生产量
第4页（共6页）
Q0?最小费用
2C3R2?100?24000??447件 C124C1Q0C3R44724000??24??100??10733元 2Q02447 C?Q0??（2）用“允许缺货，生产时间很短”模型求解 已知C3?100,R?24000,C1?24,C2?200 库存量
S?2C3C2R?C1(C1?C2)2?200?100?24000?423件
24?24?200?2?100??24?200?2C3(C1?C2)t0???0.0197
C1C2R24?24000?200最大缺货量为 24000×0.0197-423≈50件。
5、排队论M/D/1模型，某实验室有一台自动检验机器性能的仪器，要求检验机器的顾客按泊松分布到达，每小时平均4个顾客，建议每台机器所需时间为6分钟。求： （1）在检验室内机器台数； （2）等待检验的机器台数； （3）每台机器在室内消耗时间； （4）每台机器平均等候检验的时间 解：本题属于M/D/1模型 ??4,E?T??14,??,Var?T??0 101020.4???0.4??0.533 Ls???2(1??)2?1?0.4??2Lq?LS???0.133
Ws?LS?Lq?0.133(小时)=8（分钟）
Wq?
??0.033(小时)=2分钟
第5页（共6页）
6、用动态规划的逆序推法求解下面问题
2maxz?x1x2x3?x1?x2?x3?1 ??xi?0 i?1,2,3 解：