§ 运输问题及其数学建模
§ 表上作业法
§ 产销不平衡的运输问题
§ 应用举例
本章主要内容:
、系数矩阵特殊形式
、最小元素法求初始基可行解
、位势法求解过程和表上作业法求解运输问题过程
教学要求:
一、运输问题及其数学模型
在经济建设中,经常碰到物资调拨中的运输问题。
例如煤、钢材、粮食、木材等物资,在全国都有若干生产基地,分别将这些物资调到各消费基地去,应如何制定调运方案,使总的运输费用最少?
问题的提出:
运输问题的一般提法是:设某种物资有m个产地和n个销地。产地Ai的产量为;销地Bj的销量。从第i个产地向第j个销地运输每单位物资的运价为Cij。
这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。
1、运输问题的一般提法
单位运价表
(1) 。即运输问题的总产量等于其总
销量,这样的运输问题称为产销平衡的运输问题。
(2) 。即运输问题的总产量不等于总
销量,这样的运输问题称为产销不平衡的运输问题。
分两种情况来讨论:
若用xij表示从Ai到Bj的运量,那么在产销平衡的条件下,要求得总运费最小的调运方案,数学模型为:
2、运输问题的数学模型
其中,ai和bj满足: 称为产销平衡条件。
将约束方程式展开可得
约束方程式中共mn个变量,m+n个约束。
上述模型是一个线性规划问题。但是其结构很特殊,特点如下:
(mn个),但结构简单。
技术系数矩阵
该系数矩阵中每列只有两个元素为1,其余的都为零。
+n个约束中有一个是多余的(因为其间含有一个平衡关系式)
所以R(A)=m+n-1,即解的mn个变量中基变量为m+n-1个。
运输问题数学建模 来自淘豆网www.taodocs.com转载请标明出处.