河南科技大学第九届数学建模F题.doc

F题 物流与选址问题摘要根据现代物流业的发展速度，在日常激烈的竞争下，如何合理有效的采取以最低耗、最节能、最环保、最快捷的物流运输方式实现公司的盈利最大化和满足广大用户对该物资的日益需求，我们将借助于一些数学模型，利用基本的数学知识联系实际问题作出相关符合要求的解答。 问题一: 在中心仓库尚未正常投入使用之时或因特殊情况发生状况,生产工厂担负着生产物资及为全省所有城市输送物资的双重角色。为求使两个生产工厂的总花费最小时对应的生产工厂的选址及规模，在此选用混合整数规划模型。为了简化求解，做了相关假设，使得最小总费用只受各个城市需求、生产工厂的生产力、各工厂对该省所有城市生产物资的提供量非负等的条件约束，并借助计算机编程语言C+将该混合整数规划模型转化为计算机语言，继而可借助计算机进行求解。 问题二：根据物流中心仓库布局的方案，建立目标函数来求选址的最优解，即中库数目与选址最佳方案。我们根据如下的假设：生产工厂的位置已经确定，而且它的生产能力能够充分满足市场的需要的前提下，各零售店或者用户的位置和销售量也已经确定，得出所需模型，再进一步利用假设得出的混合整数规划的数学模型来求解。 问题三:生产工厂向中心仓库运货问题，需要考虑最短路径与最少运输车辆问题，以使成本降到最低。在假设的前提下，采用直达供货模型，这时0-1型混合整数规划模型，对规模比较大的实际问题，整数变量比较多，求解更是复杂，因此可将模型简化成为一个运输规划模型，然后用运输规划方法求解合理的运输路径方案；对于最少运输车辆问题，根据以往的车辆使用情况，将日常必要的车辆数量，根据概率折线图分析使用车辆数量段的概率分布规律，可以认为是泊松分布，根据泊松分布的特点，进而求解最佳车辆数目。问题四: 我们根据假设的相关具体数据、地图和铁路、公路、水路等相关信息选择10个中心仓库，其具体的相对生产工厂的距离用坐标表示，并利用混合整数规划模型及计算机matlab软件具体求解。一：问题重述该公司根据需要,计划在本省建设两个生产工厂和若干个物流中心仓库向全省所有城市供货。根据市场调研,全省有n个城市，每个城市单位时间需要该公司的物资量是已知的，有关运费的信息也是确定的，工厂和物流中心仓库的单位面积的建设费用和运营用已知，请你建立数学模型，回答以下问题:(1) 如何为两个生产工厂选址? （建多大规模？）(2) 建多少个物流中心仓库?分别建在什么地方? （ 分别建多大规模？）(3) 生产工厂如何向物流中心仓库供货?(4) 请你自己选用一组数据进行计算（可以根据假设、地图和铁路、公路、水路等信息选择有关数据），并对你的模型和结果作出评价。二：模型假设问题一作以下假设：1. 中心仓库尚未投入使用,全省各城市所需该公司的物资量仅从两个生产工厂直接配送；2. 任一工厂到全省任意城市的道路都是通的；3. 省内的各城市可以在任一工厂中获取部分该生产物资以满足需求。问题二作以下假设： 1. 生产工厂的位置已经确定，而且它的生产能力能够充分满足市场的需要; 2. 各零售店或者用户的位置和销售量已经确定； 3. 从工厂到物流中心仓库所需要的运输费用为，从物流中心仓库到零售点和用户的发送费用为，经营物流中心仓库所需要的管理费用是，模型的总的物流费用表示，即： 问题三作以下假设：1.运送的是同一种货物；2.各个中心仓库的坐标(x,y)量均及需求为已知；3.中心仓库的最低需求量大于生产工厂的发货起点限制；4.生产工厂有足够的运输能力，且任何一辆车不超载；5.每一辆车每天的总运行时间或者行驶里程不超过规定的上限。三：模型的提出与分析问题一：一、模型假设: 1. 中心仓库尚未投入使用,全省各城市所需该公司的物资量仅从两个 生产工厂直接配送； 2. 任一工厂到全省任意城市的道路都是通的； 3. 省内的各城市可以在任一工厂中获取部分该生产物资以满足需求。二、定义符号说明：第j个生产工厂最多所能生产的物资量 j=1,2: 第j个生产工厂的建厂投资 ：第j个生产工厂到第i个城市的单位物资的运费 i=1,2,n :第i个城市对物资的需求量三、模型建立： 设表示第j个生产工厂向城市i提供的物资量 混合整数规划模型：其中： 表示建设两个生产工厂的总费用 表示需求限制 表示生产力限制 表示非负限制四、模型求解 现在用计算机编程vc+软件求解#include using namespace std;#define MAXV 50#define INF 32767typedef int InfoType;typedef struct int no; InfoType info; VertexType;typedef struct int edgesMAXVMAXV; int n,e; VertexType vexsMAXV; MGraph; /弗洛伊德算法void Ppath1(int pathMAXV,int i,int j) int k; k=pathij; if(k=-1) return; Ppath1(path,i,k); Ppath1(path,k,j); void Dispath1(int AMAXV,int pathMAXV,int n) int i,j; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) continue; if(Aij=INF) Ppath1(path,i,j); void Floyd(MGraph g) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=k; Dispath1(A,path,g.n); /主函数int main() int i,j,n; MGraph g; while(true) cout请输入一个n的值：n; for(i=0;in;i+) for(j=0;jg.edgesij; cout建设这两个工厂的总费用最小为：endl; Floyd(g); coutendl; return 0; 问题二：一、 模型假设:1. 生产工厂的位置已经确定，而且它的生产能力能够充分满足市场的需要;2. 各零售店或者用户的位置和销售量已经确定；3. 从工厂到物流中心仓库所需要的运输费用为，从物流中心仓库到零售点和用户的发送费用为，经营物流中心仓库所需要的管理费用是，模型的总的物流费用表示，即： 二、 定义符号说明:备选物流中心仓库从生产工厂进货的数量；用户从备选物流中心仓库中转进货的数量；用户从生产工厂直达进货的数量；备选物流中心仓库是否选中的决策变量；备选物流中心仓库从生产工厂进货的单位物资进货费率；备选物流中心仓库向用户供货的单位物资发送费率；用户从生产工厂直达进货的单位物资进货费率；备选物流中心仓库选中后的基建投资费用；备选物流中心仓库中转单位物资的仓库管理费用;各生产工厂的供应总量；各用户的需求量。三、模型建立:多元单一物资物流中心仓库布局的数学模型在现实的物流系统中，大量存在的物流中心仓库布局是多元的，即在某计划区域内设置多个物流中心仓库，多元物流中心仓库选址的方法又可以分为两种类型: 一类是物流中心仓库无限制的情况，另一类是物流中心仓库有限制的情况。对于本题而言,我们只需解决第一类情况,即是 有限制的情况。多元单一物资物流中心仓库的布局问题，其网络结构如下图所示：假设为物流中心仓库布局方案的总成本，根据物流中心仓库布局的概念，应使总成本最低，于是有目标函数： 在这个模型中，各个生产工厂调出的物资总量不大于该生产工厂的生产、供应能力，各个用户调运进来的物资总量不小于它的需求量，则有如下的约束条件存在： (2.15) (2.16)其中：各生产工厂的供应总量；各用户的需求量。对于任何一个物流中心仓库，由于它既不能生产物资，也不消耗物资，因此每个物流中心仓库调进的物资总量应等于调出物资的总量，根据这一点，有如下的约束条件存在： 另外，物流中心仓库布局经过优化求解后的结果，可能有的备选地址被选中，而另外的一些被淘汰。被淘汰的备选物流中心仓库，经过它中转的物资数量为零。这一条件可由下面的约束条件满足： 其中：方程式中是一个相当大的正数。由于是物资调运量，不可能小于零，故a. 当为零时，成立；b. 当为1时，是一个相当大的正数； c. 足够大，为一有限值，所以不等式成立。综上所述，可以写出多元单一物资物流中心仓库布局的数学模型如下： k=1,2,3,m这是一个混合整数规划的数学模型，解这个模型可以求得和的值。表示了物流中心仓库的进货来源，决定了该物流中心仓库的规模；表示了物流中心仓库与用户的供求关系与供货量，相应地也就知道了该物流中心仓库的供货范围；而表示直达供货部分，为计划区域内应布局物流中心仓库的数目。四、模型求解:本题目标是:求解物流中心仓库最佳地点的问题就成为要使式所表示的总物流费用最小（）。为此，要确定：（1）物流中心仓库的数目m；（2）各个物流中心仓库的位置；（3）各个物流中心仓库的规模。问题三：一、模型的假设1.运送的是同一种货物；2.各个中心仓库的坐标及需求量均为已知；3.中心仓库的最低需求量大于生产工厂的发货起点限制；3.生产工厂有足够的运输能力，且任何一辆车不超载；4.每一辆车每天的总运行时间或者行驶里程不超过规定的上限；二、定义符号说明拥有上述需求要求的集合；能够满足中心仓库需求的集合；中心仓库的最低需求量；某种物资的需求总量；第个生产工厂的订发货起点限制值生产工厂自备车辆的使用费用；生产工厂自备车辆的闲置费用；生产工厂租用车辆费用；生产工厂配备的车辆数；生产工厂日常必要的车辆数量。三、问题分析与模型的建立本题是一个较为复杂的物流运输问题，即需要做相当多的一些合理假设。通过建立模型对运输费用的讨论，确定最优运输路径和最佳运输车辆数。1、最优运输路径的问题分析: 在按照经济区域组织物流配送时，一般网点的供货范围已经确定，这时的配送就是单网点配送。单网点配送问题中，生产工厂向所中心仓库送货，各中心仓库的容量为。假定以汽车作为发送工具仍以运输成本为最低目标。 2、最优路径数学模型的分析与建立:设为第个生产工厂的订发货起点限制值，由于调运模型中的决策变量不能小于订发货起点的限值，则有数学表达式： ；。考虑具有个供应点和个需求点的系统，可以得到以下直达供货调运模型 其中,表示供应量和需求量相等。 这是一个0-1型混合整数规划模型3、最佳运输车辆的问题分析:首选运输方式是汽车运输。这是由配送与汽车运输的共同特点决定的，汽车运输的最大优点是时间和空间上具有充分的自由性，不受路线和停车站的约束。生产工厂每天发货物的数量是一个变量，不能完全按照计划实行，以汽车数量量来说，如果拥有汽车数量过少，发货数量过多，就会出现车辆不足的现象，这时就要租用其它公司的车辆。相反，如果拥有汽车数量过多，发货量少时，就会出现车辆闲置的现象，增加成本。临时租用车辆会使得租金偏高，而且不能保证按质、按量、及时的拥有车辆；车辆闲置过多会造成资源浪费，富裕人员过多，造成工资成本偏高。最终，这两种情况都会造成配送成本升高，资源浪费，配送服务质量下降。这与物流系统总成本费用最低、服务质量最好的总目标是相违背的。4、最优运输车辆模型的分析与建立 模型设计步骤如下：如果，即日常必要的车辆数量比配置的车辆多，所需费用等于运行费用与租车费用之和 设为日常必要车辆数量对应的概率（将频率近似等于概率），则目标费用函数为：对目标费用函数两边的求导，得到如下方程式： 根据函数求极值的原理，令：，然后将目标函数整理得到： 利用方程式：将上式化简、整理得到： 其中频率累数当时，可以选取适当的值，使得上式成立，从而使得总的目标费用函数达到最小。只有当时，即自备车辆费用比租车费用低时，结论才能成立；当时，即自备车辆费用高于租车费用时，结论是没有意义的，此时，如果用自备车辆运输，运送成本将明显偏高，这时比较经济的做法是租车运送。四、模型的求解 1.如果能将混合整数规划模型中的整数变量去掉，简化成一个运输规划模型，那将是很有好处的。模型中 0-1整数变量的出现，是由于考虑了订货起点的限制而产生，为使模型简化，可以先暂不考虑订发货起点约束，用运输单纯法求解以后，再对优化方案作适当调整来满足这一约束。为了采用运输规划方法求解，还需要对其中不等式约束进行化简。不等式约束是由于用户的需求中有一部分具有质量及性能的特殊要求而形成的。如果用户的需求量是，其中有质量性能要求的部分是，假设该用户无质量要求的部分为，则有如下等式：因此，为了消除不等式约束，只需要将分成为两项：和，于是有如下等式存在： 当然，用以上方法求解 0-1型混合整数规划模型的调运问题，是以降低运输物流的效率为代价的，但这样做还是比直接采用混合整数规划求解简单。用这一方程组代替混合整数规划模型中的质量约束方程，即可消除原模型中的不等式。显然，当用户的需求量全部都有质量上的要求，这时，。通过以上分析和简化，混合整数规划调运问题可以用如下数学模型表示： 2. （1）根据以往的车辆使用情况，将日常必要的车辆数量进行分段。 （2）计算每个车辆数量段的出现频率。 （3）根据车辆数量段的出现频率，描绘出直方图，即在直角坐标系中，以坐标的横轴线表示车辆数量段，以纵轴表示每个车辆数量段出现的频率。 （4）根据直方图描绘出车辆数量段频率折线图，即在直方图的每个长方形的顶端中点（统计学中称为为组中值）放一个小圆点，然后将这些小圆点用折线连接起来，就形成了频率折线图。如果总次数逐渐增加，组距（车辆数量段）不断缩小，则频率折线图就会越来越光滑，变成为一条平滑曲线，简称为频率曲线。根据古典概率的特点，可以将各个车辆数量段的出现频率看成为各个车辆数量段出现的概率。 （5）根据概率折线图分析使用车辆数量段的概率分布规律。因为使用的车辆数量只能取整数，故可以得出第一个结论：使用车辆数量的概率分布是离散的。从使用的车辆数量概率折线图中，还可以观察到入下的规律：当（使用车辆数量段）值增加时，概率先是快速增加，达到极值，随后缓慢单调减少。这正是泊松分布的典型特点。（6）写出泊松分布的数学表达式：求出泊松分布的数学期望，则就是配送中心汽车车辆的最佳配置。问题四： 现在，我们根据假设、地图和铁路、公路、水路等相关信息选择10个中心仓库，其具体的相对生产工厂的距离用坐标表示，具体见以下的表格，并利用混合整数规划模型及计算机matlab软件具体求解：此时将2生产工厂和10个中心仓库向全省所有城市供货10个中心仓库的信息如下: 仓库编号中心仓库位置(千米)单位货物通过单位距离的运价(元)中心仓库需求量(千克)1（10，40）0.025102（50，100）0.03203（20，80）0.03254（60，20）0.04155（90，70）0.04306（50，10）0.02257（60，40）0.02258（70，70）0.025209（30，10）0.0351010（40，90）0.0320问题：各个生产工厂向哪些中心仓库运货使得路径最短？其中 a.中心工厂标号为1，2，5 分为一组，根据问题一的模型解对应的单源选址问题可得(u1,v1)=(62.034,70.111)；b.将标号为6，7，10 分为另一组，根据问题一的模型解对应的单源选址问题可得(u2,v2)=(56.672,42.832）根据问题二的模型可以求得生产工厂一和二分别据各个中心仓库的距离，如下表所示:仓库编号生产工厂一与中心仓库距离（千米）生产工厂二与中心仓库距离（千米）160.11846.758232.22157.556343.18252.214450.15223.073527.99642.998661.30433.503730.1824.37087.96730.261968.11442.3011029.68350.028用matlab软件绘制图形?x=60.118,32.221,43.182,50.152,27.996,61.304,30.182,7.967,68.114,29.683x = Columns 1 through 7 60.1180 32.2210 43.1820 50.1520 27.9960 61.3040 30.1820 Columns 8 through 10 7.9670 68.1140 29.6830?plot(x,g)?y=46.758,57.556,52.214,23.073,42.998,33.503,4.370,30.261,42.301,50.028y = Columns 1 through 7 46.7580 57.5560 52.2140 23.0730 42.9980 33.5030 4.3700 Columns 8 through 10 30.2610 42.3010 50.0280?plot(y,b)以下是运用matlab软件得出的图形，表示生产工厂一、二分别向10个中心仓库供货的总费用的关系：根据图形所示将10个中心仓库重新分为2组：A=2，3，5，8，10B=1,4,6,7,9 此时解对应的两个单源选址再重复上述过程即可得到 C(i)的具体计算结果如下表最优分组中心仓库编号生产工厂一向中心仓库的供货费(元)生产工厂二向中心仓库的供货费(元)A组218.67481.411336.53169.377535.79763.377818.42054.1421018.08772.511B组162.93947.895462.5757.261672.7609.104746.62222.519977.14924.446 四、模型评价 本文在建立模型时，针对不同的问题建立不同的模型，使计算得到简化，分析条理清晰。所建模型在实际应用中有一定的用途。物流选址问题所建模型通过对生产工厂以及对中心仓库的地理位置的假设，进而确定位置所在，降低建设费用。再考虑到运输路径问题，考虑不