运筹学--第三章 运输问题

《运筹学--第三章 运输问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学第三章运输问题引入我们已经讨论了线性规划的一般形式以及求解的方法。但是在实际工作中，常常碰到很多线性规划问题，由于它们的约束条件变量的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的方法求解，从而可大量节约计算的时间和费用。运输问题一、运输问题的实例和数学模型1、运输问题的实例人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题。例3-1现有A1，A2，A3三个产粮区，可供应粮食分别

2、为10，8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/吨）如表3－1所示，问如何安排一个运输计划，使总的运输费用最少。地区产粮区B1B2B3B4产量A1326310A253828A341295需要量578323运价表（元/T）表5-1产地销地A110A28A35B43B38B27B15354231682329例3-1【解】设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：（1）使总的运输费用最小，则目标函数为：（4）运量应大于或等于零（非

3、负要求），即（2）各产地粮的供应量与运出量要平衡:（3）供给各需求地的供给量与需求量的平衡:请大家试着写出约束条件的系数矩阵运输问题一、运输问题的实例和数学模型例3-2某食品公司经销的主要产品之一是糖果。它下面设有三个加工厂，每天的糖果生产量分别为：A1-7t，A2-4t，A3-9t。该公司把这些糖果分别运往四个地区的门市部销售，各地区每天的销售量为：B1-3t，B2-6t，B3-5t，B4-6t。已知从每个加工厂到各销售门市部每吨糖果的运价如表3-2所示，问该食品公司应如何调运，在满足各门市部销售需要的情况下，使总的运费支出为最少？运输问题一、运输问题的实例和数学模型例3-2

4、门市部加工厂B1B2B3B4供给量A13113107A219284A3741059销售量365620表3-2练习：请大家自行列出例3-2描述的运输问题的线性规划模型。约束条件的系数矩阵为：确定行数=？列数=？通过实例概括问题：在线性规划中我们研究的运输问题是：有某种物资需要调运，这种物资的计量单位可以是重量、包装单位或其他。已知有m个地点可以供应该种物资（以后统称产地，用i=1，…,m表示）；这m个产地的可供量（称为产量）为a1，a2,…，am（通写为ai）；有n个地点需要该种物资（以后统称销地，用j=1，…，n表示）；这n个销地的需要量（通称为销量）分别为b1，b2，…，bn

5、（通写为bj）；从第i个产地到第j个销地的单位物资运价为cij。怎样调运这些物品才能使总运费最小？上面这些数据通常用产销平衡表5-3和单位运价表5-4来表示。表3-3产销平衡表销地产地12…n产量1a12a2……mam销量b1b2…bn平衡?表3-4单位运价表销地产地12…n1c11c12…c1n2c21c22…c2n……………mcm1cm2…cmn一、运输问题的实例和数学模型2、运输问题的数学模型如果用xij代表从第i个产地调运给第j个销地的物资的单位数量，那么在产销平衡的条件下，使总的运费支出最小，可以表示为数学形式：这就是运输问题的数学模型，包含：m×n个变量m+n个约束

6、条件约束条件的系数矩阵A有m+n行m×n列所有销地的某物资的运输量之和=该物资在某产地的供给量（产量）某销地的所有物资的运输量之和=该物资在某销地的需求量（销售量）一、运输问题的实例和数学模型2、运输问题的数学模型建立了运输问题的数学模型，我们发现运输问题的数学模型仍然是线性规划模型，但是与我们以前所学习的模型相比，又有它独有的一些特点。自己总结一下。那么如何来求解运输问题呢？我们的思路与一般的线性规划问题的求解思路是一样的。即：寻找基及基解→判断是否最优→否→则继续寻找下一个基及基本解→重复直到最优解找到或确定无最优解。一、运输问题的实例和数学模型2、运输问题的数学模型从单纯

7、形法中，我们了解到：寻找初始基及基本解，要从约束条件的系数矩阵出发，确定系数矩阵的秩，并在系数矩阵中确定满秩的单位子矩阵，从而确定初始基本解。运输问题也是线性规划问题，我们根据以往的经验来看看它的系数矩阵、系数矩阵的秩等有什么特点。这就是运输问题的数学模型，包含：m×n个变量m+n个约束条件约束条件的系数矩阵A有m+n行m×n列:1…111…1…11…11…111…1…11…1m行n行运输问题模型的系数矩阵有m+n行、m×n列，那么系数矩阵的秩=？因为m+n