运筹学作业习题

思考题

主要概念及内容：

线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式；可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基向量；基本解、基本可行解、可行基、最优基。 复习思考题：

1、线性规划问题的一般形式有何特征？

2、建立一个实际问题的数学模型一般要几步？

3、两个变量的线性规划问题的图解法的一般步骤是什么？

4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？

5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它们之间的相互关系。

7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。

8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？

9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？

10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业习题

1、将下列线性规划问题化为标准型

maxz3x15x24x32x4minf3x1x24x32x42x16x2x33x4182x13x2x32x451（1）x13x22x32x413 （2）3x12x22x3x47

x4x3x5x923412x14x23x32x415x1,x2,x40x1,x20,x402、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）：

2x13x23x362x13x24x312 x,x,x0123（2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解.

maxz3x1x22x312x13x26x33x498xx4x2x10 12353x1x60xj0(j1,,6)3、用图解法求解下列线性规划问题

maxzx12x22x1x264x17x256（1） （2） 3x2x12123x5x1512x31x,x012x,x012

4、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。 maxzx12x2x3minzx13x2x1x22x36x14x2x34x,x,x0123

5、用单纯形法求解以下线性规划问题

maxz3x12x2maxzx22x3x13x24x3122x13x23（1） （2）

xx52xx121232x,x0x,x,x0121236、用大M法及两阶段法求解以下线性规划问题

maxzx13x24x3minfx13x2x33x12x213x1x2x33（1） （2） x23x317x12x222xxx13312x15x2x34x1,x2,x30x1,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零件各三件。问应如何安排使总的费用最小。试建立线性规划模型。

9、某造船厂根据合同从当年起连续三年末各提供四条规格相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮成本如下表所示：

已知加班生产时,每艘客货轮成本比较正常时高出60万元；又知造出来的客货轮若当年不交货,每艘每年积压一年造成损失为30万元。在签定合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年未完成合同还能储存一艘备用。问该厂如何安排每年

客货轮的生产量，在满足上述各项要求的情况下总的生产费用最少？试建立线性规划模型，不求解。

线性规划问题的对偶及灵敏度分析

思考题

主要概念及内容：

对偶问题，对称形式、非对称形式；对偶定理；对偶单纯形法；灵敏度分析。 复习思考题：

1、对偶问题和它的经济意义是什么？

2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？

4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？

5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？

6、在线性规划的最优单纯形表中，松弛变量（或剩余变量） ，其经济意义是什么？ 7、在线性规划的最优单纯形表中，松弛变量 的检验数 ，其经济意义是什么？

8、关于价值系数和资源常量 单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？ 9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？ 10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？ 作业习题

1、写出下列问题的对偶规划

2、试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解

3、考虑如下线性规划

（1）写出对偶规划。

（2）用单纯形法解对偶规划，并在最优表中给出原规划的最优解。 （3）说明这样做比直接求解原规划的好处。

4、用对偶单纯形方法，求解下面问题

minf5x12x24x33x1x22x34（1）6x13x25x310x,x,x01235、考虑下面线性规划

maxz2x13x22x12x2x312x2xx8124 4xx16154xx1262x1,x2,x3,x4,x5,x60maxzx12x23x32x1x2x34 （2）x1x22x38x2x32x1,x2,x30

其最优单纯形表为： 基变量 x1 x2 x3 x4 x5 x6 x3 0 4 4 2 -14 x1 x6 x2 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 0 0 -3/2 -1/8 0 0 0 0 -3/2 -1/8 0 j

试分析如下问题

（1）分别对cj 进行灵敏度分析。 （2）对bi 进行灵敏度分析。 （3）当cj=时，求新最优解。 （4）当bi= 时，求新最优解。

（5）增加一个约束 ，问对最优解有何影响？ （6）确定保持当前最优解不变的P1的范围。

6、已知某工厂计划生产A1 、A2 、A3三种产品，各产品需要在甲、乙、丙设备上加工。有关数据如下

试问：

（1）如何充分发挥设备能力，使工厂获利最大；

（2）若为了增加产量，可借用别的工厂的设备甲，每月可借用60台时，租金1.8万元，问是否合算？

（3）若另有两种新产品A4、A5 ，其中每件A4 需用设备甲12台时、乙5台时、丙10台时，每件获利2.1千元；每件A5需用设备甲4台时、乙4台时、丙12台时，每件获利1.87千元。如 甲、乙 、丙 设备台时不增加，分别回答这两种新产品投产是否合算？ （4）增加设备乙的台时是否可使企业总利润进一步增加？ 7、已知某求极大化线性规划问题用单纯形法求解时的初始单纯形表及最终单纯形表如下表所示，求表中各括弧内未知数的值。 Cj 3 2 2 0 0 0 b x1 x2 x3 x4 x5 x6 XB CB x4 x5 x6 1 1 1 1 0 0 (B) (A) 1 2 0 1 0 15 2 (C) 1 0 0 1 20 3 2 2 0 0 0 j x4 x1 x2 j 0 0 (D) (L) -1/4 -1/4 5/4 1 0 (E) 0 3/4 (I)0 25/4 0 1 (F) 0 (H) 1/2 5/2 0 (K) (G) 0 -5/4 (J) 运输问题

思考题

主要概念及内容：

运输问题、运输表、产销平衡；基本可行解；闭回路；位势；检验数；虚设产地（销地）；运输问题建模。

复习思考题：

1、运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等于 ？ 2、用西北角法确定运输问题的初始基本可行解的基本步骤是什么？

3、最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？ 4、试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？ 5、用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？

6、试述用位势法求检验数的原理、步骤和方法。

7、试给出运输问题的对偶问题（对产销平衡问题）。

8、如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。 9、一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？ 作业习题

1、 某公司生产某种产品有三个产地A1、A2、A3 ，要把产品运送到四个销售点B1、B2、B3、B4 去销售。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。

产品运输数据表 销地 B1 B2 B3 B4 产量（吨） 产地 A1 5 11 8 6 750 A2 10 19 7 10 210 A3 9 14 13 15 600 销量（吨） 350 420 530 260 1560（产销平衡）

问应如何调运，可使得总运输费最小?

(1)、分别用西北角法和最小元素法求初始基本可行解；

(2)、在上面最小元素法求得的初始基本可行解基础上，用两种方法求出非基变量的检验数； (3)、进一步求解这个问题。

2、用表上作业法求解下列运输问题: （1）运输问题数据表 销地 B1 B2 B3 B4 产量 产地 A1 8 4 7 2 90 A2 5 8 3 5 100 A3 7 7 2 9 120 销量 70 50 110 80

（2）运输问题数据表 销地 B1 B2 B3 B4 B5 产量 产地 A1 8 6 3 7 5 20 A2 5 — 8 4 7 30 A3 6 3 9 6 8 30 销量 25 25 20 10 20

3、某厂考虑安排某件产品在今后 4 个月的生产计划，已知各月工厂的情况如下表所示

试建立运输问题模型，求使总成本最少的生产计划。

选择题

1．当利用单纯形法计算某个线性规划问题时，若最终表人工变量不为零，则可以断言该性线规划问题（ A ）。

A．无可行解 B．有无界解 C．有多重解 D．唯一解

2．当利用对偶单纯形法计算某个目标函数极大化线性规划问题时，若右侧常数bi0，对应的aij0，则可以断言该性线规划问题（ A ）。

A．无可行解 B．有无界解 C．有多重解 D．唯一解

3．当利用单纯形法计算某个极大化线性规划问题时，若最终表非基变量检验数j0，且至少有一个为零，则可以断言该性线规划问题（ C ）。

A．无可行解 B．有无界解 C．有多重解 D．唯一解

4．当利用单纯形法计算某个目标函数极大化线性规划问题时，若有非基变量的检验数j>0，且对应

a0的系数列向量ij，则可以断言该性线规划问题（ B ）。 A．无可行解 B．有无界解 C．有多重解 D．唯一解

5．用单纯形法求解目标函数最大化的线性规划问题时，只有（ A ）对应的非基变量xj可以被选作为换入变量。

A．检验数j >0 B．检验数j <0 C．检验数j >0中的最大者 D．检验数j <0中的最小者 6．线性规划问题若有最优解，则一定可以在可行域的 （ C ）上达到。 A．内点 B．外点 C．顶点 D．几何点

7．线性规划问题用“管理运筹学”软件求解时，当决策变量的“最优解”为正数时，“相差值”必为（ B ）。

A．正数 B．零 C．不等于零 D．不确定 8．线性规划的标准型有特点（ D ）。

A．右端项非零 B．目标求最大或最小 C．有等式或不等式约束 D．变量均非负

9．线性规划标准型中

bi（i=1，2，……m）必须是（ B ）。

A．正数 B．非负数 C．无约束 D．非零的

10．线性规划一般模型中，自由变量可以用两个非负变量的（ B ）代换。 A．和 B．差 C．积 D．商

11．线性规划问题（ D ）是由于约束条件自相矛盾导致的建模错误。

A．存在唯一最优解的情况 B．存在无穷多最优解的情况 C．存在无界解的情况 D．无可行解的情况 12．原问题与对偶问题的最优（ B ）相同。 A．解 B．目标值 C． 解结构 D．解的分量个数

13．若原问题中xi为自由变量，那么对偶问题中的第i个约束一定为 （ A ） A．等式约束 B．“≤”型约束 C．“≥”约束 D．无法确定 14．已知

yi*为线性规划的对偶问题的最优解,若

yi*>0,说明在最优生产计划中（ A ）。

A．第i种资源已完全耗尽 B．第i种资源有剩余 C．生产第i种产品 D．不生产第i种产品 15．极大化的线性规划问题的可行解无界，则对偶规划（ D ）。

A．唯一最优解 B．有限最优解 C．无穷多最优解 D．无可行解 E．无界解

16．其他条件相同的情况下，允许缺货的经济订货批量模型的总费用（ C ）不允许缺货的经济订货批量模型的总费用。

A．大于 B．等于 C．小于 D．不确定 17．订货费与（ C ）有关。

A．订货批量数量 B．货物单价 C．订货次数 D．以上都是 18．以下目标规划中的目标函数，在逻辑上不合理的是（ ）。 A．max{d-+d+} B．max{d-—d+} C．min{d-+d+} D．min{d-—d+} 19．运输问题的基本可行解有特点（ D ）。

A．产销平衡 B．形成闭回路 C．有m+n个位势 D．有m＋n－1个基变量

x20．若是否采用j项目的0-1变量为j,那么J个项目中至多只能选择一个项目的约束方程为（ C ）。 A．jJxj1 B．jJxj1 C．jJxj1 D．无法表示