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

运筹学运输问题第一页，共四十七页。物资运输问题某种物资有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第十页，共四十七页。基变量个数m+n-1A的增广矩阵的秩等于m+n-1第十一页，共四十七页。基变量的构成闭回路其中，i1i2,….,is互不相同，j1j2,….,js互不相同）上述形式的变量的集合称为一个闭回路其中的变量称为闭回路的顶点闭回路的特点：封闭、每行每列至多两个顶点第十二页，共四十七页。基变量的构成闭回路第十三页，共四十七页。基变量的构成对于闭回路线性相关其对应的列向量第十四页，共四十七页。基变量的构成若变量组中有一部分构成闭回路，则变量组线性相关。不包含任何闭回路的变量组中必有孤立点。孤立点是其所在行和所在列中包含在该变量组中的唯一向量。定理：r个变量对应的系数列向量线性无关的充要条件是变量组不包含闭回路。推论：m+n-1个变量构成基变量的充要条件是不含闭回路。第十五页，共四十七页。运输问题求解初始基本可行解的确定①在供需表中任选一个单元xij，尽量匹配产销，使一个约束方程得以满足，填入相应位置；②调整Ai的拥有量及Bj的需求量，分别减去xij，得到调整后的拥有量ai和需求量bj；③若ai=0，则划去对应的行（拥有的量全部运走），若bj=0则划去对应的列（需求的量全部运来），且每次只划去一行或一列（每次只去掉一个约束）；④若平衡表中所有的行或列均被划去，则结束。否则，在剩下的平衡表中选下一个变量，转②第十六页，共四十七页。运输问题求解B1……Bj……BnA1:Aixijaia’i:Ambjb’jb’j=bj-xija’i=ai-xij第十七页，共四十七页。基变量的构成按照上述方法所产生的一组变量的取值将满足下面条件：a．所得的变量均为非负，且变量总数恰好为m+n-1个；b．所有的约束条件均得到满足；c．所得的变量不构成闭回路。因此所得的解一定是运输问题的基本可行解。在上面的方法中，xij的选取方法并没有加以限定，如果采取一定的规则来选取，则会产生不同的方法，若每次在调整后的供需表中选取最左上角的元素，则称为左上角方法（或称西北角法），若每次在调整后的供需表中选取对应单位运费最小的元素，则称为最小费用法。第十八页，共四十七页。西北角法运输问题某地区有两个煤矿A1A2，所产的煤要运往三个城市B1B2B3，各产地的产量、销地的销量以及各产地到各销地的单位运费见下表，求使总运费最小的运输方案

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产量A1x11x12x13200A2x21x22x23230销量10015018090709580657510010050180最优性检验21=C21-C11+C12-C22=80-90+70-65=-513=C13-C23+C22-C12=95-75+65-70=15第二十二页，共四十七页。最优性检验：闭回路法闭回路方法原理是通过寻找闭回路来找到非基变量的检验数。可以证明，如果对闭回路的方向不加区别，那么以每一个非基变量为起始顶点，以基变量为其它顶点的闭回路就存在而且唯一。如果规定作为起始顶点的非基变量为偶数次顶点，闭回路的其他顶点依次为第一个顶点、第二个顶点……，那么就有检验数=偶数点单位运费之和－奇数点单位运费之和若所有非基变量检验数≥0，则最优。第二十三页，共四十七页。最优性检验：位势法位势法其原理是利用约束条件的特殊性来找到非基变量的检验数。从约束条件中解出基变量（用非基变量表示基变量），代入目标后消去目标中的基变量，得到的非基变量的系数就是检验数。这一过程若用消元的方法加以实现，则回产生位势法。若所有非基变量检验数≥0，则最优。第二十四页，共四十七页。最优性检验：位势法位势法第二十五页，共四十七页。最优性检验：位势法位势法第二十六页，共四十七页。最优性检验：位势法第二十七页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（90）（70）9580（65）（75）第二十八页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（90）（70）9580（65）（75）第二十九页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（-20）580（65）（75）第三十页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）580（85）（75）第三十一页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）5-5（0）（-10）第三十二页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15-5（0）（0）第三十三页，共四十七页。90709580657510010050180

+-

+

-

B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180调整流量X21进基，=min{x11,x22}=min{100,50}=50X22出基第三十四页，共四十七页。调整流量调运量的调整步骤：①闭回路上的奇数次顶点的调运量减去θ；②闭回路上的偶数次顶点（包括起始变量）的调运量加上θ；③非闭回路顶点的其他变量调运量不变；④奇数点上被修改为0的变量为出基变量，在新的方案中不再标出其值。但若有两个为零的变量，则只取其一作为出基变量。第三十五页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量1001501809070958065755015050180调整流量22=C22-C21+C11-C12=65-80+90-70=513=C13-C23+C21-C11=95-75+80-90=10第三十六页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15(-5)0（0）第三十七页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）15(0)5（5）第三十八页，共四十七页。B1B2B3产量A1x11x12x13200A2x21x22x23230销量100150180最优性检验：位势法（0）（0）10(0)5（0）第三十九页，共四十七页。产大于销的运输问题虚拟销地n+1，销量第四十页，共四十七页。产大于销的运输问题B1B2B3B4需求量A1569440A2948560A31075350拥有量25204045B1B2B3B4B5需求量A15694040A29485060A310753050拥有量2520404520例3-2第四十一页，共四十七页。产大于销的运输问题B1B2B3B4B5需求量A1250015040A20200202060A3004010050拥有量2520404520第四十二页，共四十七页。销大于产的运输问题没有可行解第四十三页，共四十七页。销大于产的运输问题虚拟产地n+1，产量允许缺货第四十四页，共四十七页。销大于产的运输问题第四十五页，共四十七页。作业P1233-3第四十六页，共四十七页。内容总结运筹学。某种物资有m个产地Ai，i=1,2,。有n个销地Bj，销量分别为bj个单位，j=1,2,