第六章 运 输 问 题2.pptVIP

第六章 运 输 问 题 内 容 运输问题 要解决的是把某种产品从若干个产地调运到若干个销地。在每个产地的供应量和每个销地的需求量均为已知的前提下，如何在多种可行的调运方案中，确定一个使总的运输费用或运量最少的方案 指派问题 中转问题 6.1 运 输 问 题 例：首都电视机厂在国内拥有3个生产工厂和4个区域仓库，每个工厂生产的电视机的年产量和每个仓库的年需求量，每个工厂到每个仓库的运输费用见表，安排一个运输策略，使得每年的运费最小 建立线性规划模型 以1,2,3表示郑州、南昌、深圳的工厂，以1,2,3,4表示北京、上海、广州和武汉的仓库，那么 表示从第i个工厂运输到第j个仓库的电视机数量（百万台） 目标函数： 约束条件： 系数矩阵A是 6.1.1 运输问题的一般模型 设某种物资有m个产地 ，供应量为别为 个单位；联合供应n个销地 ，需求量分别为 个单位。又假设从产地 向销地 运输一个单位的费用，即单位运价（或计价距离） 是已知的，试问应怎样调运物资才能使运输费用最少。 解：记从产地 到销地 的运输量为 个单位。为清楚起见，把上述数字都排列在一张表上。这张表通常称为产销运输表。 其中， 是由 运到 的单位运价； 是由 运到 的供应量；是产地 可供应量； 是销地 的需求量。 约束条件： 由 调出的物资总量等于 的供应量，所以 应满足 运到 的物资总量应等于 的需求量,所以 应满足 运费 线性规划模型 共有m*n个变量，m+n个约束条件，约束条件的系数是A，常数项b,变量 当 满足 称该运输问题是平衡的，否则称为产销不平衡的运输问题。 对于产销平衡的问题，有 ，所以模型最多有m+n-1个独立的约束方程，也就是A的秩最大为m+n-1(跟原来的线性规划问题秩为m不同) 对于产销不平衡的问题，我们增加一个虚拟的产地（产大于销）或者是虚拟的销地（销大于产），变为一个产销平衡的问题求解 产大于销：增加一个虚拟的销地，并产地到销地的运价为0 例：供应量大于需求量 增加一个销地 销大于产：增加一个虚拟的产地，并产地到销地的运价为 例：需求量大于供应量 增加一个虚拟的产地 6.1.2 表上作业法 运输问题可以用单纯形法求解，但是根据它的约束条件的特殊性，可以采用特殊的算法—表上作业法(运输单纯形法) 表上作业法一般分为两个阶段， 制定初始调运方案；——找到初始可行解 从初始调运方案出发，调整调运方案，逐步获得最优解 6.1.2 表上作业法 制定初始调运方案 左上角法（西北角法） 最小运价法 元素差额法 6.1.2 表上作业法 西北角法 作产销空格表，将空格对应的产销地运费填在空格的左上角； 在表中对左上角的格进行分配，将它对应的产地产量与销地销量比较： 如果产大于销，则在这方格中填上销量，并在表中划去这一列； 如果销大于产，则在这方格中填上产量，并在表中划去这一行； 如果产销相等，则在这方格中填上产量（销量），并在表中划去相应的行(或列)，但不能行列都划去。 在剩下的表中，反复进行第二步，直至每个方格都被划过或全部格子都赋值为止 例6.1，填写产销运输表 从左上角开始比较产销 每个格子都被划去或有值，找到初始解运费为11500 不能同时划去一行一列 划去行或列的原则是尽量保持空格不被划过 6.1.2 表上作业法 最小运价法 作产销空格表，并将空格对应的产销地运费填在空格的右上角； 在表中找出运价最小的一格，将它对应的产地产量与销地销量比较： 如果产大于销，则在这方格中填上销量，并在表中划去这一列； 如果销大于产，则在这方格中填上产量，并在表中划去这一行； 如果产销相等，则在这方格中填上产量，并在表中划去相应的行(列)，但不能行列都划去。 在剩下的表中，反复进行第二步，直至每个方格都被划过 例6.1，填写产销运输表 找到运价最小的单元格开始比较产销 每个格子都被划去或有值找到初始解，运费为6400 6.1.2 表上作业法 一行和一列都是0 划去行或列的原则是尽量保持空格不被划过 6.1.2 表上作业法 元素差额法 作产销空格表，并将空格对应的产销地运费填在空格的右上角； 产销空格表增加一行和一列作为差额行和差额列，在差额行和差额列每格上填上对应行和对应列的最小元素和次小元素之差额； 在差额行和差额列的所有元