数学建模---第四章-运输问题CombinatorialOptimizationTheory第四章运输问题运输问题（TransportationProblem，简记为TP）是一类常见而且极其特殊的线性规划问题.它最早是从物资调运工作中提出来的，是物流优化管理的重要的内容之一从理论上讲，运输问题也可用单纯形法来求解，但是由于运输问题数学模型具有特殊的结构，存在一种比单纯形法更简便的计算方法表上作业法，用表上作业法来求解运输问题比用单纯形法可节约计算时间与计算费用.但表上作业法的实质仍是单纯形法加速物资流转降低流通费用运输问题及其数学模型设某种物资共有2半岛官方网站，…，n）运输单位物资的运价是cij，问怎样调运才能使总运费最小？一、运输问题的数学模型ijabcimj第四章运输问题销地产地运输表1、产销平衡问题ij表示产地A(i=1,2,…,m;j=1,2,…,n)的运量.ijij01,2,,;1,2,,ij销地产地ij在左下ij在右上角运输问题及其数学模型2、产销不平衡问题ijij01,2,,;1,2,,ijijij01,2,,;1,2,,ij第四章运输问题二、运输问题数学模型的特点讨论产销平衡问题定理平衡运输问题必有可行解，也必有最优解.证明定理平衡运输问题的约束方程系数矩阵A和增广矩定理2说明：基可行解包含m+n-1个基变量.定理平衡运输问题的约束方程系数矩阵A的所有各阶子式只取0，1-1三个值.定理都是整数，那么，它的任一基可行解都是整数解.证明noteGo的证明Proofijijab则取显然有所以，是问题的一个可行解.0(1,2,,;1,2,,)ij又因为，对于任一可行解有目标函数值，对于求极小化问题，目标函数值有下界，则必有最优解.运输问题及其数学模型Note平衡运输问题有个变量，个约束条件，规模很大。mn111212122mmmnxxxxxxxxxGoback的证明Proof的任一基可行解，1122mnmnijij为对应的基矩阵，则det(1,2,dettt1212，因此，都是整数.ttijxtmn其基变量为第四章运输问题定义凡是能排列成11122223ijijijijijijxxxxxx（其中互不相同，互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点.xxxxxx变量集合12、每一行（或列）若有闭回路的顶点，则有两个顶点；3、每两个顶点格子的连线、闭回路中顶点的个数必为偶数.闭回路的几何特征：1、每一个顶点格子都是90转角点；运输问题及其数学模型闭回路的代数性质：11122223ijijijijijijxxxxxx性质1构成闭回路的变量组对应的列向量组11122223ijijijijijijpppppp必线分组构成闭回路，则该变量组对应的列向量组1122rrijijij是线若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路.若变量组中有一个部1122rrijijijxx的证明Proof由直接计算可知11122223ijijijijijijpppppp111212122mmmnxxxxxxxxx故该向量组线性相关.第四章运输问题在变量组中，若有某1122rrijijijxx一个变量xij是它所在的行（第i中出现于（*）中的唯一变量，则称该变量xij是该变量组的一个孤立点.定义2xxxxxxxx闭回路的特征性质3没有孤立点若一变量组中不包含任何闭回路，则该变量组必有孤立点.反证孤立点不会是闭回路上的点定理5变量组对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路.证明定理的证明Proof用反证法设变量组（*）对应的列向量组线性无关，但该变量组包含一个以其中某些变量为顶点的闭回路，则由性质2知，这些变量对应的列向量必线性相关，与假设矛盾.定理5变量组对应的列向量组线性无关的充要设有一组数使得1122rrijijrijkpkpkp由于变量组（*）中不包含任何闭回路，由性质3可知其中必有孤立点，不妨设为孤立点，行上唯一的变量，这时由pij的特征，（1）的左端第i列上的唯一变量如何？22rrijrij仍不包含闭回路，其中还有孤立点,2233rrijijij运输问题及其数学模型推论2平衡运输问题中的一组m个变量能构成基变量的充要条件是它不包含任何闭回路.1122ssijijijxxxsmn该推论给出了运输问题的基可行解中基变量的一个基本特征：基变量组不含闭回路.这就是基可行解在表上的一个表现，利用它来判断个变量是否构成基变量组，就看它是否包含闭回路.这种方法简便易行，它比直接判断这些变量对应的列向量是否线性无关要简便得多.利用基变量的这个特征，将可以导出求平衡运输问题的初始基可行解的一些简便方法.运输问题的表上作业法表上作业法（又称运输单纯形法）是根据单纯形法的原理和运输问题的特点，设计的一种在表上运算的求解运输问题的简便而有效的方法.主要步骤：1、求一个初始调运方案（初始基可行解）；2、判别当前方案是否为最优，若是则迭代停止，否则转下一步；3、改进当前方案，得到新的方案（新的基可行解），再返回2第四章运输问题一、初始方案的确定1、西北角法50251015Ex.50已知某商品有三个产地A，产量、销量及单位运价如表.问应如何调运，在满足各销地需要的情况下，使总的运费支出为最少？101020规则:从运输表的西北角开始,优先安排编号小的产地和销地的运输任务.填了几个数字？105010675在填入一个数时，如果行和列同时饱和，规定只划去一行或一列5025101550运输问题的表上作业法2、最小元素法50251015规则:优先安排单位运价最小的产地与销地之间的运输任务.0620在某行（或列）填入最后一个数时，如果行和列同时饱和，规定只划去该行（或列）