华北理工大学：《运筹学》课程教学课件（讲稿）第3章 运输问题

第三部分运输间题本章主要内容8 3.1 运输问题与有关概念8 3.2运输问题的求解一表上作业法8 3.3产销不平衡的运输问题

§3.1 运输问题与有关概念 §3.2 运输问题的求解—表上作业法 §3.3 产销不平衡的运输问题 产销不平衡的运输问题 本章主要内容 第三部分 运输问题

人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的生产量和需要量及各地之间的运输费用，如何制定一个运输方案，使总的运输费用最小。这样的问题称为运输问题

人们在从事生产活动中，不可避免地要进行物资调运工作。如 某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到 需要这些物资的地区，根据各地的生产量 和需要量及各地之间 的运输费用，如何制定一个运输方案，使总的运输费用最小。 这样的问题称为运输问题

运输问题是一类常见而且极其典型的LP问题。从理论上讲，运输问题可以用单纯型来求解。但由于运输问题数学模型具有特殊的结构，存在一种比单纯型法更简便的计算方法一一表上作业法。用表上作业法来求解运输问题比单纯型可节约计算时间与计算费用，但表上作业法实质上仍是单纯型法

运输问题是一类常见而且极其典型的LP问题。从 理论上讲，运输问题可以用单纯型来求解。但由 于运输问题数学模型具有特殊的结构，存在一种 比单纯型法更简便的计算方法——表上作业法。 用表上作业法来求解运输问题比单纯型可节约计 算时间与计算费用，但表上作业法实质上仍是单 纯型法

S3.1运输问题模型及有关概念运输问题的一般提法是：设某种物资有m个产地和n个销地。产地A的产量为a,(i=1,2,,m)；销地B,的销量为b，（j=1,2,,n)。从第i个产地A向第j个销地B,运输每单位物资的运价为Ci。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小

§3.1 运输问题模型及有关概念 运输问题模型及有关概念 运输问题的一般提法是：设某种物资有m个产 地和 n个销地。产地 Ai 的产量为 mia ),2,1( i = L ；销 地Bj的销量为 njb ),2,1( j = L 。从第i 个产地 Ai 向第 j 个销地Bj 运输每单位物资的运价为Cij。这就是由多 个产地供应多个销地的单品种物资运输问题。问如 何调运这些物资才能使总运费达到最小

例3.1某公司从三个产地Ar、Az、A,将物品运往四个销地Bi、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地BiB2B3B4产量产地9A1297101325A2482547A33684销量21（产销平衡)问应如何调运，可使得总运输费最小？

例3.1 某公司从三个产地A1、A2、A3 将物品运 往四个销地B1、B2、B3、B4，各产地的产量、各 销地的销量和各产地运往各销地每件物品的运费 如下表所示 销地 产地 B1 B2 B3 B4 产量 A1 2 9 10 7 9 A2 1 3 4 2 5 A3 8 4 2 5 7 销量 3 8 4 6 21（产销平 衡） 问应如何调运，可使得总运输费最小?

解：这是一个产销平衡的运输问题，设x：为从产地A,运往销地B,的运输量（i=1，2，3；j=1，2, 3, 4)所以此运输问题的线性规划模型如下：Min z= 2xu+ 9x12+ 10xi3+ 7x14+ X21+ 3x22 +4x23+ 2x24+ 8x31+ 4x32+ 2x33+ 5x34

解： 这是一个产销平衡的运输问题，设 xij 为从产 地 Ai 运往销地 Bj 的运输量（i = 1，2，3； j = 1， 2，3，4） 所以此运输问题的线性规划模型如下： Min z= 2x11+ 9x12+ 10x13+ 7x14+ x21+ 3x22 + 4x23+ 2x24+ 8x31+ 4x32+ 2x33+ 5x34

= 9S.t. Xu+X12 +X13 + X14=5X21 + X22+ X23 + X24X31 + X32+ X33 + X24 = 7=3+X21+ X31X11= 8+X22+X32X12= 4+×23+X33X13+X34 = 6+ X24X14X, ≥0 (i=1,2,3; j=1,2,3,4)

s.t. x11+ x12 + x13 + x14 = 9 x21 + x22+ x23 + x24 = 5 x31 + x32+ x33 + x24 = 7 x11 + x21 + x31 = 3 x12 + x22 + x32 = 8 x13 + x23 + x33 = 4 x14 + x24 + x34 = 6 xij ≥ 0 ( i = 1 , 2 , 3；j = 1 , 2 , 3,4)

其系数矩阵为：0(11100100000100010000110000000011110000100000011A=000001000011000000101100000000010(011共有3+4行，分别表示产地和销地；：有3x4列分别表示各变量：每列只有两个1，其余为0

其系数矩阵为 ： ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎛ = 100010001000 010001000100 001000100010 000100010001 111100000000 000011110000 11 0000000011 A 共有 3+4 行，分别表示产地和销地；有 3×4 列分 别表示各变量；每列只有两个 1，其余为 0

表3一1销地B 1B 2B产量产地nx11X12xinAlaiA2X 21X 22X2na2：:....Amamxml+xm2mnb1b 2b销量如果a,+a2+..+am=b,+bz+..+bn，则称该运输问题为产销平衡问题；否则，称产销不平衡

销 地 产 地 1 BB 2 L B n 产量 Am A A M 2 1 m m mn n n xx x xx x xx x L LLLL L L 1 2 21 22 2 11 12 1 m a a a M 2 1 销量 1 bb 2 L b n 表3—1 如果a1 + a2 + . +am = b1 + b2 + . + bn ， 则称该运输 问题为产销平衡问题；否则，称产销不平衡

表 3—2单位运价表销地BB 1B 2n产地A1C 11C 12Cin...A2C 22C 21C2n................AmcCc...m 1m2mn

表 3—2 单位运价表 销 地 产 地 1 BB 2 L B n Am A A M 2 1 m m mn n n cc c cc c cc c L LLLL L L 1 2 21 22 2 11 12 1