第二章运筹学运输问题.

第二章运输问题产销平衡的运输问题的数学模型表上作业法产销不平衡的运输问题及其应用教学目的与要求：使学生学会建模方法能用表上作业法及WinQSB求解运输问题。重点与难点：重点是产销平衡运输问题的表上作业法，难点是基变量个数为m+n-1的理论及操作方法.教学方法:课堂讲授并辅以课件及软件.思考题,讨论题,作业:教材中第三章作业.参考资料:见前言学时分配:4学时.第二章运输问题(Transportationproblems)物资调运是一个典型的线性规划问题.1939年前苏联经济学家康托洛维奇提出这一问题,1941年美国数学家F.L.Hitchcock提出运输问题数学模型,1951年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.第一节运输问题数学模型一.平衡运输问题的数学模型)(Source产地)Pr/(ofitCost运价销地)(nDestinatio)(Demand需求量)(Supply供应量mAAA21nBBB21mnmmnnccccccccc212222111211nbbb21maaa21minjjiba11平衡表建立数学模型0,,2,1,,2,1min1111ijmijijnjiijnjmiijijxnjbxmiaxxcS.,,2,1,,2,1,njmixjiij地的调运量为地调往设从平衡运输问题数学模型的矩阵表示法0minxbAxCxS111111111111111111AmnmmnncccccccccC212222111211nmbbbaaab2121mnnxxxxxx2111211定理1在产销平衡的运输问题中,其约束方程组的系数矩阵和增广矩阵的秩相等,且等于m+n-1.定理2方程组有解的充要条件是0xbAx.11minjjiba证明:必要性.,,,11111011010njjmiinjnjmiijjminjijmiiijbaxbxax所以及则是方程组的一个可行解设充分性.,,,,,2,1,,2,1,,111011101110011njjminjijmiiminjijiinjjinjjinjijjiijnjjmiibxaxaMMabMaMbaxnjmiMbaxMba同理故取设定理3平衡的运输问题一定有最优解.minjijijijijSxcScx110.min,0,0,0存在故证明:1.编制初始调运方案方法一:最小元素法(Minimalelementsmethod)在平衡表中,按运价最小者优先满足的原则,找出m+n-1个有数字的格为基变量,空格为非基变量.方法二:西北角法(Northwestcornermethod)注意:一般来说用最小元素法得到的初始调运方案更接近于最优方案.二.运输问题的表上作业法发发量731131241928974105收量365620例1见下表:收321AAA4321BBBB4321BBBB364133433312.最优方案的判别方法一:闭回路法闭回路:从非基变量格出发,沿水平或垂直方向前进,碰到适当的基变量格转向,再回到原来的空格,称为一个闭回路.在闭回路上的基变量格称为转角点.可以证明,如果不考虑方向,则每一个空格的闭回路唯一存在.找出上例中各空格的闭回路发发量437311312314192863974105收量365620321AAA4321BBBB4321BBBB收每个空格即非基变量的检验数的求法:..偶转角点运价之和奇转角点运价之和运价之和运价之和减去偶转角点的闭回路上奇转角点等于的检验数对应于空格ijijijijxx.14)1012()35(12)7212()135(3)83()122(1)953()4122(0)115()412(1)32()13(333124221211注意:1.空格为第0次转角.2.当第一次出现正检验数时,可停止以下检验数的计算.调运方案的判优准则:对调运方案表中的每一空格作一条闭回路,并求出检验数,如果检验数全部小于等于零,则该调运方案最优.否则要调整调运方案.3.方案的调整⑴选取入基变量:第一个正检验数的空格对应的非基变量为入基变量.本例中为入基变量.22x⑵入基变量的取值为θ,θ=min{奇转角点运量}.即该非基变量的运量为θ,同时变为基变量.⑶出基变量的选择:在此闭回路上和奇转角点上最小运量对应的基变量变为零,该变量是出基变量,在新方案中它的位置是空格.⑷在该闭回路中按奇,偶点进行运量的平衡调整,得一新的调运方案.⑸对新方案判优,调整,直到求出最优方案.发发量437311312314192863974105收量365620收321AAA4321BBBB4321BBBB111111发发量527311312314192854974105收量365620321AAA4321BBBB4321BBBB收第一次调整后的新方案经过四次迭代得到最优方案如下,总运费为85.发发量257311312134192863974105收量365620收321AAA4321BBBB4321BBBB方法二:乘数法(位势法)发发量437311312314192863974105收量365620321AAA4321BBBB4321BBBB收令第一,二,三行的乘数分别为.,,321uuu令第一,二,三,四列的乘数分别为.,,,4321vvvv且有.4,3,2,1.3,2,1jicvuijji写出基变量的乘数方程:5421123344332232332211214411331cvucvucvucvucvucvu5421123344332232332211214411331cvucvucvucvucvucvu该乘数方程有六个方程,七个未知数,一定有解,且有无穷多解.可令得出一组解.,01u1231127104321321vvvvuuu由这组解按下面的公式求空格(非基变量的检验数:ijjiijcvuijjiijcvu1410371272738121191110111101320333333311331244224222222122112111111cvucvucvucvucvucvu与闭回路法求得的检验数完全相同.注意:⒈要保证调运平衡表中填有数字的格数为m+n-1,且不构成闭回路。若填上调运量后,第i行发量及第j列销量都已满足,则在运价表中只允许划去第i行与第j列中的一个,而不允许将它们全划去.此后,当运价或最小时,要在或的格子上填写0,它表示一个基变量,这属于LP中退化的情形.ijxkjcilckjxilx发发量2516483289510137243收量2213171870321AAA4321BBBB4321BBBB收请看下面的例子:2213第三行,第二列任选一个031418314182.对于有的运输问题,最优调运方案不止一个.23521432232713521516143212254518321AAA321BBB54BB321BBB54BB收发1135.,,035113511均可为入基变量xx二.产销不平衡的运输问题:.,;,.111111型为对于产大于销的运输模题称为产小于销的运输问时当题称为产大于销的运输问时当的情形是指产销不平衡的运输问题njjmiinjjmiinjjmiibababa0,,2,1,,2,1min1111ijmijijnjiijminjijijxnjbxmiaxxcS解决方法:增加一个虚拟(Dummy)库存点(销地),其库存量为.111njjmiinbab1nB再增加m个松弛变量mixni,,2,1,1,表示产地在处的库存量.在运价表中,相应的运价,但这个运价不按最小元素处理.iA1nB01,nic经过以上的处理,可将产大于销的运输问题变为产销平衡的运输问题.例3收发发量72113451035977812收量23461915321AAA4321BBBB4321BBBB收发库存发量库存72113405103590778120收量2346419321AAA4321BBBB4321BBBB将其改为产销平衡的运输问题,并求出初始调运方案4323322335222对于产销不平衡的运输问题中产小于销的情况,可在产销平衡表中虚设一个产地,其产量为,到各地的运价是一个充分大的正数M.变为产销平衡的运输问题.njmiijab11此外还有带中间转运站的运输问题,详细情况见p98例4.使用WinQSB求解运输问题.产销不平衡的运输问题实例:某研究院有三个区。每年取暖分别需要用煤3500吨，1100吨，2400吨，这些煤都要由煤矿供应，价格，质量均相同。煤矿的供应能力分别为1500吨，4000吨，运价如下表所示。由于需求大于供应，经研究决定：区供应量可减少0—900吨，区必须满足需求量，区供应量不少于1600吨，试求总费用最低的调运方案。321,,BBB21,AA21,AA1B2B3B需求地煤矿产量17519520815001601822154000需求量3500110024001B2B3B1A2A解：这是一个产销不平衡的运输问题，需求量大于供应量。处理办法是，将区和区分别设为两个区：一个是必须满足需求量的区，另一个是可以调整供应量的区。同时增加一个虚设的产地，其供应量为1500吨，同时在运价表中，取M表示一个很大的正数，使必须满足需求量的区域的运价取值为M，可调整需求量的区域的运价取值为0。（为什么？）这样，原问题变为有五个需求点，三个供应点的产销平衡的运输问题。新平衡表如下：1B3B3A需求地煤矿产量17517519520820815001601601822152154000M0MM01500需求量260090011001600800700070001B2B3B1A2A1B3B3A