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

第三章运输问题——特殊的线性规划&运输问题的模型及其特点&求解思路及相关理论&求解方法——表上作业法&运输问题的推广产销不平衡的运输问题转运问题指派问题3.1运输问题模型与性质一、运输问题的数学模型1、运输问题的一般提法：某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？单位根据具体问题选择确定。表3-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运输问题的数学模型njmixnjbxmiaxtsxcMinZijmijijnjiijminjijij,,1;,1,0,,1,,1..1111（3-1）minjjiba11产销平衡条件二、运输问题的特点与性质1．约束方程组的系数矩阵具有特殊的结构写出式（3-1）的系数矩阵A，形式如下：mnmmnnxxxxxxxxx,,,,,,,,,;,,,212222111211111111111111111111m行n行矩阵的元素均为1或0；每一列只有两个元素为1，其余元素均为0；列向量Pij=(0,…，0，1，0，…,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前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证明系数矩阵A及其增广矩阵的秩都是m+n-1AnmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,,,,,,,,,;,,,21222211121101011111111111111mD）（按第一列展开可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。定义3.1凡是能排成(3-4)或(3-5)形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中互不相同,互不相同。132222111,,,,,jijijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,,,,,siii,,,21sjjj,,,213.m+n-1个变量构成基变量的充要条件是它们不构成闭回路。X11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34例3-1设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路在表中的表示法——用折线连接起来的顶点变量。},,,,,{212434331311xxxxxx练习3-1请给出闭回路和在表中的表示法。},,,{14242212xxxx},,,,,{121131332322xxxxxxX11X13X21X24X33B1B2B3B4A1X12X14A2X22X23A3X31X32X34练习3-2下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什么？（a）（b）（c）（d）（e）表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的；为什么？表中的每一行和每一列由折线相连的闭回路的顶点只有两个；为什么？有关闭回路的一些重要结果定理3-1设是一个闭回路，则该闭回路中的变量所对应的系数列向量具有下面的关系：132222111,,,,,jijijijijijisssxxxxxx132222111,,,,,jijijijijijisssPPPPPP0132222111jijijijijijisssPPPPPP注意：列向量Pij=(0,…,0,1,0,…,0,1,0,…0)T中两个元素1分别处于第i行和第m+j行，直接计算即可得到结果。定理的证明可借助定理3-1和高等代数中“向量组中，若部分向量线性相关，则整个向量组就线性相关”的定理得到。定理3-2若变量组中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。rrjijijixxx,,,2211定理3-3不包含任何闭回路的变量组中必有孤立点。所谓孤立点是指在所在行或列中出现于该变量组中的唯一变量。可用反证法证明结论成立。定理3-4r个变量对应的系数列向量线性无关充要条件是该变量组不包含闭回路。rrjijijixxx,,,2211必要性的证明可考虑用反证法结合定理3-2的结果进行，充分性的证明可借助定理3-3，根据向量组线性无关的定义用归纳法得证。推论m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。三、运输问题的求解方法1、单纯形法（为什么？）2、表上作业法由于问题的特殊形式而采用的更简洁、更方便的方法