运筹学章运输问题

线性规划模型与图解2.2单纯形对偶问题线性规划模型与图解2.2单纯形对偶问题与灵敏度分运输问线性整数规线性目标规个仓库运往n个销售地，S处有货物a吨，个仓库运往n个销售地，S处有货物a吨，物bj吨，从Si到D的运价为cij产销平衡销产 产产销平衡销产 产… x22 … …销 aibj 单位运价销产 单位运价销产 … C22 … 二、运输问题的数学模minz二、运输问题的数学模minzc11x11c12 c1nc21x21 c22 c2ncm1xm1 cm2xm2cmnxmnmncijxiji j约束条件为(1)nm约束条件为(1)nmaibjj1,2,,x2xmxx2xmxxx1约束方程式中共m*n个变量，m+n个约束技术系矩A=技术系矩A=1111三、运输问题的解求解平衡运三、运输问题的解求解平衡运输问题的表上作业确定一个初始的可行调运方案：西北角法、gl法判断当前可行方案是否最优：法方案调整：【例12】产销平衡 【例12】产销平衡 749 单位运价销产 单位运价销产 （1）确定初始调运方案（最小元素法73493656331928745（1）确定初始调运方案（最小元素法7349365633192874533S1928274573149365633S1928274573149365633192874547314936563319287454731493656331928745473146936563319287454731469365633192874547314639365633192874547314639365633192874543731463936563319287454373146393656（1）确定初始调运方案（西北角法产3347319282247459363656销（1）确定初始调运方案（西北角法产3347319282247459363656销产3300052719281116314127456393656销213列罚21列罚1列罚12列罚产3300052719281116314127456393656销213列罚21列罚1列罚12列罚（2）判断当前方案是否为最优（闭回路法，位势法4373146393656（2）判断当前方案是否为最优（闭回路法，位势法43731463936563473146393656437314639365634731463936564373146393656437314639365643731463936567433146393656437314639365643731463936567433146393656可能的几种闭回路的形可能的几种闭回路的形c13c23c34c23c14c13c23c34c23c14c22c23c24c23c31c34c33c343743146393656331928745ijijijij1271-493656371244593656437314639365637124459365643731463936563124531245（2有数格），依次求ui和vj值，并填在相应的上。30（2有数格），依次求ui和vj值，并填在相应的上。3012-45-293计算（uivj）表，把uivj）位势和值填在表中并将有数格位置上的 值加上括号以示区别。j29计算（uivj）表，把uivj）位势和值填在表中并将有数格位置上的 值加上括号以示区别。j29089----293（ij）2903389-S19282---745VVVV1234293（3）计算检验 v)ijijij121-（ij）2903389-S19282---745VVVV1234293（3）计算检验 v)ijijij121-调整方案：方法是从具有负检验数的空格出发（负检验数时，选择绝对值大的一个），的闭回路进行调整，即在方案可行的条件下，调整方案：方法是从具有负检验数的空格出发（负检验数时，选择绝对值大的一个），的闭回路进行调整，即在方案可行的条件下，最小数。7433146393656最小数。7433146393656调整后的结527301463393656调整后的结527301463393656（i）3903371-S19282---74539302219（i）3903371-S19282---74539302219再计算新方案的空格检验数02219再计算新方案的空格检验数02219对于产销不平衡问题，可以增加虚设的销地，将不平衡问题转对于产销不平衡问题，可以增加虚设的销地，将不平衡问题转化为平衡问题处当产大于销mnbjj可以虚拟一销售地 .其销量为mnaibjj当产小于销时mnaibjj可以当产小于销时mnaibjj可以虚拟一产