运输问题08.10.ppt

运输问题,§1 运输问题的数学模型,一. 平衡运输问题的数学模型设某种物品有m个产地A1，A2，…，Am，产量分别是a1，a2，…，am个单位有n个销地B1，B2，…，Bn，销量分别为b1，b2，…，bn个单位；假设产销是平衡的，即 ，总产量等于总销量；从Ai 到Bj运输单位物品的运价是cij；,,为了方便，把上面的关系转化成下面的运输表,表格中的回路,定义1. 闭回路,闭回路是能折成 形式的变量组集合其中 i1 , i2 , …， is 互不相同，j1 , j2 , …， js 互不相同每个变量称为闭回路的顶点，连接闭回路相邻两顶点的直线段叫做闭回路的边例：x11，x12，x32，x34，x24，x21 就是一个闭回路运输问题的 mn个变量恰好和运输表的 mn 格子相对应,闭回路的特点：,1.每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的； 2.每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向； 3.每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数； 4.从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点，但每一顶点和边在闭回路中只经过一次。

§2 表上作业法,1、最小元素法,基本思想 ：按单位运价的大小决定供应的先后，优先满足单位运价最小者的供销要求从单位运价表中选最小元素，然后比较产量和销量，如果产>销，则划去列，若销>产，则划去行；修改ai和bj的值；再从划去一列和一行后的单位运价表中找最小元素，……，继续下去；直到单位运价表的所有元素划去为止步骤：,定理：用最小元素法得到的初始解是运输问题的一组基本可行解所填的 xij的值是对应基变量的取值一、初始基可行解的求法,3,1,4,6,3,3,2、西北角法,基本思想： 优先满足运输表中左上角（即西北角）空格的供销要求3,4,2,2,3,3,6,3、伏格尔法（Vogel 逼近法. VAM）,最小元素法的缺点：为了节省一处的费用，有时造成在其它处要多花几倍的运费若不能按最小运费就近供应，就选择次最小运费，差额越大，说明不能按最小运费调运时，运费增加越多每行（列）中次最小价格元素与最小价格元素的数值之差，称为该行（列）的行（列）罚数 对罚数最大处，采用最小运费调运在求一个可行解的过程中注意到包含在矩阵模型中的成本信息它通过建立“罚数”来达到此目的罚数表示对一方格不进行分配的可能的成本罚款。

步 骤：,Step1. 给定一个平衡的运输矩阵，分别计算行罚数和列罚数；,Step2. 确定具有最大罚数的行或列，然后在罚数所在行（或列）中选择最小价格元素，将可能的最大单位数分配给此方格，将相应的行（或列）的供应量和需求量减去这个量，并划去完全满足的行（或列）；,Step3. 重复step1，step2，直到给出初始解为止2 5 1 3,6,2 — 1 3,2 — 1 2,— — 1 2,— — — 2,Z=53+210+31+1 8+64+ 35= 85,二、最优解的判别,1. 闭回路法,定理：设 是一组基变量，是一个非基变量，则变量组 中存在唯一的闭回路。

从每一空格出发一定存在并可找到唯一的闭回路,对调运方案中每一空格按闭回路法求出检验数若所有检验数大于等于零，则此方案为最优方案；若存在检验数小于零，则需对此方案进行调整1,2,1,-1,10,12,不是最优解,,产销平衡 的运输 问题：,,对偶 模型,,,其中：ui为前m个约束对应的对偶变量，vj为后n个约束对应的对偶变量2、位势法,结论：对原运输问题，为满足对偶可行性,只要检验数,运输问题的解X*即为最优解满足对偶可行性,实际上,所有基变量的检验数等于零,即,定理：任何基可行解对应的方程组都有解位势：方程组的任意一组解叫做位势对于运输问题的一个基可行解，用位势法得到的检验数是唯一的（位势可能不同）对基变量，反复利用公式,求出空格的检验数求出位势后，就可由公式,0,-1,-5,1,2,1,-1,10,12,10,2,9,3,三、改进的方法—闭回路调整法,当 ij< 0 时，调运方案需要改进,,(-1),(+1),(-1),(+1),j  0 得到最优解,四、表上作业法计算中的问题,一. 无穷多最优解,当某个表格空格（非基变量）的检验数为0时，该问题有无穷多最优解以此格为调入格，作闭回路，经调整后得另一最优解。

多重最优解,,,二. 退化用表上作业法求解运输问题出现退化时，在相应的格中一定要填一个0，以表示此格为数字格1. 当确定初始解时，若在（i，j）格填入某数字后，出现ai = bj，这时在运输表上填一个数，而在运价表上相应的要划去一行和一列，这时需在划去的那行和那列的任一空格处填一个“0”，这样才能保证运输表上有m+n-1个数字格3,6,0,0,0,0,2. 在用闭回路法调整时在闭回路的下调顶点上出现两个或两个以上的相等的最小值，这时多于一个基变量退出基，经过调整后，得到退化解，在其中一个数字格填一个“0”，则表明是基变量产销不平衡的运输问题,,一、产大于销,二、销大于产,增加一个假想的产地Am+1，该产地的总产量为,即在运输表中增加一虚拟行在单位运价表上，令该假想产地到各销地的单位运价为 0有三个产地A1，A2，A3和三个销地B1，B2，B3，各产地至销地的单位运价见下表，各销地的需求量分别为10，4，6个单位由于客观条件的限制和销售需要，产地A1至少要发出6个单位的产品，最多只能发出11个单位； A2必须发出7个单位； A3至少要发出4个单位解：当 a1= 6，a2=7 时，,应 用 举 例,总产量>总销量,在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费。

单位物资的缺货损失费分别为4、3 和 7试建立运输模型, 使运输费用最小解：增加虚拟产地 A3,在下列不平衡运输问题中，假定任何一个发点的物资没运出时，都要支出存储费用，且已知三个发点的单位存储费用各为 5、4和3由于发点2为其他物资腾出地方，因而要求把现有物资全部运出，求最优解解：增加虚拟销地 B4,例:某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1 又知每条 船只每次装卸的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的要求解 该公司所需配备船只分两部分： （1）载货航程需要的周转船只数,载货需要 57+10+9+15=91 条船,（2）各港口调度所需船只数,港口城市 每天到达 每天需求 余缺数A 0 1 -1B 1 2 -1 C 2 0 2D 3 1 2E 0 3 -3F 1 0 1,为使配备船只数最少，应做到周转空船数为最少。

建立运输问题最少需周转空船数：1  2+15+113+117+13=40,故至少应配备 91+47=138 条船,作业一:用表上作业法求解表中给出的运输问 题的最优解.,作业二:,某百货公司去外地采购A、B、C、D四种规格的服装，数量分别为A—1500套，B—2000套，C—3000套，D—3500套，有三个城市可供应上述规格服装，供应数量为城市1—2500套，城市2—2500套，城市3—5000套由于这些城市的服装质量、运价及销售情况不一，预计售出后的利润（元/套）也不同，详见表： 请帮助该公司确定一个预期盈利最大的采购方案。