《运筹学学习(自制笔记)第3章 运输问题》由会员分享，可在线阅读，更多相关《运筹学学习(自制笔记)第3章 运输问题（6页珍藏版）》请在装配图网上搜索。
1、第3章 运输问题3。1标准运输问题及模型.11标准运输问题:某种物资有个产地Ai（i=,2，,），产量分别为i,另有n个销地（j1，2,n），销量（需求量)分别为bj，现在需要把这种物资从各个产地运送到各个销地，已知从Ai到B的单位运价(或运距)为cij,假定产量总数等于销量总数，即,问就如何组织调运,才能使总运费（或总运输量）最省？3.1.2标准运输问题的有关信息表单位运价 销地或运距产地B12Bn产量A1c11c c n12c 21 2c 2na2Amcm1c m2 mamb1b2b3.1。3标准运输问题的数学模型 设xi为从产地Ai运到销地Bj的物资数量（i=1,，m;=1,，n)，由于
2、从Ai运出的物资总量等于的产量，运到的物资总量等于的销量，得模型如下： miZ= st. 且有 即满足产销平衡条件，故此模型描述的是产销平衡运输问题。3.1。4标准运输问题的特点平衡条件下的运输问题必有最优解此问题是一个有mn个变量，m+n个等型约束条件的线性规划最小化问题,由于目标函数不可能为负，故有下界存在，而是问题的一组可行解，因此一定有最优解。既是线性规划问题,无疑可用单纯形法求解，但其数学模型自身结构有其特殊性，可以利用更简便的表上作业法求解。标准运输问题约束方程组的系数矩阵运输问题是一个具有n个变量，m+个等型约束条件的线性规划问题，问题的约束方程组的系数矩阵A是一个只有0和1两个
3、数值的稀疏矩阵,对应的列只有第i行和第m+j行为，其余各行皆为0。标准运输问题的基变量总数为m+n1。可以证明系数矩阵A和增广矩阵A的秩为n1。增广矩阵A的前行相加之和减后行相加之和等于0,说明m+n个行向量线性相关，和的秩都小于m+n；另外，可以在中找出一个行列式的值不为0的+n1阶方阵（取第二行至第n行的前n列及所在的列，其中=，m，得到一个副对角线上为两单位矩阵,上方为零矩阵的矩阵，显然，此矩阵满秩),所以，A和A的秩为m+n-1。 +个变量构成基变量的充要条件是它们不构成回路。 运输模型中能排列成的变量组称为一个闭回路,其中1,i2，is互不相同，1，j2，也互不相同,出现在组中的变量
4、称为回路的顶点。 由于所对应的列向量仅有第i行和+j行为，其余各行皆为0，所以很容易得出 所以，若变量组中若有一部分构成回路，则变量组所对应的系数列向量组必线性相关。 若变量组中不含任何闭回路,则变量组中至少有一变量的行标或列标只出现一次,即变量组中必有孤立点。若有孤立点则变量组所对应的所有列向量中只有的r行或第m+jr行为1，其余各列向量的第ir行或第m+j行皆为,变量组所对应的系数列向量组必线性无关。 故得结论又 所以，n1个变量构成基变量的充要条件是它们不构成回路。3.2运输问题的表上作业法表上作业法也是一种迭代法，它的基本思想是：先设法找出一个初始方案，然后对方案进行检验、调整，直到得
5、出最优方案.这和单纯形法的思想完全一致，但是具体的作法则更加简捷.2.1初始方案的确定 将决策变量填入运输信息表的所在表格(可将填入右下角而将填入中央)，得到所谓的“作业表”,下面的操作均在作业表中进行。确定初始方案就是找出一个初始基可行解,即定出m+n-1个变量并赋予它们非负的值，除这+n1个变量外，其余变量的值皆为0，且这+n-个变量所对应的系数列向量线性无关。由于上节已证明+n-1个变量所对应的系数列向量线性无关的充要条件是这m1个变量不包含任何回路，因此，只要定出这m+n1个变量的方式能保证它们不包含任何回路即可得出这1个变量线性无关。由于总变量数为mn个，当m和n取值较大时mn远大于
6、m+1，且任一变量均出现在两个约束中,为保证所有变量值非负,的取值不能大于和，所以，可以考虑用“满值法，即选择一个变量,取。具体作法是:在作业表中，按某种规则选择一个,若则取，将用所取的具体值替换，划除第i行其它变量(除前面已经定出的变量外）,并将变为；若，则取,划除第列其它变量（除前面已经定出的变量外），并将变为，然后再在剩余的变量按某种规则选择另一个变量，再运用同样的方法，最后得出+n1个变量和它们的取值，以这m+-1个变量为基变量（后面将证明它们确实可以构成基变量），其余被划除的变量为非基变量，均取值为，此时的和都已经变为0，即产销已经达到平衡。在上述操作中可能会遇到两种特殊情况：一种是
7、，此时可以划去行也可以划去列,但不能同时划去;另一种情况是产销已达平衡，但选取的变量个数未达+n1，此时可将选取未划去的变量，并取值为0。可以证明，用“满值法”得到的解是基可行解，证明如下：假设用“满值法”选定的m+n1个变量可以包含某一个回路，那么取这个回路中最先定出的一个变量，这个变量必与后来定出的一个变量同行另一个变同列，这和定出变量后划除了第i行或第j列的其它变量（除前面已经定出的变量外)相矛盾，所以用“满值法定出的+。个变量不包含任何回路，所以这n个变量对应的系数列向量线性无关,即这m+n.-1个系数列向量是系数矩阵的一个基,而“满值法”既保证了所有约束的成立又保证了所有变量取值非负,所以用“满值法”得出的解为基可行解,于是初始方案得以确定。32.最优性检验检验初始方案是否最优方案的过程就是最优性检验。检验的方法仍然是计算非基变量的检验数，因为是最小化问题，若检验数均大于等于0,则此方案为最优方案，若有非基变量的检验数小于0，则可以通过适当加大此非基变量的取值而得另一可行解，此解下目标函数有所改进（变得更小)，故此方案非最优方案。文中如有不足，请您指教！6 / 6
运筹学学习(自制笔记)第3章 运输问题
