运筹学第四章运输问题

第四章运输问题第38页第四章运输问题主要内容：1、运输问题及其数学模型；2、表上作业法；3、运输问题的进一步讨论。重点与难点：表上作业法的原理、求解步骤，产销不平衡运输问题的求解方法。要求：理解运输问题的基本概念及表上作业法的原理，掌握表上作业法确定初始可行解、最优解的判别与改进的方法。§1运输问题及其数学模型一、运输问题引例，设有m个生产地iA，可供应（产量）分别为miai,,2,1,;有n个销地,jB其需要量分别为njbj,,2,1,。已知从iA到jB运输单位物资的运价（单价）为ijc，试问如何调运物资才能使总费用最小？设用ijx表示从iA到jB的运量，可将这些数据汇总于下表：产销平衡表销地产地1B2BnB产量1A2AmAmnmmnnxxxxxxxxx2122221112111a2ama销量1b2bnb单价运价表销地产地1B2BnB第四章运输问题第39页1A2AmAmnmmnnccccccccc212222111211注：有时将两表合二为一。（1）若各产地的总产量等于各销地的总销量，即njjmiiba11，则称之为产销平衡的运输问题（或平衡运输问题）；（2）若所有产地的总产量不等于所有销地的总销量，即njjmiiba11，则称之为产销不平衡的运输问题（或不平衡的运输问题）；（3）若在运输途中，还存在中间转运点（转运点即是产地，又是销地），则称之为有转运的运输问题（或扩大的运输问题）。二、平衡运输问题的数学模型在产销平衡的条件下，要求得总运费最小，可建立以下数学模型：minjijijxcz11min0,,2,1,,2,11,1ijnjiijjmiijxmiaxnjbx该运输问题也属于线性规划问题，包括：（1）nm个决策变量；（2）m+n个约束条件；由于有njjmiiba11，所以模型只有m+n–1个独立约束条件，基变量中含有m+n–1个变量；（3）系数矩阵的秩1)(nmArank第四章运输问题第40页（4）系数矩阵为nmnm)(阶矩阵，该系数矩阵中对应于变量ijx的系数向量ijP，其分量中除第i个和第m+j个为1以外，其余的都为零。111111111111111111212222111211mnmmnnxxxxxxxxxA§2表上作业法求解步骤：（1）找出初始可行解，即在nm产销平衡表上给出1nm个数字格；（2）求各非基变量的检验数，即在表上计算空格的检验数。判别是否达到最优解，如已是最优解，则停止计算；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法调整；（4）重复（2）、（3）直至得到最优解为止。例1某公司有321AAA、、三个工厂生产一种产品，每日的产量分别为7T、4T、9T。该公司把这些产品运往四个销点，各销点的日销量为1B--3T、2B--6T、3B--5T、4B--6T。已知从各工厂到各销售点的单位产品的运价见下表。问该公司应如何调运产品，在满足各销点需要量的前提下，使总运费最少？单位运价表单位：元/T销地加工厂1B2B3B4B1A3113102A19283A74105（二）确定初始基可行解（初始调运方案）（一）最小元素法思路：就近供应，即从单位运价表中最小的运价开始确定供销关系，然后次小，直到给出初始基可行解为止。以例1为例进行讨论：第一步：从单位运价表中找出最小运价为1，表示先将2A的产品供应给1B。因12ba，2A除满足1B第四章运输问题第41页全部需要外，还多余1T产品。在2A与1B的交叉格处填上3，并将1B列的运价划去。第二步：在未划去的元素中再找出最小运价2，确定2A多余的1吨供应3B，并将2A行的运价划去。第三步：在未划去的元素中划出最小运价3，直到单位运价表上的所有元素都划去为止，最后在产销平衡表上得到一个调运方案，空格为非基变量。单位运价表单位：T销地加工厂1B2B3B4B1A3113102A19283A74105产销平衡表单位：T销地加工厂1B2B3B4B产量1A4372A3143A639销量3656注意：（1）在用最小元素法确定初始方案时，在产销平衡表上每填一个数，在单位运价表上划去一行或一列（当产大于销时；划去元素所在列；当产小于销时，划去元素所在行）。运价表中有m行和n列，需要划m+n条线，填最后一个数划去一行和一列，这样共填上1nm个数。（2）当在产销平衡表上填上某个数时，行和列都平衡，需在单位运价表上划去一行和一列（这就出现了退化问题），为保持1nm个基变量，需在行或列的任一空格处填上零，表示该基变量取值为零。（二）伏格尔法思路：一产地的产品，假如不能按最小运费就近供应，就考虑次小运费，这样就要有一差额。差额越大，说明不能按最小运费调运时，运费增加越多，因而对差额最大处，就采用最小运费调运。第一步：计算各行和各列的最小运费和次小运费的差额第四章运输问题第42页销地加工厂1B2B3B4B行差额1A31131002A192813A741051列差额2513第二步：从行或列差额中选出最大者，选择它所在行或列中的最小元素，在上表中，2B列是最大差额所在列，2B列中最小元素为4，可确定3A的产品先供应2B的需要，同时将运价表中的2B列数字划去。单位运价表销地产地1B2B3B4B1A3113102A19283A74105产销平衡表销地产地1B2B3B4B产量1A72A43A69销量3656第三步：对表中未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重复第一、二步，直到给出初始解为止。最后结果见下表。产销平衡表销地产地1B2B3B4B产量1A5272A3143A639第四章运输问题第43页销量3656注意：（1）伏格尔法与最小元素法除确定供求关系的原则不同外，其余相同；（2）伏格尔法给出的初始解更接近最优解。二、最优解的判别判别方法：计算空格检验数ijBijijpBcc1，当0ij时，为最优解。下面介绍两种求空格检验数的方法：（一）闭回路法在给出调运方案的表上，从每一空格出发找一条闭回路。它是以某一空格为起点。用水平或垂直线向前划，每碰到一数字格转90度后，继续前进，直到回到开始空格为止。对用最小元素法确定的方案：销地加工厂1B2B3B4B产量1A4372A31143A639销量36562232341413232212323414121121231311xxxxxxxxxxxxxxxxx1210112113143433332123131434313123131424243234141323222232341412122123131111cccccccccccccccccccccccccccc第四章运输问题第44页024不是最优解，需要调整。（二）位势法（对偶变量法）设nmvvvuuu,,,;,,,2121是对应运输问题的对偶变量，其中iu--行位势，jv--列位势。检验数)(jiijijvuc所有基变量的检验数0ij0)(jiijvuc即ijjicvu由此求出jivu,，再计算ij。第一步：在按最小元素法给出的初始解的数字处填入单位运价销地产地1B2B3B4Biu1A31002A12–13A45–5jv29310第二步：在表上增加一行一列，填入jivu,。第四章运输问题第45页对基变量有5421103432332124131vuvuvuvuvuvu得令01u1039251432132vvvvuu第三步：计算空格的ij)(jiijijvuc可直接在表上进行销地产地1B2B3B4Biu1A3113100122A1928–11–13A74105–51012jv29310三、调整----闭回路法当ij0时，表明未得到最优解，选取ij0中最小的所对应的变量为进基变量，以此格为出发点，作一闭回路，确定调整量)1)3,1min((（其原理与单纯形法中按规则确定换出变量相同），然后，按闭回路上的正、负号，加入或减去此值，得到新的调运方案。检验表：销地产地1B2B3B4B1A12第四章运输问题第46页2A1–13A1012新调运方案：销地产地1B2B3B4B产量1A72+_7522A2143-1+3A92963销量3656对上表求空格的检验数，见上表。因为所有ij0，所以此解为最优解，总费用的最小值z=85注意：（1）若对某方案所有0ij，且有某一个ij=0，则此问题有无穷多最优解，（两个最优解21,XX的组合21)1(XX，也一定是最优解）。（2）在用闭回路法调整时，若有两个具有“-”标记的数同时为最小值，把其中一个作为调出变量，另一个仍为基变量，其值为0；若有某个有“-”标记的数为0，调整量为零，把此格作为空格，原空格处填入零。如：13调整后变为041114调整后变为1400§3产销不平衡问题1、若产大于销njjmiiba11，需增加一个假想的销地，各产地到此的运价都为零，该地的销量为njjmiiba11。2、若产小于销njjmiiba11，需增加一个假想的产地，由此到各销地的运价都为零，该地的产量为第四章运输问题第47页miinjjab11。例2设有三个化肥厂供应四个地区同一种化肥，其产、销量和运价如下表，试求出总的运费最节省的化肥调拨方案。运价单位：万元/万吨需求地区化肥厂IIIIIIIV产量（万吨）ABC1614191313202219231715–506050最低需求（万吨）最高需求（万吨）3050707003010不限解：产销平衡表和单位运价表：销地产地I’I’’IIIIIIV’IV’’产量ABCD161419M1614190131320M22192301715MM1715M050605050销量302070301050初始调拨方案：销地产地I’I’’IIIIIIV’IV’’产量A2M-225050B30201060C005050D203050销量302070301050判别：计算空格ij。最优方案：销地产地I’I’’IIIIIIV’IV’’产量A5050B20103060第四章运输问题第48页C3020050D302050销量302070301050