企业运筹学管理--运输问题讲义.ppt

《企业运筹学管理--运输问题讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、运筹学运输问题物资运输问题某种物资有m个产地Ai，i=1,2,….,m，产量分别为ai个单位；有n个销地Bj，销量分别为bj个单位，j=1,2,…..n，Ai与Bj之间的单位运价为Cij，问应如何安排运输方案，才能使总运费最少？设从产地Ai，运往销地Bj的销量为Xij，则目标为总运费最小物资运输问题产地约束条件销地约束条件非负约束物资运输问题物资运输问题产销平衡的运输问题物资运输问题求一个初始基本可行解是判断基本可行解是否最优结束不是求使目标得到改善的基本可行解约束方程系数矩阵结构约束方程系数矩阵结构约束方程系数矩阵结构基变量个数m+n-1A的增广矩阵的秩小于m+n基

2、变量个数m+n-1A的增广矩阵的秩等于m+n-1基变量的构成闭回路其中，i1i2,….,is互不相同，j1j2,….,js互不相同）上述形式的变量的集合称为一个闭回路其中的变量称为闭回路的顶点闭回路的特点：封闭、每行每列至多两个顶点基变量的构成闭回路基变量的构成对于闭回路线性相关其对应的列向量基变量的构成若变量组中有一部分构成闭回路，则变量组线性相关。不包含任何闭回路的变量组中必有孤立点。孤立点是其所在行和所在列中包含在该变量组中的唯一向量。定理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。推论：m+n-1个变量构成基变量的充要条件是不含闭回路。运

3、输问题求解初始基本可行解的确定①在供需表中任选一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置；②调整Ai的拥有量及Bj的需求量，分别减去xij，得到调整后的拥有量ai和需求量bj；③若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）；④若平衡表中所有的行或列均被划去，则结束。否则，在剩下的平衡表中选下一个变量，转②运输问题求解B1……Bj……BnA1:Aixijaia’i:Ambjb’jb’j=bj-xija’i=ai-xij基变量的构成按照上述方法所产生的一组

4、变量的取值将满足下面条件：a．所得的变量均为非负，且变量总数恰好为m+n-1个；b．所有的约束条件均得到满足；c．所得的变量不构成闭回路。因此所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法，若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法），若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。西北角法运输问题某地区有两个煤矿A1A2，所产的煤要运往三个城市B1B2B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的

5、运输方案B1B2B3产量A1907095200A2806575230销量100150180西北角法B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180调整量100100调整量0调整量1000调整量050调整量50180调整量00调整量1800调整量0最小费用法B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180调整量15080调整量0调整量800调整量100调整量100100调整量0调整量1000调整量0907095806575+-+-B1B2B3产量A1x11x12x1320

6、0A2x21x22x23230销量10015018090709580657510010050180最优性检验21=C21-C11+C12-C22=80-90+70-65=-513=C13-C23+C22-C12=95-75+65-70=15最优性检验：闭回路法闭回路方法原理是通过寻找闭回路来找到非基变量的检验数。可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。如果规定作为起始顶点的非基变量为偶数次顶点，闭回路的其他顶点依次为第一个顶点、第二个顶点……，那么就有检验数=偶数点单位运费之和－奇数点单位运费

7、之和若所有非基变量检验数≥0，则最优。最优性检验：位势法位势法其原理是利用约束条件的特殊性来找到非基变量的检验数。从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。这一过程若用消元的方法加以实现，则回产生位势法。若所有非基变量检验数≥0，则最优。最优性检验：位势法位势法最优性检验：位势法位势法最优性检验：位势法B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（90）（70）9580（65）（75）B1B2B3产量A1x11x12