运筹学复习题

第一章 线性规划及单纯形法

一、复习思考题

1 试述线性规划数学模型的结构及各要素的特征。 2 线性规划的解有哪几种情况。

3 什么是线性规划问题的标准形式，如何将一个非标准型的线性规划问题转化为标

准形式。

4 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。 5 试述单纯形法的计算步骤，如何在单纯形表上去判别问题是具有惟一最优解、无穷多最优

解、无界解或无可行解。

6 如果线性规划的标准型式变换为求目标函数的极小化min z，则用单纯形法计算时如何判

别问题已得到最优解。

7 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中人工变量

前的系数为(一M)的经济意义是什么。

8 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶

段的计算结果来判定第二阶段的计算是否需继续进行。 9 简述退化的含义及处理退化的勃兰特规则。

10 举例说明生产和生活中应用线性规划的方面，并对如何应用进行必要描述。

二、判断下列说法是否正确

1、 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；

2、 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；

3、线性规划问题的每一个基解对应可行域的一个顶点.

4、如线性规划问题有最优解，则最优解一定对应可行域边界上的一个点； 5、用单纯形法求解标准型式的线性规划问题时，与

?j＞0对应的变量都可被选作换入变量；

6、单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长；

7、线性规划问题任一可行解都可以用全部基可行解的线性组合表示；

mCn9、对一个有n个变量，m个约束的标准型的线性规划问题，其可行域的顶点恰好为

个；

10、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解；

11、若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限

个数的最优解；

12、线形规划可行域的某一项点若其目标函数值优于所有顶点的目标函数值，则该顶点处的目标函数值达到最优。

三、计算题

1、分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形法迭代中的基本可行解跟图解法可行域中哪一顶点相对应。

maxz?10x1?5x2?3x1?4x2?9??5x1?2x2?8?x?0,x?02（1）?1

maxz?2x1?x2?5x2?15?6x?2x?24?12??x1?x2?5?（2）?x1?0,x2?0

2、用单纯形法求解下列线性规划问题

(1)maxz?2x1?2x2?x1?x2??1???0.5x1?x2?2?x?0,x?02s.t.?1(2)maxz?x1?2x2??x1?x2?1??x1?x2?2?x?0,x?02 s.t.?1

(3)maxz?5x1?3x2?2x3?4x4?5x1?x2?x3?8x4?10??2x1?4x2?3x3?2x4?10?x?0,x?0,x?0,x?0234s.t.?1(4)minz?2x1?3x2?x3?x1?4x2?2x3?8??3x1?2x2?6?x?0,x?0,x?023 s.t.?1

(5)minz?2x1?x2?x3?x4?x1?x2?2x3?x4?2?2x?x?3x?x?6?1234??x1?x2?x3?x4?7?s.t.?x1?0,x2?0,x3?0,x4?0 s.t.

(6)maxz?10x1?15x2?12x3?5x1?3x2?x3?9??5x?6x?15x?15?123??2x1?x2?x3?15??x1?0,x2?0,x3?0

3、 某一求目标函数极大值的线性规划问题,用单纯形法求解时得到某一步的单纯形如表所示: cBi xBi x2 x3 x5 x1 0 2 a3 a5 x2 1 0 0 0 x3 0 1 0 0 x4 0 a4 -4 a6 x5 0 0 1 0 x6 a1 -2 3 6 bi a2 4 10 bi/aik 表中xj 均为非人工变量,为使下列说法正确, 试确定参数a1,a2,a3,a4,a5,a6的范围. (1)现行解为唯一最优解．

(2)现行解为最优，但有多重最优解． (3)现行解为退化基本最优解．

(4)该线性规划问题有可行解，但目标函数无界． (5)该线性规划问题无可行解．

4 、某厂生产甲、乙两种产品，已知生产一吨甲产品需用资源A：3 吨，资源 B：4 m3 ；生产一吨乙产品需用资源A：2 吨，资源 B：6 m3，资源C：7个单位。若一吨甲和乙的经

，

济价值分别为7万元和5万元，A、B、C三种资源的限制量分别为90吨、200 m3和210个单位，试决定应生产这两种产品各多少吨才能使创造的总经济价值最高？

5、制造某机床需要A、B、C 三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果制造100台机车，问最少要用多少根圆钢？试建立该问题的线性规划模型，并写出其对偶规划。 轴件 A B C 6、试用单纯形法求解下列线性规划问题

2、某工厂生产A、B、C三种产品，现根据订货合同以及生产状况制定生产计划。

已知甲合同为：A产品1000件，单价600元，违约金为120元/件；

B产品700件，单价500元，违约金为100元/件。

乙合同为：B产品900件，单价550元，违约金为110元/件；

C产品800件，单价450元，违约金为90元/件。

有关各产品生产过程所需工时以及原材料的情况见下表。试以利润最大为目标，建立该工厂的生产计划线性规划模型（不求解）。

规格：长度（米） 2.9 2.1 1.5 每台机床所需轴件数量 1 1 1 工序1 （工时） 工序2 （工时） 5 4 3 8000 16 原材料1 原材料2 其他成本 （元/件） 产品A 产品B 产品C 总工时、总原材料 单位工时和单位原3 2 1 6000 15 7 6 5 9000 17 9 8 7 12000 18 12 13 14 材料成本（元）

第二章 线性规划的对偶理论和灵敏度分析

一 复习思考题

1．试从经济上解释对偶问题及对偶变量的含义。

2．根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。

3．什么是资源的影子价格，同相应的市场价格之间有何区别，以及研究影子价格的意义。

二、判断下列说法是否正确

1、任何线性规划问题存在并具有惟一的对偶问题； 2、对偶问题的对偶问题一定是原问题。

三、决算题

1、 写出下列线性规划的对偶规划

（1）min a =2x1+2x2+4x3 （2）max z =2x1+3x2+6x3+x4

?2x1?3x2?5x2?2?3x1?4x2?4x3?7x4?21?3x?x?7x?3?2x?7x?3x?8x?18?1?123234???x1?4x2?6x3?5?x1?2x2?5x3?3x4?4?x?0,x3?0?s.t.?2 s.t.?x1?0,x2?0,x4?0

2、某厂拟生产甲、乙、丙三种产品，都需要在A，B两种设备上加工，有关数据如下表所示：

产品 设备 A B 产值（千元/件） 单耗（台时/件） 甲 乙 丙 1 2 1 2 1 2 3 2 1 设备有效台时 （每月） 400 500 （1）如何充分发挥设备能力，使产品总产值最大？ （2）若为了提高质量，以每台时350元租金租外厂A设备，问是否合算？

第三章 运输问题

一、 复习思考题

1．试述运输问题数学模型的特征，为什么模型的(m+n)个约束中最多只有(m+n-1)个是独立的。

2．写出运输问题数学模型的约束条件的系数矩阵和其中变量 xij的系数列向量pij的表达式。

3．试述用最小元素法确定运输问题的初始基可行解的基本思路和基本步骤。 4．为什么用沃格尔法给出的运输问题的初始基可行解，较之用最小元素法给出的更接近于最优解。

5．试述用闭回路法计算检验数的原理和经济意义，如何从任一空格出发去寻找一条闭回路。

6，概述用位势法求检验数的原理和步骤。

7．试述表上作业法计算中出现退化的涵义及处理退化的方法。

8．如何把一个产销不平衡的运输问题(含产大于销和销大于产)转化为产销平衡的运输问

题。

9．一般线性规划问题应具备什么特征才可以转化并列出运输问题的数学模型，并从用表上作业法求解。

二、判断下列说法是否正确：

(a)运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一： 有惟一最优解，有无穷多最优解，无界解，无可行解；

三、计算题

1、对于以下运输问题

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库运筹学复习题在线全文阅读。