2017年南京大学工程管理学院922管理与运筹学基础之运筹学教程考研导师圈点必考题汇编
● 摘要
一、判断题
1． 网络图中任何一个结点都表示前一工序的结束和后一工序的开始。（ ）
【答案】×
【解析】网络图的起始点只表示一工序的开始，结束点只表示一工序的结束。
2． 整数规划问题最优解的目标函数值一定优于其相应线性规划问题最优解的目标函数值。（ ）
【答案】×
【解析】因为附加了整数条件，其可行域比其相应线性规划问题的可行域减小，故整数规划问题最优解的目 标函数值一定不优于其相应线性规划问题最优解的目标函数值。
3． 结点最早时间同最迟时间相等的点连接的线路就是关键路线。（ ）
【答案】√
【解析】关键路线是指总时差为零的工作链，而该工作链是由一系列最早时间同最迟时间相等的点连接而成的。
4． 目标规划问题的日标函数都是求最大化问题的。（ ）
【答案】×
【解析】当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值，因此目标规划的目标函数只能是最小化的。
二、填空题
5． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_____。
【答案】均有
【解析】若存在实数
6． 现有m 个约束条件，使对于任意的，就称方向）为均有下式成立:
点的一个下降方向。 ，若某模型要求在这m 个条件中取”个条件作为约束，用，1变量来实现 该问题的约束条件组为:_____。
【答案】
【解析】0一l 变量取1时取该约束条件，否则不取，又一共取S 个约束条件。则可得到约束条件组为:
。
7． 图G=（V ，E ）有生成树的充分必要条件是_____。
【答案】G 是连通图
【解析】图G 是连通图，如果G 不含圈，那么G 本身是一个树，从而G 使它自身的一个支撑树。现设G 含圈，任取一个圈，从圈中任意地去掉一条边，得到G 的一个支撑子图Gl 。如果Gl 不含圈，那么Gl 是G 的 一个支撑树，如果Gl 仍含圈，那么从Gl 中再任取一个圈，如此重复，最终可以得到G 的一个支撑子图Gk ， 它不含圈，于是Gk 就是G 的一个支撑树。
8． 无向连通图G 是欧拉图的充要条件是_____。
【答案】G 中无奇点
三、计算题
9． 已知图表示7个城市间拟建一条连接各个城市的通信线路，各边的权数表示两个城市之间的修建 费用，求连接各城市通信线路最小修建费用方案。
图
【答案】最优方案为:
可使修建费用为最少。
10．国内某化妆品公司（简称M 公司），其管理层已经为他们公司的两种新产品制定了各自的市场目标，也就是说，产品1必须占据15%的市场份额，而产品2必须占有10%的市场份额。为了获得市场，准备开展三次广告活动·其中两个广告是分别针对产品1和产品2的，而广告3是为提高整个公司及其产品的声誉。以x l 、x 2、x 3分别表示分配在二个广告上的资金（单位:千万元）。则相应的两种产品取得市场份额估计值（以百分比表示）可表示为:
产品1的市场份额=0.05x1十0.02x 3，产品2的市场份额=0.03x2十0.02x 3公司投入广告的总预算为5500万元，其中规定必须至少有1000万元投入在第二个广告上。如果两个产品的市场份额不能同时实现，管理层认为两种产品目标偏离的严重性是同等的，管理层希望得到的最有效的资金分配方案。试在上述条件下，完整写出反映该问题的目标规划数学模型（注:不用求解）。
【答案】按照决策者所要求的，这个问题的数学模型是:
11．用表上作业法求解下面运输问题的最优调运方案和最小总运费:
表
，并检验（【答案】此问题属于运输平衡问题，则由沃格尔法得初始方案（0内数据）［］内
数据）
表
存在空格检验数为负，调整其所在回路，调整量min （8，12）=8，得新的方案，并检验之