运筹学66341.doc

西北工业大学2004年硕士研究生入学考试试题试题名称：运筹学 试题编号：809说明：所有试题一律写在答题卡上 第1页 共3页一、 判断题（每小题3分，共30分）1． LP问题的任一可行解都可以用全部基可行解的线性组合表示2． 任何线性规划问题存在并具有唯一的对偶问题3． 目标规划模型中，正偏差变量应取正值，负偏差变量应取负值4． 分枝定界法在需要分枝时必须满足：一是分枝后各子问题必须容易求解，二是各子问题解的集合必须覆盖原问题的解5． 指派问题效率矩阵的每一元素都乘上同一常数k，将不影响最优指派方案6． 对于一个动态规划问题，应用顺序或逆序解法可能会得到不同的最优解7． 图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中的点与点的相对位置、点与点连线的长短曲直等都要严格注意8． 工序的总时差越大，表明该工序在整个网络中的机动时间就越大9． 假如到达排队系统的顾客来自两方面，分别服从普阿松分布，则这两部分顾客合起来的顾客仍为普阿松分布10． 排队系统中，顾客等待时间的分布不受排队服务规则的影响二、（20分）某染化料厂要用C,P,H三种原料混合配制出A,B,D三种不同规格的产品，原料C,P,H每天的最大供应量分别为100，100，60kg，每千克单价分别为65，25，35元；产品A要求原料C含量不少于50％，含原料P不超过25％；产品B含C不得少于25％，含P不超过50％；产品D的原料配比没有限制；产品A,B含原料H的数量没有限制要求，产品A,B,D每千克的单价分别为50，35，25元。

问应如何安排生产，使得利润为最大？（注：只建模型不求解）西北工业大学2004年硕士研究生入学考试试题试题名称：运筹学 试题编号：809说明：所有试题一律写在答题卡上 第2 页 共3页三、（30分）已知线性规划问题： s.t.用单纯形法求得最终单纯形表如表1所示表1 XBbix1x2x3x4x2x13/2101105/14－1/7－3/142/7cj-zj0 0 －5/14 －25/14试求：1） 直接写出上述问题的对偶问题及其最优解2）目标函数系数c1或c2分别在什么范围内变动，上述最优解不变3）约束条件右端项b1,b2当一个保持不变时，另一个在什么范围内变化，上述最优基保持不变4）问题的目标函数变为时上述最优解的变化5）约束条件右端项由变为时上述最优解的变化四、（20分）用表上作业法求解表2所示运输问题的最优调运方案和最小总运费西北工业大学2004年硕士研究生入学考试试题试题名称：运筹学 试题编号：809说明：所有试题一律写在答题卡上 第3 页 共3页表2产地运价销地B1 B2 B3 B4 B5 B6产量 A1 2 1 3 3 3 5 50 A2 4 2 2 4 4 4 40 A33 5424 160 A442212231 销量305020403011五、（30分）根据表3所示的工序列表，绘制网格图、计算各工序的时间参数与时差，并确定关键路线、说明总工期。

表3工序紧前工序工序时间（天）工序紧前工序工序时间（天）a-----2gd1ba3hc,e5ca5lf5da4mf,g6eb6nh,l,m3fc2六、简述题（20分）试述建立动态规划数学模型的步骤及应注意的问题，并说明动态规划的求解方法有哪些？西北工业大学2003年硕士研究生入学考试试题试题名称：运筹学 试题编号：809说明：所有试题一律写在答题卡上 第1页 共2页一、 判断正误（40分，每小题4分）1． LP问题的每一个基本解对应可行解域的一个顶点2． LP问题的基本类型是”max”型问题3． 在单纯形法的计算中，选取最大正检验数对应的变量Xk为换入变量，将使目标函数值得到最快的增长4． 若LP模型的可行域非空有界，则其顶点中必存在最优解5． 给一个图G=(V,E)，如果图G’=(V’,E’),使V=V’及E’E，则称G’是G的一个支撑图6． 若X是某LP的最优解，则X必为该LP可行域的某一个顶点7． 对一个有n个变量、m个约束的标准型的线性规划问题，其可行解域的顶点恰好为个8． 若到达排队系统的顾客为泊松流，则依次到达的两名顾客之间的间隔时间服从负指数分布。

9． 在网络计划中，关键路线就是最早开工时间与最迟完工时间相等的结点之间的连线10． 大M法和两阶段法是用来处理人工变量的二、 计算题（90分）1．（30分）某一最大线性规划问题在单纯形法计算时得到如表1结果其中a,b,c,d,e,f都是未知数原问题中要求各变量均为非负表1CB XB bx1 x2 x3 x4 x5 x6x3 fx4 2x6 32 c 1 0 e 0-1 -5 0 1 -1 0a -3 0 0 -4 1Cj－xjb d 0 0 -3 0问：a,b,c,d,e,f应满足什么条件，有下面各解成立？1） 是非可行基解；2） 是唯一最优解；3） 有无穷多最优解；4） 是退化基可行解；5） 无界解；6） 是可行解但非最优解，只有X1可以进基且出基变量必为第3基变量2．（20分）某寻呼台每天需要话务员人数、值班时间以及工资情况如表2所示。

每班话务员在轮班开始时报到，并连续工作9小时问如何安排，使得既满足要求又使总支付工资最低，试建立数学模型西北工业大学2003年硕士研究生入学考试试题试题名称：运筹学 试题编号：809说明：所有试题一律写在答题卡上 第2页 共2页表2时间最少人数每人工资0－33－66－99－1212－1515－1818－2121－064810131513860605550484550563（20分）用表上作业法求解表3所示运输问题的最优调运方案和最小总运费，最优调运方案是否唯一？若不是，给出另一个最优调运方案表3产地运价销地B1 B2 B3产量 A1 6 5 4 15 A2 3 7 225 销量2010154．（20分）根据表4所示的工序明细表，绘制网格图、确定关键路线、标出各结点的时间参数表4工序紧前工序时间ABCDEFG――――――A,BA,B,CD,EE2433424三、简述题（20分）试叙述影子价格的经济意义，以及它性规划中的表达式。