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