第二章运筹学运输问题

1、第二章 运输问题n产销平衡的运输问题的数学模型n表上作业法n产销不平衡的运输问题及其应用n教学目的与要求：使学生学会建模方法能用表上作业法及WinQSB求解运输问题。n重点与难点：重点是产销平衡运输问题的表上作业法，难点是基变量个数为m+n-1的理论及操作方法.n教学方法:课堂讲授并辅以课件及软件.n思考题,讨论题,作业:教材中第三章作业.n参考资料:见前言n学时分配:4学时.第二章 运输问题(Transportation problems)物资调运是一个典型的线性规划问题.1939年前苏联经济学家康托洛维奇提出这一问题,1941年美国数学家F.L.Hitchcock提出运输问题数学模型,19

2、51年Dantzig将此类问题的解法系统化,完善化,改为用表上作业法求解.第一节 运输问题数学模型一.平衡运输问题的数学模型)(Source产地)Pr/(ofitCost运价销地)(nDestinatio)(Demand需求量)(Supply供应量mAAA21nBBB21mnmmnnccccccccc212222111211nbbb21maaa21minjjiba11平衡表建立数学模型0, 2 , 1, 2 , 1min1111ijmijijnjiijnjmiijijxnjbxmiaxxcS., 2 , 1, 2 , 1,njmixjiij地的调运量为地调往设从平衡运输问题数学模型的矩阵表示法

3、0minxbAxCxS111111111111111111AmnmmnncccccccccC212222111211nmbbbaaab2121mnnxxxxxx2111211定理1 在产销平衡的运输问题中,其约束方程组的系数矩阵和增广矩阵的秩相等,且等于m+n-1.定理2 方程组 有解的充要条件是0 xbAx.11minjjiba证明:必要性 .,11111011010njjmiinjnjmiijjminjijmiiijbaxbxax所以及则是方程组的一个可行解设充分性., 2 , 1, 2 , 1,111011101110011njjminjijmiiminjijiinjjinjjinjij

4、jiijnjjmiibxaxaMMabMaMbaxnjmiMbaxMba同理故取设定理3 平衡的运输问题一定有最优解.minjijijijijSxcScx110.min, 0, 0, 0存在故证明:1.编制初始调运方案方法一:最小元素法(Minimal elements method)在平衡表中,按运价最小者优先满足的原则,找出m+n-1个有数字的格为基变量,空格为非基变量.方法二:西北角法(Northwest corner method)注意:一般来说用最小元素法得到的初始调运方案更接近于最优方案.二. 运输问题的表上作业法 发发量7 3113124 19289 74105收量3656 20

5、例1 见下表:收321AAA4321BBBB4321BBBB364133433312. 最优方案的判别方法一:闭回路法闭回路:从非基变量格出发,沿水平或垂直方向前进,碰到适当的基变量格转向,再回到原来的空格,称为一个闭回路.在闭回路上的基变量格称为转角点.可以证明,如果不考虑方向,则每一个空格的闭回路唯一存在.找出上例中各空格的闭回路发发量437 311312314 1928639 74105收量3656 20321AAA4321BBBB4321BBBB收每个空格即非基变量的检验数的求法:.偶转角点运价之和奇转角点运价之和运价之和运价之和减去偶转角点的闭回路上奇转角点等于的检验数对应于空格ij

6、ijijijxx.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奇转角点运量.即该非基变量的运量为,同时变为基变量. 出基变量的选择:在

7、此闭回路上和奇转角点上最小运量对应的基变量变为零,该变量是出基变量,在新方案中它的位置是空格. 在该闭回路中按奇,偶点进行运量的平衡调整,得一新的调运方案. 对新方案判优,调整,直到求出最优方案.发发量437 311312314 1928639 74105收量3656 20收321AAA4321BBBB4321BBBB111111发发量527 311312314 1928549 74105收量3656 20321AAA4321BBBB4321BBBB收第一次调整后的新方案经过四次迭代得到最优方案如下,总运费为85.发发量257 311312134 1928639 74105收量3656 20收

8、321AAA4321BBBB4321BBBB方法二:乘数法 (位势法)发发量437 311 312314 1928639 7410 5收量3656 20321AAA4321BBBB4321BBBB收4321vvvv321uuu令第一,二,三行的乘数分别为.,321uuu令第一,二,三,四列的乘数分别为.,4321vvvv且有. 4 , 3 , 2 , 1. 3 , 2 , 1jicvuijji写出基变量的乘数方程:5421123344332232332211214411331cvucvucvucvucvucvu5421123344332232332211214411331cvucvucvucv

9、ucvucvu该乘数方程有六个方程,七个未知数,一定有解,且有无穷多解.可令 得出一组解., 01u1231127104321321vvvvuuu由这组解按下面的公式求空格(非基变量的检验数:ijjiijcvuijjiijcvu1410371272738121191110111101320333333311331244224222222122112111111cvucvucvucvucvucvu与闭回路法求得的检验数完全相同.注意: 要保证调运平衡表中填有数字的格数为 m+n-1,且不构成闭回路。 若 填上调运量后,第i行发量及第j列销量都已满足,则在运价表中只允许划去第i行与第j列中的一个,

10、而不允许将它们全划去. 此后,当运价 或 最小时,要在 或 的格子上填写0,它表示一个基变量,这属于LP中退化的情形.ijxkjcilckjxilx发发量25 164832 8951013 7243收量22131718 70321AAA4321BBBB4321BBBB收请看下面的例子:2213第三行,第二列任选一个031418314182. 对于有的运输问题,最优调运方案不止一个. 23521432232713521516143212254518321AAA321BBB54BB321BBB54BB收发1135., 035113511均可为入基变量xx二.产销不平衡的运输问题:.,;,.1111

11、11型为对于产大于销的运输模题称为产小于销的运输问时当题称为产大于销的运输问时当的情形是指产销不平衡的运输问题njjmiinjjmiinjjmiibababa0, 2 , 1, 2 , 1min1111ijmijijnjiijminjijijxnjbxmiaxxcS解决方法:增加一个虚拟(Dummy)库存点(销地), 其库存量为.111njjmiinbab1nB再增加m个松弛变量mixni, 2 , 1,1,表示产地 在 处的库存量.在运价表中,相应的运价 ,但这个运价不按最小元素处理.iA1nB01,nic经过以上的处理,可将产大于销的运输问题变为产销平衡的运输问题.例3 收发发量7 211

12、345 103597 7812收量2346 1915321AAA4321BBBB4321BBBB 收发 库存发量库存7 2113405 103590778120收量2346 419321AAA4321BBBB4321BBBB将其改为产销平衡的运输问题,并求出初始调运方案4323322335222对于产销不平衡的运输问题中产小于销的情况,可在产销平衡表中虚设一个产地,其产量为 ,到各地的运价是一个充分大的正数M.变为产销平衡的运输问题.njmiijab11此外还有带中间转运站的运输问题,详细情况见p98例4.使用WinQSB求解运输问题.产销不平衡的运输问题实例:某研究院有 三个区。每年取暖分别

13、需要用煤3500吨，1100吨，2400吨，这些煤都要由 煤矿 供应，价格，质量均相同。 煤矿的供应能力分别为1500吨，4000吨，运价如下表所示。由于需求大于供应，经研究决定：区供应量可减少0900吨， 区必须满足需求量， 区供应量不少于1600吨，试求总费用最低的调运方案。 321,BBB21, AA21, AA1B2B3B 需求地煤矿产量17519520815001601822154000需求量3500110024001B2B3B1A2A解：这是一个产销不平衡的运输问题，需求量大于供应量。处理办法是，将 区和 区分别设为两个区：一个是必须满足需求量的区，另一个是可以调整供应量的区。同时增加一个虚设的产地 ，其供应量为1500吨，同