线性规划理论与模型应用3.pptVIP

主要内容 3.1 运输问题的模型及特点 运输问题和指派(分配)问题是常见的线性规划问题, 可以用单纯形法进行求解，本章寻求比单纯形法更为有效的特殊方法对其进行处理。 第一章例3给出了一个运输问题的实例，此处我们讨论一般情况下的运输问题模型。 1. 产销平衡的运输问题 设某种物资需要从m个产地A1,A2,…, Am运送到n个销地B1, B2, …, Bn, 其中各产地的产量为a1,a2,…,am,各销地的销售量为b1,b2,…,bn, 并且满足产销平衡, 即 从产地Ai到销地Bj的运费单价为cij(i=1,2,…,m,j=1,2,…, n), 问如何调运才能使总运费最少? 运输问题的模型及特点 建立模型 设xij为从产地Ai到销地Bj调运货物的数量，则 有如下模型： 运输问题的模型及特点 2.产大于销的运输问题 如果一个运输问题的产量大于销量，即 运输问题的模型及特点 引入m个松弛变量xi,n+1(i=1，2，…,m)，将前m个不等式约 束变为等式约束，再假设一个虚拟的销地Bn+1，其销量为: 运输问题的模型及特点 3.销量大于产量的运输问题 如果一个运输问题的销量大于产量，即 运输问题的模型及特点 引入n个松弛变量xm+1,j(j=1，2，…,n)，将后n个不等式约 束变为等式约束，再假设一个虚拟的产地Am+1，其产量为 运输问题的模型及特点 4. 有路线限制的运输问题 运输问题的模型及特点 设 运输问题的模型及特点 定理3.1 平衡运输问题一定存在最优基可行解。 证：设总产量为w, 即有 ，取 运输问题的模型及特点 定理3.2 平衡运输问题模型中系数矩阵A的秩为m+n-1。 证：将矩阵A的前m行相加减去后n行，得到全0行，从而rank(A) m+n，取A的第1, 2，…, m , m+1, 2m+1,…, (n-1)m+1列和A的后m+n-1行构成一个m+n-1方阵： 运输问题的模型及特点 例3.2 设有三个化肥厂A1、 A2、 A3，向四个批发站B1、B2 、B3 、B4运送化肥，发量、收量、运价等有关数据列于如下表中。 运输问题的模型及特点 5. 闭回路 定义3.2 一组格称为闭回路若能排成如下形式： 运输问题的模型及特点 下图不是闭回路。 闭回路的特点： 格的个数是偶数； 1、2格的行号相同，2、3格的列号相同，3、4的行号相同， 4、5格的列号相同，…，尾格与首格的列号相同； 每行或者没有格点或者有且仅有两个格点。 运输问题的模型及特点 引理3.2 若一组格(i1,j1)，(i1,j2)，(i2,j2)，(i2,j3)，…，(is,js)，(is,j1)构成了闭回路， 则有: 运输问题的模型及特点 6. 孤立格(点) 定义3.3 设G是一组格的集合，若对g?G，在G中不同时存在与g同行同列的格，则称g为G的孤立格(点)。 例如：在G={(1,2),(1,3),(2,1),(2,2),(2,4),(3,3)}中(2,1), (2,4),(3,3)是孤立格，如图。 运输问题的模型及特点 引理3.3 设G是格的集合，不包含任何闭回路，则G中必有孤立格。 证：反证法, 设G不包含任何闭回路，也没有孤立格，即任一格所在行与列上至少还有G中的另一格。现从G中任取一格(i1, j1)，则必有另一格与其同行，记为(i1, j2)；同样G中还应有一格与(i1, j2)同列，记为(i2, j2)；…，于是得到一系列格(i1, j1)，(i1, j2)，(i2, j2)，(i2, j3)，…，由于G是有限的，所以有限次之后，必然有格重复出现，则出现闭回路，与没有闭回路矛盾。 运输问题的模型及特点 引理3.4 在平衡的运输问题中系数矩阵的一组列向量 线性无关的充要条件是这组向量对应的格的集合中不包含闭回路。 证：必要性由推论3.1直接给出； 充分性、该组向量对应的格不含闭回路，要证明向量组线性无关。用反证法，若线性相关，则存在不全为0的一组数 ，使得 根据引理3.3这组格中必有孤立点，不妨设为(i1, j1)，该点所在行或所在列只有此点，从而上边方程组中或者第i1个方程为β1=0或者第m+j1个方程为β1=0，因而β1=0。 运输问题的模型及特点 同样从 没有闭回路可推出另外一个 系数为0(不妨设为β2=0)，类似一直可推出βr=0，也就是 向量组 线性无关，得出矛盾。 根据引理3.4可得出如下定理 定理3.3 在平衡的运输问题中系数矩阵的m+n-