运筹学复习题

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

一、复习思考题

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、对于以下运输问题

供应量运价（元/吨） A1 A2 A3 需求量（吨）

求总运费最小的运输方案

2、 下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价， 试用表上作业法求最优调运方案。

销地 产地 1 2 销量 8 7 4 3 5 9 20 10 20 3、 用表上作业法求下列运输问题的最优解。

销地 产地 1 2 3 销量 5 1 8 2 4 0 3 6 7 9 10 11 4、下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价，试用表上作业法求最优调运方案。

销地 产地 A B C D 产量 12 14 4 A B C 产量 15 25 A B C 产量 B1 9 14 5 9 B2 12 7 13 12 B3 10 6 15 13 B4 （吨） 8 11 20 16 24 8 18 1 2 3 销量 9 3 8 7 4 9 4 5 5 7 6 2 1 3 2 5 11 3 3 5 5、下表给出了各产地和销地的产量和销量，并给出了各产地至各销地的单位运价，试用表上作业法求最优调运方案。

销地 产地 1 2 3 销量 4 1 4 6 1 2 5 0 3 7 5 1 6 5 6 3 20 8 8 4 A B C D 产量 第四章 整数规划

一 复习思考题

1．试述研究整数规划的意义，并分别举出一个纯整数规划、混合整数规划和0—1规划的例子。

2．有人提出，求解整数规划时可先不考虑变量的整数约束，而求解其相应的线性规划问题，然后对求解结果中为非整数的变量凑整。试问这种方法是否可行，为什么? 3．试述用分枝定界法求解问题的主要思想及主要步骤，并说明这种方法的优缺点。 5．除教材中列举的例子外，你认为引进0—1变量对建立实际问题的数学模型还有哪些作用，试举例说明。

6．什么是隐枚举法，为什么说分枝定界法也是一种隐枚举法

7..指派问题是0—1型整数规划的一类特殊例子，你能否设计一个用分枝定界法来求解指派问题的程序步骤。

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

1 、整数规划解的目标函数值一般优于其相应的线性规划问题的解的目标函数值； 2 、用分技定界法求解一个极大化的整数规划问题时，任何一个可行解的目标函数是该问题

目标函数值的下界；

3、 用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取

其中一个作为下界值，再进行比较剪枝；

三、计算题

1、 下表是4个小组各自完成各项不同工作所需的时间，试确定最优分派方案。

工作 甲 乙 丙 丁 小组 A 19 10 16 20 B 14 12 9 16 C 12 15 11 13 D 18 10 14 17 2、 6个人完成4项任务，由于个人的技术专长不同，他们完成4项任务所获得的收益如下

表所示，且规定每人只能做一项工作，一项工作任务只需一人操作，试求使总收益最大的分派方案。

工作 甲 乙 丙 丁 人 A 3 5 4 5 B 6 7 6 8 C 8 9 8 10 D 10 10 9 11 E 12 11 10 12 F 13 12 11 13 3、某公司要把4个有关能源工程项目承包给4个互不相关的承包者，规定每个承包商只能

且必须承包一个项目，试在总费用最小的条件下确定各个项目的承包者，总费用为多少？

各承包商对工程的报价如下表所示： 单位：万元

项目 1 2 3 4 投标者 甲 乙 丙 丁 15 19 26 19 18 23 17 21 21 22 16 23 24 18 19 17 4、个人完成五项任务，由于个人的技术专长不同，每人完成各项任务的时间如下表所示。

（1）若规定每人只能做一项工作，一项工作任务只需一人操作，试问这四个人应分派做哪四项工作，他们所花费的总时间最短。

（2） 如果规定四个人必须完成五项工作，其中有一个人可以兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的分派方案。

工作 人 甲 乙 丙 丁 25 39 34 24 29 38 27 42 31 26 28 36 42 20 40 23 37 33 32 45 A B C D E 5、某厂拟用5台机床加工5种零件，加工费（元）如下表所示。若每台机床加工一种零件，则应如何分配任务才能使总加工费最少？

零件 1 2 3 4 5 机床 1 2 3 4 5 解 6、五人翻译五种外文的速度（印刷符号/小时）如下表所示：

语种 英 人 甲 900 400 600 800 500 俄 日 德 法 4 1 8 4 2 9 8 4 7 7 8 4 6 6 3 6 5 7 6 2 5 5 4 3 1 乙 丙 丁 戊 800 900 400 1000 500 700 800 500 900 300 600 300 1000 500 900 600 600 800 500 800 若规定每人专门负责一个语种的翻译工作，那么，试解答下列问题： （1）应如何指派，使总的翻译效率最高？

（2）若甲不懂德文，乙不懂日文，其他数字不变，则应如何指派？

第五章 图与网络分析

一 复习思考题

1．通常用G(V，E)来表示一个图，试述符号V，E及这个表达式的涵义。

2．解释下列各组名词，并说明相互间的联系和区别：(a)端点，相邻，关联边；(b)环，多重边，简单图；(c)链，初等链；(d)圈，初等圈，简单圈；(e)回路，初等路；(f)节点的次，悬挂点，孤立点；(g)连通图，支撑子图；(h)有向图，赋权图。 3．图论中的图同一般工程图、几何图的主要区别是什么，试举例说明。

4．试述树图、图的支撑树及最小支撑树的概念定义，以及它们在实际问题中的应用。 5．阐明Dijkstra算法的基本思想和基本步骤，为什么用这种算法能在图中找出从一点至任一点的最短路。

6．最大流问题是一个特殊的线性规划问题，试具体说明这个问题中的变量、目标函数和约

束条件各是什么?

7．什么是增广链，为什么只有不存在增广链时，网络中的流即为最大流。 8．简述最小费用最大流的概念以及求取最小费用最大流的基本思想和方法。 9．试用图的语言来表达中国邮递员问题，并说明该问题同一笔画之间的联系和区别。

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

图论中的图不仅反映了研究对象之间的关系，而且是真实图形的写照，因而对图中点与点的相对位置、点与点连线的长短曲直等都要严格注意；

三、计算题

1、 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图所示，图中的v1,v2 ,v3 ,v4 ,v5 ,v6 ,v7表示7个学院办公室，图中的边为可能联通的途径，边上的数字表示这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。

本文来源：https://www.bwwdw.com/article/lwx.html