运输规划

运输规划的数学模型表上作业法产销不平衡的运输问题运输规划例：某运输问题的资料如下：单位销地运价产地产量2910291342584257销量38464321BBBB321AAA运输问题的数学模型)4.3.2.1,3.2.1(06483759524824371092min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZxijij约束条件：目标函数：为运量设运输问题的数学模型数学模型的一般形式已知资料如下：单销产量产地产量销量nBB1mAA1maa1nbb1mnmncccc1111运输问题的数学模型0)(min11ijjijijiijminjijijxbabxaxxcZ当产销平衡时，其模型如下：运输问题的数学模型当产大于销时，其模型是：0)(min11ijjijijiijminjijijxbabxaxxcZ当产小于销时，其模型是：0,0,0)(0minijjijjiijjijiijijijcbabaxbxaxxcZ并假设：特征：1、平衡运输问题必有可行解，也必有最优解；2、运输问题的基本可行解中应包括m+n－1个基变量。步骤：①找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用西北角法、最小元素法；②求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用位势法计算；③改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；④重复②，③，直到找到最优解为止。表上作业法例1某运输资料如下表所示：单位销地运价产地产量311310719284741059销量36564321BBBB321AAA求初始方案(1)西北角法（或左上角法）：365674934490656404902562029005620090036360000000340002200036总的运费＝(3×3)＋(4×11)＋(2×9)＋(2×2)＋(3×10)＋(6×5)＝135元求初始方案B1B2B3B4产量A17A24A39销量3656311310192741058341633(2)最小元素法：总的运输费用＝（3×1）＋（6×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元求初始方案σij≥0（因为目标函数要求最小化）表格中有调运量的地方为基变量，空格处为非基变量。基变量的检验数σij＝0，非基变量的检验数σij≥0。σij0表示运费减少，σij0表示运费增加。最优解的判别⑴闭合回路法B1B2B3B4产量A17A24A339销量365613463（＋1）（＋1）（－1）(－1)①②③③计算如下：空格处（A1B1）＝(1×3)＋｛(－1)×3｝＋(1×2)＋｛(－1)×1｝＝1此数即为该空格处的检验数。1最优解的判别B1B2B3B4产量A17A24A39销量365631363124最优解的判别B1B2B3B4产量A17A24A39销量36563136312-14最优解的判别B1B2B3B4产量A17A24A39销量365631363121-14最优解的判别B1B2B3B4产量A17A24A39销量365631363121-1124最优解的判别B1B2B3B4产量A17A24A39销量365631363121-112104检验数中有负数，说明原方案不是最优解。最优解的判别B1B2B3B4产量A17A24A39销量365600000121-112100最优解的判别运输问题的约束条件共有m+n个，其中：m是产地产量的限制；n是销地销量的限制。其对偶问题也应有m+n个变量，据此：σij=cij－(ui+vj),其中前m个计为ui（i=1,2…,m）,前n个计为vj（j=1,2…,n）由单纯形法可知，基变量的σij＝0∴cij－(ui+vj)＝0因此ui,vj可以求出。最优解的判别⑵位势法B1B2B3B4A1310u1A212u2A345u3v1v2v3v4成本表B1B2B3B4A1293100A21829－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最优解的判别闭合回路调整法（原理同单纯形法一样）接上例：B1B2B3B4产量A17A24A39销量3656313463（＋1）（＋1）（－1）（－1）改进的方法B1B2B3B4产量A1527A2314A3639销量36566563销量9A34A27A1产量B4B3B2B1313463（＋1）（＋1）（－1）（－1）改进的方法B1B2B3B4A10200A20210A390120经检验所有σij≥0得到最优解，最小运费为85元。0v4v3v2v1u354A3u281A2u1103A1B4B3B2B1成本表10393－55－24－2A3－28171A2010393A1B4B3B2B1(ui+vj)改进的方法①无穷多最优解：产销平衡的运输问题必定存最优解。如果非基变量的σij＝0，则该问题有无穷多最优解。如上例：(1,1)中的检验数是0，经过调整，可得到另一个最优解。②退化：表格中一般要有(m+n-1)个数字格。但有时，在分配运量时则需要同时划去一行和一列，这时需要补一个0，以保证有(m+n-1)个数字格。一般可在划去的行和列的任意空格处加一个0即可。表上作业法计算中的问题B1B2B3B4A178143A226355A3142782176213552682176B1B2B3A11221A23132A32314124B1B2B3A111A222A344124000表上作业法计算中的问题0)(min11ijjijijiijminjijijxbabxaxxcZ产大于销：模型方法是先将原问题变成平衡问题，需假设一个销地(Bn+1)(实际上考虑产地的存量)，产销不平衡的运输问题模型为：0)(min1m1i111111ijminjnjjnjijijnjiijijijxbbbabxaxxcZ销大于产：同样假设一个产地即可，变化同上。单位运价表中的单位运价为01,nic产销不平衡的运输问题B1B2B3B4A12113470A21035950A378127020304060B1B2B3B4B5A121134070A210359050A378120702030406040B1B2B3B4B5A170A250A370203040604040303020302020用最小元素法求初始方案产销不平衡的运输问题