运筹学最短路问题选择题

运筹学论文

——旅游路线最短问题

摘要：

随着社会的发展，人民的生活水平的提高，旅游逐渐成为一种时尚，越来越多的人喜欢旅游。而如何才能最经济的旅游也成为人民考虑的一项重要环节，是选择旅游时间最短，旅游花费最少还是旅游路线最短等问题随之出现，如何决策成为一道难题。然而，如果运用运筹学方法来解决这一系列的问题，那么这些问题就能迎刃而解。本文以旅游路线最短问题为列，给出问题的解法，确定最短路线，实现优化问题。

关键词：最短路 0-1规划 约束条件

提出问题:

从重庆乘飞机到北京、杭州、桂林、哈尔滨、昆明五个城市做旅游，每个城市去且仅去一次，再回到重庆，问如何安排旅游线路，使总旅程最短。 各城市之间的航线距离如下表： 重庆 北京 杭州 桂林 哈尔滨 昆明

问题分析：

1．

这是一个求路线最短的问题，题目给出了两两城市之间的距离，而在最短路线中,这些城市有的两个城市是直接相连接的（即紧接着先后到达的关系），有些城市之间就可能没有这种关系，所以给出的两两城市距离中有些在最后的最短路线距离计算中使用到了，有些则没有用。这是一个0-1规划的问题，也是一个线性规划的问题。

2．

由于每个城市去且仅去一次，最终肯定是形成一个圈的结构，这就重庆

一、线性规划

1.线性规划具有无界解是指 \

A.可行解集合无界 B.有相同的最小比值

C.存在某个检验数

D.最优表中所有非基变量的检验数非零

2.线性规划具有唯一最优解是指 \

A.最优表中非基变量检验数全部非零 B.不加入人工变量就可进行单纯形法计算 C.最优表中存在非基变量的检验数为零 D.可行解集合有界 3.线性规划具有多重最优解是指 \

A.目标函数系数与某约束系数对应成比例 B.最优表中存在非基变量的检验数为零 C.可行解集合无界 D.基变量全部大于零 4.使函数

减少得最快的方向是 \

A.(－1,1,2) B.(1,－1,－2) C. (1,1,2) D.(－1,－1,－2) 5.当线性规划的可行解集合非空时一定 \

A.包含点X=(0,0,···,0) B.有界 C.无界 D.是凸集 6.线性规划的退化基可行解是指 \

A.基可行解中存在为零的非基变量 B.基可行解中存在为零的基变量 C.非基变量的

第一章 线性规划及单纯形法 一、判断下列说法是否正确

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

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

（3）线性规划问题的每一个基解对应可行域的一个顶点；F

（4）如线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；T （5）对取值无约束的变量 ，通常令 ，其中 ，在用单纯形法得的最优解中有可能同时出现 ；F

（6）用单纯形法求解标准型式的线性规划问题时，与 对应的变量都可以被选作换入变量；T

（7）单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；T

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

（9）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；T

（10）线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；T

（11）若 分别是某一线性规划问题的最优解，则 也是该线性规划问题的最优解，其中 为正的实数；F

（12）线性规划用两阶段法求解时，

运筹学最短路概念网络模型的应用

摘要： 运筹学在不同领域中的应用非常广泛，应急物流的调度问题在现实生活

中很受关注，尤其是在考虑时间、成本、显示路况等前提下解决网络规划模型优化的方法上极其重要。论文重点针对应急物资配送网络应急调度突发情形建立基于图论的最短路概念模型，将其分别抽象为最短路问题的三种具体情形：1．弧上权值的改变(变大或变小)的情形；2．去掉网络中的一条弧的情形；3．在网络中添加一条弧的情形，进而运用具有约束条件的最短路问题分析方法进行了理论分析。在此基础上解决了应急物流过程的调度和时间问题，以达到模型优化的目的，为应急物资调用问题提供有效方法。

关键词：应急配送，网络最短路，优化模型 1.1应急物资配送路线的选择指标集

在应急物资配送方面所面临的决策即是应急物资配送线路的选择，评价应急物资网络各

配送路线的指标集可分为个体表现评价指标集和协同表现评价指标集，前者包括时间效益、运输成本、线路状况等，后者包括运输总成本、柔性水平等。[1]

1.个体表现评价指标 ①时间效益

运输线路的选择要以保证时间效益为前提，及时为灾害发生地提供应急物资 保障。因此，在进行运输线路选择时必须将时间效益最大化放在第一位。

运筹学基础-阶段测评1

1.1 适宜使用专家小组法的预测是( a)

a 短期定性预测 b 长期或中期定量预测 c 短期定量预测 d 长期或中期定性预测

专家小组法为定性预测，并且节奏比较紧凑，适合短期预测。

1.2 对国民生产总值增长率的预测属于(b ) a 微观经济预测 b宏观经济预测 c 科技预测 d 社会预测

国民收入、国民生产总值等大的方面属于宏观经济预测。

1.3 下述预测方法中，属于定性方法的是(b ) a 算术平均数预测法 b 特尔斐法

c 线性回归预测法 d 指数平滑法 特尔斐法与专家小组法为定性，其余为定量。 1.4 问题域的内部环境一般是指( d)

a 问题域界面与外界的人、财、物之间的交互活动 b 问题域外界的人、财、物之间的交互活动

c 问题域界面与问题域内部的人、财、物之间的交互活动 d 问题域内部的人、财、物之间的交互活动。

内部环境指内部的交互活动，外部环境指问题域界面与外界的交互活动，两者有区别。

1.5 不属于时间序列组成形式的是(b ) a 季节性波动 b 偶然性波动 c随机波动 d 长期趋势

时间序列大致可分为：长期趋势、季节性波动、周期性波动和随机波动。 1.6 下列说法

最短路问题最短(通)路问题是最重要 的优化问题之一，例如各种管道 的铺设、线路的安排、厂区的布 局、设备的更新及运输网络的最 小费用流等。(最短距离、费时 最少、费用最省)

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

2

1

3

2

5

20 1 8

6

5 1 2 9

3 6 4 6

9

72

9

7 7 1

11 1

13

3 1

4 10

9

一般的最短路问题描述：给定一个赋权有向图D=(V,A),对每一个弧a=(vi,vj),相应 地有权w(a)=wij,又给定D中的任何两个顶点vs和vt ,设P是 从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P), 最短路问题就是要在所有从vs到vt的路中，求一条权最小的路， 即一条从vs到vt的路P0使得：

(P0 ) min (P)P

路P0的权称为从vs到vt的距离，记为d(vs,vt)。

求网络上的一点到其它点 的最短路 Dinkstra标号法

这是解决网络中某一点到其它点的最 短路问题时目前认为的最好方法。 适用于有向图权值非负的情况

有向图权值非负---- Dijkstra算法

Dijkstra算法的基本步骤(权值非负) 1、给顶点v1标号(0),v1称为已

运筹学教程

运筹学Operations Research Chapter 2 对偶问题Dual Problem

1. 线性规划的对偶模型 Dual Model of LP 2.对偶性质 对偶性质 3.对偶单纯形法 对偶单纯形法 4.灵敏度分析 灵敏度分析 Dual property Dual Simplex Method Sensitivity Analysis

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Problem2010年11月26日星期五 Page 2 of 19

在线性规划问题中，存在一个有趣的问题，即每一个线性规 划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。

【例2.1】 某企业用四种资源生产三种产品，工艺系数、 例 资源限量及价值系数如下表：产品 资源 Ⅰ Ⅱ Ⅲ Ⅳ 每件产品利润 9 5 8 7 100 8 4 3 6 80 6 7 2 4 70 500 450 300 550 A B C 资源限量

建立总收益最大的数学模型。

运筹学教程

§2.1线性规划的对偶模型 线性规划的对偶模型 Dual model of LP

Ch2 Dual Prob

最短路径问题作图练习

1.已知：P、Q是△ABC的边AB、 AC上的点，你能在BC上确定一点R，使△PQR的周长最短吗？ 作法：

2.已知P是△ABC的边BC上的点，你能在AB、AC上分别确定一点Q和R，使△PQR的周长最短吗？ 作法：

3. 如图，直角坐标系中有两点A、B,在坐标轴上找两点C、D,使得四边形ABCD的周长最小。

.A . B 作法：

4. 如图，OMCN是矩形的台球桌面，有黑、白两球分别位于B、A两点的位置上，试问怎样撞击白球，使白球A依次碰撞球台边OM、ON后，反弹击中黑球？

作法：

CM

AB N O

5. 如图，A、B是直线a同侧的两定点，定长线段PQ在a上平行移动，问PQ移动到什么位置时，

AP+PQ+QB的长最短？

作业：

6.．．

.已知：A、B两点在直线l的同侧，试分别画出符合条件的点M． （1）如图1，在l上求作一点M，使得｜ AM－BM ｜最小； 作法：

图1

（2）如图2，在l上求作一点M，使得｜AM－BM｜最大； 作法：

图2

运筹学(专升本)阶段性作业4 总分: 100分 考试时间:分钟 判断题

1. 存储由于需求而不断减少，所以在一定的时候必须进货，也即对存储进行补充。(5分) 正确错误 参考答案：正确 解题思路：

2. 存储系统是一个由订货、存储、需求三个环节紧密构成的现实运行系统。(5分) 正确错误 参考答案：正确 解题思路：

3. 按性质分类，可将决策分为程序化决策和非程序化决策。(5分) 正确错误 参考答案：错误 解题思路：

4. 运筹学的目的在于针对所研究的系统求得一个合理应用人才，物力和财力的最佳方案。(5分) 正确错误 参考答案：正确 解题思路：

5. 运筹学的主要研究对象是各种有组织系统的管理问题及生产经营活动。(5分) 正确错误 参考答案：正确 解题思路：

6. 风险型决策问题是指决策者对某一自然因素发生的概率是未知的。(5分) 正确错误 参考答案：错误 解题思路：

7. 在风险型决策问题中，如果自然因素出现的概率为0，而其他自然因素出现的概率为1，即为确定性决策问题。(5分) 正确错误 参考答案：错误 解题思路：

8. 对于同一个目标，虽然决策者“选优”原则不同，但所选的最优方案相同。(5分)

正确错误 参考答案：错误 解题思路：

填空题

判断题√√×× 一、 线性规划

1.若线性规划存在最优解则一定存在基本最优解 √ (若存在唯一最优解，则最优解为最优基本可行解（一个角顶），若存在多重最优解（由多个角顶的凸组合来表示)

2.若线性规划为无界解则其可行域无界 √ （可行域封闭有界则必然存在最优解） 3.可行解一定是基本解 × （基本概念）

4.基本解可能是可行解 √ （基本概念）

5.线性规划的可行域无界则具有无界解 ×

（有可能最优解，若函数的梯度方向朝向封闭的方向，则有最优解） 6.最优解不一定是基本最优解 √

（在多重最优解里，最优解也可以是基本最优解的凸组合）

7.xj 的检验数表示变量 xj 增加一个单位时目标函数值的改变量 √ （检验数的含义，检验函数的变化率）

8.可行解集有界非空时,则在极点上至少有一点达到最优值 √

（可行解集有界非空时，有可行解，有最优解，则至少有一个基本最优解）

9.若线性规划有三个基本最优解X(1)、X(2)、X(3)，则X=αX(1)+(1-α)X(3)及X=α1X(1)+α2X(2)+α3X(3)均为最优解,其中