管理运筹学运输问题.ppt

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

1、运输问题运输问题运输问题（TransportationProblem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一。从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法——表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法§1运输问题及其数学模型§1运输问题及其数学模型设某种物资共有m个产地A1，A2，…，Am，各产地的产量分别是a1，a2，…，am；有n个销地B1，B2，…，Bn，各

2、销地的销量分别为b1，b2，…，bn.假定从产地Ai（i=1，2，…，m）向销地Bj（j=1，2，…，n）运输单位物资的运价是cij，问怎样调运才能使总运费最小？一、运输问题的数学模型加速物资流转降低流通费用运输问题销地产地B1B2…Bn产量A1c11c21…c1na1A2c21c22…c2na2ミミミミミAmcm1cm2…cmnam销量b1b2…bn运输表1、产销平衡问题即设xij表示产地Ai运往销地Bj(i=1,2,…,m;j=1,2,…,n)的运量.销地产地B1B2…Bn产量A1x11c11x12c21…x1nc1na1A2x21c21x22c22…x2nc2na2

3、ミミミミミAmxm1cm1xm2cm2…xmncmnam销量b1b2…bnNote:cij在左下角xij在右上角§1运输问题及其数学模型2、产销不平衡问题当当运输问题二、运输问题数学模型的特点讨论产销平衡问题定理1平衡运输问题必有可行解，也必有最优解.证明定理2平衡运输问题的约束方程系数矩阵A和增广矩阵的秩相等，且等于m+n-1.即定理2说明：基可行解包含m+n-1个基变量.定理3平衡运输问题的约束方程系数矩阵A的所有各阶子式只取0，1或-1三个值.定理4如果平衡运输问题中的所有产量ai和销量bj都是整数，那么，它的任一基可行解都是整数解.note定理1的证明Proof:

4、则取显然有，又所以，是问题的一个可行解.又因为，对于任一可行解有目标函数值，对于求极小化问题，目标函数值有下界，则必有最优解.§1运输问题及其数学模型Note:平衡运输问题有个变量，个约束条件，规模很大。Goback运输问题定义1凡是能排列成（其中互不相同，互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点.B1B2B3B4B5A1x11x12x13x14x15A2x21x22x23x24x25A3x31x32x33x34x35A4x41x42x43x44x45如：变量集合变量集合2、每一行（或列）若有闭回路的顶点，则有两个顶点；3、每两个顶点格子的

5、连线都是水平的或垂直的；4、闭回路中顶点的个数必为偶数.闭回路的几何特征：1、每一个顶点格子都是90°转角点；§1运输问题及其数学模型闭回路的代数性质：性质1构成闭回路的变量组对应的列向量组必线性相关.证明性质2分组构成闭回路，则该变量组对应的列向量组是线性相关的.推论1若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.若变量组中有一个部Goon性质1的证明Proof:由直接计算可知故该向量组线性相关.运输问题在变量组中，若有某一个变量xij是它所在的行（第i行）或列（第j列）中出现于（*）中的唯一变量，则称该变量xij是该变量组的一个孤立点.定义2闭回路的特征

6、性质3没有孤立点若一变量组中不包含任何闭回路，则该变量组必有孤立点.孤立点不会是闭回路上的点定理5变量组对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.定理5的证明Proof:用反证法设变量组（*）对应的列向量组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，则由性质2知，这些变量对应的列向量必线性相关，与假设矛盾.定理5变量组对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.设有一组数使得由于变量组（*）中不包含任何闭回路，由性质3可知其中必有孤立点，不妨设为孤立点，又不妨设是（*）在第i1行上唯一的变量，这时由pij的特征，（1）的

7、左端第i1个分量和为k1，而右端为0，但仍不包含闭回路，其中还有孤立点,与前面类似分析可证k2=0.同理得k3=k4=…=kr=0这就证明了向量组（*）线性无关.§1运输问题及其数学模型推论2平衡运输问题中的一组m+n-1个变量能构成基变量的充要条件是它不包含任何闭回路.该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路.这就是基可行解在运输平衡表上的一个表现，利用它来判断m+n–1个变量是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多.利用