5-1运输问题模型与性质

运筹学（OR:operationalresearch(英)\operationsresearch(美)）第5章运输问题——特殊的线性规划问题&模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广产销不平衡的运输问题转运问题5.1运输问题模型与性质一、运输问题的数学模型1、运输问题的一般提法：设某种物品有m个产地A1,A2,...,Am，对应的产量分别是a1,a2,...,am；有n个销地B1,B2,...,Bn，销量分别为b1,b2,....bn。假定从产地Ai(i=1,2,…,m)向销地出Bj(j＝l,2,….n)运输单位物品的运价是cij，问怎样调运这些物品才能使总运费最小.运输问题网络图s3=19s2=27s1=14供应量231供应地运价d1=22d2=13d3=12d4=13需求量2341需求地6753784259106产销平衡：供应量＝需求量表5-1运价表单位运价销或运距地产地B1B2…Bn产量A1A2┆Amc11c12…c1nc21c22…c2n………cm1cm2…cmna1a2┆am销量b1b2…bnnjjmiiba112、运输问题的数学模型设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：miaxnjiij,,2,11同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：总运费为：mijijnjbx1,,1minjijijxcz11运输问题的数学模型minjjiba11产销平衡条件二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构系数矩阵A的形式如下：mnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211111111111111111111m行n行矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。将该矩阵分块，特点是：前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）；后n行构成m个n阶单位阵。2.运输问题的基变量总数是m+n-1写出增广矩阵nmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211证明系数矩阵A及其增广矩阵的秩都是m+n-1前m行相加之和减去后n行相加之和结果是零向量()，说明m+n个行向量线性相关，因此的秩小于m+n；？()AA因此的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1由的第二至m+n行和前n列及对应的列交叉处元素构成m+n-1阶方阵D非奇异；？A13121,,,mxxxnjjmiiba11nmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,,,,,,,,,;,,,21222211121101011111111111111mD）（按第一列展开可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。产销平衡运输问题数学模型的特征：1.产地：m个；2.销地：n个；3.变量：m×n个；4.约束条件：m+n个；5.约束矩阵具有：分布稀疏性，排列规律性，数据单一性（0或1）；6.约束矩阵的秩：r=m+n–1;7.基变量个数：m+n–1；8.非基变量个数：m×n–(m+n–1)。