运筹学之运输问题-表格法网上找的PPT

运输问题(TransportationProblem)例：某运输问题的资料如下：单位销地运价产地产量2910291342584257销量38464321BBBB321AAA一、运输问题的数学模型)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设数学模型的一般形式已知资料如下：单销产量产地产量销量nBB1mAA1maa1nbb1mnmncccc1111)(0min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：当产大于销时，其模型是：)(0min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：0,0,0)(0minijjijjiijjijiijijijcbabaxbxaxxcZ并假设：特征：1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基可行解中应包括m+n－1个基变量。这是平衡的运输问题的数学模型，包含m×n个变量，m×n个约束方程。系数矩阵如下：111111111111111111mnmmnnxxxxxxxxx212222111211m行n行⑷.重复⑵.⑶，直到找到最优解为止。步骤：⑴.找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法、伏格尔法（Vogel）；⑵.求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；⑶.改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；二、表上作业法例一、某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36564321BBBB321AAA1、求初始方案：此法是纯粹的人为的规定，没有理论依据和实际背景，但它易操作，特别适合在计算机上编程计算，因而受欢迎。西北角法（或左上角法）西北角法（或左上角法）1、先确定左上角变量的值，令它取尽可能的值。将这个值填入该变量对应位置，并在该数字上画上圈。画圈格子的对应的变量是基变量。2、在画圈格子所在的行或列应取0值的变量处填上×号。当画圈格子所在行和列的其余变量都应取0时，则或者只对行打×，不能同时对行或列都打×。打×格子对应的变量是非基变量。3、对表中尚未画圈和打×的部分，重复1、2的手续。若遇左上角变量取0值，则在该位置填0，并且同样画上圈，对应变量仍是基变量。B1B2B3B4产量A17A24A39销量3656311310192741058341633⑵.最小元素法：基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元最小元素法1、先确定运价最小的格子所对应的变量值。若有几个格子同时达到最小运价，则可任取一个。令该变量取尽可能大的值。将此值填入该变量对应位置并画圈。画圈的格子对应的变量是基变量。2、在画圈格子所在的行或列应取0值的变量处填上×号。当画圈格子所在行和列的其余变量都应取0时，则或者只对行打×，不能同时对行或列都打×。打×格子对应的变量是非基变量。3、对表中尚未画圈和打×的部分，重复1、2的手续。当表剩余部分仅是一行或一列时，确定其最小运价对应变量后，不管其余元素是否取零值，都不能打×，应作剩余部分处理。闭回路为一个闭回路。互不相同）集合ssjijijijijijijjjiiixxxxxxsss,,,;,,,(},,,,,,{2121132222111性质：回路中的顶点必是偶数，在运输表中，回路遇到顶点必须转90度与另一顶点连接。集合中的变量称为闭回路的顶点，相邻两个变量的连线为闭回路的边。X43X41A4X33X32A3A2X12X11A1B3B2B1在运输问题中，若变量组含有闭回路，则变量所对应的列向量线性相关。m+n-1个变量构成基变量的充要条件是他不包含任何闭回路。B1B2产量A18510A22120销量1515最小元素法：12510XZ1=105另一方案：51510XZ=85销地31131019287410520aiB2B37B4A1A2bjB13产地A3659640110122513⑥2-13③01-2-12③01-2-1-①②⑤85538335461132Z(3)伏格尔法（Vogel）：基本思想：同时考虑每一产地到每一销地和每一销地来自每一产地的最小运价和次小运价，若两者差额大，说明若不能按最小运价供应，就有可能按次小运价供应，从而运费很高。因此，应先对最大差额所在的行或列，按最小元素确定供销关系。一般讲，按此法所得可行解较最小元素法所得可行解更接近最优解。销地产地B1B2B3B4产量A178143A226535A314278销量2176σij≥0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij0表示运费减少，σij0表示运费增加。2、最优解的判别（检验数的求法）：⑴.闭合回路法：B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）①②③③计算如下：空格处（A1B1）＝(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－1)×1｝＝1此数即为该空格处的检验数。1检验数就是闭回路中所有增加1个运量处的单位运价之和减去所有减少1个运量处的单位运价之和。（经济解释）闭回路画法：从某一空格出发，横向或纵向画直线，在适当的数字格转向以回到出发的空格。•从每一个空格出发一定存在和可以找到唯一的闭回路。因（m+n-1）个数字格（基变量）对应的系数向量是一个基。于是，任意一个空格（非基变量）对应系数向量是这个基的线性组合。B1B2B3B4产量A17A24A39销量365631363124B1B2B3B4产量A17A24A39销量36563136312-14B1B2B3B4产量A17A24A39销量365631363121-14B1B2B3B4产量A17A24A39销量365631363121-1124B1B2B3B4产量A17A24A39销量365631363121-112104检验数中有负数，说明原方案不是最优解。B1B2B3B4产量A17A24A39销量365600000121-112100运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，由对偶性可知CBB-1=（u1,u2,…,um;v1,v2,…,vn)，于是有CBB-1Pij=ui+vj。又因为，σij=cij-CBB-1Pij=cij－(ui+vj),其中前m个计为ui（i=1.2…m）,后n个计为vj（j=1.2…n）由单纯形法可知，基变量的σij＝0∴cij－(ui+vj)＝0因此ui,vj可以求出。位势法接上例：B1B2B3B4A1310u1A212u2A345u3v1v2v3v4B1B2B3B4A1293100A21829－1A3－34－25－529310u2+v1=1u2+v3=2u3+v2=4u1+v4=10u1+v3=3u3+v4=5令：u1＝0u1＝0v1＝2u2＝－1v2＝9u3＝－5v3＝3v4＝10(ui+vj)按σij=cij－(ui+vj)计算检验数，并以σij≥0检验，或用(ui+vj)－cij≤0检验。B1B2B3B4A1311310A21928A374105cijB1B2B3B4A129310A21829A3－34-25(ui+vj)－B1B2B3B4A11200A2010－1A3100120＝表中还有负数，说明还未得到最优解，应继续调整。σij位势法步骤：1、确定初始基可行解后，在对应初始方案的数字格处填入单位运价。2、在表中增加一行一列，在列中填入ui（i=1,2，…，m），在行中填入vj（j=1,2,…,n)先令u1=0，接着，通过ui+vj=cij，i，j∈B来确定ui，vj。3、由，计算所有空格的检验数。Njivucjiijij,)(B1B2B3B4A1×2⑤9×10④79A2③1×3×4②25A3×8③4④2×573846——闭合回路调整法（原理同单纯形法一样）接上例：B1B2B3B4产量A17A24A39销量3656313463①③④②3、改进的方法B1B2B3B4产量A1527A2314A3639销量36566563销量9A34A27A1产量B4B3B2B1313463①③④②B1B2B3B4A10200A20210A390120经检验所有σij≥0得到最优解，最小运费为85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B110393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)闭回路调整法步骤：1、取非基变量中检验数最小的非基变量为入基变量。2、从这个非基变量出发，寻求一条以基变量为顶点的闭回路（存在且唯一），并将这条闭回路按顺时针或逆时针依次编号（该非基变量为第一号）。3、将闭回路中偶序顶点的基变量值最小者取作调整量，并将该基变量选取为离基变量。4、将该闭回路上奇序顶点的值加，偶序顶点的值减，闭回路外的值一律不变。⑴.无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。⑵.退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。4、表上作业法计算中的问题)(0min11ijjijijiijminjijijxbabxaxxcZ1、产大于销：模型方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，三、产销不平衡的运输问题及其求解方法模型为：0)min1111111ijminjnjjnjijijnjiijijijxbbbabxaxxcZm1i(2、销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为01,nicB1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5A121134070A210359050A378120702030406040B1B2B3B4B5A170A250A370203040604040303020302020用最小元素法求初始方案例题：例如下表所示三个化肥厂供应四个地区的化肥，求运费最省的调拨方案。需求地区化肥厂一二三四产量（万吨）A1613221750B1413191560C192023——50最低需求（万吨）3070010最高需求（万吨）507030不限需求地区化肥厂一(1)一(2)二三四(1)四(2)产量（万吨）A50B60C50D50销量302070301050需求地区化肥厂一(1)一(2)二三四(1)四(2)A161613221717B141413191515C19192023MMDM0M0M0需求地区化肥厂一(1)一(2)二三四(1)四(2)产量A5050B20103060C3020050