运筹 运输问题08.10.ppt

§1 运输问题的数学模型一. 平衡运输问题的数学模型• 设某种物品有m个产地A1，A2，…，Am，产量分别是a1，a2，…，am个单位• 有n个销地B1，B2，…，Bn，销量分别为b1，b2，…，bn个单位；• 假设产销是平衡的，即 ，总产量等于总销量；• 从Ai 到Bj运输单位物品的运价是cij；其中 ：为了方便，把上面的关系转化成下面的运输表产地销地B1 … Bj … Bn 产量A1…Ai…Am销量C11 C1j C1nCm1 Cmj CmnCi1 Cij Cinx11 x1j x1nxi1 xij xinxm1 xmj xmn… … … … … .… … … … … .......a1aiamb1bj bn表格中的回路定义1. 闭回路闭回路是能折成 形式的变量组集合。

其中 i1 , i2 , …， is 互不相同，j1 , j2 , …， js 互不相同 每个变量称为闭回路的顶点，连接闭回路相邻两顶点的直线段叫做闭回 路的边例：x11，x12，x32，x34，x24，x21 就是一个闭回路B1 B2 B3 B4A1A2A3x11x12x21x32x24x34运输问题的 mn个变量恰好和运输表的 mn 格子相对应闭回路的特点：1.每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的；2.每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向；3.每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数；4.从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点，但每一顶点和边在闭回路中只经过一次§2 表上作业法1、最小元素法基本思想 ：按单位运价的大小决定供应的先后，优先满 足单位运价最小者的供销要求。

• 从单位运价表中选最小元素，然后比较产量和销量，如果产>销，则划 去列，若销>产，则划去行； • 修改ai和bj的值； • 再从划去一列和一行后的单位运价表中找最小元素，……，继续下去 ； • 直到单位运价表的所有元素划去为止步骤：定理：用最小元素法得到的初始解是运输问题的一组基本可行解所填的 xij的值是对应基变量的取值一、初始基可行解的求法3124433436供销B1 B2 B3 B4 产量A1A2A3销量3113101794210853 6 5 6 749113533662、西北角法基本思想： 优先满足运输表中左上角（即西北角）空格的供销要求 34142222433566供销B1 B2 B3 B4 产量A1A2A3销量3113101794210853 6 5 6 74966323、伏格尔法（Vogel 逼近法. VAM）• 最小元素法的缺点：为了节省一处的费用，有时造成在其 它处要多花几倍的运费。

若不能按最小运费就近供应，就选 择次最小运费，差额越大，说明不能按最小运费调运时，运 费增加越多• 每行（列）中次最小价格元素与最小价格元素的数值之差 ，称为该行（列）的行（列）罚数 • 对罚数最大处，采用最小运费调运在求一个可行解的过程中注意到包含在矩阵模型中的成本 信息它通过建立“罚数”来达到此目的罚数表示对一 方格不进行分配的可能的成本罚款步 骤：Step1. 给定一个平衡的运输矩阵，分别计算行罚数和列罚数；Step2. 确定具有最大罚数的行或列，然后在罚数所在行（或列）中选择最小价格元素，将可能的最大单位数分配给此方格，将相应的行（或列）的供应量和需求量减去这个量，并划去完全满足的行（或列）；Step3. 重复step1，step2，直到给出初始解为止例见下页！011供销B1 B2 B3 B4 产量 行罚数 A1A2A3销量3113101794210853 6 5 6 20 749列 罚 数2 5 1 3 60122 — 1 3 1301 —2 — 1 232376—— — 1 2 00—— — — 2331152267542Z=53+210+31+1 8+64+ 35= 85二、最优解的判别1. 闭回路法定理：设 是一组基变量 ，是一个非基变量，则变量组 中存在唯一的闭回路。

从每一空格出发一定存在并可找到唯一的闭回路• 对调运方案中每一空格按闭回路法求出检验数 • 若所有检验数大于等于零，则此方案为最优方案； • 若存在检验数小于零，则需对此方案进行调整xujxijxlkxlsxusxik检验数供销B1 B2 B3 B4 产量A1A2A3销量3113101794210853 6 5 6 749364133121-11012不是最优解此种 颜色 代表 检验 数产销平衡的运输问题：对偶模型其中：ui为前m个约束对应的对偶变量，vj为后n个约束对应的对偶变量 2、位势法结论：对原运输问题，为满足对偶可行性只要检验数运输问题的解X*即为最优解满足对偶可行性实际上所有基变量的检验数等于零即定理：任何基可行解对应的方程组都有解 运输问题的基可行解 在这一组基变量下，建立求解ui，vj的方程组：位势：方程组的任意一组解叫做位势• 对于运输问题的一个基可行解，用位势法得到的检验 数是唯一的（位势可能不同）。

对基变量，反复利用公式 求出空格的检验数求出位势后，就可由公式0-1-5121 -11012此种 颜色 代表 检验 数10311310179421085供销B1 B2 B3 B4 uiA1A2A3Vj364133此种 颜色 代表 初始 解293三、改进的方法—闭回路调整法当 ij总销量供销B1 B2 B3 B4 产量A1A1A2销量2 43M2145360M10 4 6 5 657332244M0A3A3’43在下列不平衡运输问题中，已知三个收点的需求量一旦不能满足，就要承担缺货损失费单位物资的缺货损失 费分别为4、3 和 7试建立运输模型, 使运输费用最小供销B1 B2 B3 产量A1A2销量4 526838 7 14 1015供销B1 B2 B3 产量A1A2A3销量4 526483378 7 14 10154解：增加虚拟产地 A3在下列不平衡运输问题中，假定任何一个发点的物资没运 出时，都要支出存储费用，且已知三个发点的单位存储费 用各为 5、4和3。

由于发点2为其他物资腾出地方，因而要求把现有物资全部运出，求最优解供销B1 B2 B3 产量A1A2A3销量1 2102435330 20 20 204030供销B1 B2 B3 B4 产量A1A2A3销量1 2024315330 20 20 202040305M3解：增加虚拟销地 B4航线 起点城市 终点城市 每天航班数1 E D 32 。