运筹学课件 第三章 运输问题.ppt

1、第三章运输问题、模型及其特点、解决方案和相关理论解决方案。基于操作的运输问题的概括见表1。产销不平衡的运输问题。转运问题。第一节运输问题及其数学模型。运输问题的数学模型。运输问题的一般表述：一种材料有几个产地和销售地，现在需要将这种材料从每个产地运输到每个销售地。总产量等于总销售量。给定每个产地的产量和每个销售地点的销售量，以及从每个产地到每个销售地点的单位运费率(或运输距离)，如何组织运输可以使总运费率(或总运输量)最经济？单位是根据具体问题确定的。表相关信息，2，运输问题的数学模型，设xij为从Ai到Bj运输的物料量(i=1，m；J=1，n)，因为从ai装运的物料总量应等于Ai的产量Ai，

2、所以xij应满足以下要求：同样，装运到bj的物料总量应等于Bj的销售量Bj，所以xij还应满足以下要求：总运费为：运输问题的数学模型，2。运输问题数学模型的特点1约束方程的系数矩阵有一个特殊的结构系数矩阵，它是：运输列向量Pij=(0，0，1，0，0，1，0，0)T，其中两个元素1分别位于第I行和第m行。该矩阵被分成块，其特征在于，前m行构成m个mn阶矩阵，并且只有第k行矩阵的第k行中的元素全部为1，而其他元素全部为0(k=1，m)；最后n行构成m个n阶单位矩阵。证明了系数矩阵a及其增广矩阵的秩都是m n-1，加减后的前m行之和是零向量，这说明m n行向量是线性相关的，所以秩小于m n；因此，

3、a的秩正好等于m n-1，d本身包含在a中，所以a的秩也等于m n-1，m n-1方阵d由第二至m n行、前n列和相应的列相交元素组成；可以证明任意m n-1个m n约束方程是线性无关的。在第二节中，求解运输问题的表上作业法的基本思想是：首先尝试给出一个初始方案，然后根据确定的准则对初始方案进行检查、调整和改进，直到得到如图所示的最优方案。表运算法和单纯形法的求解思路完全一致，但具体方法更简单。解决运输问题的思路，1。初始方案1的确定。操作表(产销平衡表)初始方案是初始的基本可行方案。“作业表”(产销平衡表)是将运输问题的信息表与决策变量的调度量结合起来形成的。下表是两个产地和三个销售地的运输

4、问题操作表。表运输问题操作表(生产和销售平衡表)，其中xij是一个决策变量，表示从第I个产地到第j个销售地点的运输数量，cij是从第I个产地到第j个销售地点的单位运费率或运输距离。2.确定初始方案的步骤：(1)选择一个xij，让xij=minai，bj=，并在表中xij的位置填入具体值；(2)调整生产和销售的剩余量：分别从ai和bj中减去xij的值，如果ai-xij=0，则划掉ai所在的行，即该地的产量已经无剩余地运出，而Bj仍有需求缺口-Ai；如果Bj-xij=0，则Bj所在的列被划掉，表示对该土地的需求已经得到满足，在原产地Ai仍有剩余的Ai-Bj；(3)当操作表中的所有行或列都被划掉时，

5、意味着所有的输出已经被运送到所有的销售地点，并且所有的需求已经被满足。xij的值构成了初始方案。否则，在作业表的剩余网格中选择下一个决策变量，并返回步骤(2)。根据上述情况采用不同的规则选择xij，形成不同的方法。例如，对应于最低运费率(或运输距离)的xij总是在操作表的剩余网格中选择，这构成了最小元素法。如果每次选择与左上角网格对应的xij，将形成西北角方法(也称为左上角方法)和Vogel(3)方法。3.例如，在某个部门有三个工厂生产类似的产品，生产的产品在四个地方销售。1，最小元素法，产地，销售地，4，12，10，2，8，5，11，3，4，11，9，6，8，2，10，14，8，6，z，在价

6、格表上找到最小值，并在平衡表上设置生产和销售；为满足销售量，应删除“栏”，并在头脑中修改“生产线”；(“行”应在满足输出时划掉，而“输出”应修改。)剩余的表将用于查找最小的表。2，西北角方法，4，3，9，4，11，12，11，6，8，5，10，2，8，8，8，6，4，8，14，z=8x4 8x其他过程与最小元素方法相同。3.在vogel方法中，从每个供应地到销售地(或从每个销售地到供应地)的单位运费率中找出最小运费率和次最小单位运费率，并且运费率的差异是从供应地到销售地的惩罚。如果罚款金额不大，按最小单位不能运输时造成的损失也不大；如果罚值较大，未按最小单位运输造成的损失较大，应尽可能按最小单

7、位运输；计算步骤1:计算每一行和每一列的惩罚数，称为行惩罚数和列惩罚数。2.将计算的行惩罚和列惩罚添加到表中。3.根据行惩罚数和列惩罚数(行等于列)找出最大惩罚数，确定惩罚数所在的行或列，并根据最小单位法对表进行运算。4、9、4、11、6、11、5、8、12、2、3、10、14、8、12、2、4、Z. 2。三种表格运算法求解运输问题的计算步骤。网络作业：作业1:下载lingo软件，安装并使用它。将下载网址存储在word文件中，并作为附件发送到以下电子邮件地址：1 0501:云初学1 _ 1 0502:云初学1 _要求：主题：学号名称1 (052820528刘1)附件文件名：学号名称1(052820528刘1)作业1截止日期：第7周数据表的建立；数学模型的建立；行话软件解决方案；敏感性分析。形成的文件是一个word文档，并作为附件发送到以下邮箱：1 0501:运畴学1 _ 1 0502:运畴学1 _要求：1。数学模型是用mathtype写成的。2.第三个标题是粗体；副标题小3号加粗；四号歌的文字很小；固定行距为18磅；3.科目：学号2 (052820528刘2) 4。附件档案名称：学号2 (052820528刘2)作业2