运输问题模型与性质.ppt

第三章 特殊的线性规划 运输问题,& 模型及其特点 & 求解思路及相关理论 & 求解方法表上作业法 & 运输问题的推广 产销不平衡的运输问题 转运问题 & 运输问题的线性规划软件求解,3.0 运输问题引例,1.施工组织多供点调运问题 大型施工企业,工程建筑中所需的材料、混合料会存放在多个中心仓库或由多个拌和站提供,而每个仓库或拌和站又会给多个不同的施工工地供应材料,这样就出现了多个供点与多个需点间调运优化的问题。,1.1工程实例 某大型建筑施工公司,有6个施工工地需使用水泥砼混合材料,公司经过技术经济分析后,决定购买商品砼给这6个工地使用。通过市场调查,有3家砼供应商的水泥砼能满足这6个工地的施工使用要求。各供应商供货的原始资料见表1,各工地砼的需要量及各供应商可供砼的数量见表2。确定各工地应从这3个砼供应商处分别购买多少砼可使该建筑公司对此商品砼投入的费用最低。,2.垃圾运输问题,随着人民生活水平的提高,人们对环境质量的要求越来越高,城市垃圾作为城市公害问题越来越受到各级政府部门的重视. 如何科学合理地运输城市垃圾,成为一个重要问题.,2.1 工程实例,沈阳市内5区为沈河区,和平区,铁西区,皇姑区,大东区,要把这5个区的垃圾运到赵家沟处理场,塔山处理场,沈阳市处理场,畜牧场垃圾处理场,马古垃圾处理场进行处理.怎样调运各区垃圾量才能使总的运输吨公里最小?各区,各处理场及其运距的量见表1.,3.土方工程施工中的运输问题,一个土方工程项目中,往往会有多个挖区和填区,特别是当工程为分期分批施工时,先期工程与后期之间的土方堆放和调运问题应当全面考虑,力求避免重复挖运和场地混乱,为使土方总运输量最小或土方运输成本最小或土方施工费用最小,土方施工前先进行土方调配设计非常有必要.,3.1 工程实例,青山湖电排站扩建工程位于南昌市青山湖区塘山镇,青山湖北部出入口处,北邻赣江。该工程土方开挖总量为4.8万3,土方回填总量为5.7万3,为弥补回填料不足需另取土料0.9万3。具体见表1。,3.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？,单位根据具体问题选择确定。,表3-1 有关信息,2、运输问题的数学模型,设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足：,同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：,总运费为：,运输问题的数学模型,（3-6）,二、运输问题的特点与性质 1约束方程组的系数矩阵具有特殊的结构 写出式（3-1）的系数矩阵A，形式如下：, 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 列向量Pij =(0,，0，1，0，,0,1,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行相加之和结果是零向量，说明m+n个行向量线性相关，因此 的秩小于m+n； ？,因此 的秩恰好等于m+n-1，又D本身就含于A中，故A的秩也等于m+n-1,由 的第二至m+n行和前n列及 对应的列交叉处元素构成m+n-1阶方阵D 非奇异； ？,可以证明：m+n个约束方程中的任意m+n-1个都是线性无关的。,定义3.1 凡是能排成 (3-4) 或 (3-5) 形式的变量集合称为一个闭回路,并称式中变量为该闭回路的顶点；其中 互不相同, 互不相同。,3. m+n-1个变量构成基变量的充要条件是它们不构成闭回路。,例3-1 设m=3，n=4，决策变量xij表示从产地Ai到销地Bj的调运量，列表如下，给出闭回路 在表中的表示法用折线连接起来的顶点变量。,练习3-1 请给出闭回路 和 在表中的表示法。,练习3-2 下面的折线构成的封闭曲线连接的顶点变量哪些不可能是闭回路？为什麽？, 表中的折线构成一条封闭曲线，且所有的边都是水平或垂直的； 表中的每一行和每一列由折线相连的闭回路的顶点只有两个；,有关闭回路的一些重要结果,定理3-1 设 是一个闭回路，则该闭回路中的变量所对应的系数列向量 具有下面的关系：,注意：列向量Pij =(0,0,1,0,0,1,0,0)T中两个元素1分别处于第i行和第m+j行，直接计算即可得到结果。,定理的证明可借助定理3-1和高等代数中“向量组中，若部分向量线性相关，则整个向量组就线性相关”的定理得到。,定理3-2 若变量组 中有一个部分组构成闭回路，则该变量组对应的系数列向量线性相关。,定理3-3 不包含任何闭回路的变量组中必有孤立点。 所谓孤立点是指在所在行或列中出现于该变量组中的唯一变量。 可用反证法证明结论成立。,定理3-4 r个变量 对应的系数列向量线性无关充要条件是该变量组不包含闭回路。,必要性的证明可考虑用反证法结合定理3-2的结果进行，充分性的证明可借助定理3-3，根据向量组线性无关的定义用归纳法得证。 推论 m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。,三、运输问题的求解方法,1、单纯形法（为什麽？） 2、表上作业法 由于问题的特殊形式而采用的更简洁、更方便的方法,1.