运筹学学习(自制笔记)第3章 运输问题

第3章运输问题3.1标准运输问题及模型3.1.1标准运输问题：某种物资有m个产地Ai（i=1,2,…,m）,产量分别为ai，另有n个销地Bj（j=1,2,…,n），销量（需求量）分别为bj，现在需要把这种物资从各个产地运送到各个销地，已知从Ai到Bj的单位运价(或运距)为cij，假定产量总数等于销量总数，即11mnijijab,问就如何组织调运，才能使总运费（或总运输量）最省?3.1.2标准运输问题的有关信息表单位运价销地或运距产地B1B2…Bn产量A1c11c12…c1na1A2c21c22…c2na2………………Amcm1cm2…cmnamb1b2…bn11mnijijab3.1.3标准运输问题的数学模型设xij为从产地Ai运到销地Bj的物资数量（i=1,2,…,m；j=1,2,…,n），由于从Ai运出的物资总量等于Ai的产量，运到的物资总量等于的销量，得模型如下：minZ=11mnijijijcxs.t.1nijijxa1mijjixb0ijx且有11mnijijabQ即满足产销平衡条件，故此模型描述的是产销平衡运输问题。3.1.4标准运输问题的特点⑴平衡条件下的运输问题必有最优解此问题是一个有m×n个变量，m+n个等型约束条件的线性规划最小化问题，由于目标函数不可能为负，故有下界存在，而/ijijxabQ是问题的一组可行解，因此一定有最优解。既是线性规划问题，无疑可用单纯形法求解，但其数学模型自身结构有其特殊性，可以利用更简便的表上作业法求解。⑵标准运输问题约束方程组的系数矩阵运输问题是一个具有m×n个变量，m+n个等型约束条件的线性规划问题，问题的约束方程组的系数矩阵A是一个只有0和1两个数值的稀疏矩阵，ijx对应的列ijP只有第i行和第m+j行为1，其余各行皆为0。⑶标准运输问题的基变量总数为m+n-1。可以证明系数矩阵A和增广矩阵A′的秩为m+n-1。增广矩阵A′的前m行相加之和减后n行相加之和等于0，说明m+n个行向量线性相关，A′和A的秩都小于m+n；另外，可以在A′中找出一个行列式的值不为0的m+n-1阶方阵D(取第二行至第n行的前n列及1ix所在的列，其中i=2，3，…m,得到一个副对角线上为两单位矩阵，上方为零矩阵的矩阵，显然，此矩阵满秩)，所以,A′和A的秩为m+n-1。⑷m+n-1个变量构成基变量的充要条件是它们不构成回路。运输模型中能排列成｛111222231,,,,,jsssiijijijijijxxxxxx｝的变量组称为一个闭回路，其中i1,i2,…is互不相同，j1,j2,…js也互不相同，出现在组中的变量称为回路的顶点。由于ijx所对应的列向量ijP仅有第i行和m+j行为1，其余各行皆为0,所以很容易得出1112222310jsssiijijijijijPPPPPP所以，若变量组112233,,,jssiijijijxxxx中若有一部分构成回路，则变量组所对应的系数列向量组必线性相关。若变量组中不含任何闭回路，则变量组中至少有一变量的行标或列标只出现一次，即变量组中必有孤立点。若有孤立点rrijx则变量组所对应的所有列向量中只有rrijP的ir行或第m+jr行为1，其余各列向量的第ir行或第m+jr行皆为0，变量组所对应的系数列向量组必线性无关。故得结论变量组对应的系数列向量线性无关变量组不含任何回路又m+n-1个变量对应的系数列向量线性无关此m+n-1个变量构成基变量所以，m+n-1个变量构成基变量的充要条件是它们不构成回路。3.2运输问题的表上作业法表上作业法也是一种迭代法，它的基本思想是：先设法找出一个初始方案，然后对方案进行检验、调整，直到得出最优方案。这和单纯形法的思想完全一致，但是具体的作法则更加简捷。3.2.1初始方案的确定将决策变量ijx填入运输信息表的ijc所在表格（可将ijc填入右下角而将ijx填入中央），得到所谓的“作业表”，下面的操作均在作业表中进行。确定初始方案就是找出一个初始基可行解，即定出m+n-1个变量并赋予它们非负的值，除这m+n-1个变量外，其余变量的值皆为0，且这m+n-1个变量所对应的系数列向量线性无关。由于上节已证明m+n-1个变量所对应的系数列向量线性无关的充要条件是这m+n-1个变量不包含任何回路，因此，只要定出这m+n-1个变量的方式能保证它们不包含任何回路即可得出这m+n-1个变量线性无关。由于总变量数为m×n个，当m和n取值较大时m×n远大于m+n-1，且任一变量ijx均出现在两个约束中，为保证所有变量值非负，ijx的取值不能大于ia和jb，所以，可以考虑用“满值法”，即选择一个变量ijx，取min,ijijxab。具体作法是：在作业表中，按某种规则选择一个ijx，若ijab则取ijixa，将ijx用所取的具体值替换，划除第i行其它变量（除前面已经定出的变量外），并将jb变为jb－ia；若jiba，则取ijjxb，划除第j列其它变量（除前面已经定出的变量外），并将ia变为ia－jb，然后再在剩余的变量按某种规则选择另一个变量，再运用同样的方法，最后得出m+n-1个变量和它们的取值,以这m+n-1个变量为基变量（后面将证明它们确实可以构成基变量），其余被划除的变量为非基变量，均取值为0，此时的ia和jb都已经变为0，即产销已经达到平衡。在上述操作中可能会遇到两种特殊情况：一种是ijab，此时可以划去行也可以划去列，但不能同时划去；另一种情况是产销已达平衡，但选取的变量个数未达m+n-1，此时可将选取未划去的变量，并取值为0。可以证明，用“满值法”得到的解是基可行解，证明如下：假设用“满值法”选定的m+n-1个变量可以包含某一个回路，那么取这个回路中最先定出的一个变量ijx，这个变量必与后来定出的一个变量同行另一个变同列，这和定出变量ijx后划除了第i行或第j列的其它变量（除前面已经定出的变量外）相矛盾，所以用“满值法”定出的m+n-1个变量不包含任何回路，所以这m+n-1个变量对应的系数列向量线性无关，即这m+n-1个系数列向量是系数矩阵的一个基，而“满值法”既保证了所有约束的成立又保证了所有变量取值非负，所以用“满值法”得出的解为基可行解，于是初始方案得以确定。3.2.2最优性检验检验初始方案是否最优方案的过程就是最优性检验。检验的方法仍然是计算非基变量的检验数，因为是最小化问题，若检验数均大于等于0，则此方案为最优方案，若有非基变量的检验数小于0，则可以通过适当加大此非基变量的取值而得另一可行解，此解下目标函数有所改进（变得更小），故此方案非最优方案。