运输问题数学建模.ppt

§ § 运输问题及其数学建模§ § 表上作业法§ 产销不平衡的运输问题§ § 应用举例本章主要内容: ?1 .掌握运输问题的数学模型、系数矩阵特殊形式?2 .掌握用西北角法、最小元素法求初始基可行解?3 .掌握回路、位势法求解过程和表上作业法求解运输问题过程教学要求: 一、一、运输问题及其数学模型?在经济建设中,经常碰到物资调拨中的运输问题。?例如煤、钢材、粮食、木材等物资,在全国都有若干生产基地,分别将这些物资调到各消费基地去,应如何制定调运方案,使总的运输费用最少? 问题的提出: 运输问题的一般提法是:设某种物资有 m个产地和 n个销地。产地 A i的产量为;销地 B j的销量。从第 i个产地向第 j个销地运输每单位物资的运价为 C ij。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。),,2,1(m ia i??),,2,1(njb j??1、运输问题的一般提法单位运价表(1)。即运输问题的总产量等于其总销量,这样的运输问题称为产销平衡的运输问题。(2)。即运输问题的总产量不等于总销量,这样的运输问题称为产销不平衡的运输问题。????? nj j mi iba 11????? nj j mi iba 11分两种情况来讨论: 若用 x ij表示从 A i到B j的运量,那么在产销平衡的条件下, 要求得总运费最小的调运方案,数学模型为: ????????????????????????0 ,,2,1 )13(,,2,1.. min 1 1 11 ij nj i ij mi j ij mi nj ij ijx m iax njbxts xcz?? 2、运输问题的数学模型其中, a i和b j满足: 称为产销平衡条件。????? nj j mi iba 11 将约束方程式展开可得 11 1 1 21 2 2 1 11 21 1 1 12 22 2 nn m mn m mm x x a x x a x x a x x x b x x x ? ? ?? ? ?? ? ?? ? ?? ???? ???? 2 1 2 n n mn n b x x x b ?????????????? ? ??? ????约束方程式中共 mn个变量, m+n 个约束。行行 n m A xxxxxxxxx mn mm n n?????????????????????????????????????????111 111 111 111 111 111 212 22 21 1 12 11???????????????上述模型是一个线性规划问题。但是其结构很特殊, 特点如下: ( mn个),但结构简单。技术系数矩阵该系数矩阵中每列只有两个元素为 1,其余的都为零。 i j a b ?? ? +n 个约束中有一个是多余的(因为其间含有一个平衡关系式) 所以 R(A)=m+n-1 ,即解的 mn个变量中基变量为 m+n-1 个。