运筹学(423)

2006年天津工业大学硕士研究生入学考试试题试题编号：423（运筹学）运筹学试卷第1页（共4页）考生注意：本试卷共九大题，满分150分。考试时间为3小时；所有答案均写在答题纸上，在此答题一律无效。一．（本题共5小题，每小题3分，满分15分）判断下列论断的正确性（正确者在括弧内填T，错误者填F）（1）线性规划的基本可行解满足所有的约束条件；（）（2）赋权图G的最小支撑树是它的边数最小的支撑树；（）（3）解运输问题的表上作业法中，对每一非基空格，均可找到唯一的一条闭回路；（）（4）无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，余下的决策序列必构成最优策略；（）（5）在贝叶斯决策中，完全信息的价值与补充信息的价值含义相同。（）二．（本题共5小题，每小题4分，满分20分）选择填空（将所选答案的标号填在空白处，每空填一个标号）（1）标准形式的线性规划问题，其可行解是基本可行解，最优解是可行解，最优解能在可行域的某一顶点达到。（a）一定（b）不一定（c）一定不（2）动态规划的研究对象是，其求解的一般方法是。（a）最优化原理（b）静态决策（c）逆序求解（d）函数迭代法（e）多阶段决策过程（3）运用表上作业法求解运输问题时，计算检验数可用，调整方案可用。（a）闭回路法（b）西北角法（c）最小元素法（4）影子价格是，其经济意义是。（a）对偶最优解（b）B-1b（B为最优基，b为资源限量）（c）约束资源的供应限制（d）约束条件所付的代价（5）单纯形法中的主元素一定是，B-1b（含义同上）一定不是。（a）正的（b）负的（c）零三．（本题满分17分）现有一个求目标函数极小值的线性规划问题，用单纯形法求解它时得到某次迭代的单纯形表如表1（表中的a1、a2、a3、a4、a5是待定系数）2006年天津工业大学硕士研究生入学考试试题试题编号：423（运筹学）运筹学试卷第2页（共4页）表1试问：在什么条件下（1）当前解为唯一最优解（4分）；（2）该问题具有无界解（4分）；（3）该问题无可行解（假设只有x5是人工变量）（4分）（4）当前解不是最优解，但尚可用单纯形法继续迭代。请指出换入变量和换出变量（5分）。四.(本题满分18分)已知线性规划问题maxz=2x1+3x2+5x3+6x4x1+2x2+3x3+x4≥2-2x1+x2-x3+3x4≤-3x1，x2，x3，x4≥0（1）写出其对偶问题（4分）；（2）用图解法求解对偶问题（6分）；（3）利用（2）的结果及对偶性质求原问题的解（8分）。五．（本题满分14分）设某种物资存放于m个产地，要运往n个销地。第i个产地可供应的物资量为ai个单位（i=1,2,…,m），第j个销地该物资的需求量为bj个单位（j=1,2,…,n）。从第i个产地到第j个销地该种物资的每单位运价为cij，问应如何调运这种物资才能使总运费最小？（1）设产销是平衡的，请建立线性规划模型（7分）。（2）设产销是不平衡的，且供过于求，请建立线性规划模型（7分）。六．（本题满分14分）某地输油管网络如图1所示，其中A为油田产地，C为原油出口码头，图上所标括号外数字为每段输油管的日输油能力，括号内数字为目前采用输油方案。（1）问现行方案是否最优？为什么？（4分）基变量X1X2X3X4X5资源限量bX3X4X5-13100a14010a2a500141a4检验数σja320002006年天津工业大学硕士研究生入学考试试题试题编号：423（运筹学）运筹学试卷第3页（共4页）（2）如现行方案不是最优，以现行方案为基础构成新方案。用最大流的标号算法求出最优方案。（10分）V110(10)V413(11)3(1)5(5)6(5)V3A4(4)C6(6)8(7)6(4)10(9)V23(3)V5（图1）七．（本题满分14分）某工程有十道工序A,B,…,J，各费时如下：工序ABCDEFGHIJ费时（天）10534565664又A、B同时开工；B的紧后工序是C；A、C是D、E的紧前工序；D的紧后工序是G、H；F的紧前工序是E；I的紧前工序是F和H；J的紧前工序是G；I，J是同时结束工序。（1）绘出计划网络图（7分）。（2）求出关键工序及其完工期（7分）。八．（本题满分22分）有1000台机器生产A、B两种产品，用y台机器生产A产品，可获得收入5y，用y台机器生产B产品，可获得收入4y。一年后，生产A产品的机器完好率为0.8，生产B产品的机器完好率为0.9，问五年内如何安排A、B两种产品，使得总收入最大？试结合本例具体说明，当用动态规划逆序方法求解时的下列基本概念（不必计算）：（1）阶段变量k（2分，要求写出所表示的实际意义及取值）（2）状态变量Sk（3分，要求写出所表示的实际意义）（3）决策变量Xk（3分，要求写出所表示的实际意义）（4）允许决策集合D(Xk)（3分，要求写出集合的表示）（5）状态转移方程（3分，要求写出具体方程）2006年天津工业大学硕士研究生入学考试试题试题编号：423（运筹学）运筹学试卷第4页（共4页）（6）阶段指标Vk（3分，要求写出计算公式及所表示的实际意义）（7）指标函数Vk5（2分，要求写出具体表达式）（8）递推方程（3分，要求采用逆序解法写出递推方程）九．（本题满分16分）某工厂面对激烈的市场竞争，拟制订利用先进技术对产品改型的计划。现有三个改型方案可供选择：d1，d2，d3。根据市场需求调查，该厂产品面临高需求、一般需求与低需求三种自然状态，这三种自然状态的概率分别为0.5，0.3，0.2。在三种自然状态下不同的改型方案所获得的收益不一样，表2给出了预期收益的情况：表2单位：万元d1d2d3θ1θ2θ34070110203010100-50（1）用期望值准则进行决策（4分）。（2）用决策树方法进行决策（4分）。（3）求完全信息价值EVPI，并说明其意义（8分）。