运筹学各章试题

《运筹学》各章的小测试----复习思考题及测试题第一章绪论复习思考题1、从运筹学产生的背景认识本学科研究的内容和意义。2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。3、体会运筹学的学习特征和应用领域。第二章线性规划建模及单纯形法复习思考题1、线性规划问题的一般形式有何特征？2、建立一个实际问题的数学模型一般要几步？3、两个变量的线性规划问题的图解法的一般步骤是什么？4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？9、大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？测试题:1、把以下线性规划问题化为标准形式：(1)maxz=x1-2x2+x3s.t.x1+x2+x3≤122x1+x2-x3≥6-x1+3x2＝9x1,x2,x3≥0(2)minz=-2x1-x2+3x3-5x4s.tx1+2x2+4x3-x4≥62x1+3x2-x3+x4＝12x1+x3+x4≤4x1,x2,x4≥02(3)maxz=x1+3x2+4x3s.t.3x1+2x2≤13x2+3x3≤172x1+x2+x3=13x1,x3≥02、用图解法求解以下线性规划问题(1)maxz=x1+3x2s.t.x1+x2≤10-2x1+2x2≤12x1≤7x1,x2≥0(2)minz=x1-3x2s.t.2x1-x2≤4x1+x2≥3x2≤5x1≤4x1,x2≥03、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。maxz=2x1+x2-x3s.t.x1+x2+2x3≤6x1+4x2-x3≤4x1,x2,x3≥04、用单纯形表求解以下线性规划问题(1)maxz=x1-2x2+x3s.t.x1+x2+x3≤122x1+x2-x3≤6-x1+3x2≤9x1,x2,x3≥0(2)minz=-2x1-x2+3x3-5x4s.tx1+2x2+4x3-x4≤62x1+3x2-x3+x4≤12x1+x3+x4≤4x1,x2,x3,x4≥035、用大M法和两阶段法求解以下线性规划问题(1)Maxz=x1+3x2+4x3s.t.3x1+2x2≤13x2+3x3≤172x1+x2+x3=13x1,x2,x3≥0(2)maxz=2x1-x2+x3s.t.x1+x2-2x3≤84x1-x2+x3≤22x1+3x2-x3≥4x1,x2,x3≥06、某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示：饲料蛋白质（克）矿物质（克）维生素（毫克）价格（元/公斤）1310．50．2220．51．00．7310．20．20．446220．35120．50．80．8要求确定既满足动物生长的营养要求，又使费用最省的选择饲料的方案。7、某工厂生产Ⅰ、Ⅱ、Ⅲ、Ⅳ四种产品，产品Ⅰ需依次经过A、B两种机器加工，产品Ⅱ需依次经过A、C两种机器加工，产品Ⅲ需依次经过B、C两种机器加工，产品Ⅳ需依次经过A、B机器加工。。有关数据如表所示，请为该厂制定一个最优生产计划。产品机器生产率（件/小时）原料成本（元）产品价格（元）ＡＢＣⅠ10201665Ⅱ20102580Ⅲ10151250Ⅳ20101870机器成本（元／小时）200150225每周可用小时数15012070第三章线性规划问题的对偶及灵敏度分析复习思考题1、对偶问题和它的经济意义是什么？2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？44、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6、在线性规划的最优单纯形表中，松弛变量（或剩余变量）0knx，其经济意义是什么？7、在线性规划的最优单纯形表中，松弛变量knx的检验数0kn，其经济意义是什么？8、关于ijjibca,,单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？测试题1、写出以下问题的对偶问题(1)minz=2x1+3x2+5x3+6x4s.t.x1+2x2+3x3+x4≥2-2x1-x2-x3+3x4≤-3x1,x2,x3,x4≥0(2)minz=2x1+3x2-5x3s.t.x1+x2-x3+x4≥52x1+x3≤4x2+x3+x4=6x1≤0,x2≥0,x3≥0,x4无符号限制2、已知如下线性规划问题Maxz=6x1-2x2+10x3s.t.x2+2x3≤53x1-x2+x3≤10x1,x2,x3≥0其最优单纯形表为b6-21000x1x2x3x4x510x35/201/211/206x15/21-1/20-1/61/3-z-400-40-4-2（1）写出原始问题的最优解、最优值、最优基B及其逆B-1。（2）写出原始问题的对偶问题，并从上表中直接求出对偶问题的最优解。53、用对偶单纯形法求解以下问题(1)minz=4x1+6x2+18x3s.t.x1+3x3≥3x2+2x3≥5x1,x2,x3≥0(2)minz=10x1+6x2s.t.x1+x2≥22x1-x2≥6x1,x2≥04、已知以下线性规划问题maxz=2x1+x2-x3s.t.x1+2x2+x3≤8-x1+x2-2x3≤4x1,x2,x3≥0及其最优单纯形表如下：b21-100x1x2x3x4x52x18121100x61203-111-z-160-3-3-20(1)求使最优基保持不变的c2=1的变化范围。如果c2从1变成5，最优基是否变化，如果变化，求出新的最优基和最优解。(2)对c1=2进行灵敏度分析，求出c1由2变为4时的最优基和最优解。(3)对第二个约束中的右端项b2=4进行灵敏度分析，求出b2从4变为1时新的最优基和最优解。(4)增加一个新的变量x6，它在目标函数中的系数c6=4，在约束条件中的系数向量为a612，求新的最优基和最优解。(5)增加一个新的约束x2+x32，求新的最优基和最优解。65、某工厂用甲、乙、丙三种原料生产A、B、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示:产品ABCD原料数量（吨）对原料甲的单耗(吨/万件)32142400对原料乙的消耗(吨/万件)2－233200对原料丙的消耗(吨/万件)13－21800单位产品的利润(万元/万件)25121415（1）求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余量。（2）求四种产品的利润在什么范围内变化，最优生产计划不会变化。（3）求三种原料的影子价格。（4）在最优生产计划下，哪一种原料更为紧缺?如果甲原料增加120吨，这时紧缺程度是否有变化?第四章运输问题复习思考题1、运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于1nm？2、用西北角法确定运输问题的初始基本可行解的基本步骤是什么？3、最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4、试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？5、用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？6、试述用位势法求检验数的原理、步骤和方法。7、试给出运输问题的对偶问题（对产销平衡问题）。8、如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。9、一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？测试题1、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。（1）用西北角法、最小元素法求初始基本可行解；7（2）由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要的迭代次数。销地产地甲乙丙丁产量1231089523674768252550销量152030351002、用表上作业法求下列产销平衡的运输问题的最优解：（表上数字为产地到销地的运价，M为任意大的正数，表示不可能有运输通道）（1）销地产地甲乙丙丁产量1237349535810264171523销量1015201055（2）产地销地甲乙丙丁戊销量12347458267817M66M32767620201015产量1015121018653、用表上作业法求下列产销不平衡的运输问题的最优解：（表上数字为产地到销地的里程，M为任意大的正数，表示不可能有运输通道）。（1）产地销地甲乙丙丁戊销量12310784M510412746578804060产量5040306020（2）产地销地甲乙丙丁戊销量1237463289512462111053024368产量12182114154、某农民承包了5块土地共206亩，打算小麦、玉米和蔬菜三种农作物，各种农作物的计划播种面积（亩）以及每块土地种植各种不同的农作物的亩产数量（公斤）见下表，试问怎样安排种植计划可使总产量达到最高？土地块别作物种类甲乙丙丁戊计划播种面积12350085010006008009506507008501050900550800950700867050土地亩数3648443246提示：为了把问题化为求最小的问题，可用一个足够大的数（如1200）减去每一个亩产量，得到新的求最小的运输表，再进行计算。得到求解的结果后，再通过逆运算得到原问题的解。（想一想为什么？）第五章动态规划思考题主要概念及内容：多阶段决策过程；阶段及阶段变量；状态、状态变量及可能的状态集合；决策、决策变量及允许的决策集合；策略、策略集合及最优策略；状态转移方程；K－子过程；阶段指标函数、过程指标函数及最优值函数；边界条件、递推方程及动态规划基本方程；最优性原理；逆序法、顺序法。复习思考题：1、试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。2、动态规划的阶段如何划分？3、试述用动态规划求解最短路问题的方法和步骤。4、试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界条件等概念。5、试述建立动态规划模型的基本方法。6、试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。测试题1、用动态规划求解以下网络从A到G的最短路径。ABBBCCDDDEEF123121231252164373332542710897119121392、某公司有5台设备，分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。台数012345A01015202325B51720222324C712151820233、用动态规划求解以下非线性规划问题：maxz=x1•2x2·3x3s.t.x1+3x2+2x3≤12x1,x2,x3≥04、某企业生产某种产品，每月月初按订货单发货，生产的产品随时入库，由于空间的限制，仓库最多能够贮存产品90000件。在上半年（1至6月）其生产成本（万元／千件）和产品订单的需求数量情况如下表：月份(k)成本与需求123456生产成本(ck)（万元／千件）2.12.82.32.72.02.5需求量(rk)（千件）356350326744已知