南京航空航天大学
2013年硕士研究生入学考试参考答案
考试科目：运筹学
说 明：答案一律写在答题纸上，写在试卷上无效
一、简述题（每题5分，共30分）
1、 已知有线性规划问题如下，请写出其标准形式。
minz?7x1?4x2?3x3??4x1?2x2?6x3??20??3x?3x?5x?13?123s..t??5x2?3x3?30?imited,x3?0?x1?0,x2unl
答：
maxw?-20y1?13y2??4y1?3y2?7??2y?3y?4 ?12s..t???6y1?5y2??3??y1?0,y2?02、 下列论断是否正确，给出简要分析。
“资源的影子价格可被认为是最优生产方案中投入生产的机会成本”。
答：正确。影子价格是由资源在生产中所做出的贡献，当该价格大于市场价格时，可以购买该资源；当小于市场价格时，可以出售该资源。
3、 简述线性规划问题存在无有限最优解（无界解）的判定条件。
答：当某非基变量检验数为正，而其所对应的约束系数列向量全部不大于0时，则其解不受限制。
4、 简述弱对偶定理的内容。
答：如果xj是原问题的可行解，yi是其对偶问题的可行解，则恒有：5、 简述最大流和最小截集之间的关系。 答：最大流为最小截集容量之和。
6、 简述最小费用最大流问题求解过程中“最小费用增广链”的确定方法。 答：（1）加权：对零流弧，以费用流bij加权；对饱和弧，以-bij反向加权；对非饱和非零流弧以bij加权，同时添加反向弧，以-bij加权。
（2）寻找增广链：对费用流网络，用Dijkstra寻找增广链。 二、（本题20分）某企业考虑两种资源限制的生产计划问题，在利润最大化目标下列出了如下的线性规划模型：
_
_
?cx??by
jjiij?1i?1nmmaxz?6x1?14x2?13x3?2?1/4x1?x2?1/2x3?12?s..t?3/4x1?3/2x2?x3?45?x,x,x?0?123 （1） 用单纯形法求解该线性规划问题的最优解；
（2） 若企业拟投资增加一些资源量以提升企业的利润，你建议优先购买哪种资源？简
要分析原因。 （3） 若资源系数由??12??24?变为???，分析最优解的变化。 ?45??28?X1 6 1/4 3/4 6 1/4 3/8 5/2 1/2 1/4 X2 14 [1] 3/2 14 1 0 0 2 -1/2 X3 13 1/2 1 13 [1/2] 1/4 6 1 0 X4 0 1 0 0 1 -3/2 -14 2 -2 X5 0 0 1 0 0 1 0 0 1 b 12 45 0 12 27 168 24 21 解：（1）用单纯形法求解： Cij X4 X5 cj-zj X2 X5 cj-zj X3 X5 13 0 14 0 0 0 cj-zj -1/2 -12 0 -26 0 312 （2）应购买第1种资源，其影子价格为26，而第2种资源影子价格为0，表示未得到充分利用（剩余21）。
?20??24??48?b??B?1b???????即x3的产量由24增加到48。 ???11??28??4?三、（本题15分）甲、乙、丙三个煤矿供应A，B，C，D四个城市用煤，煤矿产量、城市需煤量及各煤矿到各城市之间的距离如表1，问如何安排调运方案使总的运输量最少？
表1
城市 煤矿 甲 乙 丙 A 40 20 80 B 120 100 50 C 40 30 110 D 110 90 60 日产量（供应量） 200 100 200 80 120 150 150 日销量（需要量） 解：这是一个产销平衡的运输问题，用表示作业法求解。由Vogel法给出初始方案： 城市 煤矿 甲 乙 丙 日销量（需要量） A 80 80 B 120 120 C 150 150 D 50 20 80 150 日产量（供应量） 200 100 200 由位势法检验：
城市 煤矿 甲 乙 丙 A (0) 20 (90) B (20) (20) 50 C 40 (10) (120) 40 D 110 90 60 110 ui 0 -20 -50 vj 40 100 所给方案即为最优方案，总运费25700. 四、（本题15分）某公司拟将四种新产品配置到四个工厂生产，每个工厂生产一种新产品，四个工厂的单位产品成本如表2所示，求最优的生产配置方案。 表2：各工厂的单位产品成本 单位成本 工厂 工厂1 工厂2 工厂3 工厂4 解： 产品1 73 80 70 87 产品2 89 60 80 65 产品3 190 150 170 200 产品4 170 130 150 180 min?73?80??70??8789190170?60150130??80170150??65200180?73607065?01611797??0162727??2009070??20000?????01010080?????0101010????? ?220135115??2204545?min009070??162727??0161717???161717??200?0??301000??301000???k=10,???,???0101010??01000??01000? ??????
?22?4545??2203535??22?3535?方案1：x11=x23=x34=x42=1其余=0；方案2：x11=x24=x33=x42=1，其余=0. 最优值：73+150+150+65=438.
五、（本题15分）已知图2表示7个城市（A、B、C、D、E、F、G）间拟建一条连接各个城市的通信线路，各边数字表示两个城市之间的修建费用，求连接各城市通信线路最小修建费用方案。
2013 运筹学(试题)参考答案 南京航空航天大学 硕士研究生入学考试试题
