1、昆明理工大学2017年硕士研究生招生入学考试试题(A卷)考试科目代码:813 考试科目名称 :运筹学 考生答题须知1 所有题目(包括填空、选择、图表等类型题目)答题答案必须做在考点发给的答题纸上,做在本试题册上无效。请考生务必在答题纸上写清题号。2 评卷时不评阅本试题册,答题如有做在本试题册上而影响成绩的,后果由考生自己负责。3 答题时一律使用蓝、黑色墨水笔或圆珠笔作答(画图可用铅笔),用其它笔答题不给分。4 答题时不准使用涂改液等具有明显标记的涂改用品。一、将正确的答案填在空格处。(每空1分,共10分)1、在单纯形法中,初始基可能由决策变量、松弛变量和 三种类型的变量组成。2、生产过程中如果
2、某种资源bi未得到充分利用时,该种资源的影子价格为 。3、在线性规划问题的最优解中,如果对应某一约束条件的对偶变量值为 ,则该约束条件取严格等式。4、目标规划的目标函数由各目标约束的偏差变量及相应的 和权系数构成。5、在用图解法解目标规划时,首先必须满足所有绝对约束。在此基础上,再按照优先级从高到底的顺序,逐个地考虑各个 。6、0-1型整数线性规划,指决策变量只能取 的整数线性规划。7、任何图中,顶点次数的总和等于边数的 倍。8、在网络计划中, 为零的工作链为关键路线。9、动态规划是解决 决策过程最优问题的一种方法。10、求解线性规划问题时,解的情况有:唯一最优解、无穷多最优解、无可行解、 。
3、二、解释下列名词。(每题2分,共10分)1、工作总时差2、有向完全图3、整数规划4、状态转移方程5、线性规划问题的基3、 回答下列问题。(每题5分,共10分)1、 针对求解线性规划问题,请阐述单纯形法的计算步骤。2、 阐述Dijkstra算法的基本思想。四、写出下列线性规划问题的对偶问题。(10分) 五、用单纯形法中的大M法求解下列线性规划问题。(15分) 六、某产品零件制造商考虑将工厂A1、A2、A3、A4生产的零件运至仓库B1、B2、B3,希望总运费最小。下表列出了各处产量、需求量及单位运价。请求出总运费最小的运输方案。 (25分) 仓库工厂B1B2B3产量A13173A211946A33
4、2105A412856需求量749七、写出下列问题的动态规划的基本方程。(10分) 昆明理工大学2017年硕士研究生招生入学考试试题(A卷)八、有4个工人甲、乙、丙、丁,指派他们分别完成4项工作A、B、C、D,每个人只能完成一项工作,每项工作只能由1个人去完成。每人分别完成各项工作所消耗的时间如下表所示,问如何指派工作才能使总的消耗时间最小?(20分)时间 工作人ABCD甲10131619乙14181713丙21121114丁14161812九、求下列网络中的最大流。(20分) 十、根据下列资料,(1)绘制网络图;(2)计算各工序的最早开工、最早完工、最迟开工及最迟完工时间;(3)确定关键路线和总工期(20分)工序ABCDEFG紧前工序A,BA,BBCD,E时间/天5334312第 5 页 共 5页