物流运输与配送管理 教学课件 作者 杜文 13.ppt

《物流运输与配送管理 教学课件 作者 杜文 13.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13章运输问题（TransportationProblem）在线性规划问题中，有一类特殊类型的问题－－运输问题。这类问题主要研究把某种物资从若干个产地调运到若干个销地，每个产地的供应量和每个销地的销售量及从一个产地到一个销地的运输费用已知，要求确定一个总运费最少的方案。第13章运输问题（TransportationProblem）13.1物资调配问题（MaterialTransferringProblem）13.1.1运输问题及数学模型（ModelforTransportation）13.1.2用表上作业法求解运输问题（SolveTran

2、sportationProblembyTable）13.1.3运输问题的进-步讨论（FurtherDiscussionaboutTransportationProblem）13.1.4应用问题举例（Parexample）13.2网络流问题（NetworkFlowProblem）13.2.1图的基本概念（ConceptoftheDagram）13.2.2最短路（ShortPath）13.2.3最大流问题（TheMaximumFlowProblem）13.2.4最小费用最大流问题（TheMinimumCostsandMaximumFlowPro

3、blem）13.1物资调配问题在经济建设中，经常会碰到大宗物资调运问题，如煤、钢铁，木材、粮食等物，在全国有若干生产基地，根据已有交通网络，应如何制订调运方案，将这些物资运到各销售地点，而运费最小，效率最高。在物流系统中，物资的调拨和配送是物流管理决策的一项主要工作。在市场经济条件下，对资源实行市场实行优化配置，有利于国民经济持续发展。13.1物资调配问题13.1.1运输问题及数学模型本章研究单一品种物资的运输调度问题。其典型情况是：设某种物品有个产地（或供方）Ai（i=1，2，…，m），各产地的产量分别是ai（i=1，2，…，m），有n个

4、销地Bj（j=1，2，…，n）,各销地的销量分别为bj（j=1，2，…，n）。假定从Ai（i=1，2，…，m）产地向销地Bj（j=1，2，…，n）运输单位物品的运价是。问怎样调运这些物品才能使总运费最小?1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型这是由多个产地供应多个销地的单品种物品运输问题。为直观起见，可列出该问题的运输表（见下页）。表中的变量Xij（i=1，2，…，m；j=1，2，…，n）为由产地Ai运往销地Bj的物品数量。cij为Ai到Bj的单位运价。有时，将单位运价单独列入另一个表中，并称其为运价表。1.

5、运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型1.运输问题数学模型运输单价cij销售地Bi供应量B1B2…Bnai产地AiA1c11c12…c1na1A2c21c22…c2na2┆┆┆…┆┆Amcm1cm2…cmnam销售量bjb1b2…bn分布变量表A1x11x12…x1nA2x21x22…x2n┆┆┆…┆Amxm1xm2…xmn13.1物资调配问题13.1.1运输问题及数学模型1.运输问题数学模型如果运输问题的总产量等于其总销量，即有则称该运输问题为产销平衡运输问题；反之，称产销不平衡运输问题。13.1物资调配问题1

6、3.1.1运输问题及数学模型1.运输问题数学模型产销平衡运输问题的数学模型可表示如下：其中，约束条件右侧常数ai和bj满足13.1物资调配问题13.1.1运输问题及数学模型在上页模型中，目标函数表示运输总费用极小化；前m个约束条件的意义是：由某一产地运往各个销地的物品数量之相等于该产他的产量；中间n个约束条件指：由各产地运往某一销他的物品数量之和等于该销地的销量。1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型该模型属于线性规划问题。单纯形法是求解线性规划问题十分有效的一般方法。因而可用单纯形法求解上述运输问题。但是，

7、当用线性规划的单纯形法求解运输问题时，先得在每个约束条件中引入一个人工变量，这样一来，即使对于m＝3,n＝4这样简单的运输问题，变量数目也会达到19个之多(未考虑去掉一个多余约束条件)，因而需要寻求更简便的解法。1.运输问题数学模型13.1物资调配问题13.1.1运输问题及数学模型（1）运输问题有有限最优解2.运输问题数学模型的特点对前述运输问题，若令其变量其中，，则xij就是前述述运输问题的一个可行解；另一方面，其目标函数有下界。目标函数值不会趋于-∞。由此可知，运输问题必存在有限最优解。13.1物资调配问题13.1.1运输问题及数学模型

8、（2）运输问题约束条件的系数矩阵2.运输问题数学模型的特点13.1物资调配问题13.1.1运输问题及数学模型即除第i个和第m+j个分量为l外，其它分量全等于0。（2）运输问题约束