运筹学第三章运输问题ppt课件

26.04.2020,.,1,第3章运输问题第3节产销不平衡的运输问题及其求解方法第4节应用举例,运筹学,26.04.2020,.,2,第3节产销不平衡的运输问题及其求解方法,前面一节所讲的表上作业法，都是以产销平衡为前提条件的，即但是实际问题中产销往往是不平衡的。因此就需要把产销不平衡的问题化成产销平衡的问题。当产大于销,26.04.2020,.,3,运输问题的数学模型可写成,目标函数：满足：,从Ai到Bj的运量小于供应量,从Ai到Bj的运量等于需要量,26.04.2020,.,4,由于总的产量大于销量，就要考虑多余的物资在哪一个产地就地储存的问题。设xi,n+1是产地Ai的储存量，于是有：,26.04.2020,.,5,令：,当i=1,，m，j=1,，n时,当i=1,，m，j=n+1时,将其分别代入，得到,26.04.2020,.,6,满足：,由于这个模型中,所以这是一个产销平衡的运输问题。,26.04.2020,.,7,若当产大于销时，只要增加一个假想的销地j=n+1(实际上是储存)，该销地总需要量为,而在单位运价表中从各产地到假想销地的单位运价为，可以理解为就地“销售”，就转化成一个产销平衡的运输问题,26.04.2020,.,8,当销大于产时，即可以在产销平衡表中增加一虚拟行，表示增加一个假想的产地i=m+1，该地产量为,在单位运价表上令从该假想产地到各销地的运价，同样可以转化为一个产销平衡的运输问题.。,26.04.2020,.,9,例2设有三个化肥厂(A，B，C)供应四个地区(，)的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表3-1所示。试求出总的运费最节省的化肥调拨方案。表3-1,26.04.2020,.,10,解这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，第个地区每年最多能分配到60(160-30-70-0=60)万吨，这样其不限的最高需求可等价认为是60万吨。按最高需求分析，总需求为210万吨，大于总产量160万吨，将此问题定义为销大于产的运输问题。为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为50万吨。由于各地区的需要量包含两部分，如地区，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)，而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以写出这个问题的产销平衡表(表3-2)和单位运价表(表3-3)。,26.04.2020,.,11,产销平衡表(表3-2),单位运价表(表3-3),26.04.2020,.,12,利用表上作业法求解步骤如下,1.首先利用最小元素法求出基可行解，步骤如下第一步见表3-4，3-5,26.04.2020,.,13,第二步见表3-6，3-7,26.04.2020,.,14,第三步，见表3-8，3-9,26.04.2020,.,15,第四步，见表3-10，3-11,26.04.2020,.,16,第五步，见表3-12，3-13,26.04.2020,.,17,第六步，见表3-14，3-15,26.04.2020,.,18,第七步，在单位运价表上相应地要划去一行和一列,因此需要添一个“0”。见表3-16，3-17,26.04.2020,.,19,第八步，此时基可行解就是表3-18，3-19,26.04.2020,.,20,2.利用位势法求空格检验数，如下图所示计算表3-20,26.04.2020,.,21,3.表中还有负检验数。说明未得最优解，利用闭回路调整法，见表3-21,26.04.2020,.,22,即为表3-22,此时再利用闭回路法求各空格的检验数，见表3-23,26.04.2020,.,23,26.04.2020,.,24,表中还有负检验数。说明未得最优解，利用闭回路调整法，得到表3-24,26.04.2020,.,25,即为表3-25,26.04.2020,.,26,依次按照上述方法进行，一直到得到最优解为止，可以求得这个问题的最优方案如表3-26所示,26.04.2020,.,27,第4节应用举例,由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多。所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型。下面介绍几个典型的例子。,26.04.2020,.,28,例3某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表3-27所示。又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，作出使该厂全年生产(包括储存、维护)费用最小的决策,26.04.2020,.,29,表3-27,26.04.2020,.,30,解由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数。根据合同要求，必须满足,26.04.2020,.,31,又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：,26.04.2020,.,32,第i季度生产的用于j季度交货的每台柴油机的实际成本cij应该是该季度单位成本加上储存、维护等费用。cij的具体数值见表3-28,26.04.2020,.,33,设用ai表示该厂第i季度的生产能力，bj表示第i季度的合同供应量，则问题可写成：,目标函数：满足,26.04.2020,.,34,显然，这是一个产大于销的运输问题模型。注意到这个问题中当ij时，xij=0，所以应令对应的cij=M，再加上一个假想的需求D，就可以把这个问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，见表3-29)。,26.04.2020,.,35,利用表上作业法进行求解步骤如下,1.利用最小元素法确定基可行解第一步见表3-30，3-31,26.04.2020,.,36,第二步，在单位运价表上相应地要划去一行和一列,因此需要添一个“0”。见表3-32，3-33,26.04.2020,.,37,第二步，以此类推，结果见表3-34，3-35,26.04.2020,.,38,2.利用位势法求空格检验数，如下图所示计算表3-36,26.04.2020,.,39,表中的所有检验数都非负，故表3-37的解为最优解,26.04.2020,.,40,经过用表上作业法求解，可得多个最优方案，表3-37中列出最优方案之一。即第季度生产25台，10台当季交货，15台季度交货；季度生产5台，用于季度交货；季度生产30台，其中25台于当季交货，5台于季度交货。季度生产10台，于当季交货。按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元。,26.04.2020,.,41,例4某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务。已知各条航线的起点、终点城市及每天航班数见表3-38。,26.04.2020,.,42,假定各条航线使用相同型号的船只，又各城市间的航程天数见表3-39。,26.04.2020,.,43,又知每条船只每次装卸货的时间各需1天，则该航运公司至少应配备多少条船，才能满足所有航线的运货需求?,解该公司所需配备船只分两部分。(1)载货航程需要的周转船只数。例如航线1，在港口E装货1天，ED航程17天，在D卸货1天，总计19天。每天3航班，故该航线周转船只需57条。各条航线周转所需船只数见表3-40。,26.04.2020,.,44,表3-40,以上累计共需周转船只数91条.,26.04.2020,.,45,(2)各港口间调度所需船只数。有些港口每天到达船数多于需要船数，例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B。各港口每天余缺船只数的计算见表3-41。,26.04.2020,.,46,为使配备船只数最少，应做到周转的空船数为最少。因此建立以下运输问题，其产销平衡表见表3-42。,26.04.2020,.,47,单位运价表应为相应各港口之间的船只航程天数，见表3-43。,26.04.2020,.,48,用表上作业法求出空船的最优调度方案，具体步骤如下。1.利用最小元素法确定基可行解第一步(见表3-44，3-45),26.04.2020,.,49,第二步，不过本步要注意在单位运价表上相应地要划去一行和一列,因此需要添一个“0”。(见表3-46，3-47),26.04.2020,.,50,第三步(见表3-48，3-49),26.04.2020,.,51,2.利用位势法求空格检验数，如下图所示计算表(见表3-50),26.04.2020,.,52,3.利用闭回路调整法进行改进(见表3-51),26.04.2020,.,53,4.再利用位势法求各空格的检验数见表3-52，表中所有检验数都非负,26.04.2020,.,54,由表3-53知最少需周转的空船数为21+131+51+171+31=40条。这样在不考虑维修、储备等情况下，该公司至少应配备40+91=131条船。,最终的最优调度方案见表3-53,26.04.2020,.,55,例5在本章的例1中，如果假定,每个工厂生产的产品不一定直接发运到销售点，可以将其中几个产地集中一起运；运往各销地的产品可以先运给其中几个销地，再转运给其他销地；除产、销地之外，中间还可以有几个转运站，在产地之间、销地之间或产地与销地间转运。已知各产地、销地、中间转运站及相互之间每吨产品的运价如表3-54所示，问在考虑到产销地之间直接运输和非直接运输的各种可能方案的情况下，如何将三个厂每天生产的产品运往销售地，使总的运费最少。,26.04.2020,.,56,表3-54,26.04.2020,.,57,解从表3-54中看出，从A1到B2每吨产品的直接运费为11元，如从A1经A3运往B2，每吨运价为3+4=7元，从A1经T2运往B2只需1+5=6元，而从A1到B2运费最少的路径是从A1经A2，B1到B2，每吨产品的运费只需1+1+1=3元。可见这个问题中从每个产地到各销地之间的运输方案是很多的。为了把这个问题仍当作一般的运输问题处理，可以这样做：,26.04.2020,.,58,(1)由于问题中所有产地、中间转运站、销地都可以看作产地，又可看作销地。因此把整个问题当作有11个产地和11个销地的扩大的运输问题。(2)对扩大的运输问题建立单位运价表。方法将表3-54中不可能的运输方案的运价用任意大的正数M代替。,26.04.2020,.,59,(3)所有中间转运站的产量等于销量。由于运费最少时不可能出现一批物资来回倒运的现象，所以每个转运站的转运数不超过20吨。可以规定T1，T2，T3，T4的产量和销量均为20吨。由于实际的转运量,可以在每个约束条件中增加一个松弛变量xii，xii相当于一个虚构的转运站，意义就是自己运给自己。(20-xii)就是每个转运站的实际转运量，xii的对应运价cii=0。,26.04.2020,.,60,(4)扩大的运输问题中原来的产地与销地因为也有转运