运筹学运输问题课件.ppt

线性规划(4)  运输问题 Transportation Problem 内容提要 运输问题简介 运输问题的数学模型 运输问题的性质 运输问题的求解方法表上作业法 运输问题的建模示例 运输问题简介 问题的提出 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 例：某公司经销产品甲。其下设3个加工厂(产地)A1、A2 、A2,公司将这些产品分别运往4个销地B1、B2、B3 、B4 。各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？ 运输问题的数学模型 已知 设某种物品有m个产地，产地 i 的产量为 设有n个销地，销地 j 的销量分别为 从产地 i 向销地 j 运输单位物品的运价是 目标 问怎样调运这些物品才能使总运费最小？ 设由产地 i 运往销地 j 的物品数量 xij，则得到如下线性规划问题: 矩阵形式 运输问题的性质 因此运输问题最多有的独立约束方程数为 运输问题的求解 运输问题的求解步骤1 线性规划问题的求解过程 初始基可行解的确定 确定一个基可行解 即在表格中填入m+n-1个非负数字，为基变量的取值，其余为非基变量，取值为0，不用填。 方法 最小元素法 差额法(伏格尔法) 初始基可行解的确定(1) 最小元素法 尽可能将资源分配给整个表格中具有最小成本的变量，划去已满足的行或列。调整所有未划去元素的供求量后，重复尽可能将资源分配给整个表格中具有最小成本的变量这一过程。当正好剩下一行或一列未被划去时，程序完成。 例子 初始基可行解的确定(2) 差额法(伏格尔法) 计算每一行(列)中最小运费与次最小运费的差额； 选取差额最大的行或列，将资源尽可能多地分配给具有最小运费的变量，调整资源后，划去满足条件的行或列； 当剩下最后一个差额时，用最小元素法分配。 最优性检验与解的判别 最优性的检验 对每个非基变量计算检验数，填入表中，若全为非负，即得最优解 方法 闭回路法 位势法 闭回路法 对每一非基变量定义一条封闭的回路，这条回路从所指定的非基变量开始并终止，由连续的水平和垂直线段组成，除在非基变量开始和终止的2条线段外，其它所有线段的端点为基变量。 线段的方向是无关紧要的，且在一个给定的基可行解中，对每一个非基变量构成的回路是唯一的。 利用回路计算非基变量的检验数。 位势法 1. 对应每一个基变量写出m+n-1个等式 令任意一个为零值(通常是 ) ，可求出所有的 和 运输问题的对偶问题 相关性质 由互补松弛性得，和基变量(非零)相对应的对偶约束条件必需以等式的形式得到满足 基变量有m+n-1个，因此，可通过假设 ，从而可求出所有的 和 。 表上作业法须注意的问题 须注意的问题(1) 在最终调运表中，若有某个空格(非基变量)的检验数为0时，则表明该运输问题有多重调运方案； 在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列(绝对不能同时把行、列划去，否则就不满足圈格=m+n-1个的要求，即基变量的个数永远要保持为m+n-1个）； 运输问题的电子表格求解 产销不平衡问题 不平衡问题转化为平衡问题 虚拟一个销地，其销量为　　　　　　，运费为0 运输问题的建模示例 生产计划问题 例：某公司在不同的工厂生产3种钢材。下表给出了生产1吨钢材（不考虑型号）需要的时间以及每个工厂的成本。每周每种型号(1、2和3)的钢材都必须生产130吨。每家工厂每周的工作时间为40小时。如何安排生产可使生产成本最小。 每个工厂每周工作40小时，即2400分钟。因此3个工厂每周可生产的钢材如下：分别可生产的钢材 　　 工厂1：2400/20＝120吨 　 工厂2：2400/16＝150吨 工厂3：2400/20＝120吨 问题分析： 已知： 　2个工厂（每周可生产钢材数量已知） 　3种钢材（每周的需求量已知） 　不同工厂生产不同型号的钢材成本不同 目标： 　生产钢材费用最小 设xij为第i个工厂生产钢材j的数量 求得生产方案为 设xij为第i个工厂生产钢材j的数量 作业： P98　3.3 表3-46，3-48（产销不平衡问题） P99　3.5，3.6 满足运输问题特征！ 转化为运输问题的图表示法 130 130 钢材3 120 150 120 产量 130 10 120 钢材2 130 120 10 钢材1 3 需求 2 1 工厂 最优总生产成本为14660 6 5 6 3 销量 9 3 5 10 6 4 7 A3 4 8 1(