第三部分运输问题目jssk运筹学.pptVIP

运 筹 学 教 程 运输问题 在经济建设中，经常会遇到大宗物资调拨中的运输问题，如煤炭、钢铁、木材、粮食等物资，在全国有若干生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运到各消费地点，而使总运费最小。 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。 运输问题 解：我们知道A1、A2两个产地的总产量为：200 + 300 = 500（件）；B1，B2，B3三个销地的总销量为：150+150+200=500（件）,总产量等于总销量这是一个产销平衡的运输问题。把 A1，A2 的产量全部分配给B1，B2，B3，正好满足这三个销地的需要。 运输问题 假设有m个生产地点（以后称为产地），可以供应某种物资，用Ai表示，i=1,2…,m；有n个销售地（以后称为销地），用Bj表示，j=1,2,…,n；产地的产量和销地的销售量分别为ai，i=1,2,…,m和bj，j =1,2,…,n，从Ai到Bj运输单位物资的运价为cij。 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 将检验数填入产销平衡表中，并用括号括起来。 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 表上作业法计算中的问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 运输问题 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 第3节 产销不平衡的运输问题及其求解方法 运输问题的数学模型可写成 由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。这时，只要增加一个假想的销地j＝m+1（实际上是储存），该销地的总需要量为： 设xi, n+1是产地Ai的储存量，于是有： 可转化为产销平衡的运输问题 因为 可转化为产销平衡的运输问题 因为 在单位运价表中，从各产地到假想销地的单位运价为ci,n+1=0，就可转化成产销平衡的运输问题。 当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为 而在单位运价表中从各产地到假想销地的单位运价为， 就转化成一个产销平衡的运输问题。 在最优解中，虚设产地Am+1到销地Bj的运量实际上就是最后分配方案中销地Bj的缺货量。 在产销不平衡问题中，如果某产地不允许将物资就地贮存或者不允许缺货，则要令相应运价Ci,n+1或Cm+1,j=M（M是充分大的正数）。 第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素。如表中，B2列是最大差额所在列，B2列中最小元素为4，可确定A3的产品先供应B2的需要，同时将B2列数字划去，如图： 第三步：对表中未划去的元素再分别计算出各行、各列的最小元素和次最小运费的差额，并填入该表的最右列和最下行。重复第一、二步。直到给出初始解为止。如图： 由以上可见，伏格尔法同最小元素法除在供求关系的原则上不同外，其余步骤相同。伏格尔法给出的初始解比用最小元素法给出的初始解更接近最优解。本例用伏格尔法给出的初始解就是最优解。 2）最优解的判别－闭回路法 在用西北角法和最小元素法确定初始方案，产销平衡表中，我们称右上角没有填数字的格子为空格，而把右上角填有数字的个子称为基格。 闭回路，就是从某一空格出发，沿水平或垂直方向前进，如遇基格可作垂直或水平方向转向（转向处称顶点）前进，也可穿越继续前进。如遇空格不能转向，必须穿越继续前进，但最后仍回到原来的空格，目的是围成一个矩形的，或各边顺次垂直的曲折多变形的闭合回路。 2）最优解的判别－闭回路法 闭回路的顶点除去起始和终了是同一个空格外，其他所有顶点均为基格。凡是可行的调运方案，每一个空格，也就是每一个非基变量，都可以画一个闭回路