文档介绍：运输问题1第五章运输问题一、运输问题的数学模型在经济建设中,经常会遇到大宗物资调拨中的运输问题。如煤炭、钢铁、木材、粮食等物资在全国有若干生产基地, 根据已有的交通网, 应如何制定调运方案,将这些物资运到各消费地点,而使总运费最小。这类问题可用以下数学语言来描述:运输问题:假设有m 个生产地点(以后称为产地),可以供应某种物资,用Ai表示,i = 1,2,…,m;有n 个销售地,用Bj 表示,j = 1,2, …,n;产地的产量和销售地的销售量分别为ai和bj ,从Ai 到Bj运输单位物资的运价为cij,这些数据可汇总于如下表1。在假设产销平衡的条件下,即?????njjmiiba11运输问题2表1 产销平衡表与单位运价表销地产地B1B2…Bn产量A1C11 (x11)C12(x12)…C1n(x1n)a1A2C21(x21)C22(x22)…C2n(x2n)a2…………AmCm1(xm1)Cm2(xm2)…Cmn(xmn)am销量b1b2…bn?????njjmiiba11运输问题3解:假设xij表示从Ai到Bj的运量,则所求的数学模型为: ???????????????????????????njmixnjbxmiaxxcZMinijjmiijinjijminjijij,,2,1;,,2,10,,2,1,,2,11111?????????njjmiiba11运输问题4二、表上作业法(一)、表上作业法的基本概念与重要结论系数矩阵: (x11)2 (x12) (x13)120A27 (x21) (x22) (x23)80需求量50708020011 12 13 21 22 231 1 1 0 0 00 0 0 1 1 11 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1x x x x x x? ?? ?? ?? ?? ?? ?? ?? ?运输问题5(1)该矩阵中,每列只有两个元素为1,其余都是0。如变量x11的系数列向量p11只有第1个和第3个元素为1。(2)任一变量的系数列向量可表示为两个单位列向量之和。pij=ei+em+j,ei表示第i个元素为1的单位向量。11 12 13 21 22 231 1 1 0 0 00 0 0 1 1 11 0 0 1 0 00 1 0 0 1 00 0 1 0 0 1x x x x x x? ?? ?? ?? ?? ?? ?? ?? ?矩阵特点:运输问题6单纯形法求解:基变量的个数;其次,要知道这样一组基变量应当是由哪些变量来组成。基变量个数:m+n-1个变量。(即基变量的个数= 产地个数+ 销售地个数– 1)根据这个特点,在单纯形法的基础上,创造出一种专门用来求解运输问题的方法--表上作业法。由于是产销平衡的,其中任何一个约束方程都可以等于其余方程的线性组合,因此独立的方程个数为m+n-1。运输问题71、确定初始基可行解:即首先给出初始的调运方案。方法一:最小元素法:基本思想:就近供应。即从单位运价表中最小的运价开始确定产销关系,依次类推,直到给出初始方案为止。例1:某公司经销甲产品,它下设三个加工厂,每日的产量分别为:A1—9吨、A2—5吨、A3—7吨。该公司把这些产品分别运往四个销售点。各销售点每日数据及从各工厂到各销售点的单位产品的运价如表示。问该公司应如何调运产品