运筹学作业习题

1、线性规划建模及单纯形法思考题主要概念及内容：线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式； 可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基 向量；基本解、基本可行解、可行基、最优基。复习思考题：1、线性规划问题的一般形式有何特征？2、建立一个实际问题的数学模型一般要几步？3、两个变量的线性规划问题的图解法的一般步骤是什么？4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概

2、念及 它们之间的相互关系。7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多 个最优解、无界解或无可行解。8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？9、大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？作业习题1、将下列线性规划问题化为标准型max z = 3xi max z = 3xi 5x2 -4x3 2x42xi 6x2 - x3 3x4 0, x4 M 02、（1）求出下列不等式组所定义的多面体的所有基

3、本解和基本可行解（极点）：2xi +3x2 +3x3 6一2xi +3x2 +4x3 i2xi, x2,x3 之0（2）对下述线性规划问题找出所有基本解，指出哪些是基本可行解，并确定最优解.maxz = 3xi x2 2x3 i2xi +3x2 +6x3 +3x4 =9 8xix2 - 4x3 2x5 = i03xi x6 = 0 xj 20(ji,K K ,6)3、用图解法求解下列线性规划问题max z = xi 2x22xi -x2 工6(1) max z = xi 2x22xi -x2 工6(1) 3xi 2x2 12xi 0min z - xi 3x24xi 7x2 _ 563x1 一

4、 5x2 _ i5xi,x2 04、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解 max z = xi 2x2 一 x3xi x2 2x3 _ 6xi 4x2 -x3 - 4xi, x2,x3 , 05、用单纯形法求解以下线性规划问题max z = 3xi 2m2xi - 3x2 0maxz = x2 - 2x3xi 3m 4x3 = i2 2x2 -x3 06、用大M法及两阶段法求解以下线性规划问题max z = xi 3x2 4x3min f = xi 3x2 - 贝3xi 2x2 i3(1) x2 3x3 i72xi x2 x3 = i3xi, x2, x3 - 0

5、 xi x2 x3 - 3-xi 2x2-2-xi +5x2 +治 4xi,x2 ,x3 之 07、某工厂生产过程中需要长度为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零件各三件。问应如何安排使 总的费用最小。试建立线性规划模型。在两种设备上分别加工T零件的费用阮）设备零件1234A5030

6、9040B3010050709、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该 厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示：造船厂三年内生产大型客货轮的a约及每艘客货轮成本年度正常生产时间内可完成加胜产时间内可完成的客货轮数的客货轮数正常生产时每a婀本 （万元）133500252600323500已知加班生产时，每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年 不交货，每艘每年积压一年造成损失为30万元。在签定合同时，该厂已积压了两艘未交 货的客货轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年客货轮的生产量，在满足上述

7、各项要求的情况下总的生产费用最少？试建立线性规划模 型，不求解。线性规划问题的对偶及灵敏度分析思考题主要概念及内容：对偶问题，对称形式、非对称形式；对偶定理；对偶单纯形法；灵敏度分析。复习思考题：1、对偶问题和它的经济意义是什么？2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数 之间的关系？5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？6、在线性规划的最优单纯形表中，松弛变量(或剩余变量)，其经济意义是什么？7、在线性规划的最优单

8、纯形表中，松弛变量的检验数，其经济意义是什么？8、关于价值系数和资源常量单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？ 如何去处理？10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响? 如何去处理？作业习题1、写出下列问题的对偶规划maxZ = -3xj + 5x2 一七+ 2五M 5 工+ 3电4 2 工1，町20max E =再+ 2马一号药+ w玉 一/+万maxZ = -3xj + 5x2 一七+ 2五M 5 工+ 3电4 2 工1，町2

9、012 Xj - 9x3 + 7x3 + 6 0(2)mm f =-+ 2 电 + % 2访一句十石之一4$ + 2电=。勺，时， 03、考虑如下线性规划min /=/% + 芍 + 工4丐+为勺4与J丐+为勺4与Ja十个Of587勺个，q 0(1)写出对偶规划。(2)用单纯形法解对偶规划，并在最优表中给出原规划的最优解。(3)说明这样做比直接求解原规划的好处。4、用对偶单纯形方法，求解下面问题min f = min f = 5xi 2x2 4x33xi，X2，2x3 _ 4)6xi 3x2 5x3 ,10 xi,x2,x3 _05、考虑下面线性规划maxz - -xi - 2x2 - 3x3

10、2xi - x2 x3 _ 4(2) xi x2 2x3 0max z = 2xi 3m2xi +2x2 +x3 =i2x i2x + x =8l| 2 44x x5 =i64x2 +x6 =i2Xi, x2,x3,x4,x5,x6 0其最优单纯形表为：基变量xix2x3x4x5x6x3001-1-1/400 xi10001/404x6000-21/214x2000-3/2-1/802Tj000-3/2-1/80-14试分析如下问题(1)分别对Cj进行灵敏度分析。(2)对bi进行灵敏度分析。(3)当3=时，求新最优解。(4)当b =时，求新最优解。(5)增加一个约束，问对最优解有何影响？(6)

11、确定保持当前最优解不变的P1的范围。6、已知某工厂计划生产Ai、A2、A3三种产品，各产品需要在甲、乙、丙设备上加工 有关数据如下备 j4A也工MB艮书上每月)甲8161Q304乙105400丙21310420单位产品矛件闰(千兀:)322.?试问：(1)如何充分发挥设备能力，使工厂获利最大；(2)若为了增加产量，可借用别白工厂的设备甲，每月可借用60台时，租金1.8万元， 问是否合算？(3)若另有两种新产品A4、A ,其中每件A4需用设备甲12台时、乙5台时、丙10台时，每件获利2.1千元；每件A5需用设备甲4台时、乙4台时、丙12台时，每件获利1.87千元。如甲、乙、丙 设备台时不增加，分

12、别回答这两种新产品投产是否合算？(4)增加设备乙的台时是否可使企业总利润进一步增加？7、已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如 下表所小，求表中各括弧内未知数的值。Cj322000bXbCbXiX2X3X4X5X6X4111100(B)X5(A)1201015X62(C)1001203322000MMMX400(D)(L)-1/4-1/45/4Xi10(E)03/4(I)025/4X201(F)0(H)1/25/260(K)(G)0-5/4(J)运输问题思考题主要概念及内容：运输问题、运输表、产销平衡；基本可行解；闭回路；位势；检验数；虚设产地（销地）；运输问

13、题 建模。复习思考题：1、运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于？2、用西北角法确定运输问题的初始基本可行解的基本步骤是什么？3、最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？4、试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？5、用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯 一的？6、试述用位势法求检验数的原理、步骤和方法。7、试给出运输问题的对偶问题（对产销平衡问题）。8、如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。9、一

14、般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？作业习题1、某公司生产某种产品有三个产地A1、A2、A3 ,要把产品运送到四个销售点B1、B2、B3、B4 去销售。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。产品运输数据表B1B2B3B4产量（吨）A151186750A21019710210A3914r 1315600销量（吨）3504205302601560（产销平衡）问应如何调运，可使得总运输费最小？（1）、分别用西北角法和最小元素法求初始基本可行解；（2）、在上面最小元素法求得的初始基本可行解基础上，用两种方法求出非基变量的检验数;（3）、进

15、一步求解这个问题。2、用表上作业法求解下列运输问题：（1）运输问题数据表地B1B2B3B4）里Ai847290A25835100A377r 29120销量705011080Ai8637520A25一84730A36396830销量2525二2010203、某厂考虑安排某件产品在今后4个月的生产计划，已知各月工厂的情况如下表所示- 计划月项目一_一第一月第二月第二月第四月单件生产成本10121416每月需求量40080098600正常生产自匕700700700700加班能力02002000加班单件成本15171921库存费用3333试建立运输问题模型，求使总成本最少的生产计划。选择题.当利用单纯

16、形法计算某个线性规划问题时，若最终表人工变量不为零，则可以断言该性线规划问题（ A ）。A.无可彳T解B.有无界解 C.有多重解 D.唯一解.当利用对偶单纯形法计算某个目标函数极大化线性规划问题时，若右侧常数bi 0,则可以断言该性线规划问题（A ）。A.无可彳T解B.有无界解 C.有多重解 D.唯一解.当利用单纯形法计算某个极大化线性规划问题时，若最终表非基变量检验数仃jW0,且至少有一个为零，则可以断言该性线规划问题（C ）。A.无可彳T解B.有无界解 C.有多重解 D.唯一解.当利用单纯形法计算某个目标函数极大化线性规划问题时，若有非基变量的检验数一0,且对应 的系数列向量aij -0,

17、则可以断言该性线规划问题（B ）。A.无可彳T解B.有无界解 C.有多重解 D.唯一解5,用单纯形法求解目标函数最大化的线性规划问题时，只有（ A ）对应的非基变量xj可以被选作为换入变量。A.检当金数0 B.检当金数0中的最大者 D.检当金数仃j 0,说明在最优生产计划中（A ）。A.第i种资源已完全耗尽B.第i种资源有剩余C.生产第i种产品 D.不生产第i种产品.极大化的线性规划问题的可行解无界，则对偶规划（D ）。A.唯一最优解 B.有限最优解 C.无穷多最优解D.无可彳T解E.无界解.其他条件相同的情况下，允许缺货的经济订货批量模型的总费用（C ）不允许缺货的经济订货 批量模型的总费用。A.大于