《2017年中国科学技术大学管理学院818管理学与运筹学之运筹学考研导师圈点必考题汇编.doc》由会员分享，可在线阅读，更多相关《2017年中国科学技术大学管理学院818管理学与运筹学之运筹学考研导师圈点必考题汇编.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年中国科学技术大学管理学院818管理学与运筹学之运筹学考研导师圈点必考题汇编一、选择题1 求解指派问题的匈牙利方法要求系数矩阵中每个元素都是（ ）。A. 非负的 B. 大于零 C. 无约束 D. 非零常数 【答案】A【解析】系数矩阵中的系数表示的是费用、成本、时间等。 2 企业进行库存管理与控制的目标不包括以下（ ）。A. 保证生产或销售的需要 B. 降低库存占用资金C. 降低花在存储方面的管理费用 D. 较低的货损 【答案】D【解析】货损与库存管理与控制无关，与采购的运输等其他环节有关。 3 关于最小费用最大流，求解时不会用到下面哪种方法（ ）。A.Dijkstra 算法 B.Flo
2、yd 算法C.Ford 一Fulkerson 算法 D. 奇偶点作业法 【答案】D【解析】奇偶点作业法为中国邮递员问题中寻找欧拉圈时所用的方法，最小费用最大流问题并不涉及此法。 4 某一线性规划问题中的某一资源的影子价格为4，当其可用量在其灵敏度允许范围内增加一，下述正确的是（ ）个单位时（假 定资源获得价格不变）。A. 收益减少4个单位 B. 收益增加4个单位 C. 最优解不会发生变化 D. 产量一定增加4个单位【答案】B【解析】某种资源的影子价格的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数的最 优值的变化。 二、简答题5 简述对偶问题的“互补松弛性”。【答案】互补松弛性
3、:若当且仅当为最优解。6 什么是可行流?【答案】满足下列条件的网络流f 称为可行流 （l ）容量限制条件:对每一弧（v i ，v j ）对于起点Vs ，记对于终点V t ，记 （2）平衡条件 对于中间点，流出量=流入量，即对每个分别是原问题和对偶问题的可行解。那么，式中，V （f ）称为这个可行流f 的流量，即发点的净输出量（或收点的净输入量）。7 对在多台设备上加工多个工件的工件排序问题来说，应如何衡量不同排序方案的优劣? 你认为应有哪 些准则? 这些准则的适用条件是什么? 请举出两个实例加以详细说明。【答案】（l ）应根据工期最短、成本最低、质量最优等优劣标准来衡量不同排序方案的优劣。（2
4、）设备充分利用、总加工时间最短等某一或某几种目标函数最优。（3）每个工件在m 台设备加工都有一定的先后顺序，工件在不同设备的加工顺序不同的情况不作考虑以及 信息掌握情况和资源约束等适用条件。（4）举例。建筑施工流水作业问题:在不同的施工段上按一定的施工工艺进行施工，而施工工艺又由不同 的施工工序组成，每道施工工序都要消耗一定的人工费用，机械台班和材料费用，并且某些施工工序之间有一定的先后约束关系，如支起模板后才能浇注混凝土，而此问题关注不 使整个施工按照最短施工时间保持一定施工节拍进同施工工序如何搭接排序组成一定施工工艺，行流水作业，同时消耗人、机、材等资源也合理。 8 简述求解最小费用最大流
5、的赋权网络设置方法。，有可行流f ，保持原网络各点， 【答案】解:对网络G=（ V ，E ，C ，d ）每条边用两条方向相反的有向边代替，各边的权 当边（vj 名）为原来G 中边（vi ，vj ）的反向边，令按如下规则: 三、证明题9 设G=（V ，E ）是一个简单圈，令证明:（l ）若（2）若，则G 必有圈； ，则G 必有包含至少条边的圈。，（称为G 的最小次）。（3）设G 是一个连通图，不含奇点。证明:从G 中丢失任一条边后，得到的图仍是连通图。 【答案】（l ）因为G （V ，E ）是一个简单圈，故该图中无环，也无重复边。若假设G 中无圈，则G 可能是树或非连通图，这两种情况均存在悬挂点
6、，即 相矛盾。故假设不成立， 所以，G 必有圈。（2）若，设与对应的点为v k ，则v k 必与，也至少与个端点相连。由（l ）的结论知，个端点构成圈）。G 中必有圈（由于对圈中的连通图而言，v k 至少与这的次至少为个端点不构成圈，那么在端点处必向外延伸（因为最小次为外某点相连）经连通链而到另一端点，对该圈而言，边数大于少于占条边的圈。个端点相连。如果v k 与v i这， 不与其中某点相连，必与其条，故G 必定 是包含不（3）证明:因为G 连通且不含奇点，故d （v ）=2n，且该图中无悬挂点。由题（l ）的结论知，G 必有圈。又因为G 是连通的，所以从G 中去掉任一条边，都必在某一圈中。而从圈中去掉任一条边，所得图仍是连通图。 10证明:矩阵对策 的鞍点不存在的充要条件是有一条对角线的每一个元素均大于另一对角线上的每一个元素。 【答案】（l ）先证充分性，要使鞍点存在，就必存在有可假设主对角线的每一个元素均大于次对角的每一个元素，即 使对一切， 则充分性得证。（2）证必要性。假设“有一条对角线的每一个元素均大于另一条对角线上的每一个元素”这一、选择题考研试题
