《运筹学-3运输问题讲解》由会员分享，可在线阅读，更多相关《运筹学-3运输问题讲解（90页珍藏版）》请在金锄头文库上搜索。
1、统计学院 运筹学第三章 运输问题 张 红 历 本章内容 4.应用问题举例 3.运输问题的进一步讨论 2.表上作业法 1.运输问题及其数学模型 第一节 运输问题及其数学模型 一、运输问题的提出 例：某运输问题的资料如下： 单位 销地 运价 产地 产量 291029 13425 84257 销量 3846 21 二、数学模型的一般形式 1. 已知资料如下： p 设某种物品有m个产地A1，A2，Am，产量 分别是 a1，a2，am个单位 p 有n个销地B1，B2，Bn，销量分别为b1， b2，bn个单位； p 从Ai 到Bj运输单位物品 的运价是cij； 2. 运输问题的几种类型： p 产销平衡问题
2、 p 产销不平衡问题 u 产大于销 u 销大于供 p当产销平衡时，其模型如下： p当产大于销时，其模型是： p 当销大于产时，其模型是： 三、运输问题数学模型的特点 （1）运输问题有有限最优解。 定理. 运输问题有可行解的充要条件 是：产销平衡 其中： （2）运输问题约束条件的系数矩阵 记变量xij对应A中向量为 Aij Aij = 0 . 1 . 0 . 1. 0 第 i分量 第 m+j分 量 矩阵的元素均为1或0； 每一列只有两个元素为1，其 余元素均为0； 列向量Pij =(0,，0，1， 0，,0,1,0,0)T，其中两 个元素1分别处于第i行和第 m+j行。 将该矩阵分块，特点是：
3、前m行构成m个mn阶矩阵，而 且第k个矩阵只有第k行元素全 为1，其余元素全为0（k=1， ，m）；后n行构成m个n阶单 位阵。 （3）运输问题的解 定义1. 闭回路 闭回路是能折成 形式的变量组集合。其中 i1 , i2 , ， is 互不相同，j1 , j2 , ， js 互不相同 。每个变量称为闭回路的顶点，连接闭回路相邻两顶点的直线段叫做闭回 路的边。 例：x11，x12，x32，x34，x24，x21 就是一个闭回路。 B1 B2 B3 B4 A1 A2 A3 x11 x12 x21 x32 x24 x34 闭回路的特点： 1.每一个顶点都有两条边与之相接，一条是水平的，一条是铅直的
4、； 2.每一个顶点都是转角点，与之相邻的两个顶点，分别在它的水平和铅直方向； 3.每一行（列）如果有闭回路的顶点，则必出现一对，顶点总个数是偶数； 4.从任何一个顶点出发，沿任何一个方向到它的位于同一行或同一列的相邻 顶点，如此继续下去，经过闭回路的所有顶点和边，最后又回到开始的顶点， 但每一定和边在闭回路中只经过一次。 B1 B2 B3 B4 A1 A2 A3 x11 x12 x21 x32 x24 x34 有关闭回路的一些重要定理 定理定理1:1: 设设 是一个闭回路，则该闭回路中的变量所对应是一个闭回路，则该闭回路中的变量所对应 的系数列向量的系数列向量 具有下面的关系：具有下面的关系：
5、 定理2: 若变量组 中有一个部分组构成闭回路，则该变量组对应 的系数列向量线性相关。 定理3 r个变量 对 应的系数列向量线性无关充要条件是该变量组不包 含闭回路。 推论：m+n-1 个变量 构成基的充要条件是它不含闭回路。 第二节 表上作业法 一、表上作业法的基本思想 寻找初始基本可行解 给出基本可行解为最优解的判别准则 给出从目前基本可行解转移到新基本 可行解的方法 Review Step4.重复2. 3，直到找到最优解为止。 二、表上作业法的步骤 Step1.找出初始基本可行解（在m*n产销平衡 表上寻找初始调运方案，一般m+n-1个数字格） ，用最小元素法、西北角法、伏格尔法； St
6、ep2.求出各非基变量的检验数，判别是否 达到最优解。如果是停止计算，否则转入下一步 ，用闭回路或位势法计算； Step3.改进当前的基本可行解（确定换入、 换出变量），用闭合回路法调整； 1.求初始方案（寻找初始基可行解） Step1. 选择一个xij， 对xij的选择采用不同的规则就形成各种不 同的方法，比如每次总是在作业表剩余的格子中 选择运价（或运距）最小者对应的xij，则构成最 小元素法，若每次都选择左上角格子对应的xij就 形成西北角法（也称左上角法）。 Step2. 调整产销剩余数量：从ai和bj中分别减去xij的 值，若ai-xij=0，则划去产地Ai所在的行，即该产地产 量已
7、全部运出无剩余，而销地Bj尚有需求缺口bj-ai； 若bj-xij =0，则划去销地Bj所在的列，说明该销地需 求已得到满足，而产地Ai尚有存余量ai-bj； Step3.当作业表中所有的行或列均被划去，说明所 有的产量均已运到各个销地，需求全部满足，xij的取 值构成初始方案。否则，在作业表剩余的格子中选择 下一个决策变量，返回步骤（2）。 按照上述步骤产生的一组变量必定不构成闭 回路，其取值非负，且总数是m+n-1个，因此构成 运输问题的基本可行解。 p 从单位运价表中选最小元素，然后比较 产量和销量，如果产销，则划去列，若销 产，则划去行； p 修改ai或bj的值； p 再从划去一列和一
8、行后的单位运价表中 找最小元素，继续下去； p 直到单位运价表的所有元素划去为止。 步 骤： 就近供应。按单位运价的大小决定供应 的先后，优先满足单位运价最小者的供 销要求。 基本思想 ： 最小元素法 单位 销地 运价 产地 产量 3113107 19284 741059 销量3656 例 31 2 4 4 3 3 4 36 供 销 B1 B2 B3 B4 产量 A1 A2 A3 销量 3113 10 1 7 9 4 2 10 8 5 3 6 5 6 7 4 9 1 1 3 5 3 3 6 6 西北角法 基本思想： 优先满足运输表中左上角（即西北角 ）空格的供销要求。 3 4 1 4 2 2
9、2 2 4 3 3 5 6 6 供 销 B1 B2 B3 B4 产量 A1 A2 A3 销量 3113 10 1 7 9 4 2 10 8 5 3 6 5 6 7 4 9 6 6 3 2 伏格尔法（Vogel 逼近法. VAM） 最小元素法的缺点：为了节省一处的费用，有时造成在 其它处要多花几倍的运费。若不能按最小运费就近供应，就 选择次最小运费，差额越大，说明不能按最小运费调运时， 运费增加越多。 每行（列）中次最小价格元素与最小价格元素的数值之差 ，称为该行（列）的行（列）罚数最大差额费用。 对罚数最大处，采用最小运费调运。 在求一个可行解的过程中注意到包含在矩阵模型中 的成本信息。它通过
10、建立“罚数”来达到此目的。 罚数表示对一方格不进行分配的可能的成本罚款。 步 骤： Step1. 给定一个平衡的运输矩阵，分别计算行罚数和列罚数； Step2. 确定具有最大罚数的行或列，然后在罚数所在行（或 列）中选择最小价格元素，将可能的最大单位数分配 给此方格，将相应的行（或列）的供应量和需求量减 去这个量，并划去完全满足的行（或列）； Step3. 重复step1，step2，直到给出初始解为止。 例 见下页！ 0 1 1 供 销 B1 B2 B3 B4 产量 行罚数 A1 A2 A3 销量 3113 10 1 7 9 4 2 10 8 5 3 6 5 6 20 7 4 9 列 罚 数
11、 2 5 1 3 6 0 1 2 2 1 3 1 3 0 1 2 1 2 3 2 3 7 6 1 2 0 0 2 3 3 1 1 5 2 2 6 7 5 4 2 Z=53+210+31 +1 8+64+ 35 = 85 2. 解的最优性检验 （1）闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量 作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶 点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基 变量而言，以其为起点的闭回路存在且唯一。 n 判别的方法是计算空格(非基变量)的检验数， 因运输问题的目标函数是要求实
12、现最小化，故当所 有的检验数0时，为最优解。 n 常用两种求空格检验数的方法为：闭回路法和 位势法。 =（闭回路上奇数次顶点运距或运价之和）-（ 闭回路上偶数次顶点运距或运价之和） xuj xij xlk xls xus xik 检验数 对调运方案中每一空格按闭回路法求出检验数 若所有检验数大于等于零，则此方案为最优方案； 若存在检验数小于零，则需对此方案进行调整。 供 销 B1 B2 B3 B4 产量 A1 A2 A3 销量 3113 10 1 7 9 4 2 10 8 5 3 6 5 6 7 4 9 3 6 4 1 3 3 1 2 1 -1 10 12 不是最优解 此种 颜色 代表 检验
13、数 经济含义：在保 持产销平衡的条 件下，该非基变 量增加一个单位 运量而成为基变 量时目标函数值 的变化量。 （2）对偶变量法（位势法） 定理：任何基可行解对应的方程组都有解。 运输问题的基可行解 在这一组基变量下，建立求解ui，vj的方程组： 位势：方程组的任意一组解叫做位势。 对于运输问题的一个基可行解，用位势法得 到的检验数是唯一的（位势可能不同）。 对基变量，反复利用公式 求出空格的检验数。 求出位势后，就可由公式 B1B2B3B4 A1310u1 A212u2 A345u3 v1v2v3v4 成本表Cij B1B2B3B4 A1293100 A218291 A334255 2931
14、0 u2+v1=1 u2+ v3 =2 u3+v2=4 u1+ v4 =10 u1+v3=3 u3+ v4 =5 令： u10 u10 v12 u2 1 v2 9 u3 5 v3 3 v4 10 (ui+vj) 按ij=cij(ui+vj) 计算检验数，并以ij0 检验，或 用(ui+vj) cij 0 检验。 B1B2B3B4 A1311310 A21928 A374105 cij B1B2B3B4 A129310 A21829 A334-25 (ui+vj) B1B2B3B4 A11200 A20101 A3100120 表中还有负数， 说明还未得到最 优解，应继续调 整。 ij 0 -1 -5 1 2 1 -1 1012 此种 颜色 代表 检验 数 10 3113 10 1 7 9 4 2
