数学建模 运输问题

郭敦顒回答：

天晚了，明天正式回答。

2014-8-27回答：

制定运输方案（F）的原则——

（一）两车运油总量U=供油之和∑u=14000+3000+6000+16000+15000+5000=59000，

=u1+u2，且u1，u2≤39000，u1，u2分别是两车运油量；

（二）两车运输路程和最短minL=l1+l2，l1+l2分别是两车运输路程。

（三）运输路径按排的原则

（1）初供应点路程和末供应点路程短者优先按排，它们是：S2=55，S3=32，S4=70，S6=73；

（2）两供应点间路程短者优先按排，它们是：S（A1，A5）=12，S（A2，A4）=20，S（A6，A2）=28，S（A6，A4）=49，…

两供应点前后对调路程等价，如S（A5，A1）=S（A1，A5）=12，

（3）综合路程最短，在初供应点路程和末供应点路程最短，与两供应点间路程短者产生矛盾时，可者采用初供应点路程或末供应点路程较短者

（四）运输方案（F）类型

（1）三+三式，即每辆车都供应三个供应点，

（2）二+四式，即每辆车都供应二个供应点，一辆车都供应四个供应点

运输方案（F）——各运输方案（F）的组合各车运油量与路程

F1= f1+ f2，f1=（A2，A1，A3），f2=（A4，A5，A6）

F1u1=3000+6000+14000=23000＜39000，

F1u2=16000+15000+5000=36000＜39000，23000+36000=59000；

F1 l1=55+93+180+32=360， F1l2=70+85+73+73=301

F1L= F1 l1+ F1l2=360+301=661。

F2= F2f1+ F2f2，F2f1=（A2，A5，A3），F2f2=（A4，A1，A6）

F2u1=3000+15000+14000=32000＜39000，

F2u2=16000+6000+5000=27000＜39000，32000+27000=59000；

F2 l1=55+83+174+32=344， F2l2=70+99+72+73=314

F2L= F2 l1+ F2l2=344+314=658。

以上给出的是运输方案内容的计算模式，未完全尊守运输路径按排的原则，故不是最优。

F3= F3f1+ F3f2，F3f1=（A5，A1， A6），F3f2=（A3，A2， A4）

F3u1=15000+14000+5000=34000＜39000，

F3u2=6000+3000+16000=25000＜39000，34000+25000=59000；

F3 l1=140+12+72+73=297， F2l2=32+85+20+70=207

F3L= F2 l1+ F2l2=297+207=504。

F4= F4f1+ F4f2，F4f1=（A4，A6，），F4f2=（A2，A5，A1，A3，）

F4u1=16000+5000=21000＜39000，

F4u2=3000+15000+14000+6000=38000＜39000，21000+38000=59000；

F4 l1=70+49+73=192， F2l2=55+83+12+180+32=362

F4L= F2 l1+ F2l2=192+362=554。

F5= F5f1+ F5f2，F5f1=（A3，A4，），F5f2=（A2，A1，A5，A6）

F5u1=6000+16000=22000＜39000，

F5u2=3000+14000+15000+5000=37000＜39000，22000+37000=59000；

F5 l1=32+100+70=202， F5l2=55+93+12+73+73=306

F5L= F5 l1+ F5l2=202+306=508。

F1L——F5L，也记为L1——L5。

minL=L1∨L2∨L3∨L4∨L5，

∵661＞658＞554＞508＞504，

∴L1＞L2＞L4＞L5＞L3=504，

∴minL=L3=504。

线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。

0-1规划是决策变量仅取值0或1的一类特殊的整数规划。在处理经济管理中某些规划问题时，若决策变量采用 0-1变量即逻辑变量，可把本来需要分别各种情况加以讨论的问题统一在一个问题中讨论。

蒙特卡罗法(Monte Carlo method)是以概率与统计的理论、方法为基础的一种计算方法，蒙特卡罗法将所需求解的问题同某个概率模型联系在一起，在电子计算机上进行随机模拟，以获得问题的近似解。因此，蒙特卡罗法又称随机模拟法或统计试验法。

在生活中经常遇到这样的问题，某单位需完成n项任务，恰好有n个人可承担这些任务。由于每人的专长不同，各人完成任务不同(或所费时间)，效率也不同。于是产生应指派哪个人去完成哪项任务，使完成n项任务的总效率最高(或所需总时间最小)。这类问题称为指派问题或分派问题。

无约束最优化方法是求解无约束最优化问题的方法，有解析法和直接法两类。

解析法

解析法就是利用无约束最优化问题中目标函数 f(x) 的解析表达式和它的解析性质（如函数的一阶导数和二阶导数），给出一种求它的最优解 x 的方法，或一种求 x 的近似解的迭代方法。

直接法

直接法就是在求最优解 x*的过程中，只用到函数的函数值，而不必利用函数的解析性质，直接法也是一种迭代法，迭代步骤简单，当目标函数 f(x) 的表达式十分复杂，或写不出具体表达式时，它就成了重要的方法。

可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。基本内容是：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。 [1]

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树

管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。

最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊与与1956年提出，20世纪50年代福特(Ford)、(Fulkerson)建立的“网络流理论”，是网络应用的重要组成成分。

最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以在流量最大的前提下，达到所用的费用最小的要求。如n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。

最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1%内

计划评审法(Program Evaluation and Review Technique，简称PERT)，是指利用网络分析制订计划以及对计划予以评价的技术。它能协调整个计划的各道工序，合理安排人力、物力、时间、资金，加速计划的完成。在现代计划的编制和分析手段上，PERT被广泛使用，是现代化管理的重要手段和方法。

关键路线法(Critical Path Method，CPM)，又称关键线路法。一种计划管理方法。它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。

人口系统数学模型，用来描述人口系统中人的出生、死亡和迁移随时间变化的情况，以及它们之间定量关系的数学方程式或方程组，又称人口模型。

初值问题是指在自变量的某值给出适当个数的附加条件，用来确定微分方程的特解的这类问题。

如果在自变量的某值给出适当个数的附加条件，用来确定微分方程的特解，则这类问题称为初值问题。

边值问题是定解问题之一，只有边界条件的定解问题称为边值问题。二阶偏微分方程(组)一般有三种边值问题：第一边值问题又称狄利克雷问题，它的边界条件是给出未知函数本身在边界上的值；第二边值问题又称诺伊曼边值问题或斜微商问题，它的边界条件是给出未知函数关于区域边界的法向导数或非切向导数；第三边值问题又称鲁宾问题，它的边界条件是给出未知函数及其非切向导数的组合

目标规划是一种用来进行含有单目标和多目标的决策分析的数学规划方法。线性规划的一种特殊类型。它是在线性规划基础上发展起来的，多用来解决线性规划所解决不了的经济、军事等实际问题。它的基本原理、数学模型结构与线性规划相同，也使用线性规划的单纯形法作为计算的基础。所不同之处在于，它从试图使目标离规定值的偏差为最小入手解题，并将这种目标和为了代表与目标的偏差而引进的变量规定在表达式的约束条件之中。

时间序列（或称动态数列）是指将同一统计指标的数值按其发生的时间先后顺序排列而成的数列。时间序列分析的主要目的是根据已有的历史数据对未来进行预测。

支持向量机(Support Vector Machine，SVM)是Corinna Cortes和Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

在机器学习中，支持向量机（SVM，还支持矢量网络）是与相关的学习算法有关的监督学习模型，可以分析数据，识别模式，用于分类和回归分析。

聚类分析法是理想的多变量统计技术，主要有分层聚类法和迭代聚类法。 聚类分析也称群分析、点群分析，是研究分类的一种多元统计方法。

例如，我们可以根据各个银行网点的储蓄量、人力资源状况、营业面积、特色功能、网点级别、所处功能区域等因素情况，将网点分为几个等级，再比较各银行之间不同等级网点数量对比状况。

成分分析（Principal Component Analysis，PCA）， 是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。

在实际课题中，为了全面分析问题，往往提出很多与此有关的变量（或因素），因为每个变量都在不同程度上反映这个课题的某些信息。

主成分分析首先是由K.皮尔森（Karl Pearson）对非随机变量引入的，尔后H.霍特林将此方法推广到随机向量的情形。信息的大小通常用离差平方和或方差来衡量。

因子分析是指研究从变量群中提取共性因子的统计技术。最早由英国心理学家C.E.斯皮尔曼提出。他发现学生的各科成绩之间存在着一定的相关性，一科成绩好的学生，往往其他各科成绩也比较好，从而推想是否存在某些潜在的共性因子，或称某些一般智力条件影响着学生的学习成绩。因子分析可在许多变量中找出隐藏的具有代表性的因子。将相同本质的变量归入一个因子，可减少变量的数目，还可检验变量间关系的假设。

判别分析又称“分辨法”，是在分类确定的条件下，根据某一研究对象的各种特征值判别其类型归属问题的一种多变量统计分析方法。

其基本原理是按照一定的判别准则，建立一个或多个判别函数，用研究对象的大量资料确定判别函数中的待定系数，并计算判别指标。据此即可确定某一样本属于何类。

当得到一个新的样品数据，要确定该样品属于已知类型中哪一类，这类问题属于判别分析问题。

对互协方差矩阵的一种理解，是利用综合变量对之间的相关关系来反映两组指标之间的整体相关性的多元统计分析方法。它的基本原理是：为了从总体上把握两组指标之间的相关关系，分别在两组变量中提取有代表性的两个综合变量U1和V1（分别为两个变量组中各变量的线性组合），利用这两个综合变量之间的相关关系来反映两组指标之间的整体相关性。

对应分析也称关联分析、R-Q型因子分析，是近年新发展起来的一种多元相依变量统计分析技术，通过分析由定性变量构成的交互汇总表来揭示变量间的联系。可以揭示同一变量的各个类别之间的差异，以及不同变量各个类别之间的对应关系。

对应分析主要应用在市场细分、产品定位、地质研究以及计算机工程等领域中。原因在于，它是一种视觉化的数据分析方法，它能够将几组看不出任何联系的数据，通过视觉上可以接受的定位图展现出来。

多维标度法是一种将多维空间的研究对象(样本或变量)简化到低维空间进行定位、分析和归类，同时又保留对象间原始关系的数据分析方法。

在市场营销调研中，多维标度法的用途十分广泛。被用于确定空间的级数(变量、指标)，以反映消费者对不同品牌的认知，并且在由这些维构筑的空间中，标明某关注品牌和消费者心目中理想品牌的位置。

偏最小二乘法是一种数学优化技术，它通过最小化误差的平方和找到一组数据的最佳函数匹配。 用最简的方法求得一些绝对不可知的真值，而令误差平方之和为最小。 很多其他的优化问题也可通过最小化能量或最大化熵用最小二乘形式表达。

系统介绍了禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、人工神经网络算法和拉格朗日松弛算法等现代优化计算方法的模型与理论、应用技术和应用案例。

禁忌（Tabu Search）算法是一种元启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。

模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

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

The Technique for Order of Preference by Similarity to Ideal Solution (TOPSIS) is a multi-criteria decision analysis method, which was originally developed by Hwang and Yoon in 1981[1] with further developments by Yoon in 1987,[2] and Hwang, Lai and Liu in 1993.[3] TOPSIS is based on the concept that the chosen alternative should have the shortest geometric distance from the positive ideal solution (PIS)[4] and the longest geometric distance from the negative ideal solution (NIS).[4]

TOPSIS是一种多准则决策分析方法，最初由Hwang和Yoon于1981年开发[1]，1987年由Yoon进一步开发，[2]和Hwang， 1993年赖和刘。[3] TOPSIS是基于这样一个概念，即所选择的方案应该具有离正理想解（PIS）最短的几何距离[4]和距负理想解（NIS）最远的几何距离[4]。

模糊综合评价法是一种基于模糊数学的综合评价方法。该综合评价法根据模糊数学的隶属度理论把定性评价转化为定量评价，即用模糊数学对受到多种因素制约的事物或对象做出一个总体的评价。它具有结果清晰，系统性强的特点，能较好地解决模糊的、难以量化的问题，适合各种非确定性问题的解决。

数据包络分析方法(Data Envelopment Analysis,DEA)是运筹学、管理科学与数理经济学交叉研究的一个新领域。它是根据多项投入指标和多项产出指标，利用线性规划的方法，对具有可比性的同类型单位进行相对有效性评价的一种数量分析方法。DEA方法及其模型自1978年由美国著名运筹学家A.Charnes和W.W.Cooper提出以来，已广泛应用于不同行业及部门，并且在处理多指标投入和多指标产出方面，体现了其得天独厚的优势。

对于两个系统之间的因素，其随时间或不同对象而变化的关联性大小的量度，称为关联度。在系统发展过程中，若两个因素变化的趋势具有一致性，即同步变化程度较高，即可谓二者关联程度较高；反之，则较低。因此，灰色关联分析方法，是根据因素之间发展趋势的相似或相异程度，亦即“灰色关联度”，作为衡量因素间关联程度的一种方法。

主成分分析也称主分量分析，旨在利用降维的思想，把多指标转化为少数几个综合指标（即主成分），其中每个主成分都能够反映原始变量的大部分信息，且所含信息互不重复。这种方法在引进多方面变量的同时将复杂因素归结为几个主成分，使问题简单化，同时得到的结果更加科学有效的数据信息。在实际问题研究中，为了全面、系统地分析问题，我们必须考虑众多影响因素。这些涉及的因素一般称为指标，在多元统计分析中也称为变量。因为每个变量都在不同程度上反映了所研究问题的某些信息，并且指标之间彼此有一定的相关性，因而所得的统计数据反映的信息在一定程度上有重叠。主要方法有特征值分解，SVD，NMF等。

秩和比法（Rank-sum ratio，简称RSR法），是我国学者、原中国预防医学科学院田凤调教授于1988年提出的，集古典参数统计与近代非参数统计各自优点于一体的统计分析方法，它不仅适用于四格表资料的综合评价，也适用于行×列表资料的综合评价，同时也适用于计量资料和分类资料的综合评价。

灰色预测是就灰色系统所做的预测

灰色预测是一种对含有不确定因素的系统进行预测的方法。灰色预测通过鉴别系统因素之间发展趋势的相异程度，即进行关联分析，并对原始数据进行生成处理来寻找系统变动的规律，生成有较强规律性的数据序列，然后建立相应的微分方程模型，从而预测事物未来发展趋势的状况。其用等时距观测到的反应预测对象特征的一系列数量值构造灰色预测模型，预测未来某一时刻的特征量，或达到某一特征量的时间。

回归分析预测法，是在分析市场现象自变量和因变量之间相关关系的基础上，建立变量之间的回归方程，并将回归方程作为预测模型，根据自变量在预测期的数量变化来预测因变量关系大多表现为相关关系，因此，回归分析预测法是一种重要的市场预测方法，当我们在对市场现象未来发展状况和水平进行预测时，如果能将影响市场预测对象的主要因素找到，并且能够取得其数量资料，就可以采用回归分析预测法进行预测。它是一种具体的、行之有效的、实用价值很高的常用市场预测方法，常用于中短期预测。

包含未知函数的差分及自变数的方程。在求微分方程 的数值解时，常把其中的微分用相应的差分来近似，所导出的方程就是差分方程。通过解差分方程来求微分方程的近似解，是连续问题离散化 的一个例子。

马尔可夫预测法主要用于市场占有率的预测和销售期望利润的预测。就是一种预测事件发生的概率的方法。马尔科夫预测讲述了有关随机变量 、 随机函数与随机过程。

逻辑性的思维是指根据逻辑规则进行推理的过程；它先将信息化成概念，并用符号表示，然后，根据符号运算按串行模式进行逻辑推理；这一过程可以写成串行的指令，让计算机执行。然而，直观性的思维是将分布式存储的信息综合起来，结果是忽然间产生想法或解决问题的办法。这种思维方式的根本之点在于以下两点：1.信息是通过神经元上的兴奋模式分布储在网络上；2.信息处理是通过神经元之间同时相互作用的动态过程来完成的。

中文名 神经网络算法 外文名 Neural network algorithm

---