运筹学OR8运输问题模型与性质new

1、第三章特殊的线性计划运输问题、模型及其特征解决构想和相关理论解决方法表的作业法运输问题的推进生产销售的不均衡运输问题、3.1运输问题模型和性质一、运输问题的数学模型1、运输问题的一般建议：某物资有几个产地和卖场，现在需要将该物资从各产地运送到各卖场，产量的总数销售知道各产地的产量和各产地的销售量和各产地的单位运输价格(或运输距离)，如何组织运输，最能节约总运输费(或总运输量)？ 单位是根据具体的问题选择而决定的。 将与表3-1有关的信息、2、运输问题的数学模型、xij作为从产地Ai向销售地Bj的物资量(i=1，m； j=1，n )，因为从Ai发货的物资总量必须等于Ai的产量Ai，所以xij，也

2、因为向Bj发货的物资总量必须等于Bj的销售量Bj，所以xij，总运费必须是：运输问题的数学模型，(3-1)，2，运输问题每列只有两个元素1，其馀的元素为0。列向量Pij=(0，0，1，0，0，0，0，0 ) t。 两个要素1分别位于第I行和第m j行。 该分块矩阵的特征在于，前m行构成m个mn阶矩阵，并且第k行的第k行元素都是1，其馀元素都为0(k=1，m )，然后n行构成m个n阶矩阵。 2 .输送问题的基变量的总数是m n-1写放大矩阵，系数矩阵a及其放大矩阵的秩都是m n-1，前面m行的加法和减法后的n行的加法和结果是零向量，说明mnn个行向量的线性相关，因此秩小于mnn，因此秩等于mnn

3、-1，且d本身包含在a中，所以a的秩也等于mnn-1，难怪用的第二到mnn行和第一n列对应列的交叉元素构成mnn-1次方阵d？m n个约束方程式中的任何m 定义3.1全部以(3-4)或(3-5)形式排列的变量的集合称为一个闭合回路，式中的变量称为该闭合回路的顶点，其中互不相同，互不相同。 3. m n-1个变量构成基变量的充分条件是它们不构成闭合电路。 例3-1设m=3、n=4，决定变量xij表示从产地Ai向销售路径Bj的输送量，表中的闭环的表现用折线连接的顶点变量如下所示。、三、运输问题的解决方法，1、单纯形式法(为什么) 2、表作业法是根据问题的特殊形式所采用的更简洁方便的方法，3.2运输

4、问题的表作业法1、表作业法的基本思想是：先提出初始方案，然后根据决定的判别标准对初始方案进行检查、调整、改进，最表作业法和单纯形法的求解思想完全一致，但具体做法更简单。 图3-1运输问题的解决构想图、二、初期案的确定1、作业表(生产销售平衡表)的初期案是初期的基本的可行解。 组合有关运输问题的信息表和决策变量的运输量，构成“作业表”(生产销售平衡表)。 表3-3是两个产地、三个据点的运输问题作业表。 表3-3运输问题作业表(产销平衡表)。 其中xij是决定变量，表示从确定的第I个产地到第j个产地的输送量，cij表示从第I个产地到第j个产地的单位输送价格或输送距离。2、确定初始方案的步骤： (1

5、)选择xij，在xij=minai、bj=、xij表的位置填写具体的数值(2)调整生产的剩馀数量：从ai和bj中分别减去xij的值，如果ai-xij=0，则为产地ai的某行，即如果在销售地bj上存在需求间隙bj-Ai，则除了有引脚目的地bj的列以外，虽然满足了该引脚目的地需求，但表示产地ai还有馀量ai-bj的(3)如果作业表的所有行或列被删除，则所有的产量都是各销售否则，在表的剩馀单元格中选择下一个决定变量，返回步骤(2)。 按照以上顺序发生的一系列变量必须不构成闭合电路，其值为非负，而且总数为m n-1个，因此有可能构成输送问题。 xij的选择采用不同的规则形成各种方法，一般的方法是最小元

6、素法和博尔凝胶法。 以下，通过具体的例子分别进行介绍。 3、例3-2甲、乙两个煤矿提供a、b、c三个城市用煤，各煤矿产量和各城市的必要煤炭量、各煤矿到各城市的运输距离如表3-4所示，求出了总运输量最小的运输计划。 使用表3-4例3-2相关信息表、例3-2的数学模型、最小要素法求出初始方案(1)最小要素法的基本思想是“最近的供给”:即从单位价目表或运输距离表的最小要素确定供给关系，直到给出次小的、初始基的可执行解。 用、最小元素法决定例3-2的初始调合方案时，150，100，100，100，100，100，100，x11=100，x22=150，x23=100，最小元素法的缺点是，为了节约一个地

7、方的费用，在其他地方(2)博尔格尔法，其基本思想，考虑到下面的运费(运输距离)，其中有差额。 因此，在差额最大的地方，必须以最小运费(运输距离)运输。 寻找最大差额的最小运费，求出、最小、差额、初始运费，x1=50、x21=50、x23=200、3，最优检查，当前运费是否是最佳方案检查的方法：计算非基本变量的检查数没有加入数值的格(空间)空间的检查数都在零以上的话，那个方案是最佳的运输方案，否则就调整。1、闭回路法，根据确定初始调运案的工作表，以一个非基底变量为开始顶点求出闭回路。 闭回路的特征：除了开始顶点不是基变量外，其他顶点是基变量(对应于填写数值的格)。 如果不区分闭合回路的方向，则可

8、以证明每个非基底变量都存在以其为起点的闭合回路，是唯一的。的开始顶点标记为非基础变量、偶数次顶点，约定从1开始依次排列其他顶点，则该非基础变量xij的检测常数：现在，在用最小要素法决定例3-2的初始调试方案的基础上，非基础变量X12的检测常数：=(闭回路中偶次顶点的运输距离或运价之和) (闭回路中奇数次顶点的运输距离或运价之和)、(3-6)、例3-2的初始运行方案中，以X12(X21 )为起点的闭回路，非基本变量X12的检测常数：=(c12c 23 )-(c13c 22 )=70 -。 经济意义是保持生产销售平衡的条件，这个非基本变量是增加单位运输量成为基本变量时目标函数值的变化量。2、电位法

9、，以例3-2的初始调整方案为例，设定电位变量，根据初始调整方案表追加1行和1列(参照下页表)。然后，构筑下一个方程式：(3-7)、例3-2初始调整方案的电势变量对应表、方程式的特征：方程式的个数为m n-1=2 3-1=4个，电势变量为m n=2 3=5个，ui被称为第I行的电势，vj与第j列的电势对应于行和列的电势变量之和等于对应于基变量的运输距离(或运输价格):ui vj=cij； 方程式正好有自由变量，可以证明方程式中的任何变量都可以作为自由变量来取。 另外，给出自由变量的值，通过解方程式(3-7)，能够求出电位变量的值，当根据方程式(3-6)结合方程式(3-7)时，计算非基础变量xij

10、检测常数的式ij=cij-(ui vj) (3-8)，通过式(3-7)求出ui VJ v2=90 12=c 12-(u1v2)=70-(090 )=-20=c 21-(u2v1)=80-(-2590 )=15与先前用闭合回路法求出的结果相同。 四、方案调整至少一个非基础变量的检查数为负值时，应说明并调整工作表现在的运输方案不最佳。 如果检查数ij小于0，则首先在工作表上作成以xij为开始变量的闭环，求出调整量：在上述的例子中作成以12=-20、x12为开始变量的闭环，并计算调整量：=min (100，150 )=100。 调整运输量，闭合回路上：闭合回路以外的变量的运输量不变。 从奇数次顶点的输送量中减去，加到偶数次顶点的输送量上，得到新的输送方案：重复以上的步骤，直到求出最佳的输送方案。 结果最佳的运输方案是，相当于x1=50、x12=150、x21=50、x23=200的最小总运输量为zmin=90507015075200=34000 (吨公里)，3.3运输问题的推进，另一方面，生产销售不平衡的运输问题，虚拟销售地的增加，以及对应的运输距离(或运输价格)，二、运输问题的特征：运送的物资不是从产地直接运送到销售地，而是通过几个中继站运送。 解构思：转化为等效的产销平衡运输问题，用表作业法寻求最佳运输方案。 如何转换呢？ 第一步是重组产地、运输点、销售地，运输点为产