《运筹学》课程教学资源（试卷习题）第4章 运输问题

第四章运输问题本章主要内容$ 4.1运输问题与有关概念$ 4.2运输问题的求解----表上作业法S4.3运输问题应用----建模

§4.1 运输问题与有关概念 §4.2 运输问题的求解-表上作业法 §4.3 运输问题应用-建模 本章主要内容 第 四 章 运 输 问 题

85.1、运输问题模型及有关概念问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案

§5.1 、运输问题模型及有关概念 问题的提出 一般的运输问题就是要解决把某种 产品从若干个产地调运到若干个销地， 在每个产地的供应量与每个销地的需求 量已知，并知道各地之间的运输单价的 前提下，如何确定一个使得总的运输费 用最小的方案

例4.1某公司从三个产地A、Az、A,将物品运往四个销地B、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示销地B1B2B3B4产量产地337A11110924A2185749A310365销量620（产销平衡）问应如何调运，可使得总运输费最小？

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

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

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

s.t.Xi1+ X12 + Xi3 + Xi4 = 7X21 + X22+ X23 + X24 = 4X31 + X32+ X33 + X24 = 9Xi1 + X21 + X31 = 3X12 + X22 + X32 = 6X13 + X23 + X33 = 5X14 + X24 + X34 = 6X;≥0 (i=1、2、3; j=1、2、3

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

其系数矩阵为：111100000000000000001一1一00000001一010000000101A=10000001010010000100001100000010000011共有 m+n 行，分别表示产地和销地；有mn 列分别表示各变量；每列只有两个1，其余为0

其系数矩阵为 ：                         = 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 A 共有 m+n 行，分别表示产地和销地；有 mn 列分别表示各变量；每列只有两个 1，其 余为 0

一般运输问题的提法：假设 Al、A、.、Am表示某物资的m个产地；Bi、B2、、B，表示某物资的n个销地;S.表示产地A.的产量；d.表示销地B.的销量；C；表示把物资从产地 A,运往销地 B,的单位运价。 如果s, + s + ... + Sm= d, + d, +... + d, '则称该运输问题为产销平衡问题；否则，称产销不平衡。下面，首先讨论产销平衡问题

一般运输问题的提法： 假设 A1、 A2、.、 Am 表示某物资的m个 产地；B1、B2、.、Bn 表示某物资的n个销地； si 表示产地 Ai的产量；dj 表示销地 Bj的销量； cij 表示把物资从产地 Ai 运往销地 Bj 的单位运 价。如果s1 + s2 + . + sm = d1 + d2 + . + dn ， 则称该运输问题为产销平衡问题；否则，称产 销不平衡。下面，首先讨论产销平衡问题

销地产量B1B2 ... Bn产地A1aiC11C12CinA2a2C21C22C2n---.-AmamCm2CmnCml销量b1bnb2.解：设x为从产地A,运往销地B.的运输量

销地 产地 B1 B2 . Bn 产量 A1 A2 ┇ Am c11 c12 . c1n c21 c22 . c2n ┇ ┇ ┇ ┇ cm1 cm2 . cmn a1 a2 ┇ am 销量 b1 b2 . bn 解：设 xij 为从产地Ai 运往销地 Bj的运输量

mnmin f=Zcjxui=l j=lnZx,≤a,s.t.i=1,2,...,mj=1mZx,≥b,j=1,2,...,ni=1i=1,2,...,m j=1,2,...,nXj ≥0

i j m i n j f ci jx = = = 1 1 min st x ai i m n j i j . . 1,2, , 1   =  = x b j n j m i i j 1,2, , 1   =  = x 0 i 1,2, ,m j 1,2, ,n ij  =  = 

对于产销平衡问题，可得到下列运输问题的模型：mnZZcijxjmin f =i-l j=ln2s.t.i=1,2,...,mXij =α;i=1mZx,=b,j=1,2,...,ni=1X, ≥0i=1,2,..,mj= 1,2,..,n

对于产销平衡问题，可得到下列运输 问题的模型： i j m i n j f ci jx = = = 1 1 min st x ai i m n j i j . . 1,2, , 1  = =  = x b j n j m i i j 1,2, , 1  = =  = x 0 i 1,2, ,m j 1,2, ,n ij  =  = 