运筹学大作业(第五小组)

《高级运筹学》课程大作业

旅游线路的优化设计问题

小组成员：汪栋李一鸣黄舒婷房浩

同济大学电子与信息工程学院控制科学与工程

旅游线路的优化设计问题

汪栋李一鸣黄舒婷房浩

电子与信息工程学院，控制科学与工程

摘要：本文研究了旅游路线的选取在各种限制情形下的优化问题，通过上网搜索了各地之间直线距离及旅游路线、车次（航班）、门票等有关数据，得到了路程最短的旅游路线以及费用最少的出行方式。针对最短路径即旅行商问题（TSP），我们采用了四种方法（蚁群算法，模拟退火算法，遗传算法、动态规划方法），得到了如下的最短路径最优解：北京-呼和浩特-太原-延安-西安-洛阳-徐州-南京-日照-青岛-威海-济南-天津-沈阳-承德-北京。

关键词：最短路径MATLAB 非线性规划

1 研究内容

1.1 研究背景

旅游线路是指一定的区域内，为使游人能够以最短的时间获得最大的观赏效果，由交通线路把若干个旅游点或旅游城市合理的贯穿起来，并具有一定特色的路线。

旅游线路设计是旅游者应关注的问题。它是旅游者的行为决策，作为为旅游者设计的一种消费产品，是应旅游者的需求而产生并存在的。因此它不仅要符合旅游规律，而且还要考虑旅游者的情况。旅游线路是一种时间安排。同样的交通线路，倘若给予不同的时间安排，就可以被认为是不同的旅游线路。例如五一黄金周线路、十一黄金周线路、周末旅游线路等，均反映了出行时间的特征；一日游线路、两日游线路等则体现了旅游活动持续时间的特征。旅游线路的时间维度包含三个方面：旅游线路开始的时间、结束的时间(时间点)；作为节点的景区(点)的时间顺序(时间序列)；旅游线路持续的时间(时间段)。1.2 提出问题

旅游活动正在成为全球经济发展的重要动力之一，它加速国际资金流转和信息、技术管理的传播，创造高效率消费行为模式、需求和价值等。随着我国国民经济的快速发展，人们生活水平得到很大提升，越来越多的人积极参与有益于身心健康的旅游活动。

有一名北京自驾游游客，打算利用寒假外出游玩。他预选了十四个旅游景点，分别为：天津，青岛，济南，威海，日照，南京，洛阳，西安，太原，延安，呼和浩特，承德，沈阳，徐州。

采用自驾游的旅行方式，高速公路优先的策略。同时基于安全考虑，行车时间限定于每天7:00至19:00之间，每天开车时间不超过8小时；在高速公路上的行车平均速度为90公里/小时，在普通公路上的行车平均速度为40公里/小时。

请根据具体问题建立模型，求解游客将十五个城市全游览完，求最短时间。

2 问题分析

2.1 模型确立

本题为旅游线路规划问题，该问题可以归结为旅行商问题，即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题。

这类问题是是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

2.2 方法提出

旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。关于TSP问题，现如今有多种解法，本文中，我们将用四种方法对该问题加以解答。

2.2.1蚁群算法

1991年由意大利学者M. Dorigo，V. Maniezzo 和A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。

它是一种是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。

它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题

其原理是一种正反馈机制或称增强型学习系统：它通过以下流程达到最终收敛于最优路径

【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量进一步增加】

蚂蚁搜寻食物的具体过程如下：

在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素，信息素随着时间的推移会逐渐挥发消失。蚂蚁在觅食过程中能够感知这种物质的存在及其强度，并以此来指导自己的运动方向，倾向于朝着这种物质强度高的方向移动，即选择该路径的概率与当时这条路径上该物质的强度成正比。这样路径越短，激索浓度便越高。

这样便形成一个正反馈：最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，最终整个蚁群会找出最优路径。

基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP 问题。

2.2.2模拟退火算法

模拟退火算法由KirkPatrick于1982提出[7]，他将退火思想引入到组合优化领域,提出一种求解大规模组合优化问题的方法，对于NP-完全组合优化问题尤其有效。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其缓慢降温(即退火)，使之达到能量最低点。反之，如果急速降温(即淬火)则不能达到最低点。加温时，固体内部粒子随温升变为无序状，内能增大，而缓慢降温时粒子渐趋有序，在每个温度上都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为exp(-E/(kT))，其中E为温度T时的内能， E为其改变量，k为

Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复产生“新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子a、每个t值时的迭代次数L和停止条件C。2.2.3 遗传算法

是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是多个基因的组成的一个染色体(chromosome)。在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

2.2.4动态规划法

选取（i，S）为状态变量，决策为由一个城市到另一个城市，并且最优值函数fk(i,s)为从起点城市经由k个中间城市的S集到i城的最短路线的距离，则动态规划的递推关系为

其中S集中的城市顺序从右往左表示经历这些城市的顺序。

设一共有N个城市（包括起点城市），则计算出k=1,2···N-1的最优值函数就可以得到最短路径。

3 问题的建模求解

3.1 假设

因为在某地旅游所花时间和费用相对固定，我们假设在两地之间的路费（或所花时间）为主要考虑的变量，将问题简化为求最短路径。假设两点之间的距离为其欧氏距离，且其间的往返距离相等。3.2蚁群算法

3.2.1 蚁群算法与TSP问题

TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值也称信息素痕迹。2 可见度，即先验值。

信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。

蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。

蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。

3.2.2 蚁群算法具体流程

假如蚁群中所有蚂蚁的数量为m，所有城市之间的信息素用矩阵pheromone表示，搜索次数为nc；

最短路径为bestLength，最佳路径为bestTour；

每只蚂蚁都有自己的内存，用一个禁忌表T abu来存储该蚂蚁已经访问过的城市，表示其在以后的搜索中将不能访问这些城市；用另外一个允许访问的城市表Allowed来存储它还可以访问的城市；

矩阵来存储它在一个迭代中给所经过的路径释放的信息素，为信息素增量矩阵

还有另外一些数据，例如一些控制参数(α，β，ρ，Q)，该蚂蚁行走玩全程的总距离tourLength 等等。

α：启发因子，反映蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度

β：期望启发因子，反映了启发式信息在指导蚁群搜索过程中的相对重要程度

ρ：信息素挥发因子

Q：信息素强度，蚂蚁循环一周时释放在所经路径上的信息素总量

STEP 0 初始化变量

nc=0，初始化所有的蚂蚁的矩阵和矩阵，所有元素初始化为0；

Tabu表清空，Allowed表中加入所有的城市节点，

随机选择它们的起始位置（也可以人工指定）。

在Tabu中加入起始节点，Allowed中去掉该起始节点。

STEP 1 为每只蚂蚁选择下一个节点

为每只蚂蚁选择下一个节点，该节点只能从Allowed中以概率公式搜索到，每搜到一个，就将该节点加入到T abu中，并且从Allowed中删除该节点。

其中表示选择城市j的概率，k表示第k个蚂蚁，表示城市i,j在第t时刻的信息素浓度，表

示从城市i到城市j的可见度，，表示城市i,j之间的距离。由此可见越小，越大，也

就是从城市i到j的可见性就越大。

该过程重复n-1次，直到所有的城市都遍历过一次。遍历完所有节点后，将起始节点加入到Tabu 中。此时T abu表元素数量为n+1（n为城市数量），Allowed元素数量为0。

按照公式计算每个蚂蚁的矩阵值。

所有蚂蚁走完之后，最后计算最佳路径，比较每个蚂蚁的路径成本，然后和bestLength比较，若它的路径成本比bestLength小，则将该值赋予bestLength，并且将其Tabu赋予BestTour。

其中，表示蚂蚁k在城市i与j之间留下的信息素。表示蚂蚁k经过一个循环（或迭代）所经过路径的总距离，即tourLength。α,β,Q 均为控制参数。

STEP 2 更新信息素矩阵

按照更新信息素矩阵。

为t+n时刻城市i与j之间的信息素浓度。

ρ为控制参数，为城市i与j之间信息素经过一个迭代后的增量。

并且有

STEP 3 检查终止条件

如果nc>=最大迭代次数，算法终止，转到STEP 4；

否则，重新初始化所有的蚂蚁的矩阵所有元素初始化为0，T abu表清空，Allowed表中加入

所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在T abu中加入起始节点，Allowed 中去掉该起始节点，重复执行STEP 1、2、3。

STEP 4 输出最优值

3.2.3 实验结果

以下为蚁群算法得到的部分结果：

在实验中，蚁群算法会根据参数选取的不同而得到不同的结果，而且并不能判断该结果是否是最优解。针对这样的问题设计了一个重复执行算法并能对结果进行比较的函数。

对蚁群函数的参数设定如下：

令算法重复执行100次，最终得到一个最短距离5727km，最优路线：

北京-呼和浩特-太原-延安-西安-洛阳-徐州-南京-日照-青岛-威海-济南-天津-沈阳-承德-北京

图3-1

3.3模拟退火算法

模拟退火算法描述：

若J( Y(i+1) )>= J( Y(i) ) (即移动后得到更优解)，则总是接受该移动。

若J( Y(i+1) )< J( Y(i) ) (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。

根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：

P(dE) = exp( dE/(kT) )

其中k是一个常数，exp表示自然指数，且dE<0。这条公式说白了就是：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于dE总是小于0（否则就不叫退火了），因此dE/kT < 0，所以P(dE)的函数取值范围是(0,1) 。

随着温度T的降低，P(dE)会逐渐降低。

我们将一次向较差解的移动看做一次温度跳变过程，我们以概率P(dE)来接受这样的移动。

模拟退火算法可以分解为解空间、目标函数和初始解3部分。其基本思想是：

(1)初始化：初始温度T(充分大)，初始解状态s(是算法迭代的起点)，每个T值的迭代次数L；

(2)对k=1，……，L做第(3)至第6步；

(3)产生新解s′；

(4)计算增量cost=cost(s′)-cost(s)，其中cost(s)为评价函数；

(5)若t′ 0则接受s′作为新的当前解，否则以概率exp(-t′/T)接受s′作为新的当前解；

(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法；

(7)T逐渐减少，且T趋于0，然后转第2步运算。

如果时间不限，为旅游者设计一条所花费用最少的路线，根据一般规律，由于游览各个景点的费用，都是一个定值，如果旅行的路程越短，则旅行所花的总费用，也就最少，因此，题目便变转化一个典型的旅行商的问题。我们为江苏徐州编号为1，所要游玩的景点依次编号为2,3，…，11,15。最后回到北京，再重复时的编号设为16（这样便于在程序中进行计算）。

解空间S可表为{0,1,2···,11···，16}的多有固定起点和终点的循环排列结合，

此时的目标函数为游玩所有景点的路程长度或称代价函数。我们要求

minf(π1,π2,···，π16)=∑dπiπi+1

任选序列号u，v（u

π1···πu-1πvπv+1···πu+1πuπv+1···π16

路径差可表示为

Δf=(dπu-1πv+dπudπv+1)-(dπu-1πu+dπvdπv+1)

如果Δf<0，则接受新的路径。否则，以概率exp(-Δf/T)接受新的路径，即若exp(-Δf/T)大于0小于1之间的随机数则接受。

利用选定的降温系数α进行降温即：T<----αT，得到新的温度，这里我们取α=0.999。

用选定的终止温度e=10-30，判断退火过程是否结束。若T

图3-2

以下为模拟退火算法得到的部分结果：

图3-3

得到最终路线： 北京-呼和浩特-太原-延安-西安-洛阳-徐州-南京-日照-青岛-威海-济南-天津-沈阳-承德-北京。

3.3遗传算法

3.3.1遗传算法的基本运算过程如下：

(1)确定群体规模n(整数),使用随机方法或其它方法产生n 个可能解

)

1)((n i k x i ≤≤组成初始解群:

(2)对于每一个个体)

(k x i (变量k 为世代数,初始时k=1),计算其适应度

))

((k x f i ；

(3)对于每一个体

)

(k x i ,计算其生存概率）（k P i :

∑

==n

i i i i x f x f k P 1

)

(/)()(。然后设一个随机选择器,

依据）（k P i 以一定的随机方法产生配种个体

)

(k x i 。

(4)产生下一代种群。选取两个配种个体)(1k X 、)(2k X ,并依据一定的组合规则(如交叉、变异、逆转等)将)(1k X 、)(2k X 结合成两个新一代的个体)1(1+k X 、)1(2+k X ,直至新一代n 个个体形成完毕。

(5)重复(2)至(4)步,直至满足程序终结条件(如时间上的限制或解的质量达到满意的范围等)。

图3-4

3.3.2 编码

遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一转换操作就叫做编码，也可以称作(问题的)表示(representation)。

评估编码策略常采用以下3个规范:

a)完备性(completeness):问题空间中的所有点(候选解)都能作为GA空间中的点(染色体)表现。

b)健全性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c)非冗余性(nonredundancy):染色体和候选解一一对应。

目前的几种常用的编码技术有二进制编码，浮点数编码，字符编码，变成编码等。

而二进制编码是目前遗传算法中最常用的编码方法。即是由二进制字符集{0,1}产生通常的0,1字符串来表示问题空间的候选解。它具有以下特点：

a)简单易行

b)符合最小字符集编码原则

c)便于用模式定理进行分析，因为模式定理就是以基础的。

适应度函数

进化论中的适应度，是表示某一个体对环境的适应能力，也表示该个体繁殖后代的能力。遗传算法的适应度函数也叫评价函数，是用来判断群体中的个体的优劣程度的指标，它是根据所求问题的目标函

数来进行评估的。

遗传算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。由于遗传算法中，适应度函数要比较排序并在此基础上计算选择概率，所以适应度函数的值要取正值。由此可见，在不少场合，将目标函数映射成求最大值形式且函数值非负的适应度函数是必要的。

适应度函数的设计主要满足以下条件：

a）单值、连续、非负、最大化

b) 合理、一致性

c）计算量小

d）通用性强。

在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数设计直接影响到遗传算法的性能。

3.3.3初始群体选取

遗传算法中初始群体中的个体是随机产生的。一般来讲，初始群体的设定可采取如下的策略:

a)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。

b)先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。

3.3.4 选择

从群体中选择优胜的个体，淘汰劣质个体的操作叫选择。选择的目的是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以

下几种：适应度比例方法、随机遍历抽样法、局部选择法。

其中轮盘赌选择法（roulette wheel selection）是最简单也是最常用的选择方法。在该方法中，各个个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度为，则i 被选择的概率，为

显然，概率反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大。其被选择的概率就越高、反之亦然。计算出群体中各个个体的选择概率后，为了选择交配个体，需要进行多轮选择。每一轮产生一个[0，1]之间均匀随机数，将该随机数作为选择指针来确定被选个体。个体被选后，可随机地组成交配对，以供后面的交叉操作。

3.3.5 交叉

在自然界生物进化过程中起核心作用的是生物遗传基因的重组(加上变异)。同样，遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。

交叉算子根据交叉率将种群中的两个个体随机地交换某些基因，能够产生新的基因组合，期望将有益基因组合在一起。根据编码表示方法的不同，可以有以下的算法：

a)实值重组（real valued recombination）

1)离散重组（discrete recombination）

2)中间重组（intermediate recombination）

3)线性重组（linear recombination）

4)扩展线性重组（extended linear recombination）。

b)二进制交叉（binary valued crossover）

1)单点交叉（single-point crossover）

2)多点交叉（multiple-point crossover）

3)均匀交叉（uniform crossover）

4)洗牌交叉（shuffle crossover）

5)缩小代理交叉（crossover with reduced surrogate）。

最常用的交叉算子为单点交叉(one-point crossover)。具体操作是:在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新个体。下面给出了单点交叉的一个例子：

个体A：1 0 0 1 ↑1 1 1 →1 0 0 1 0 0 0 新个体

个体B：0 0 1 1 ↑0 0 0 →0 0 1 1 1 1 1 新个体

3.3.6 变异

变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：

一般来说，变异算子操作的基本步骤如下：

a)对群中所有个体以事先设定的变异概率判断是否进行变异

b)对进行变异的个体随机选择变异位进行变异。

遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性，以防止出现未成熟收敛现象。此时收敛概率应取较大值。

遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。所谓相互配合.是指当群体在进化中陷于搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。如何有效地配合使用交叉和变异操作，是目前遗传算法的一个重要研究内容。

3.3.7 终止条件

当最优个体的适应度达到给定的阈值，或者最优个体的适应度和群体适应度不再上升时，或者迭代次数达到预设的代数时，算法终止。预设的代数一般设置为100-500代。

针对TSP 问题各模块的设置

TSP 问题描述十分简单,简言之就是寻找一条最短的遍历n 个城市的路径,或者说搜索整数子集X={l,2,…,n}(X 的元素表示对n 个城市的编号)的一个排列

）

（}...,,{21n v v v X =π使

∑-=++=1

1

11)

,(),(n i i i n d v v d v v d T

取最小值,式中的

)

,(1+i i v v d 表示城市

i v 到城市1+i v 的距离。

3.3.8 编码和适应度函数

根据TSP 问题的要求,任意一个城市必须而且只能访问一次。因此在编码时,要求一个个体(即一条遍历路径)的染色体编码中不允许有重复的基因码。

在求解TSP 问题的各种遗传算法中,多采用以遍历城市的次序排列进行编码的方法,如码串82631457表示自城市8开始,依次经城市2,6,3,1,4,5,7,最后返回城市8的遍历路径。显然,这是一种针对TSP 问题的最自然的编码方式,这一编码方案的主要缺陷在于造成了交叉操作的困难。

适应度函数常取路径长度d T 的倒数,即d T f /1=。

3.3.9 交叉

OX 顺序交叉

1985年Davis 等人提出了基于路径表示的顺序交叉(OX)操作,OX 操作能够保留排列,并融合不同排列的有序结构单元。此方法开始也是选择一个匹配区域:

A=985|467|1320 B=863|201|9547

首先,两个交叉点之间的中间段保持不变,在其区域外的相应位置标记X,得到: A'=XXX|467|XXXX B'=XXX|201|XXXX

其次,记录父个体B 从第二个交叉点开始城市码的排列顺序,当到达表尾时,返回表头继续记录城市码,直至到达第二个交叉点结束,这样便获得了父个体B 从第二个交叉点开始的城市码排列顺序为9-5-4-7-8-6-3-2-0-1。对于父个体A 而言,已有城市码4,6,7将它们从父个体B 的城市码排列顺序中去掉,得到排列顺序9-5-8-3-2-0-1,再将这个排列顺序复制给父个体A,复制的起点也是从第二个交叉点开始,以此决定子个体1对应位置的未知码x,这样新个体A ”为:

A ”=2014679583

同样,可以产生子个体B ”为: B ”=4672013985 3.3.10 变异

目前已有多种变异算子,如2-opt 变异算子、倒位变异算子、启发式变异算子等,其中启发式变异算子相对其他变异算子更有效。

启发式变异算子的操作过程如下:

设:P1=123456789

随机选择三个点,例如:2、6、8,任意交换位置可以得到5个不同个体:

A1=123458769

A2=163452789

A3=183456729

A4=163458729

AS=183452769

从中选择最好的作为新的个体。

3.3.11终止条件

终止条件有两方面考虑：

(1)迭代次数达到预设的代数

(2)最优个体的适应度和群体适应度迭代多次不再上升

根据以上两个因数，并结合实验结果分析，最终确定迭代次数为2000代。迭代次数为2000代时，能稳定地得到最优结果。

结果分析：

经计算，得到最短距离为5727KM，从北京出发，整个路线途径：北京-呼和浩特-太原-延安-西安-洛阳-徐州-南京-日照-青岛-威海-济南-天津-沈阳-承德-北京。

图3-5

对比：

第1代

北京-太原-济南-日照-承德-沈阳-南京-呼和浩特-延安-西安-洛阳-天津-徐州-威海-青岛

10326km

图3-6

第200代

北京-天津-济南-南京-徐州-日照-青岛-威海-沈阳-承德-延安-西安-洛阳-太原-呼和浩特

6898km

图3-7

第1000代

北京-天津-济南-威海-青岛-日照-徐州-南京-洛阳-西安-延安-太原-呼和浩特-承德-沈阳

5836km

图3-8

3.4动态规划法

3.4.1计算过程

规定旅行者从北京（城市1）出发，设旅行者行至i 城，记

i N ={1，2，3，4，5，7，8，9，10，11, 12, 13, 14, 15}

S 表示达到i 城之前中途所经过的城市的集合，i S N ?

选取（i ，S ）为状态变量，决策为由一个城市到另一个城市，并且最优值函数)

,(S i f k 为从起点城

市经由k 个中间城市的S 集到i 城的最短路线的距离，则动态规划的递推关系为

边界条件为i

d i f 10),(=φ，其中S 集中的城市顺序从右往左表示经历这些城市的顺序。

3.4.2 模型复杂度分析

不考虑条件情况下，k 表示从北京出发经k 个城市到达某城市。 k=i 时，i=

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},到达某城市中间经过的城市个数为i 个，且可能经过的城市有13个（15个城市中除去出发城市北京和终点城市），因此最优值函数的个数为 个，除北京以外的十三个

城市都可以作为终点城市，因此k=i 时的最优值函数总个数为 。 k=15时，表示从北京出发经历所有的十四个中间城市回到北京，最优值函数个数有1个。经计算复杂度大于7000，15个城市的货郎担问题一共需要超过7000最优值函数，可见其计算过程是极其繁琐和复杂的。 3.4.3 模型简化计算

1(,)[(,\{})]

min k k j j S

f i S f j S j d -∈=+13

14i C ?

为了减少最优值函数的个数，必须简化模型求解的计算量，最优值函数)

,(S i f k 中能改变的变量只

有k ，因此，可以通过减少城市总数N 从而减少最优值函数的个数。，一个块当作一个城市节点进行

模型求解。

? 济南*={济南，威海，青岛，烟台} ? 徐州*={徐州，南京} ? 洛阳*={西安，洛阳，延安} 原来的路线表如下所示：

如图所示，途中黄色标记的为不满足条件的数据，实际意义中为不满足旅游条件的路线，因此在利用动态规划进行求解时候要对距离进行判断，以来确定是否满足条件。经过简化之后的模型为

简化之后的模型依旧是比较复杂的，因此借助于计算机实验运算，代码基于java 语言，伪代码如下所示：

TSP(intD[][]，int n)

//输入n 个顶点的有向图，矩阵D[][]是有向图的邻接矩阵 //D[][]是原图的邻接矩阵

//F[][]中存储阶段最短路径，M[][]中存储阶段最优策略,行数是n，列数是2n-1 //找到从V0出发，遍历所有城市一次且仅一次再回到V0的最短路径长度 //并输出最短路

径 { for(i=0; i

for(i=1; i<2n-1-1; i++) //列 for(j=1; j

{

计算D[j][k]+F[k][i-2k-1]并选择使之取得最小值min的k*;

F[k][i] = min //填表，记录阶段最优值 M[k][i] = k* //记录每个状态的最优决策k*

}

//i==2n-1-1 时

对于i中的每个节点k

计算D[0][k] + F[k][[i-2k-1]并选择使之取得最小值min的k* F[0][2n-1-1] = min; //总最短路径M[0][2n-1-1] = k*;

//回溯查表M输出最短路径输出V0

for(2n-1-1,j=0; i>0; ) { j = M[j][i];//下一步去往哪个结点 i = i–2j-1;//从i表示的集合中删除

j 输出Vj }

}

具体代码见附录。

如下为运算过程部分展示

K=1的时候

可以得到最近的城市为天津市

当K=2时

可以得出最近距离为承德

K=3

可得最近距离为沈阳

K=4时

可根据图可得最近城市为济南，但是两者之间的距离不满足条件，所以此时该路线不符合要求，因此返回到上一城市选择第二优先城市进行尝试

运筹学大作业

大连科技学院运筹学(Z)大作业LINGO软件在函数最大值中的运用 学院名称 专业班级 学生组号 学生姓名 指导教师 二〇一八年五月

实验LINGO软件在函数最大值中的运用 大作业目的 掌握LINGO软件求解函数最大值的基本步骤，了解LINGO软件解决函数最大值的基本原理，熟悉常用的函数最大值计算代码，理解函数最大值的迭代关系。 仪器、设备或软件 电脑，LINGO软件 大作业内容 1．LINGO软件求解函数最大值的基本原理； 2．编写并调试LINGO软件求解函数最大值的计算代码； 实施步骤 1．使用LINGO计算并求解函数最大值问题； 2．写出实验报告，并浅谈学习心得体会(选址问题的基本求解思路与方法及求解过程中出现的问题及解决方法)。 实施过程 有一艘货轮，分为前、中、后三个舱位，它们的容积与允许载重量如下表所示。现有三种商品待运，已知有关数据列于下表中。又为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间的载重量比例偏差不超过15%，前、后舱之间不超过10%。问货轮应装载A、B、C各多少件，运费收入为最大？试建立这个问题的线性规 首先分析问题，建立数学模型： 确定决策变量 假设i=1,2,3分别代表商品A、B、C，8用j=1,2,3分别代表前、中、后舱，设决策变量x ij为装于j舱位的第i种商品的数量（件）。 确定目标函数

商品A 的件数为： 商品B 的件数为： 商品A 的件数为： 为使运费最高，目标函数为： 确定约束条件 前、中、后舱位载重限制为： 前、中、后舱位体积限制为： A 、 B 、 C 三种商品数量的限制条件： 各舱最大允许载重量的比例关系构成的约束条件： 且决策变量要求非负，即x ij ≥0,i=1,2,3；j=1,2,3。 综上所述，此问题的线性规划数学模型为： 111213x x x ++212223x x x ++313233x x x ++()()()111213212223313233 1000700600Max Z x x x x x x x x x =++++++++112131122232132333865200086530008651500 x x x x x x x x x ++≤++≤++≤112131122232132333105740001057540010571500 x x x x x x x x x ++≤++≤++≤1112132122233132336001000800 x x x x x x x x x ++≤++≤++≤1121311222321323331222321121311323338x 6x 5x 2 2(10.15)(1+0.15)38x 6x 5x 3 8x 6x 5x 11(10.15)(1+0.15)28x 6x 5x 2 8x 6x 5x 4 4(10.10)(1+0.10)38x 6x 5x 3++-≤≤++++-≤≤++++-≤≤++()()() 111213212223313233112131122232132333112131122232132333 1000700600865200086530008651500105740001057540010571500 Max Z x x x x x x x x x x x x x x x x x x x x x x x x x x x =++++++++++≤++≤++≤++≤++≤++≤

运筹学大作业 哈工大

课程名称：对偶单纯形法 一、教学目标 在对偶单纯形法的学习过程中，理解和掌握对偶问题；综合运用线性规划和对偶原理知识对对偶单纯形法与单纯形法进行对比分析，了解单纯形法和对偶单纯形法的相同点和不同点，总结出各自的适用范围；掌握对偶单纯形法的求解过程；并能运用对偶单纯形法独立解决一些运筹学问题。 二、教学内容 1) 对偶单纯形法的思想来源(5min) 2) 对偶单纯形法原理(5min) 3) 总结对偶单纯形法的优点及适用情况(5min) 4) 对偶单纯形法的求解过程(10min) 5) 对偶单纯形法例题(15min) 6) 对比分析单纯形法和对偶单纯形法(10min) 三、教学进程： 1）讲述对偶单纯形法思想的来源： 1954年美国数学家C.莱姆基提出对偶单纯形法（Dual Simplex Method ）。单纯形法是从原始问题的一个可行解通过迭代转到另一个可行解，直到检验数满足最优性条件为止。对偶单纯形法则是从满足对偶可行性条件出发通过迭代逐步搜索原始问题的最优解。在迭代过程中始终保持基解的对偶可行性，而使不可行性逐步消失。因此在保持对偶可行性的前提下，一当基解成为可行解时，便也就是最优解。 2）讲述对偶单纯形法的原理 A.对偶问题的基本性质 依照书第58页，我们先介绍一下对偶问题的六个基本性质： 性质一：弱对偶性 性质二：最优性。如果 x j （j=1...n)原问题的可行解，y j 是其对偶问题可 行解，且有 ∑=n j j j x c 1 =∑=m i i i y b 1 ，则x j 是原问题的最优解，y j 是其对偶问题的最

优解。 性质三：无界性。如果原问题（对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 性质四：强对偶性。如果原问题有最优解，则其对偶问题也一定有最优解。 性质五：互补松弛型。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 性质六：线性规划的原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量；这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这对互补的基解分别代入原问题和对偶问题的目标函数有z=w. B.对偶单纯形法（参考书p64页） 设某标准形式的线性规划问题，对偶单纯形表中必须有c j -z j ≤0（j=1...n),但b i (i=1...m)的值不一定为正，当对i=1...m ，都有b i ≥0时，表中原问题和对偶问题均为最优解，否则通过变换一个基变量，找出原问题的一个目标函数值较小的相邻的基解。 3）为什么要引入对偶单纯形法 从理论上说原始单纯形法可以解决一切线性规划问题，然而实际问题中，由于考虑问题的角度不同，变量设置的不同，便产生了原问题及其对偶问题，对偶问题是原问题从另外一个角度考虑的结果。用对偶单纯形法求解线性规划问题时，当约束条件为“≥”时，不必引入人工变量，使计算简化。 例如，有一线性规划问题： min ω =12 y 1 +16y 2 +15 y 3 约束条件 ?? ?? ???≥=≥+≥+0)3,2,1(3522 423121 i y y y y y i

运筹学作业答案1

《运筹学》作业 第2章 1．某公司计划生产两种产品，已知生产单位产品所需的三种原材料的消耗及所获的利润，如下表所示。问应如何安排生产使该工厂获利最多？（建立模型，并用图解法求解） 答：产品1和产品2分别生产15和7.5单位，最大利润是975. 2．某公司计划生产两种产品，已知生产单位产品所需的两种原材料的消耗和人员需要及所获的利润，如下表所示。问应如何安排生产使该工厂获利最多？（建立模型，并用图解法求解） 答：产品1和产品2分别生产2和6单位，最大利润是3600. 3. 下表是一个线性规划模型的敏感性报告，根据其结果，回答下列问题： 1）是否愿意付出11元的加班费，让工人加班； 2）如果第二种家具的单位利润增加5元，生产计划如何变化？ Microsoft Excel 9.0 敏感性报告 工作表 [ex2-6.xls]Sheet1 报告的建立: 2001-8-6 11:04:02 可变单元 格 终递减目标式允许的允许的单元格名字值成本系数增量减量 $B$15 日产量（件）100 20 60 1E+30 20 $C$15 日产量（件）80 0 20 10 2.5 $D$15 日产量（件）40 0 40 20 5.0 $E$15 日产量（件）0 -2.0 30 2.0 1E+30 约束 终阴影约束允许的允许的单元格名字值价格限制值增量减量 $G$6 劳动时间（小时/件）400 8 400 25 100 $G$7 木材（单位/件）600 4 600 200 50

$G$8 玻璃（单位/件）800 0 1000 1E+30 200 答：1）因为劳动时间的阴影价格是8，所以不会愿意付出11元的加班费，让工人加班；2）因为允许的增加量是10，所以生产计划不变。 4某公司计划生产两种产品，已知生产单位产品所需的三种原材料的消耗及所获的利润，如 5. 下表是一个线性规划模型的敏感性报告，根据其结果，回答下列问题： 1）是否愿意付出11元的加班费，让工人加班； 2）如果工人的劳动时间变为402小时，日利润怎样变化？ 3）如果第二种家具的单位利润增加5元，生产计划如何变化？ Microsoft Excel 9.0 敏感性报告 工作表 [ex2-6.xls]Sheet1 报告的建立: 2001-8-6 11:04:02 可变单元 格 终递减目标式允许的允许的单元格名字值成本系数增量减量 $B$15 日产量（件）100 20 60 1E+30 20 $C$15 日产量（件）80 0 20 10 2.5 $D$15 日产量（件）40 0 40 20 5.0 $E$15 日产量（件）0 -2.0 30 2.0 1E+30 约束 终阴影约束允许的允许的单元格名字值价格限制值增量减量 $G$6 劳动时间（小时/件）400 8 400 25 100 $G$7 木材（单位/件）600 4 600 200 50 $G$8 玻璃（单位/件）800 0 1000 1E+30 200 答：1）因为劳动时间的阴影价格是8，所以不会愿意付出11元的加班费，让工人加班；2）日利润增加2*8=16 3）因为允许的增加量是10，所以生产计划不变。 第3章 1．一公司开发出一种新产品，希望通过广告推向市场。它准备用电视、报刊两种广告形式。 这两种广告的情况见下表。要求至少30万人看到广告，要求电视广告数不少于8个，

运筹学课后作业答案

<运筹学>课后答案 [2002年版新教材] 前言： 1、自考运筹学课后作业答案，主要由源头活水整理；gg2004、杀手、mummy、promise、月影骑士、fyb821等同学作了少量补充。 2、由于水平有限，容如果不对之处，敬请指正。欢迎大家共同学习，共同进步。 3、帮助别人，也是帮助自己，欢迎大家来到易自考运筹学版块解疑答惑。 第一章导论P5 1.、区别决策中的定性分析和定量分析，试举例。 定性——经验或单凭个人的判断就可解决时，定性方法 定量——对需要解决的问题没有经验时；或者是如此重要而复杂，以致需要全面分析（如果涉及到大量的金钱或复杂的变量组）时，或者发生的问题可能是重复的和简单的，用计量过程可以节约企业的领导时间时，对这类情况就要使用这种方法。 举例：免了吧。。。 2、. 构成运筹学的科学方法论的六个步骤是哪些？ .观察待决策问题所处的环境； .分析和定义待决策的问题； .拟定模型； .选择输入资料； .提出解并验证它的合理性（注意敏感度试验）； .实施最优解； 3、．运筹学定义： 利用计划方法和有关许多学科的要求，把复杂功能关系表示成数学模型，其目的是通过定量分析为决策和揭露新问题提供数量根据 第二章作业预测P25 1、. 为了对商品的价格作出较正确的预测，为什么必须做到定量与定性预测的结合？即使在定量预测法诸如加权移动平均数法、指数平滑预测法中，关于权数以及平滑系数的确定，是否也带有定性的成分？ 答：（1）定量预测常常为决策提供了坚实的基础，使决策者能够做到心中有数。但单靠定量预测有时会导致偏差，因为市场千变万化，影响价格的因素很多，有些因素难以预料。调查研究也会有相对局限性，原始数据不一定充分，所用的模型也往往过于简化，所以还需要定性预测，在缺少数据或社会经济环境发生剧烈变化时，就只能用定性预测了。（2）加权移动平均数法中权数的确定有定性的成分；指数平滑预测中的平滑系数的确定有定性的成分。 2.、某地区积累了5 个年度的大米销售量的实际值（见下表），试用指数平滑法，取平滑

运筹学第四次作业排队论问题.doc

一、汽车维修站问题 某汽车维修站只有一名修理工，一天8h 平均修理10辆汽车。已知维修时间服从负指数分布，汽车的到来服从泊松流，平均每小时有1辆汽车到达维修站。假如一位司机愿意在维修站等候，一旦汽车修复就立即开走，问司机平均需要等待多长时间。如果假设每小时有1.2辆汽车去修理，试问该维修工每天的空闲时间有多少？这对维修站里的汽车数及修理后向顾客交货时间又有怎样的影响？结合以上所求得的数据，分析汽车维修站的服务质量水平。 解：该问题是一个标准的M/M/1/2模型，即汽车司机相继到达间隔时间的分布满足负指数分布，维修工服务时间分布满足负指数分布，服务台数为c=1，系统容量限制为N=2。 (1)已知汽车的到来服从泊松流，平均到达率为=1/h λ，维修时间服从负指数分布，平均每辆汽车接受服务的时间为T=0.8h,单位时间服务车辆的数量为 1.25μ=。则根据该模型运行指标的计算公式可得出： ①系统的平均服务强度为/0.8ρλμ==； ②顾客到达后理科就能得到服务的概率，即维修站空闲，没有顾客的概率为 0+1 11N P ρ ρ -= -； ③系统的队长为1 1 (1)11N s N N L ρ ρρρ +++=---; ④系统的排队长0(1)q S L L P =--; ⑤系统的有效到达率为0(1)e P λμ=-； ⑥顾客逗留时间为0(1) s s s e L L W P λμ= = -； ⑦系统满员的概率，即顾客被拒绝的概率为1 1·1N N N P ρ ρρ +-=-； 利用LINGO 软件来求解，记有关参数1c =，系统最大容量为N=2，顾客平均到达率为1L λ==，平均每个顾客的服务时间为1 0.8T μ ==。则相应程序如 下： MODEL: sets:

运筹学大作业(线性规划问题)

运筹学 结课大作业 姓名：苏同锁 学号：1068132104 学院：数理与生物工程学院 班级：数学2010

实例：有三家物流企业将一批货物分别运送到四个城市。物流公司A，B，C所运送货物量分别为110吨、70吨、100吨四个城市I， Il，III，Ⅳ，需求量分别为60吨、70吨、50吨、70吨。物流公司A往城市I，II，III，Ⅳ每吨的运价分别为l0元、15元、20元、25元；物流公司 B到城市I，II，III，Ⅳ每吨的运价分别为2O元、10元、l5元、15元：物流公司 C 到城市I，II，III，Ⅳ每吨的运价分别为25元、30元、20元、25元。 运输费用数据表 如何确定调运方案，才能使运输总费用最小。 首先，设运输总费用为f，我们要求运输总费用最小，故目标函数为：Minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+ 30x32+20x33+25x34 其中Xij表示从物流公司i调运到城市j物资的数量，minf表示运输费用最少。 考虑约束条件如上表所述的量和销地的需求量要满足运输平衡条件，以及各变量取非负数，于是可得如下约束条件：

x11+x12+x13+x14<=110 x21+x22+x23+x24<=70 x31+x32+x33+x34<=100 x11+x21+x31>=60 x12+x22+x32>=70 x13+x23+x33>=50 x14+x24+x34>=70 Xij≥0(i=1,2,3;j=1,2,3,4) 最后，我们将目标函数和约束条件写在一起，就得到了物资调运问题的数学模型，即线性规划问题： minf=10x11+15x12+20x13+25x14+20x21+10x22+15x23+15x24+25x31+ 30x32+20x33+25x34 x11+x12+x13+x14<=110 x21+x22+x23+x24<=70 x31+x32+x33+x34<=100 x11+x21+x31>=60 x12+x22+x32>=70 x13+x23+x33>=50 x14+x24+x34>=70 Xij≥0(i=1,2,3;j=1,2,3,4)

运筹学(胡运权)第五版课后答案-运筹作业

运筹学(胡运权)第五版课后答案-运筹作业

47页1.1b 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47页1.1d 无界解 1 2 3 4 5 4 3 2 1 - 1 -6 -5 -4 -3 -2 X2 X1 2x1- -2x1+3x 1 2 3 4 4 3 2 1 X1 2x1+x2=2 3x1+4x2= X

1.2（b） 约束方程的系数矩阵A= 1 2 3 4 2 1 1 2 P1 P2 P3 P4 基 基解 是否可行解目标函数值X1 X2 X3 X4 P1 P2 -4 11/2 0 0 否 P1 P3 2/5 0 11/5 0 是43/5 P1 P4 -1/3 0 0 11/6 否 P2 P3 0 1/2 2 0 是 5 P2 P4 0 -1/2 0 2 否 P3 P4 0 0 1 1 是 5 最优解A=(0 1/2 2 0)T和(0 0 1 1)T 49页13题 设Xij为第i月租j个月的面积 minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x1 3 +6000x23+7300x14 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 Xij≥0 用excel求解为： ( )

用LINDO求解： LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION V ALUE

哈工大运筹学大作业-对偶单纯形法对比

哈工大运筹学大作业-对偶 单纯形法对比 标准化文件发布号：（9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-

运筹学课程 运筹学对偶单纯形法与单纯形法 对比分析大作业 哈尔滨工业大学工业工程系 学生姓名: 学号： 指导教师： 成绩： 评语：

运筹学对偶单纯形法与单纯形法对比分析 摘要：这篇论文主要介绍了对偶单纯形法的实质、原理、流程和适用条件等。将对偶单纯形法与单纯形法的基本思想进行对比分析，从而说明对偶单纯形法的优点和适用范围。 关键词：对偶单纯形法；对偶理论；单纯形法；基本思想 在线性规划早期发展阶段的众多重要发现中，对偶的概念及其分支是其中最重要的内容之一。这个发现指出，对于任何一个线性规划问题都具有对应的称为对偶问题的线性规划问题。对偶问题与原问题的关系在众多领域都非常有用。 （一）教学目标： 通过对偶单纯形法的学习，加深对对偶问题的理解。掌握对偶单纯形法的解题过程，理解对偶理论的其原理，了解对偶单纯形法的作用和应用范围 （二）教学内容： 1）对偶单纯形法的思想来源 2）对偶单纯形法原理 3）对偶理论的实质 4）单纯形法和对偶单纯形法的比较 （三）教学进程： 一、对偶单纯形法的思想来源

所谓对偶单纯形法，就是将单纯形法应用于对偶问题的计算，该方法是由美国数学家C.莱姆基于1954 年提出的，它并不是求解对偶问题解的方法，而是利用对偶理论求解原问题的解的方法。 二、对偶问题的实质 下面是原问题的标准形式以及其对应的对偶问题： 原问题对偶问题 从而可以发现如下规律： 1.原问题目标函数系数是对偶问题约束方程的右端项。 2.原问题约束方程的右端项是对偶问题目标函数的系数。 3.原问题一个变量在所有约束方程中的系数是对偶问题一个约束方程中的所有系数。 三、对偶单纯形法原理 对偶单纯形法是通过寻找原问题的对偶问题的可行解来求解原问题的最优解的方法，它的应用包括影子价格和灵敏度分析等。为了理解对偶单纯形法为什么能够解出原方程的最优解，我们需要对对偶理论的几个基本原理有所了解。 1.弱对偶性 如果是原问题的可行解，是其对偶问题的可行解，则恒有

管理运筹学作业答案MBA

管理运筹学作业答案MBA

第1章 线性规划基本性质 P47 1—1（2） 解：设每天从i 煤矿()2,1=i 运往j 城市()3,2,1=j 的煤为ij x 吨，该问题的LP 模型为： () ?????????? ?==≥=+=+=+=++=+++++++==∑∑==3,2,1;2,10200150100250 200 ..85.681079min 231322122111232221 13121123 22211312112 13 1j i x x x x x x x x x x x x x t s x x x x x x x c ij i j ij ij ω P48 1—2（2） ??? ??≥-≤-≥-+=0,)2(33) 1(0..max 2 1212121x x x x x x t s x x z

解：Φ =2 1 R R ，则该LP 问题无可行解。 P48 1—2（3） ??? ??≥-≥-≥--=0,)2(55)1(0..102min 2 1212121x x x x x x t s x x z

解：目标函数等值线与函数约束（2）的边界线平行，由图可知则该LP 问题为多重解（无穷多最优解）。 ?? ?? ?==????-=-=-45 45550212121x x x x x x 则10 ,45,45**1-=?? ? ??=z X T （射线QP 上所有点均为最优点） P48 1—2（4） ???????≥≤-≤+≤+--=0 ,)3(22)2(825) 1(1043..1110min 212121 2121x x x x x x x x t s x x z

运筹学上机作业答案

人力资源分配问题 第一题 （1）安排如下： x1=8,x2=0,x3=1,x4=1,x5=0,x6=4,x7=0,x8=6,x9=0x10=0,x11=0。 （2）总额为320，一共需安排20个班次； 因为在13:00—14:00,14:00—15:00,16:00—17:00,分别存在2,9,5个工时的剩余，（例如11:00—12:00）安排了8个员工而在14:00-15：00剩余了九个所以可以安排一些临时工工作3个小时的班次，使得总成本更小。 （3）在18:00—19:00安排6个人工作4小时；在11:00—12:00安排8个人，13:00—14：00安排1个人，15:00—16:00安排1个人，17:00—18:00安排4个人工作3小时。总成本最低为264元。

生产计划优化问题第二题 产品1在A 1生产数量为1200单位，在A 2 上生产数量为230单位，在B 1 上不生产，B 2 上生产数量为 858单位，B 3 上生产数量为571单位；产品2在A1上不生产，在A2上生产数量为500单位，在B1上生产数量为500单位；产品3在A2上生产数量为324单位，在B2上生产数量为324单位。最大利润为2293.29元。

第三题 设Xi为产品i最佳生产量。 （1）最优生产方案唯一，为X1=1000、X2=1000、X3=1000、X4=1000、X5=1000、X6=55625、X7=1000. （2）如上图所示，产品5的单价价格为0-30时，现行生产方案保持最优。 （3）由于环织机工的影子价格为300，且剩余变量值为零，而其他几种资源的影子价格为0，剩余变量均大于0，所以应优先增加环织工时这种资源的限额，能增加3.33工时，单位费用应低于其影子价格300才是合算的。 （4）因为产品2对偶价格= -3.2<0 ，950>933.33，3.2*（1000-950）=160；所以当产品2的最低销量从1000减少到950时，总利润增加160元。 （5）原最优解并没有把针织工时用尽，还有943.75工时的剩余，因此，不能通过增加针织工时来提高总利润。 （6）环织工时为630 - 5003.33时，最优生产方案不变，因为5010>5003.33，因此，若环织机工时的限额提高到5010小时，最优生产方案发生了变化。

运筹学作业习题

线性规划建模及单纯形法 思考题 主要概念及内容： 线性规划模型结构（决策变量，约束不等式、等式，目标函数）；线性规划标准形式； 可行解、可行集（可行域、约束集），最优解；基、基变量、非基变量、基向量、非基 向量；基本解、基本可行解、可行基、最优基。 复习思考题： 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，哪种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基本解、基本可行解、最优解、最优基本解的概念及它 们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个 最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什 么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情 况下，继续第二阶段？ 作业习题 1、将下列线性规划问题化为标准型 （1）???????≥=--+-≥-+-≤+-++-+=0,,953413223183622453max 4214321432143214321x x x x x x x x x x x x x x x x x x x z （2）???????≤≥=+-+-≥-+--≤--++++=0 ,0,15 2342722351232243min 4214321432143214 321x x x x x x x x x x x x x x x x x x x f 2、（1）求出下列不等式组所定义的多面体的所有基本解和基本可行解（极点）： ?????≥≤++-≤++0,,1243263323 21321321x x x x x x x x x （2）对下述线性规划问题找出所有基本解,指出哪些是基本可行解,并确定最优解. ??? ????≥=-=+-+=+++++=)6,,1(00 31024893631223max 61532143213 21K K j x x x x x x x x x x x x x x z j 3、用图解法求解下列线性规划问题

兰州大学运筹学_运输问题课后习题题解

第七章运输问题 7.1 一个农民承包了6块耕地共300亩，准备播种小麦、玉米、水果和蔬菜四种农产品， 问如何安排种植计划，可得到最大的总收益。 解： 本问题地块总面积：42+56+44+39+60+59=300亩 计划播种总面积：6+88+96+40=300亩 因此这是一个产销平衡的运输问题。可以建立下列的运输模型： 代入产销平衡的运输模板可得如下结果：

种植计划方案 7.2 某客车制造厂根据合同要求从当年开始起连续四年年末交付40辆规格型号相同的 年度 可生产客车数量（辆） 制造成本（万元/辆） 正常上班时间 加班时间 正常上班时间 加班时间 1 20 30 50 55 2 38 24 56 61 3 15 30 60 65 4 42 23 53 58 根据该厂的情况，若制造出来的客车产品当年未能交货，每辆车每积压一年的存储和维护费用为4万元。在签订合同时，该厂已储存了20辆客车，同时又要求四年期未完成合同后还需要储存25辆车备用。问该厂如何安排每年的客车生产量，使得在满足上述各项要求的情况下，总的生产费用加储存维护费用为最少？ 解：这是一个生产储存问题，可以化为运输问题来做。根据已知条件，我们可以做以下 地块1 地块2 地块3 地块4 地块5 地块6 计划播种面积（亩） 小麦 6 39 31 76 玉米 29 59 88 水果 2 56 38 96 蔬菜 40 40 地块面积（亩） 42 56 44 39 60 59 300 300

分析，建立运输模型。 1、由于上年末库存20辆车，这些产品在这四年中只计仓储费不计生产费用，所以我们记为0年，第一行； 2、在建立的运输表中，相应单元格填入当年交付产品的所有成本（包括生产和存储成本）； 3、年份从1到4表示当年的正常生产，而1’到4’表示当年加班生产的情况； 4、由于期末（4年底）要有25辆车的库存，即4年末的需求量是40+25=65辆； 5、在表中没有具体成本的单元格中，表示没有生产也没有交货，为了保证这个真实情况的描述，在这些格中填M，使安排的生产量为0。 6、在计算成本时，当年生产当年交货不加存储成本，但对未交付的产品，第二年要付一个年的存储费4万元，依此类推。 根据上面的分析，可得运价表如下。 年度1 年度2 年度3 年度4 库存生产能力（辆） 0 4 8 12 16 20 20 1 50 54 58 6 2 66 20 1’55 59 63 67 71 30 2 56 60 64 68 38 2’61 65 69 74 24 3 60 6 4 68 15 3’65 69 74 30 4 53 57 42 4’58 62 23 合同需求量（辆）40 40 40 40 25 这是一个产大于销的运输模型，代入求解模型可得： 即：生产安排的方案：

运筹学离线作业 (答案)

浙江大学远程教育学院 《运筹学》课程作业 姓名：姜胜超学号：715003322021 年级：15秋学习中心：宁波学习中心————————————————————————————— 第2章 1．某公司计划生产两种产品，已知生产单位产品所需的三种原材料的消耗及所获的利润， 产品1 产品2 可用的材料数 原材料A 原材料B 原材料C 1 3 2 2 2 30 60 24 单位产品获利40万元50万元 1. 产品利润为P（万元） 则P=40x+50y 作出上述不等式组表示的平面区域，即可行域：

由约束条件可知0ABCD 所在的阴影部分，即为可行域 目标函数P=40x+50y 是以P 为参数，-54 为斜率的一族平行线 y =- 5 4 x +50P （图中红色虚线） 由上图可知，目标函数在经过C 点的时候总利润P 最大 即当目标函数与可行域交与C 点时，函数值最大 即最优解C=（15，7.5），最优值P=40*15+50*7.5=975（万元） 答：当公司安排生产产品1为15件，产品2为7.5件时使工厂获利最大。 2． 某公司计划生产两种产品，已知生产单位产品所需的两种原材料的消耗和人员需要及所 获的利润，如下表所示。问应如何安排生产使该工厂获利最多？（建立模型，并用图解 产品1 产品2 可用的材料数 原材料A 原材料B 人时 1 0 3 0 2 2 4 12 24 单位产品获利 300万元 500万元 解：设生产产品1为x 件，生产产品2为y 件时，使工厂获利最多 产品利润为P （万元） 则 P=300x+500y 作出上述不等式组表示的平面区域，即可行域：

运筹学大作业

运筹学课程上机实践要求及内容（2） 一、实验教学的目的和要求 目的：借助运筹学软件的强大功能，通过小组的充分讨论，对管理实践中的实际问题进行建模、求解，并对求解结果进行分析（特别是敏感性分析），进而激发学生的学习兴趣和热情，克服对课程学习的“恐惧感”。 要求：熟练掌握LINGO、WinQSB等软件的基本功能和基本语法结构，能用软件对运筹学问题进行求解和分析。 二、请于第1次-第6次上机时间及平时完成。 三、作业务请写清学号、姓名、专业、班级，上机作业格式请用老 师提供的模版。 四、编写的代码请用记事本单独保存。 五、要求所有题目用LINGO和教材自带的求解软件各做一遍。并分 析解释求解的结果。 六、各题目中的A，B，C，D，E，F为参数，除特别规定外，请自 行设定，各个同学参数值不能相同，若发现完全一致的，作业以零分计。 A=1，B=2，C=2，D=4，E=4，F=1

第1题(线性规划) (1)介绍单纯型算法及其处理人工变量的两阶段法； (2)建立下列问题的数学模型并求解，讨论资源的影子价格； 某造纸厂拟生产漂白松木浆、包装纸(水泥、松木包装纸、松木本色纸)、漂白桦木纸和胶版纸等四种产品，单位产品所需资源情况见表1，市场上胶版纸的需求量不超过6000吨。(a)制订该造纸厂的生产计划；(b)若电的资源可用量下降10%，重新制订该造纸厂的生产计划。 (3)结合本题，谈谈你对线性规划的认识。 Hint: 若参数为5，5，5，5，5，5，则最优目标函数值为(a)167236800； (b)167236800。 解： (1)单纯形法是求解线性规划问题的通用方法。单纯形法的基本思想是：先找出 一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转 换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因 基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最 优解也可用此法判别。 两阶段单纯形法也是一种人工变量法，它的算法可分为两个阶段：第一阶段，引 入人工变量，构造一个具有标准基的新线性规划，求解这个新线性规划，其结果

运筹学第五版课后答案,运筹作业

47页1.1b 用图解法找不到满足所有约束条件的公共范围，所以该问题无可行解47页1.1d 无界解

1.2（b） 约束方程的系数矩阵 A= 1 2 3 4 ( ) 2 1 1 2 P1 P2 P3 P4 最优解A=(0 1/2 2 0)T和(0 0 1 1)T 49页13题 设Xij为第i月租j个月的面积 minz=2800x11+2800x21+2800x31+2800x41+4500x12+4500x22+4500x32+6000x13 +6000x23+7300x14 s.t. x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 Xij≥0 用excel求解为：

用LINDO求解： LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 118400.0 VARIABLE VALUE REDUCED COST Z 0.000000 1.000000 X11 3.000000 0.000000

X21 0.000000 2800.000000 X31 8.000000 0.000000 X41 0.000000 1100.000000 X12 0.000000 1700.000000 X22 0.000000 1700.000000 X32 0.000000 0.000000 X13 0.000000 400.000000 X23 0.000000 1500.000000 X14 12.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -2800.000000 3) 2.000000 0.000000 4) 0.000000 -2800.000000 5) 0.000000 -1700.000000 NO. ITERATIONS= 3 答若使所费租借费用最小，需第一个月租一个月租期300平方米，租四个月租期1200平方米，第三个月租一个月租期800平方米，

《运筹学》课堂作业及答案

第一部分绪论 第二部分线性规划与单纯形法 1 判断下列说法是否正确： (a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的； (b)线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大； (c)线性规划问题的每一个基解对应可行域的一个顶点； (d)如线性规划问题存在可行域，则可行域一定包含坐标的原点； (e)对取值无约束的变量x i，通常令其中 ，在用单纯形法求得的最优解中有可能同时出现 (f)用单纯形法求解标准型的线性规划问题时，与对应的变量都可以被选作换入变量； (g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负； (h)单纯形法计算中，选取最大正检验数δk对应的变量x k作为换入变量，将使目标函数值得到最快的增长； (i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果； (j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示； (k)若x1，x2分别是某一线性规划问题的最优解，则 也是该线性规 划问题的最优解，其中λ1，λ2可以为任意正的实数； (1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为 X ai为人工变量)，但也可写为，只要所有 k i均为大于零的常数； (m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好 为个； (n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解； (o)线性规划问题的可行解如为最优解，则该可行解一定是基可行解； (p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解； (q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优；

运筹学天津大学作业答案

运筹学天津大学作业答 案 文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）

运筹学复习题 第一阶段练习题 一、填空题 1．某足球队要从1、2、3、4号五名队员中挑选若干名上场，令 ???=号不上场 第号上场第i i x i 01 4 ,,1 =i ，请用x i 的线性表达式表示下列要求：(1)若2 号被选中，则4号不能被选中：_________________；(2)只有1名队员被选中，3号才被选中：___________________。 2．线性规划的对偶问题约束的个数与原问题____________的个数相等。因此，当原问题增加一个变量时，对偶问题就增加一个____________。这时，对偶问题的可行域将变_______________(大、小还是不变？)，从而对偶目标值将可能变____________(好还是坏？)。 3．将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设 量。 二、某厂生产Ⅰ，Ⅱ，Ⅲ三种产品。产品Ⅰ依次经A 、B 设备加工，产品Ⅱ经A 、C 设备加工，产品Ⅲ经C 、B 设备加工。已知有关数据如下表所示，请为该厂制定一个最优的生产计划。

三、某厂准备生产A 、B 、C 三种产品，它们都消耗劳动力和材料，有关数据见下表所示： （1）确定获利最大的产品生产计划； （2）产品A 的利润在什么范围内变动时，上述最优计划不变； （3）如设计一种新产品D ，单件劳动力消耗为8单位，材料消耗为2单位，每件可获利3元，问该种产品是否值得生产？ （4）如劳动力数量不变，材料不足时可从市场购买，每单位0.4元，问该厂要不要购进原材料扩大生产，购多少为宜？ 四、某彩色电视机组装工厂，生产A 、B 、C 三种规格电视机。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6小时，8小时和10小时。生产线每月正常工作时间为200小时；三种规格电视机销售后，每台可获利分别为500元，650元和800元。每月销量预计为12台、10台、6台。该厂经营目标如下： 1p ：利润指标定为每月4106.1 元；

运筹学第一次作业

练习一 1.某厂接到生产A 、B 两种产品的合同，产品A 需200件，产品B 需300件。这两种 产品的生产都经过毛坯制造与机械加工两个工艺阶段。在毛坯制造阶段，产品 A 每件需要2小时，产品B 每件需要4小时。机械加工阶段又分粗加工和精加工两道 工序，每件产品A 需粗加工4小时，精加工10小时；每件产品B 需粗加工7小时，精 加工12小时。若毛坯生产阶段能力为1700小时，粗加工设备拥有能力为1000小时, 精加工设备拥有能力为3000小时。又加工费用在毛坯、粗加工、精加工时分别为 每小时3元、3元、2元。此外在粗加工阶段允许设备可进行 500小时的加班生产, 但加班生产时间内每小时增加额外成本元。 试根据以上资料，为该厂制订一个成 本最低的生产计划。 解：设正常生产A,B 产品数X 1,X 2，加班生产A,B 产品数X 3,X 4 min z 3(2x 1 2X 3 4X 2 4X 4 4X 1 4X 3 7X 2 7&) 7.5(4X 3 7X 4) 2(10X 1 10X 3 12X 2 12X 4) X 3 200 X 4 300 4x 2 1700 7x 2 1000 12x 2 3000 7x 2 500 0且为整数，i=1,2,3,4 2.对某厂I ,n,m 三种产品下一年各季度的合同预订数如下表所示。 该三种产品I 季度初无库存，要求在4季度末各库存150件。已知该厂每季度生产 工时为15000小时，生产I 、n 、m 产品每件分别需时2、4、3小时。因更换工艺装备, 产品I 在2季度无法生产。规定当产品不能按期交货时， 产品I , n 每件每迟交一个季 度赔偿20元，产品m 赔偿10元；又生产出来产品不在本季度交货的，每件每季度的 库存费用为5元。问：该厂应如何安排生产，使总的赔偿加库存的费用为最小 （要求 建立数学模型，不需求解）。 解：设X ij 为第j 季度产品i 的产量，S ij 为第j 季度末产品i 的库存量，d ij 为第j 季度 X 1 X 2 2为 s.t 4x , 10x 1 4X 1 X i 量,

《运筹学参考综合习题》

《运筹学参考综合习题》 （我站搜集信息自编，非南邮综合练习题，仅供参考） 资料加工、整理人——杨峰（函授总站高级讲师） 可能出现的考试方式（题型） 第一部分填空题（考试中可能有5个小题，每小题2分，共10分） ——考查知识点：几个基本、重要的概念 第二部分分步设问题（即是我们平常说的“大题”，共90分） ——参考范围： 1、考两变量线性规划问题的图解法（目标函数为max z和min z的各1题） 2、考线性规划问题的单纯形解法（可能2个题目：①给出问题，要求建立线性规划模型，再用单纯形迭代表求解；②考查对偶问题，要求写出原问题的线性规划模型之后写出其对偶问题的线性规划模型，然后用大M法求解其对偶问题，从而也得到原问题的最优解） 3、必考任务分配（即工作指派）问题，用匈牙利法求解。 4、考最短路问题（如果是“动态规划”的类型，则用图上标号法；如果是网络分析的类型，用TP标号法，注意不要混淆） 5、考寻求网络最大流（用寻求网络最大流的标号法） 6、考存储论中的“报童问题”（用概率论算法模型解决） ——未知是否必考的范围： 1、运输规划问题（用表上作业法，包括先求初始方案的最小元素法和将初始方案调整至最优的表上闭回路法）； 2、求某图的最小生成树（用破圈法，非常简单） ※考试提示：可带计算器，另外建议带上铅笔、直尺、橡皮，方便绘图或分析。

第一部分 填空题复习参考 一、线性规划部分： ㈠基本概念：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。 定义：达到目标的可行解为最优解。 由图解法得到的三个结论：①线性规划模型的可行解域是凸集； ②如果线性规划模型有唯一的最优解的话，则最优解一定是凸集（可行解域）的角顶； ③任何一个凸集，其角顶个数是有限的。 ㈡有关运输规划问题的概念：设有m 个产地A i （i=1，2，…，m ），n 个销地B j （j=1，2，…，n ）, A i 产量（供应量）S i ，B j 销量（需求量）d i ，若产、销平衡，则：∑∑===n j j m i i d s 1 1 二、网络分析中的一些常用名词： 定义：无方向的边称为边；有方向的边称为弧。 定义：赋“权”图称为网络。 定义：有向图中，若链中每一条弧的走向一致，如此的链称为路。闭链称为圈。闭回路又称为回路。 定义：在图G 中任两点间均可找到一条链，则称此图为连通图。无重复边与自环的图称为连通图。 定义：树是无圈的连通图。 树的基本性质：①树的任两点之间有且只有一条链； ②若图的任两点之间有且只有一条链，则此图必为树；