第三章 运输问题h

第三章运输问题第一节运输问题及其数学模型产销平衡表销量产量销地产地nBBB21mAAA21mnmmnnxxxxxxxxx212222111211maaa21nbbb21单位运价表mnmmnnccccccccc212222111211销地产地nBBB21mAAA21销量产量销地产地nBBB21mAAA21mnmmnnxxxxxxxxx212222111211maaa21nbbb21njmixnjbxmiaxxcZijjmiijinjijminjijij,,1;,,10),,1(),,1(min1111nmnnnmmmmnmmnnbxxxbxxxbxxxaxxxaxxxaxxx2122221211211121222221111211mnmmnnxxxxxxxxx212222111211m行n行111111111111111111A该系数矩阵中对应于变量xij的系数向量Pij，其分量中除第i个和第m+j个为1以外，其余的都为零。例3.1：某运输问题的资料如下：单位销地运价产地B1B2B3B4产量A1291079A213425A384257销量3846)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设第二节表上作业法步骤：⑴.找出初始基本可行解（初始调运方案，m+n-1个数字格）；⑵.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步；⑶.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；⑷.重复⑵.⑶，直到找到最优解为止。一、初始基本可行解的确定（1）最小元素法6483销量75248A352431A2971092A1产量B4B3B2B1销地产地销地产地B1B2B3B4A12591047A2313422A3834425100224742345931z6483销量75248A352431A2971092A1产量B4B3B2B1销地产地销地产地B1B2B3B4产量A1291079A213425A384257销量3846销地产地B1B2B3B4产量A1369A2235A3167销量3846（2）西北角法（3）伏格尔法步骤：第一步：由产销平衡表分别计算出各行和各列的最小运价和次最小运价的差额；第二步：从行差额或列差额中选出最大者，选择它所在行或列中的最小元素，以其对应的产地供应销地，并将满足条件的行或列划去；第三步：重复第二步，直到给出初始基本可行解为止。销地产地B1B2B3B4产量行差A1291079A213425A384257销量3846销地产地B1B2B3B4A1351A25A334单位销地运价产地B1B2B3B4产量A13113107A219284A3741059销量3656例：某运输资料如下表所示，用最小元素法，西北角法，伏格尔法求初始方案。最小元素法单位销地运价产地B1B2B3B4产量A1437A2314A3639销量3656Z=3×1+6×4+4×3+1×2+3×10+3×5=86西北角法单位销地运价产地B1B2B3B4产量A1347A2224A3369销量3656Z=3×3+4×11+2×9+2×2+3×10+6×5=135伏格尔法：单位销地运价产地B1B2B3B4产量A1527A2314A3639销量3656Z=3×1+6×4+5×3+2×10+1×8+3×5=85二、解的最优性检验1、闭回路法销地产地B1B2B3B4产量A125910479-43A23134225-12A3844257373销量38462、位势法Bjicvuijji,Bjivucjiijij,)(销地产地B1B2B3B4产量uiA1259104790-43A23134225-5-12A3844257-5373销量3846vj6977三、解的改进销地产地B1B2B3B4产量uiA1259104790-43A23134225-5-12A3844257-5373销量3846vj6977销地产地B1B2B3B4产量uiA132591017903A2134525-54-12A3844257-53113销量3846vj2977销地产地B1B2B3B4产量uiA132091067903A213425-65531A3844257-53113销量3846vj2977最优解：销地产地B1B2B3B4产量uiA132910679014A2134025-5543A3844257-4362销量3846vj2867最优解：单位销地运价产地B1B2B3B4产量A1437A2314A3639销量3656求最优方案：113743210581019单位销地运价产地B1B2B3B4产量A1527A2314A3639销量3656Z=3×1+6×4+5×3+2×10+1×8+3×5=85最优方案：四、表上作业法中需要说明的问题（1）无穷多最优解当迭代到运输问题的最优解时，如果有某非基变量的检验数等于零，则说明该运输问题有多重（无穷多）最优解。（2）退化在迭代过程中有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时出现退化。为了使表上作业法的迭代工作能进行下去，应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量，使基变量个数为m+n-1个。单位销地运价产地12345产量11023159252510152430315514715204201513M830销量2020301025例：某运输资料如下表所示，求最优方案。第三节产销不平衡的运输问题1、产大于销：),,2,1;,,2,1(0),,2,1(),,2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijijnjjmiinbab111njjmiiba11)1,,2,1;,,2,1(0)1,,2,1(),,2,1(min111111njmixnjbxmiaxxczijjmiijinjijminjijij销地产地B1…BnBn+1产量A1c11…c1n0a1………………Amcm1…cmn0am销量b1…bnbn+1njjmiinbab111例3已知某运输问题的运输表如下,试确定最优的调运方案。销地产地B1B2B3B4产量A1312348A2112595A367159销量43562218销地产地B1B2B3B4B5产量A13123408A21125905A3671509销量435642222二、销大于产：miinjjab11),,2,1;,,2,1(0),,2,1(),,2,1(min1111njmixnjbxmiaxxczijjmiijinjijminjijijmiinjjmaba111),,2,1;1,,,2,1(0),,2,1()1,,,2,1(min111111njmmixnjbxmmiaxxczijjmiijinjijminjijijmiinjjmaba111销地产地B1…Bn产量A1c11…c1na1……………Amcm1…cmnamAm+10…0am+1销量b1…bn例3.3已知某运输问题的运输表如下销地产地B1B2B3产量A187415A235925销量2010204050销地产地B1B2B3产量A187415A235925A300010销量201020第四节应用举例例3.4某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15×104元。要求在完成合同的情况下做出使该厂全年生产（包括储存、维护）费用最小的决策。季度生产能力（台）单位成本（万元）12510.823511.13301141011.31234110.810.9511.111.25211.1011.2511.40311.1011.25411.30设xij为第i季度生产的用于第j季度交货的柴油机数。2025151044342414332313221211xxxxxxxxxx1030532544343324232214131211xxxxxxxxxx)4,3,2,1,(0)4,3,2,1()4,3,2,1(min41414141jixjbxiaxxczijjiijijijijijij1234产量110.810.9511.111.25252M11.1011.2511.40353MM11.1011.25304MMM11.3010销量101525201234D产量110.810.9511.111.250252M11.1011.2511.400353MM11.1011.250304MMM11.30010销量10152520301234D产量11015025253035320103041010销量1015252030最优解：例、设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同。各化肥厂年产量，各地区年需要量及从各化肥厂到各地区运送单位化肥的运价如表所示。试求出总的运费最节省的化肥调拨方案。ⅠⅡⅢⅣ产量ABC1614191313202219231715－506050最低需求最高需求3050707003010不限需求化肥厂Ⅰ1Ⅰ2ⅡⅢⅣ1Ⅳ2产量ABCD161419M1614190131320M22192301715MM1715M050605050销量302070301050产地销地产销平衡表例、已知运输问题的产销平衡表、单位运价表及最优调运方案分别如表所示。产销平衡表及最优调运方案单位运价表B1B2B3B4产量A151015A20101525A355销量5151510B1B2B3B4A11012011A2127920A321416181、从A2－B2的单位运价c22在什么范围变化时，上述最优调运方案不变？2、A2－B4的单位运价c24变为何值时，有无穷多最优调运方案，除上述最优方案外，至少再写出两个。B1B2B3B4uiA15100A201015c-1A35c-11vj13-c110-c11101221c1420916112018c-324-c10+c1710-c18-c3≤c22≤101、B1B2B3B4uiA15100A2010156A35-4vj613111012217142091611c184171717c-1711c24=172、B1B2B3B4产量A11515A200151025A355销量5151510B1B2B3B4产量A110515A2515525A355销量5151510(1)(2)