运筹学运输问题表上作业法

1、运运 筹筹 学学 李细霞李细霞2013物流工程物流工程1班班20142015学年第二学期学年第二学期课程主要内容Transportation problemTransportation problem3第三章 运输问题学习目标主要内容思考u运输问题要解决什么？u什么叫一个运输方案？u什么叫一个最优的运输方案？u若用xij表示从Si到Dj的运量，那么在产销平衡的条件下，求总运费最小的方案。问题描述问题描述7表格模型8生产量：生产量：A1A1-7 7吨，吨， A2-4A2-4吨，吨， A3-9A3-9吨吨销售量：销售量：B1-3B1-3吨，吨，B2-6B2-6吨，吨，B3-5B3-5吨，吨，B4-

2、6B4-6吨吨产地产地单位运价单位运价销地销地B1 B2 B3 B4B1 B2 B3 B4 A1A1A2A2A3A3 3 11 3 11 3 3 10 10 1 1 9 9 2 2 8 8 7 7 4 4 10 105 5产销平衡？9A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地调运示意图10此问题是线性规划问题吗？请建立此问题的模型目标？约束条件？思考11二、建立模型二、建立模型设：设：x xijij第第i i产地到第产地到第j j销地之间的调运量，则有销地之间的调运量，则有Min z = Min z

3、= c cijij x xijij3 34 4i=1i=1 j=1j=1x x1111+x+x1212+x+x1313+x+x1414=7=7x x1111+x+x2121+x+x3131=3=3x xijij 0 0,(i=1,2,(i=1,2,3,3；j=1,2,j=1,2,4),4)产量限制产量限制销量限制销量限制x x2121+x+x2222+x+x2323+x+x2424=4=4x x3131+x+x3232+x+x3333+x+x3434=9=9x x1212+x+x2222+x+x3232=6=6x x1313+x+x2323+x+x3333=5=5x x1414+x+x2424

4、+x+x3434=6=612销销地地 产产地地 B 1 B 2 B n 产产量量 C 11 C 1 2 C 1 n A 1 x 11 x 1 2 x 1 n a 1 C 21 C 2 2 C 2 n A 2 x 21 x 2 2 x 2 n a 2 C m 1 C m 2 C m n A m x m1 x m 2 x m n a m 销销量量 b 1 b 2 b n ai= = bj产销平衡运输问题的一般表示13njmixnjbxmiaxxczijjmiijinjijminjijij, 2 , 1;, 2, 1, 0, 2 , 1, 2 , 1,min1111调运模型为：调运模型为：mn个变量

5、m个约束n个约束共有m+n个约束条件？14nnmmnnnmmmnmmnmnmmmnmnnmnnnmnnbxxxxxxbxxxxxxxbxxxxxxxaxxxxxxaxxxxxxxaxxxxxxx1221111221222112111122211121121111123122221111131221112110000000000000000000000约束条件展开15111111111111111111212221212111nmmmnnxxxxxxxxx行行nm约束条件的系数矩阵有何特点？161.变量数：mn个2.约束方程数：m+n个 最大独立方程数：m+n-13.系数列向量结构：Pij=第i

6、个分量第m+j个分量产销平衡运输问题模型的特点Why?01.1.017 定理平衡条件下的运输问题一定有最优解平衡条件下的运输问题一定有最优解 证：若设证：若设 njjmiibaQ11，并令，并令Qbaxjiij ，则，则ijx显然是一显然是一组可行解，又因为总费用不会为负值，这说明，运输问题既有可行解，又组可行解，又因为总费用不会为负值，这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。必然有下界存在，因此一定有最优解存在。显然，由于运输问题属线性规划问题，因此无疑可以用单纯形方法显然，由于运输问题属线性规划问题，因此无疑可以用单纯形方法求解，但由于其数学模型自身结构的特殊性

7、，也可以利用更简便的方法求解，但由于其数学模型自身结构的特殊性，也可以利用更简便的方法来求解。这与运输问题的特点有关。来求解。这与运输问题的特点有关。唯一最优解？无穷多最优解？18基本可行解检验数基变换用单纯形法求解线性规划问题的步骤表上作业法表上作业法19单纯形法在求解运输问题时的一种简化方法单纯形法在求解运输问题时的一种简化方法201.西北角法 2.最小元素法3.伏格尔法1.闭回路法2.位势法闭回路法产量产量产地产地销地销地A1 A1 A2 A2 A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量4 41 13 310102 25 53 6 5 63 6 5 67 7 4 4 9

8、 9 3 3 11 11 9 9 8 8 7 10运价运价总产总产= =总销总销2223西北角法产量产量产地产地销地销地A1 A1 A2 A2 A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量3 6 5 63 6 5 67 7 4 4 9 9342236108653102229411333141ijijijxcZ有何疑问？24西北角法的优劣？太简单咯！最优解有点望尘莫及呢25几点疑问为什么要从西北角开始？为什么要从西北角开始？为什么每次填数一定要填最大允许量，然后划掉一行（或一列）？26基本可行解基本可行解一个基本可行解：有m+n-1个基变量（有数格），其余为非基变量（空格）m+n

9、-1个变量不能不能构成闭回路闭回路充要条件举例1234123123412312341231234123下面这些有数格组成了闭回路下面这些有数格组成了闭回路（不能作为基本可行解）（不能作为基本可行解）什么是闭回路？123412312341231234123123412312341231234123下面这些有数格没有组成闭回路下面这些有数格没有组成闭回路（可以作为基本可行解）（可以作为基本可行解）29几点疑问的解答为什么要从西北角开始？为什么要从西北角开始？为什么每次填数一定要填最大允许量，然后划掉一行（或一列）m+n-1个变量不能构成闭回路只有6个有数格基变量的个数为m+n-1（3+4-1）30

10、所有问题答案归结一句话：保证初始方案是运输问题（线性规划问题）的基本可行解Why？随便一个可行解不行么？31最小元素法产量产量产地产地销地销地A1 A1 A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量3 6 5 63 6 5 67 7 4 4 9 93113101928741053146338635641231310433141ijijijxcZ32最小元素法的优劣？也很简单哦最优解可望，但还是有一定距离的33伏格尔法产量产量产地产地销地销地A1 A1 A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量3 6 5 63 6 5 67 7 4 4 9 93

11、1131019287410534产地产地销地销地A1 A1 A2 A2 A3A3B1 B2 B3 B4B1 B2 B3 B4行差额行差额列差额列差额3 11 3 10 3 11 3 10 1 9 2 8 1 9 2 8 7 4 10 5 7 4 10 5 0 0 1 1 1 12 5 1 3 2 5 1 3 0 0 1 1 2 22 - 1 32 - 1 30 0 1 1 - -2 - 1 22 - 1 27 7 6 6 - - - 1 2- - 1 2VogelVogel法法: :产地产地销地销地A1 A1 A2 A2 A3A3B1 B2 B3 B4B1 B2 B3 B47 7 4 4 9

12、9产量产量销量销量3 6 5 63 6 5 66 63 35 52 21 13 3产销平衡表产销平衡表单位运价表单位运价表伏格尔法（差额法）8535641831210533141ijijijxcZ对最小元素法的改进35伏格尔法的优劣？离最优解貌似很近了哦求解过程有点麻烦呢！用用VogelVogel法求出的初始解叫做法求出的初始解叫做“近似最优解近似最优解”36课堂练习：用最小元素法求初始解课堂练习：用最小元素法求初始解产量产量产地产地销地销地A1 A1 A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量3 5 8 43 5 8 49 9 4 4 7 7531041696201

13、05737产量产量产地产地销地销地A1 A1 A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4销量销量3 5 8 43 5 8 49 9 4 4 7 7531041696201057只有5个有数格，不是基本可行解吗？53417课堂练习答案38 销地 利润产地ABCD产量1056725082762509348500销量150200300350应用举例：用最小元素法或伏格尔法求初始解“总利润最大”而不是“运费最小”，“最小元素”怎么找？39最优性检验闭回路法表示什么？表示什么？每个空格都能找到闭回路吗？有的话，是否唯一？每个空格有且只有一条闭回路！46u若存在某些检验数小于0，则说明调

14、整后运价将减少。（不是最优解）u 若存在某些检验数等于0，则说明调整后运价将不发生改变。（多个最优解）u若所有检验数大于0，说明调整后运价将增加。（唯一最优解）最优方案：所有检验数0注意是目注意是目标最小化标最小化的问题的问题如果将运输问题的运价表改为利润表，则应如果求初始方案，如何判断方案是否最优？48最优性检验位势法（对偶变量法）u 设设 U1,U2,Um,V1, V2, Vn 是对应是对应m+n个个约束条件的对偶变量约束条件的对偶变量u 其中其中Ui对应第对应第i个产地的产量约束，个产地的产量约束， Vj对应对应第第j个销地的销量约束个销地的销量约束u 称称Ui为行位势，为行位势， Vj

15、为列位势为列位势492.2. 令令u u1 1=0=0，则依，则依c cijij=u=ui i+v+vj j 计算各计算各u ui i和和v vj j 3.3.计算空格处位势；计算空格处位势； ijij=c=cij-ij-（u ui i+v+vj j）1.1.在表中增加一行一列在表中增加一行一列, ,填上行位势填上行位势u ui i, ,列位势列位势v vj j, , 在在对应初始方案有数格处写对应初始方案有数格处写0 0（基变量检验数为（基变量检验数为0 0）；）；位势法的图表形式位势法的图表形式:u ui i产地产地销地销地A1 A1 A2A2A3A3B1 B2 B3 B4B1 B2 B3

16、 B4v vj ju u3 3=-5=-5311310192874105B1B2B3B4A143A231A363000000v v3 3=3=3v v4 4=10=10u u1 1=0=0 u u2 2=-1=-1 v v1 1=2=2v v2 2=9=9121-1101250位势法计算非基变量位势法计算非基变量x xijij检验数的公式检验数的公式 ijij=c=cijij- -（u ui i+v+vj j）ij =（闭回路上偶数次顶点运价之和）（闭回路上偶数次顶点运价之和）-（闭（闭 回路上奇数次顶点运价之和）回路上奇数次顶点运价之和） 闭回路法计算非基变量闭回路法计算非基变量xij检验数

17、的公式：检验数的公式：比较检验数计算的两种方法比较检验数计算的两种方法5152ij若有多个检验数小于零，则取其中最小的负数若有多个检验数小于零，则取其中最小的负数5354 +1-1+1+1-155B1B2B3B4A152A231A3630，即得到最优方案。568535641831210533141ijijijxcZB1B2B3B4A152A231A363运输问题的应用产销不平衡问题生产与存储问题转运问题由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。设有三个化肥厂设有三个化

18、肥厂(A(A，B B，C)C)供应四个地区供应四个地区(，)的农用化肥。各化肥厂年产量，各地区年需要的农用化肥。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如下表量及从各化肥厂到各地区运送单位化肥的运价如下表所示。试求出总的运费最节省的化肥调拨方案。所示。试求出总的运费最节省的化肥调拨方案。产销不平衡问题产销不平衡问题这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60万吨，这样最高需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由

19、于各地区的需要量包含两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表和单位运价表。产销平衡表单位运价表根据表上作业法计算，可以求得这个问题的最优方案请简单描述此方案生产与储存问题某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需

20、储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产费用(包括储存、维护费用) 最小的方案。 解：由于每个季度生产出来的柴油机不一定当季解：由于每个季度生产出来的柴油机不一定当季交货，所以设交货，所以设x xijij为第为第i i季度生产的用于第季度生产的用于第j j季度交季度交货的柴油机数。根据合同要求，必须满足货的柴油机数。根据合同要求，必须满足2025151044342414332313221211xxxxxxxxxx又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有： 1030352544343324232214131211xxxxxx

21、xxxx第第i i季度生产的用于季度生产的用于j j季度交货的每台柴油机的实季度交货的每台柴油机的实际成本际成本c cijij应该是该季度单位成本加上储存、维护应该是该季度单位成本加上储存、维护等费用。等费用。c cijij的具体数值见下表：的具体数值见下表：设用设用a ai i表示该厂第表示该厂第i i季度的生产能力，季度的生产能力，b bj j表表示第示第i i季度的合同供应量，则问题可写成：季度的合同供应量，则问题可写成：目标函数：约束条件：4141minijijijxcz04141ijijijjiijxbxax显然，这是一个产大于销的运输问题模型。注意到这个问题显然，这是一个产大于销的

22、运输问题模型。注意到这个问题中当中当i ij j时，时，x xijij=0=0，所以应令对应的，所以应令对应的c cijij=M=M，再加上一个假，再加上一个假想的需求想的需求D D，就可以把这个问题变成产销平衡的运输模型，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表并写出产销平衡表和单位运价表( (合在一起，见下表合在一起，见下表) )。经用表上作业法求解，可得多个最优方案，下表是最优方案之一。即第季度生产25台，10台当季交货，15台季度交货；季度生产5台，用于季度交货；季度生产30台，其中20台于当季交货，10台于季度交货。季度生产10台，于当季交货。按此方案生产

23、，该厂总的生产费用(包括储存、维护费用)为773万元。转运问题每个产地的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间进行转运。71产地：原产地、中间转运站、转运物资的销地产地：原产地、中间转运站、转运物资的销地销地：原销地、中间转运站、转运物资的产地销地：原销地、中间转运站、转运物资的产地如果是产销不平衡问题，先通过增加虚拟的产如果是产销不平衡问题，先通过增加虚拟的产地或销地转化为产销平衡问题。地或销地转化为产销平衡问题。设各转运站转运物资的数量均为

24、总产量设各转运站转运物资的数量均为总产量 a ai i（或总销量（或总销量 b bj j ）专职转运站专职转运站的产量和销量均为的产量和销量均为 a ai i原产地原产地A Ai i的产量均为（的产量均为（a ai i+ a+ ai i）原销地原销地B Bj j的销量均为（的销量均为（ b bj j+ a+ ai i）将各条线路实际的运输单价列成将各条线路实际的运输单价列成单位运价表单位运价表，其中不可能的运输其单位运价用其中不可能的运输其单位运价用M M表示。表示。扩展运输表扩展运输表的构建步骤的构建步骤举例：举例：A A、B B两个化肥厂每年各生产磷肥两个化肥厂每年各生产磷肥900900万

25、吨和万吨和600600万万吨，这些化肥要运到三个港口，已知三个港口吨，这些化肥要运到三个港口，已知三个港口C C、D D、E E每每年能承担的船运量分别为年能承担的船运量分别为700700、400400、300300万吨，两个工厂万吨，两个工厂及三个港口之间单位运价如下表所示，为按需要把磷肥及三个港口之间单位运价如下表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？运到各港口，怎样安排运输才能使运费最少？ABCDEA029107B2071010C97034D1010302E71042073C CD DE E产量产量A A900900B B600600销量销量700700400400

26、300300C CD DE EF F产量产量A A900900B B600600销量销量700700400400300300100100产（或产（或销）销）=1500=1500A AB BC CD DE E产量产量( (转运量转运量) )A A15001500B B15001500C C15001500D D15001500E E15001500销量销量( (转运量转运量) )150015001500150015001500150015001501500 0转运转运=7500=7500表表1 1表表2 2表表3 3产销平衡运输表的构建产销平衡运输表的构建ABCDEA029107B2071010

27、C97034D1010302E710420=1500+7500=9000=1500+7500=9000F发量发量收量收量900+1500=2400600+1500=21001500150015001500 1500700+1500=2200400+1500=1900300+1500=1800100000 00将表将表2 2和表和表3 3合并为一张表（加上单位运价）合并为一张表（加上单位运价）例：已知各产地、销地、中间转运站及相互之间每吨产品的运价如表所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。(1) 由于问题中所有

28、产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。(2) 对扩大的运输问题建立单位运价表。方法将表中不可能的运输方案的运价用任意大的正数M代替。(3) 所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。由于实际的转运量mijijinjijbxax11,可以在每个约束条件中增加一个松弛变量xii，xii相当于一个虚构的转运站，意义就是自己运给自己。(20-xii)就是每个转运站的实际转运量，xii的对应运价cii=0。(4) 扩大的运输问题中原来的产地与销地因为也有转运站的作用，所以同样在原来产量与销量的数字上加20吨，即三个厂每天糖果产量改成27，24，29吨，销量均为20吨；四个销售点的每天销量改为23，26，25，26吨，产量均为20吨，同时引进xii作为松弛变量。下面写出扩大运输问题的产销平衡表与单位运价表，由于这是一个产销平衡的运输问题，所以可以用表上作业法求解(计算略) 带有约束的运输问题及推广应用在某军供点B1处有10车物资，4车运往A1点，6车运往A2点；在B2处有2车物资运往A3点；在B3处有3车物资运往A4点。车队只有两辆卡车、两辆加载车可供使用，空车送货前集中在A0