第五章运输问题§5.1运输问题的数学模型及其特征如何调运，使总的运输费用最小？销产(1)运输问题数学模型根据运输问题中总供应量与总需求量的关系可将运输问题分为两类：平衡型运输问题和不平衡型运输问题。产销平衡运输问题的数学模型：平衡型运输问题的数学模型产大于销运输问题的数学模型：销大于产运输问题的数学模型：例1.现有A1，A2，A3三个产地，可供应物资分别为10，8，5个单位，现将物资运往B1，B2，B3，B4四个销地，销量分别为5，7，8，3个单位。产地到销地的单位运价cij如表1所示，问如何安排一个运输计划，使总的运输费用最少。解：设xij(i=1,2,3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量，这样得到下列运输问题的数学模型：有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型。解：设xij(i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的数量，则此问题的数学模型为(3)平衡型运输问题的对偶问题(4)运输问题的特征则有定理2平衡运输问题的约束方程系数矩阵A的秩r(A)=m+n-1。A中任意m+n阶子式等于零.再取第一行到m+n－1行与对应的列（共m+n-1列）组成的m+n－1阶子式B故r(A)=m+n－1.为了在mn个变量中找出m+n－1个变量作为一组基变量，就是要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。x23表4中闭回路是（1）每个顶点都是转角点；（2）每一条边都是水平线段或垂直线段；（3）每一行（或列）若有闭回路的顶点，则必有两个.性质1若变量组B包含有闭回路，则B中的变量对应的列向量线性相关。定义2在变量组中，若有某一变量xij是它所在的行（第i行）或列（第j列）中出现在该变量组中的唯一变量，则称该变量为孤立点。求运输问题的一组基变量，就是要找到m+n－1个变量，使得它们对应的系数列向量线性无关，由性质1，找这样的一组变量是很容易的，只要m+n－1个变量中不包含闭回路，就可得到一组基变量。因而有：例如，m=3,n=4，在运价表cij的格子的右上方填上相应的xij，如表5所示。这个运输问题的基变量数目是3+4－1=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。运输问题是一类特殊的线性规划问题对于平衡型运输问题：约束方程数为m+n个，但有一个冗余方程，所以独立方程数为m+n-1个，即秩r(A)=m+n-1。存在最优解当供应量和需求量均为整数时，存在整数最优解。基可行解中基变量个数为m+n-1个基可行解中基变量的重要特征：不含闭回路。本节介绍了具有m个产地n个销地的平衡运输问题1.具有m+n－1个基变量2.闭回路的概念3.怎样判断m+n－1个变量是否构成一组基变量(1)找出初始调运方案（初始基可行解）。即在(m×n)产销平衡表上给出m+n-1个数字格。§5.2初始基可行解的求法（1）西北角法----“就近供应”8（2）最小元素法优先安排单位运价最小的产销之间的业务最小元素法实施步骤口诀(2)最小元素法(0)(2)最小元素法(1)(2)最小元素法(2)(2)最小元素法(3)(2)最小元素法(4)(2)最小元素法(5)(2)最小元素法(6)课堂练习1课堂练习解答课堂练习答案销产销产销产销产(3)Vogel法（元素差额法）课堂练习2课堂练习2解答课堂练习2答案§5.3最优性检验与基可行解的改进（1）闭回路法●以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。●该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。●可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。3空格(1)闭回路法(0)5-55777(2)位势法基变量的检验数为零(基变量xij)，σij=cij-(ui+vj)销产基变量检验数xaca-u1=0∵ca=0∴u1=0x23c23-(u2+v3)=0即2-(u2+v3)=0x34c34-(u3+v4)=05-(u3+v4)=0x21c21-(u2+v1)=01-(u2+v1)=0x32c32-(u3+v2)=04-(u3+v2)=0x13c13-(u1+v3)=03-(u1+v3)=0x14c14-(u1+v4)=010-(u1+v4)=0从以上7个方程中,由u1=0可求得u2=-1,u3=-5,v1=2,v2=9,v3=3,v4=103000(2)位势法(0)选择含基变量最多的行或列，令相应的u或v为零。v1=