运输问题小结

1、第三章 运输问题上页上页下页下页返回返回运输问题运输问题数学模型的特点 运输问题一定存在有界的最优解 运输问题约束条件的系数矩阵 约束条件系数矩阵每列只有两个1,其余为0 约束条件中线性独立方程个数最多为m+n-1,运输问题的解中的基变量数一般为m+n-1个； 对产销平衡运输问题 约束条件均为等式，且产量之和=销量之和；上页上页下页下页返回返回运输问题表上作业法 表上作业法是单纯形法在求解运输问题的一种简便方法。 表上作业法的步骤：计算表中空格检验数表上给出m+n-1个数字格检验数是否全大于或等于零表上作业法最小元素法、Vogel法闭回路法、位势法上页上页下页下页返回返回运输问题表上作业法换基

2、：表上调整（闭回路调整）重复上述过程,运输问题必有最优解停止最优解？是否表上作业法上页上页下页下页返回返回上页上页下页下页返回返回运输问题一、产销不平衡的运输问题（）若总产量大于总销量，即njjmiiba11minjjinbab111令假想销地的销量为：上页上页下页下页返回返回运输问题（）若总产量小于总销量，即njjmiiba11miinjjmaba111令假想产地的产量为：一、产销不平衡的运输问题上页上页下页下页返回返回运输问题二、有转运的运输问题 由于问题中所有产地、中间转运站、销地都可以看做产地,又可看做销地.因此,把整个问题当作扩大的运输问题. 建立单位运价表，将原表中不可能的运输方案

3、的运价用任意大的正数M代替. 所有中间转运站的产量小于等于销量. 扩大的运输问题中原来的产地与销地因为也起转运站作用，所以，在原来产量和销量的数字上加上总转运量.上页上页下页下页返回返回习题三3.1已知运输问题的产销地的供需量与单位运价表如表3-35至表3-36所示，试用表上作业法求各题最优解，同时用Vogel法求出各题的近似最优解。101515551816142252097121511202103214321AAABBBB销量产量销地销地产地产地表3-35上页上页下页下页返回返回运输问题表上作业法用Vogel法得到的近似最优解1015155552515100151053214321AAABB

4、BB销量产量销地销地产地产地33511109157102525 z目标函数值目标函数值上页上页下页下页返回返回运输问题表上作业法检验数表8171704000016033214321AAABBBB销地销地产地产地所有检验数都大于等于零，所以用Vogel法得到的解即为最优解。上页上页下页下页返回返回习题三15201010263435257496721483214321AAABBBB销量产量销地销地产地产地表3-36上页上页下页下页返回返回习题三因产大于销,设一虚拟销地B5,建立产销平衡表.产地销地上页上页下页下页返回返回习题三产地销地用Vogel法得到的近似最优解上页上页下页下页返回返回运输问题表

5、上作业法193z检验数表产地销地所有检验数都大于等于零，故用所有检验数都大于等于零，故用Vogel法得到法得到的解即为最优解，对应的目标函数值的解即为最优解，对应的目标函数值上页上页下页下页返回返回习题三3.5已知运输问题的产销平衡表、最优调运方案及单位运价表分别如下表3-38和3-39所示：产地销地表3-38 产销平衡表及最优方案上页上页下页下页返回返回习题三试分别分析:(a)从A2至B2的单位运价在什么范围变化时,上述最优调运方案不变;(b)从A2至B4的单位运价变为何值时,将有无限多最优调运方案.除表3-38中给出方案,至少再写出其他两个最优调运方案;(c)若从A3-B1的通道因故暂时封

6、闭,试提出一个较为简便的方法重新找出最优运输方案;(d)以x12,x14,x21,x22,x23,x31为基变量列出本问题若用单纯形法求解时的单纯形表,并判别给出方案是否为最优.产地销地表3-39 单位运价表上页上页下页下页返回返回习题三10301802401001003222222222222cccccc检验数表算得检验数表的值看成未知，重新计将单位运价表中解：22)(ca产地销地上页上页下页下页返回返回习题三17017111724242424ccc最优方案.)(242424可通过闭回路法求的值，验数，只影响的变化不会影响其他检解： cb产地销地上页上页下页下页返回返回习题三其他最优方案：方案一产地销地方案二产地销地上页上页下页下页返回返回习题三新最优方案再继续表上作业法问题的初始可行方案可将原最优方案作为该无穷大为则它们之间的单位运价的通道因故暂时封闭，解：,),(M)(13BAc产地销地产地销地新单位运价