《运筹学作业习题.docx》由会员分享，可在线阅读，更多相关《运筹学作业习题.docx（10页珍藏版）》请在三一文库上搜索。
1、思考题线性规划建模及单纯形法主要概念及内容：线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式；可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基向量；基本解、基本可行解、可行基、最优基。复习思考题：1、线性规划问题的一般形式有何特征？2、建立一个实际问题的数学模型一般要几步？3、两个变量的线性规划问题的图解法的一般步骤是什么？4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及
2、它们之间的相互关系。7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？9、大M 法中， M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？作业习题1、将下列线性规划问题化为标准型maxz 3x1 5x2 4x31）2x4min f3x1x24x32x4182x13x2x32x45113( 2)3x12x22x3x4792x14x23x32x415x1,x
3、20,x402x1 6x2 x3 3x4x1 3x2 2x3 2x4x1 4x2 3x3 5x4x1 ,x2, x402、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：2x1 3x2 3x362x1 3x2 4x3 12x1, x2 , x302）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解.maxz 3x1 x2 2x312x1 3x2 6x3 3x498x1 x2 4x3 2x5 103x1 x6 0xj 0(j1,6)3、用图解法求解下列线性规划问题max z x1 2x2 2x1 x2 6 (1) 3x1 2x2 12x13x1,x2 0
4、min zx13x2(2)4x1 7 x2 563x1 5x215x1, x204、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解 maxz x1 2x2 x3x1 x2 2x36x1 4x2 x34x1,x2,x35、用单纯形法求解以下线性规划问题maxz 3x1 2x2maxz x2 2x3(1)2x1 3x23x1x2(2)X 3x24x3122x2 x3 12x1,x2 0Ox2%06、用大M法及两阶段法求解以下线性规划问题maxz x1 3x2 4x33x1 2x213(1) x2 3x3 172x1 x2 x3 13x1,x2,x30min fx1 3x2 x3
5、x1 x2 x3 3(2) x1 2x2 2x1 5x2 x3 4x1, x2, x307、某工厂生产过程中需要长度为3.1米、2.5米和1.7米的同种棒料毛坯分别为 200根、100根和300根。现有的原料为 9米长棒材，问如何下料可使废料最少？8、有1, 2, 3, 4四种零件均可在设备 A或设备B上加工，已知在这两种设备上分别加 工一个零件的费用如下表所示。又知设备A或B只要有零件加工均需要设备的启动费用， 分别为100元和150元。现要求加工1,2, 3, 4零件各三件。问应如何安排使总的费用 最小。试建立线性规划模型。在两种设备上分另加工Y零牛的费丹阮）零件1234ASO80优4CI
6、B30IDO507CI9、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示：造船厂三年内生产大型客货轮的冒功及每艘雪货轮成事年度正常生产时间 的客货轮数加既生产时间内可完成 的客货锈正常生产时每成本 （万元）13m5002526 00313500已知加班生产时，每艘客货轮成本比较正常时高出 60万元；又知造出来的客货轮若当年 不交货，每艘每年积压一年造成损失为 30万元。在签定合同时，该厂已积压了两艘未交 货的客货轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产量，在满足上述各项要求
7、的情况下总的生产费用最少？试建立线性规划模 型，不求解。线性规划问题的对偶及灵敏度分析思考题主要概念及内容：对偶问题，对称形式、非对称形式；对偶定理；对偶单纯形法；灵敏度分析。复习思考题：1、对偶问题和它的经济意义是什么？2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？4、如何根据原问题和对偶问题之间的对应关系， 找出两个问题变量之间、解及检验数之 问的关系？5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6、在线性规划的最优单纯形表中，松弛变量(或剩余变量) ，其经济意义是什么？7、在线性规划的最优单纯形
8、表中，松弛变量的检验数，其经济意义是什么？8、关于价值系数和资源常量单个变化对线性规划问题的最优方案及有关因素将会产生 什么影响？有多少种不同情况？如何去处理？9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？ 如何去处理？10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？ 如何去处理？作业习题1、写出下列问题的对偶规划由型工=/ 42巧 -3与 4 4彻= -3% + 5小=一工1 +西-讥=5CD(2)白工 1 +了曲-X5 + 5 J1- * 012- 9勺 4 7G + 双 W 10如后 口,啊,不无符号限制2、试用对偶理论讨论
9、下列原问题与它们的对偶问题是否有最优解min / = -Tj + t52或均+%三4 0m型 = 2/+2町(2)，4千的*0*2V - 2式十天2 一* 1J卜工中号 03、考虑如下线性规划miti 1y =均 + 句 + % + 勺/十叼之61万+演之8%+ q之7-c(1)写出对偶规划。(2)用单纯形法解对偶规划，并在最优表中给出原规划的最优解(3)说明这样做比直接求解原规划的好处。4、用对偶单纯形方法，求解下面问题(1)min f 5x1 2x2 4x33x1 x2 2x3 46x1 3x2 5x3 10为区区 0(2)maxz x 2x2 3x32x1 x2 x3 4 x1 x2 2
10、x3 8 x2 x32x1,x2,x305、考虑下面线性规划max z 2x1 3x22x1 2x2 x312x1 2x2 x484x1 x5164x2 x612x1,x2,x3,x4,x5,x6其最优单纯形表为:基变量x1x2x3x4x5x6x3001-1-1/400x110001/404x6000-21/214x2000-3/2-1/802j000-3/2-1/80-14试分析如下问题(1)分别对Cj进行灵敏度分析。(2)对0进行灵敏度分析。(3)当Cj=时，求新最优解。(4)当bi=时，求新最优解。(5)增加一个约束，问对最优解有何影响？(6)确定保持当前最优解不变的 P1的范围。6、已
11、知某工厂计划生产A1、A2、A3三种产品，各产品需要在甲、乙、丙设备上加工有关数据如下备4也:W限群Jt每月)甲16103C4乙105400丙21310420单位产品用J同(千元)3229试问：(1)如何充分发挥设备能力，使工厂获利最大；(2)若为了增加产量，可借用别的工厂的设备甲，每月可借用 60台时，租金1.8万元， 问是否合算？(3)若另有两种新产品A4、A5 ,其中每件A4需用设备甲12台时、乙5台时、丙10台时，每件获利2.1千元；每件A5需用设备甲4台时、乙4台时、丙12台时，每件获利1.87千元。如 甲、乙、丙 设备台时不增加，分别回答这两种新产品投产是否合算？(4)增加设备乙的
12、台时是否可使企业总利润进一步增加？7、已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下 表所示，求表中各括弧内未知数的值。Cj322000bX BCBX1X2X3X4X5X6X4111100(B)X5(A)1201015X62(C)100120j322000X400(D)(L)-1/4-1/45/4X110(E)03/4(I)025/4X。01(F)0(H)1/2X25/2j0(K)(G)0-5/4(J)运输问题思考题主要概念及内容：运输问题、运输表、产销平衡；基本可行解；闭回路；位势；检验数；虚设产地（销地）；运输问题建模。复习思考题：1、运输问题的数学模型具有什么
13、特征？为什么其约束方程的系数矩阵的秩最多等于？2、用西北角法确定运输问题的初始基本可行解的基本步骤是什么？3、最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4、试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？5、用闭回路法检验给定的调运方案时， 如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一 的？6、试述用位势法求检验数的原理、步骤和方法。7、试给出运输问题的对偶问题（对产销平衡问题）。8、如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。9、一般线性规划问题应具备什么特征才可以转化为运输问题的
14、数学模型？作业习题1、某公司生产某种产品有三个产地 A1、A2、A3 ,要把产品运送到四个销售点 B1、B2、B3、B4去 销售。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。产品运输数据表肖地B1B2B3B4产量（吨）A151186750A21019710210A39141315600销量（吨）3504205302601560 （产销平衡）问应如何调运，可使得总运输费最小 ？（1）、分别用西北角法和最小元素法求初始基本可行解；（2）、在上面最小元素法求得的初始基本可行解基础上，用两种方法求出非基变量的检验数;（3）、进一步求解这个问题。2、用表上作业法求解下列
15、运输问题：（1）运输问题数据表B1B2B3B4）里A1847290A25835100A377I 29120销量705011080（2）运输问题数据表.销地 n*B1B2B3B4B5J里A18637520A25一84730A36396830销量25252010203、某厂考虑安排某件产品在今后 4个月的生产计划，已知各月工厂的情况如下表所示7一计划月项目一一一第一月第二月第二月第四月单件生产成本10121416野月“需求堇400800900600正常生产有吹?00700700700加班能力02003000加旺单件成本15171S21库存费用3333试建立运输问题模型，求使总成本最少的生产计划。选
16、择题1 .当利用单纯形法计算某个线性规划问题时， 若最终表人工变量不为零，则可以断言该性线规划问题（A ）。A.无可行解 B .有无界解C .有多重解D .唯一解2 .当利用对偶单纯形法计算某个目标函数极大化线性规划问题时，若右侧常数bi 0,对应的a。 0,则可以断言该性线规划问题（A ）。A.无可行解 B .有无界解C .有多重解D .唯一解3 .当利用单纯形法计算某个极大化线性规划问题时，若最终表非基变量检验数。0,且至少有一个为零，则可以断言该性线规划问题（C ）。A.无可行解 B .有无界解C .有多重解D .唯一解4 .当利用单纯形法计算某个目标函数极大化线性规划问题时，若有非基变
17、量的检验数。0,且对应的系数列向量aij 0,则可以断言该性线规划问题（B ）。A.无可行解 B .有无界解C .有多重解D .唯一解5 .用单纯形法求解目标函数最大化的线性规划问题时，只有（ A ）对应的非基变量Xj可以被选作 为换入变量。A.检验数。0 B .检验数j 0中的最大者D .检验数j 0, 说明在最优生产计划中（ A ）。A.第i种资源已完全耗尽B .第i种资源有剩余C .生产第i种产品D .不生产第i种产品15极大化的线性规划问题的可行解无界，则对偶规划（D ）。A.唯一最优解B .有限最优解C .无穷多最优解 D .无可行解E .无界解16其他条件相同的情况下，允许缺货的经
18、济订货批量模型的总费用（C ）不允许缺货的经济订货批量模型的总费用。A.大于B .等于C .小于D .不确定17订货费与（C ）有关。A.订货批量数量 B .货物单价 C .订货次数D .以上都是18以下目标规划中的目标函数，在逻辑上不合理的是（）。A maxd -+d+ B maxd - d+ C mind -+d+ D mind - d+19运输问题的基本可行解有特点（D ）。A.产销平衡B .形成闭回路 C .有m+n位势D .有rni+ n1个基变量20 若是否采用 j 项目的 0-1 变量为 xj , 那么 J 个项目中至多只能选择一个项目的约束方程为 （ C ）xj1xj1xj 1A j JB j JC j JD 无法表示