1、重 庆 工 商 大 学2015年攻读硕士学位研究生入学考试（初试）试题学科专业：管理科学与工程 研究方向：考试科目：运筹学 试题代码：804 （试题共 3 页） 注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效； 2.试题附在考卷内交回。 一、判断题（判断下列说法是否正确，请将“正确”与“错误”的判断结果按照题号顺序写在答题纸上。本大题共10小题，每小题2分，共20分）1、线性规划问题的图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。2、线性规划问题的基可行解对应可行域的顶点。3、在单纯形法计算中，如不按照最小原则选取换出变量，则在下一个解中至少有一个基变量
2、的值为负。4、运输问题是一种特殊的线性规划问题，因而求解结果也可能出现下列四种情况之一：有唯一最优解、有无穷多最优解、无界解、无可行解。5、如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数，最优调运方案将不会发生变化。6、用割平面法求解整数规划问题时，所构造的割平面有可能切去一些不属于最优解的整数解。7、指派问题效率矩阵的每一个元素都乘上同一个常数，将不影响最优指派方案。8、假定为0-1变量，则表示做第件事的充要条件是不做第件事。9、如果图中某一点有若干个相邻点，与其距离最远的相邻点为，则边必不包含在最小支撑树内。10、在任一图中，当点集确定后，树图是中边数最少的连通图。二、简答
3、题（本大题共2小题，其中第1小题8分，第2小题7分，共15分）1、简述线性规划数学模型的结构及各要素的特征。2、简述最小费用最大流的概念及其求解最小费用最大流问题的基本思想和方法。 （试题共 3 页，本页为第 1 页） 三、建模题（建立下列问题的线性规划模型，不需要求解。本大题共25分）某饲料厂用三种原材料I、II、III混合调配出三种不同规格的精饲料产品A、B、C。已知产品的规格要求、单位产品的加工费用和销售单价，每天能供应的原材料数量及原材料单价见下表，该饲料厂应该如何安排生产才能使利润最大？ 原材料ABC原材料价格（元/千克）每天限制用量（千克）60%15%2.00 20001.50 2
4、50020%60%50%1.00 1200加工费（元/千克）0.500.400.30售价（元/千克）3.402.852.25四、计算题（本大题共4小题，第1、2、3小题各25分，第4小题15分，共90分）1、下表是某求极大化线性规划问题得到的单纯形表，表中无人工变量，、为待定常数。试确定这些常数分别取何值时，以下结论成立：（1）表中解为唯一最优解；（2）表中解为最优解，但存在无穷多最优解；（3）表中解为退化的可行解；（4）表中解非最优，下一步迭代将以替换基变量；（5）该线性规划问题具有无界解；（6）该线性规划问题无可行解。基 4100213011035004100302、现有一运输问题，产量、
5、销量及单位运输价格如下表所示，试求最优调运方案。 销地产地甲乙丙丁戊产量A102059105B21083066C12071042D863759销量44624 （试题共 3 页，本页为第 2 页） 3、分配甲、乙、丙、丁、戊五人去完成A、B、C、D、E五项任务，要求每个人只能承担一项任务，每项任务只能由一个人承担。每个人完成各项任务的时间（单位：小时）如下表所示。试确定最优的任务指派方案，使完成任务的总时间最少。 任务人ABCDE甲127979乙89666丙71712149丁15146610戊41071094、求下列赋权有向图中到的最短路。452313217536v2v3v4v5v6v7v1 （试题共 3 页，本页为第 3 页）
