运筹学试卷A试题.doc

运筹学 课程考试试卷（ A ） 四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。运价（元/吨）B1B2B3供应量（吨）A11267A204212A331511需求量（吨）101010装订线五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。 a ,7 e,10 g,35 b,8 d,17 h,26 C,12 f,24 i,17 j,34 1、 指出项目的关键路线；（5分）2、 求项目的完工期。（5分）六、（10分） 求以下网络的最大流的流量（10分）；Cij 7 8 4 3 10 9 8 4 装订线 3 2 4 9 6 运筹学 课程考试试卷（ B ）二、(16分)已知LP问题： max z = x1 + 2x2 +3x3 + 4x4s.t. x1 + 2x2 + 2x3 + 3x4 20 (1) 2x1 + x2 + 3x3 + 2x4 20 (2) x1 、 x2 、 x3 、 x4 0的最优解为（0，0，4，4）T，最优值为Z=28。求： （1）写出该问题的对偶问题。（6分）(2) 请用互补松弛定理计算其对偶问题的最优解。（10分）三、解下表所示的供需平衡的运输问题（20分）运价（元/吨）B1B2B3B4供应量（吨）A1912108240A214761180A35131520180需求量（吨）901201301601、（15分）求出使总的运费最小的最优运输方案以及最小运输费用； 2、（5分）从A1到B1的运价C11=9 在什么范围内变化，以上最优解保持不变？装订线四、（20分）求以下纯整数规划问题(方法不限)： min z = -3x1 - 7x2s.t. 2x1 + 3x2 12 (1) -x1 + x2 2 (2) x1 ， x2 0 x1, x2 为整数五、（20分）求解：（1）以下网络的最小支撑树（5分）（2）从节点1到节点7的最短路径。（15分） 7Wij 5 2 6 3 1 7 2 2 6 4六.（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。（1）找出所有关键路线及对应的关键工序；（13分）（2）求项目的完工期。（5分） 运筹学 课程考试试卷（ C ）装订线三、（20分）对于如下的线性规划问题 min z = 3x1 + 2x2 +x3s.t. x1 + x2 + x3 15 (1) 2x1 - x2 + x3 9 (2) -x1 + 2x2 +2x3 8 (3) x1 x2 x3 0 1、（5分）写出题目中线性规划问题的对偶问题； 2、（10分）分别求出原始问题和对偶问题的最优解（求解的次序和方法不限）； 3、（5分）C3如何变化，使该问题的最优性保持不变。四、（15分）在一个33的运输问题中，已知供应量a115，a230，a385；而需求量b120，b230，b380，其最优解运输量如下表所示：15525580又设各位势为u1-2，u23，u35，v12，v25，v310，现问：1、最优总运费是多少？（10分）2、在保持上面解最优解的条件下，各个非基变量的Cij的最小值是什么？（5分）五、（10分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。 a ,7 e,10 g,35 装订线 b,8 d,17 h,26 C,12 f,24 i,17 j,34 1、 指出项目的关键路线；（5分）2、 求项目的完工期。（5分）六、（15分）1、求以下网络的最小支撑树（5分）；2、求以下网络从节点1到节点12的最短路径（10分）。 3 4 7 装 订 线 6 2 5 1 1 9 8 4 8 6 3 7 2 4 运筹学 课程考试卷（ D ） 二、选择题（16分，每题2分）对于如下的线性规划问题 x5=0x2=0x4=0x2x1MinZ= X1+2X2s.t. X1+ X24AGOBCDEFH412341230X1X2X3=0X4=0X5=0 -X1+ X21 X23X1, X20的图解如右图所示。三个约束对应的松弛变量分别为x3、x4、x5，请选择一个正确的答案填在相应括号中。1、这个问题的可行域为（ ）；A、（OCBA） B、（EFH） C、（FGB） D、（BCEF）2、该问题的最优解为（ ）；A、（F） B、（G） C、（H） D、（C）3、这个问题的基础解为（ ）；A、（OABCDEFGH） B、（ABCDEH） C、（OABCEFGH） D、（CEFB）4、这个问题的基础可行解为（ ）；A、（HEF） B、（BCEF） C、（FGB） D、（OABC）5、A点对应的解中，小于零的变量为（ ）； A、（x2） B、（x4） C、（x3）6、F点对应的基变量为（ ）； A、（x1 x2 x4） B、（x2 x3 x4） C、（x1 x4 x5） D、（x1 x3 x5）7、F点对应的非基变量为（ ）；A、（x1 x3） B、（x3 x5） C、（x2 x3） D、（x2 x4）8、从O到C的单纯形叠代，进基变量为（ ），离基变量为（ ）； A、（x1、x2） B、（x2、x3） C、（x2、x4） D、（x2、x5）三、(14分)一个工厂用四种原料生产三种产品，生产每种产品要消耗的各种原料数量（表中“”表示相应的产品不需要这种原料）、各种产品的利润以及各种原料的限量如下表所示。1、 （5分）写出原料限制条件下利润最大化的线性规划模型；（4分）写出以上问题的对偶问题；2、 （5分）已知利润最大的线性规划问题的最优解是产品A生产120件，产品B不生产，产品C生产52件，用互补松弛关系求四种原料的影子价格。原料消耗（吨/件）产品A产品B产品C原料限量（吨）原料甲128102400原料乙610151500原料丙15181800原料丁20222000产品利润（万元/件）120180210四、（20分）某运输问题的供需平衡表与单位运价表如下表所示运价（元/吨）B1B2B3B4供应量（吨）A112910735A26118925A37861040需求量（吨）15203530 1、（15分）求出使总的运费最小的最优运输方案以及最小运输费用； 2、（5分）从A2到B4的运价C24=9 在什么范围内变化，以上最优解保持不变？装订线五、（20分）根据项目工序明细表，工序ABCDEFG紧前工序-AAB,CCD,ED,E工序时间（周） 961219678求解： （1）画出网络图。（5分）（2）计算各工序的最早开始、最迟开始时间和总时差。（10分）（3）找出关键路线和关键工序。（5分）六、（10）求以下网络的最大流的流量。 10 3 10 1 2 3 1 5 2 4 5 9 运筹学 课程考试试卷（ F 三、数学建模题（10分）某班有男生30 人，女生20人，周日去植树。根据经验，一天男生平均每人挖坑20个，或栽树30 棵，或给25 棵树浇水；女生平均每人挖坑10 个，或栽树20 棵，或给15 棵树浇水。每个同学在挖坑、栽树、浇水三种工作种只做一种。问应怎样安排，才能使植树（包括挖坑、栽树、浇水）最多？请建立此问题的线性规划模型，不必求解。四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。运价（元/吨）B1B2B3供应量（吨）A11235A23246需求量（吨）254装订线五、（15分）已知项目各工序的三种估计时间如下表所示 工序紧前工序工序的三种时间（小时）ambA91012BA6810CA131516DB8911EB,C151720FD,E91214 1、 绘制网络图并计算各工序的期望时间；（5分）2、 计算关键工序和关键路线。（5分）3、 项目完工时间的期望值。（5分）6、 （15分）计算如图所示的从A 到E 的最短路线及其长度（单位：km）四、（20分）某运输问题的供需平衡表与单位运价表如下，求出使总的运费最小的最优运输方案以及最小运输费用。装订线运价（元/吨）B1B2B3供应量（吨）A11235A23246需求量（吨）254五、（15分）已知项目各工序的三种估计时间如下表所示 工序紧前工序工序的三种时间（小时）ambA91012BA6810CA131516DB8911EB,C151720FD,E91214 1、 绘制网络图并计算各工序的期望时间；（5分）2、 计算关键工序和关键路线。（5分）3、 项目完工时间的期望值。（5分） 六、（13分）某公司为经营业务的需要，决定要在现有生产条件不变的情况下，生产一种新产品，现可供开发生产的产品有I、II、III、IV四种不同产品，对应的方案为A1,A2,A3,A4由于缺乏相关资料背景，对产品的市场需求只能估计为大中小三种状态，而且对于每种状态出现的概率无法预测，每种方案在各种自然状态下的效益值表，如下表所示 自然状态供选方案Ai需求量大S1需求量中S2需求量小S3A1:生产产品I800320250A2:生产产品II600300200A3:生产产品III30015050A4:生产产品IV400250100求：（1）用悲观主义准则求解的决策方案（4分） （2）用乐观主义准则求解的决策方案（4分） （3）用最小机会损失准则求解的决策方案（5分） 三、简答题（12分）1. 什么是线性规划问题的基本可行解？（3分）答：对应基 ，令所有的非基变量为零，求 解约束方程组AX=b，可惟一得出基变 量的 一组值，这样得到的N个变量的一组解成为一个“基本解”或“基解”。如果一个基本解中的所有变量都大于或等于0，则称这个基本解为“基本可行解”或“基可行解”。2. 在对偶单纯形法中使用最小比值定理的作用是什么？（3分）答：在对偶单纯形法中，当求解进基变量是采用最小比值定理，是为了不改变对偶问题的可行性。3. 如何理解动态规划问题中的“状态”的概念？（3分）答：状态（State）是描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为sk。各阶段所有状态组成的集合称为状态集。4.决策分析的基本原则是什么？（3分）答: 最优化（满意）原则; 系统原则;可行性原则;.信息对称、准全原则 运筹学 课程考试试卷（ I ）四、解下表所示的供需平衡的运输问题（20分）运价（元/吨）B1B2B3B4供应量（吨）A1912108240A214761180A35131520180需求量（吨）901201301601、（15分）求出使总的运费最小的最优运输方案以及最小运输费用； 2、（5分）从A1到B1的运价C11=9 在什么范围内变化，以上最优解保持不变？装订线五.（18分）某项目网络图如下，英文字母表示工序，数字表示该工序需要的时间。（1）找出所有关键路线及对应的关键工序；（13分）（2）求项目的完工期。（5分）六、（10分）以下题目任选一道，多做只给一道题目的分。1、（10分）求以下网络从节点1到节点12的最短路径。 3 4 7 6 2 5 1 1 9 8 4 8 6 3 7 2 42、（10分）求以下网络的最大流的流量。 6 7 4 3 10 9 6 4 3 1 4 8 5 1. 为什么在线性规划问题标准型中通常记约束方程组AM*N（mn）的秩为r()m？（3分）答：为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况mn，通常设A的秩r（A）= m，且m n。 即AX=b中所包含的 m个方程式彼此 独立，没有多余方程，且方程个数小于未知量个数。2. 在普同单纯形法中使用最小比值定理的作用是什么？（3分）答：在普同单纯形法中，求解出基变量时通常使用最小比值定理，是为了保持原始问题的可行性不变，即右端的资源向量始终大于等于零。3. 什么是影子价格？可以用于哪些经济活动的分析？（3分）答：影子价格(Shadow price)是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量yi的值（1分）。正确理解影子价格，利用影子价格作下列经济活动分析（1）调节生产规模例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模（2）生产要素对产出贡献的分解通过影子价格分析每种资源获得多少产出例如，企业获得100万元的利润，生产过程中产品的直接消耗的资源有材料A、材料B、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来（3）由性质2.5知，第i个松弛变量大于零时第i个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第i种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加（ 4）影子价格是企业生产过程中资源的一