运筹学第三章31运输问题模型与性质new.ppt

第三章 特殊的线性规划——运输问题 ?3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 运输问题的数学模型 三、运输问题的求解方法 1、单纯形法（为什么？） 2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法 3、举例 例3-2 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。 表3-4 例3-2有关信息表 例3-2 的数学模型 （2）伏格尔法 它的基本思想是： 考虑次小运费(运距)，这就有一个差额。因而对差额最大处，就应当采用最小运费(运距)调运。 用伏格尔法确定例3-2初始调运方案 得到初始调运方案为： x11=50，x12=150，x21=50，x23=200 三、最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法： 计算非基变量的检验数 未填上数值的格(空格) 空格的检验数 若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。 1、闭回路法 以确定初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 闭回路的特点： 除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。 约定:起始顶点为非基变量，记为偶数次顶点，其它顶点从1开始顺次排列，那么，该非基变量xij的检验数： 现在，用最小元素法确定例3-2初始调运方案的基础上，计算非基变量X12的检验数 ： = (闭回路上偶数次顶点运距或运价之和) －(闭回路上奇数次顶点运距或运价之和) (3-6) 450 200 150 100 销 量 250 75 X23 65 X22 80 X21 A2 200 100 X13 70 X12 90 X11 A1 产 量 B3 B2 B1 调 销地 运 量 产地 100 100 100 150 例3-2初始调运方案中以X12(X21)为起点的闭回路 * * 模型及其特点 求解思路及相关理论 求解方法——表上作业法 运输问题的推广 ? 产销不平衡的运输问题 ? 转运问题 单位根据具体问题选择确定。 表3-1 有关信息 单位 运价 销 或运距 地产地 ? B1 B2 … Bn ? 产 量 A1 A2 ┆ Am c11 c12 … c1 n c21 c22 … c2n … … … cm1 cm2 … cm n a1 a2 ┆ am ? 销 量 ? ? b1 b2 … bn 同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： 总运费为： （3-1） 二、运输问题的特点与性质 1．约束方程组的系数矩阵具有特殊的结构 写出式（3-1）的系数矩阵A，形式如下： m行 n行 ? 矩阵的元素均为1或0； ? 每一列只有两个元素为1，其余元素均为0； ? 列向量Pij =(0,…，0，1，0，…