运输问题

运运输输问问题题运运输输问问题题及及其其数数学学模模型型表表上上作作业业法法产产销销不不平平衡衡的的运运输输问问题题应应用用举举例例运运输输问问题题及及其其数数学学模模型型一一、、运运输输问问题题的的数数学学模模型型单单一一品品种种运运输输问问题题的的典典型型情情况况：：设设某某种种物物品品有有mm个个产产地地AA11,,AA22,,……,,AAmm，，各各产产地地的的产产量量分分别别是是aa11,,aa22,,……,,aamm；；有有NN个个销销地地BB11,,BB22,,……,,BBnn，，各各销销地地地地销销量量分分别别为为bb11,,bb22,,……,,bbnn。。假假定定从从产产地地AAii((ii==11,,22,,……,,mm))向向销销地地BBjj((jj==11,,22,,……,,nn))运运输输单单位位物物品品的的运运价价是是cciijj，，问问怎怎样样调调运运这这些些物物品品才才能能使使总总运运费费最最小小？？数数据据如如下下标标所所示示。。表1产销平衡表表表22单单位位运运价价表表有时可把两表合一。如如果果运运输输问问题题的的总总产产量量等等于于其其总总销销量量，，即即有有则则称称该该运运输输问问题题为为产产销销平平衡衡运运输输问问题题；；反反之之，，称称为为产产销销不不平平衡衡运运输输问问题题。。运运输输问问题题的的数数学学模模型型如如下下：：这这就就是是运运输输问问题题的的数数学学模模型型，，它它包包含含MM××nn个个变变量量，，((MM十十MM))个个约约束束方方程程．．其其系系数数矩矩阵阵的的结结构构比比较较松松散散，，且且特特殊殊．．二二、、运运输输问问题题数数学学模模型型的的特特点点11、、运运输输问问题题有有有有限限最最优优解解，，即即必必有有最最优优基基本本可可行行解解22、、运运输输问问题题约约束束条条件件的的系系数数矩矩阵阵AA的的秩秩为为((mm++nn--11))该系数矩陈中对应于变量xij的系数向量pij，其分量中除第i个和第m十j个为1以外，其余的都为零．即Pij＝(0…1…1…0)’=ei+em+j对产销平衡的运输问题，由于有以下关系式存在：特点：((11))约约束束条条件件系系数数矩矩阵阵的的元元素素等等于于00或或11((22))约约束束条条件件系系数数矩矩阵阵的的每每一一列列有有两两个个非非零零元元素素，，对对应应于于每每一一个个变变量量在在前前mm个个约约束束方方程程中中出出现现一一次次，，在在后后nn个个约约束束方方程程中中也也出出现现一一次次。。∴∴RR((AA))≤≤mm++nn--11此此外外，，对对于于产产销销平平衡衡问问题题，，还还有有以以下下特特点点((33))所所有有结结构构约约束束条条件件都都是是等等式式约约束束((44))各各产产地地产产量量之之和和等等于于各各销销地地销销量量之之和和表表上上作作业业法法一一、、解解题题步步骤骤第第11步步：：用用西西北北角角法法或或最最小小元元素素法法确确定定初初始始基基本本可可行行解解。。第第22步步：：位位势势法法求求非非基基变变量量的的检检验验数数((解解的的最最优优性性检检验验))，，若若最最优优准准则则σσiijj≥≥00，，则则当当前前解解最最优优，，计计算算停停止止，，否否则则转转第第33步步。。第第33步步：：取取一一个个检检验验数数最最小小的的非非基基变变量量做做进进基基变变量量。。第第44步步：：用用闭闭回回路路法法调调整整当当前前基基本本可可行行解解，，转转第第22步步1.确定初始基本可行解（初始调运方案）以以实实例例介介绍绍：：例例某某公公司司生生产产糖糖果果，，它它有有三三个个加加工工厂厂AA11,,AA22,,AA33,,每每月月产产量量分分别别为为77tt,,66tt,,55tt,,66tt。。已已知知从从第第ii个个加加工工厂厂到到第第jj个个销销售售店店的的每每吨吨糖糖果果的的运运价价CCiijj见见表表，，试试设设计计在在满满足足各各销销售售店店需需求求量量的的前前提提下下，，各各加加工工厂厂到到各各销销售售店店的的每每月月调调运运方方案案，，使使总总的的运运费费最最小小。。运价表A西北角法B最小元素法2．解的最优性判别（位势法，也称对偶变量法）3．用闭回路法调整当前基可行解二二、、表表上上作作业业法法计计算算中中的的几几个个问问题题11、、某某个个基基本本可可行行解解有有几几个个非非基基变变量量的的检检验验数数为为负负若运输问题的某个基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量均可使目标函数值得到改善，但通常取σij0中最小者对应的变量为换入变量。22、、无无穷穷多多个个最最优优解解当迭代到运输问题的最优解时，如果有某非基变量的检验数＝0，则说明该运输问题有无穷多最优解。（如上例，为得到另一个最优解，只需让σij＝0的非基变量进基）33、、退退化化问问题题当运输问题某部分产地的产量和与另一部分销地的销量和相等时，在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的，为了使表上作业法的迭代工作进行下去，退化解应在同时划去的一行或一列中的某个空格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基可行解的分量恰好为m+n-1个。b.在用闭回路法调整当前基本可行解时，调整量θ的取值应为θ＝min{xij/(i,j)为闭回路上所有偶数号格点}。这时可能出现有两个（或以上）偶数号格点的xij都相等且都为极小值，只能取其中一个为离基格，其余的仍作为基格，而在作运输量调整时，运输量与θ相等的那些偶数号格点的xij都将调整为0，因此得到的也是一个退化了的基可行解。44、、循循环环问问题题练练习习产产销销不不平平衡衡的的运运输输问问题题一一、、总总产产量量大大于于总总销销量量即即此此时时运运输输问问题题的的数数学学模模型型为为0,...,2,1,...,2,1min1111ijmijijnjiijminjijijxnjbxmiaxxcznjjmiiba11二二、、总总销销量量大大于于总总产产量量例例11某某市市有有三三个个造造纸纸厂厂AA11,,AA22,,AA33,,其其纸纸产产量量分分别别为为88，，55，，99个个单单位位，，有有44个个集集中中用用户户BB11,,BB22,,BB33,,BB44,,其其需需用用量量为为44，，33，，55，，66个个单单位位，，由由各各厂厂到到各各用用户户的的单单位位运运价价如如表表所所示示，，试试确确定定总总运运费费最最小小的的调调运运方方案案。。例例22较较为为复复杂杂的的产产销销不不平平衡衡问问题题设设有有三三个个化化肥肥厂厂供供应应四四个个地地区区的的农农用用化化肥肥，，假假设设每每个个地地区区使使用用各各厂厂的的化化肥肥效效果果相相同同，，各各化化肥肥厂厂的的年年产产量量，，各各地地区区的的需需求求量量以以及及它它们们之之间间的的单单位位运运价价如如表表，，求求总总运运费费最最少少的的化化肥肥调调运运方方案案。。01,...,2,1,...,2,1min111111ijmijijnjiijminjijijxnjbxmiaxxcz0,...,2,11,...,2,1min11111ijmijijnjiijminjijijxnjbxmiaxxcz分析：(1)这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限．根据现有产量及Ⅰ，Ⅱ，Ⅲ地区的最低需求，第Iv个地区每年最多能分配到(50+60+50)-(30+70+0)=60万吨，这样四个地区的最高需求为50＋70＋30＋60＝210万吨，大于总产量．(2)为了求得平衡，在产销平衡表中增加一个假想的化肥厂D，其年产量为210-160=50万吨．(3)由于各地区的需要量包含两部分，最低需求和额外需求。如地区Ⅰ，其中30万吨是最低需求，故不能由假想化肥厂D供给，令相应运价为M(任意大正数)．而另一部分20万吨满足或不满足均可以，因此可以由假想化肥厂D供给，按前面讲的，令相应运价为0。这样，凡是需求分两种情况的地区，实际上可按照两个地区看待．这样可以写出这个问题的产销平衡表(表3—26)和单位运价表(表3—27)．产销平衡表单位运价表两个表也可以合在一起写。根据表上作业法计算，可以求得这个问题的最优方案如下：应应用用举举例例由于在变量个数相等的情况下，表上作业法的计算远比单纯形法简单得多．所以在解决实际问题时，人们常常尽可能把某些线性规划的问题化为运输问题的数学模型．下面介绍几个典型的例子．例1某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机．已知该厂各季度的生产能力及生产每台柴油机的成本如表所示．又如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用0.15万元．要求在完成合同的情况下，做出使该厂全年生产(包括储存、维护)费用最小的决策．解:由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的用于第j季度交货的柴油机数．根据合同要求，必须满足：又每季度生产的用于当季和以后各季交货的柴油机数不可能超过该季度的生产能力，故又有：第i季度生产的用于j季度交货的每台柴油机的实际成本Cij应该是该季度单位成本加上储存、维护等费用．Cij的具体数值见表设用ai表示该厂第i季度的生产能力，bj表示第j季度的合同供应量，则问题可写成：因为当ji时，xij=0所以当ji时,取Cij=M,M为一个充分大的正数。此外，由于是产量大于销量的不平衡问题，∴加上一个假想的需求D，就可以把问题变成产销平衡的运输模型，并写出产销平衡表和单位运价表(合在一起，如下)经用表上作业法求解，可得多个最优方案，表3—32中列出最优方案之一．即第1季度生产25台，10台当季交货，15台Ⅱ季度交货；Ⅱ季度生产5台．用于Ⅲ季度交货；Ⅲ季度生产30台，其中20台于当季交货，10台于Ⅳ季度交货Ⅳ季度生产10台，于当季交货．按此方案生产，该厂总的生产(包括储存、维护)的费用为773万元．例2某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务．已知(1)各条航线的起点、终点城市及每天航班数．(2)假定各条航线使用相同型号的船只，又已知各城市间的航程天数．(3)又知每条船只每次装卸货的时间各需1天。问该航运公司至少应配备多少条船，才能满足所有航线的运输需求?每天航班数表各城市之间的航程天数解：该公司所需配备船只分两部分：(1)载货航程需要的周转船只数。例如航线l，在港口E装货1天，E—D航程l7天，在D卸货1天，总计19天．每天3航班，故该航线周转船只需57条．各条航线周转所需船只数见表．以上累计共需周转船只数91条．(2)各港口间调度所需船只数．有些港口每天到达船数多于需要船数．例如港口D，每天到达3条，需求1条；而有些港口到达数少于需求数，例如港口B．各港口每天余缺船只数的计算见表．为使配备船只数最少，应做到周转的空船数为最少．因此建立以下运输问题，其产销平衡表见表．单单位位运运价价表表应应为为相相应应各各港港口口之之间间的的船船只只航航程程天天数数，，见见表表用表上作业法求出空船的最优调度方案见表另一最优解为xCA=1,xCE=1,xDB=1,xDE=1,xFE=1按这两个方案掉运船只，解得Z=40，说明各港口之间调度所需船只至少为40艘。综合以上两方面的要求，在不考虑维修、储备等情况下，该公司至少配备131条船，才能满足4条航线正常运输的需要。