[理学]运筹第4章运输问题ppt课件

1、12w 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，。已知各产地的和各销地的以及各产地到各销地的，问应如何组织调运，才能使？3根据具体问题选择确定根据具体问题选择确定。 表表4-1 有关信有关信息息单位单位 运价运价 销销 或运距或运距 地地产地产地 B1 B2 Bn 产产 量量 A1 A2 Am c11 c12 c1 n c21 c22 c2n cm1 cm2 cm n a1 a2 am 销销 量量 b1 b2 bn njjmiiba114w设xij为从产地Ai运往销地Bj的物资数量（i=1，m；j=1，n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应

2、满足： w miaxnjiij, 2 , 115w同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足： w总运费为： mijijnjbx1, 1minjijijxcz116 njmixnjbxmiaxtsxcMinZijmijijnjiijminjijij,1;,1,0,1,1.1111minjjiba11产销平衡条件7mnmmnnxxxxxxxxx,;,212222111211111111111111111111m行行n行行89nmbbbaaaA1111111111111111112121mnmmnnxxxxxxxxx,;,21222211121110132222111,ji

3、jijijijijisssxxxxxxsssjijijijijijixxxxxx123221211,siii,21sjjj,2111 X11 X13 X21 X24 X33 B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 111333342421,xxxxxx12 X11 X13 X21 X24 X33 B1 B2 B3 B4 A1 X12 X14 A2 X22 X23 A3 X31 X32 X34 12222414,xxxx222333311112,xxxxxx13（a） （b） （c） （d） （e）表中的折线构成一条封闭曲线，表中的折线构

4、成一条封闭曲线，且所有的边都是且所有的边都是或或的；为什麽？的；为什麽？ 表中的表中的和和；为什麽？；为什麽？14三.运输问题求解 表上作业法 15 ( (初初 始始 基本可行解基本可行解) ) （换基迭代）（换基迭代） 图图4-1 运输问题求解思路图运输问题求解思路图16调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销 量量 b1 b2 b3 表表4-2 运输问题作业表（产销平衡表）运输问题作业表（产销平衡表） 23i=11ijjab17 1 1、初

5、始基本可行解的确定、初始基本可行解的确定 找到找到 m m + + n n 1 1 个不构成个不构成闭回路的基变量。闭回路的基变量。 较常用的方法有西北角法、最较常用的方法有西北角法、最小元素法和伏格尔法。小元素法和伏格尔法。 二、产销平衡问题表上作业法步骤18 西北角法 19调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用西北角法确定例用西北角法确定例4-2初始调运方案初始调运方案 100100100 50 502

6、0020020 w运输费用为运输费用为3425021调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450用最小元素法确定例用最小元素法确定例3-2初始调运方案初始调运方案 15010010010010010010022w运输费用为运输费用为3625023 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销量量 100 150 2

7、00 450用用伏格尔伏格尔法确定例法确定例3-2初始调运方案初始调运方案 5050200150505050两最两最小元小元素之素之差差101525101510两最小元素之差两最小元素之差202001015024w运输费用为运输费用为3400025 2627 现在，在用最小元素法确定例现在，在用最小元素法确定例4-2初始调运初始调运方案的基础上，计算非基变量方案的基础上，计算非基变量X12的检验数的检验数 ：ij（3-6）28调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X2

8、3 250 销销 量量 100 150 200 45010010010015029122130 iujv7565100902332222213311111cvucvucvucvu（3-7）31例例4-2初始调运方案位势变量对应表初始调运方案位势变量对应表 调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450位势变量位势变量vj v1 v2 v3 100100100150位势位势变量变量 ui u1 u2 32 33 34ij

9、 3536调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100100150+-3738调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100200 5039调调 销地销地 运运 量量 产地产地 B1 B2 B3 产产 量量 A1 90

10、 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450150 50200 504041 ？转化转化421、产量大于销量、产量大于销量w增加虚拟销地增加虚拟销地w虚拟销地的销量？运价？虚拟销地的销量？运价？43运价见下表，产地产量分别为运价见下表，产地产量分别为7、5、7t，销地销量分别为销地销量分别为2、3、4、6t，试决定总运，试决定总运费最少的调运方案。费最少的调运方案。B1B2B3B4A121134A210359A3781244B1B2B3B4虚拟虚拟销地销地产量产量A12113407A21035

11、905A3781207销量销量23464452、产量小于销量、产量小于销量w增加虚拟产地增加虚拟产地w虚拟产地的产量？运价？虚拟产地的产量？运价？46运价见下表，产地产量分别为运价见下表，产地产量分别为7、5、2t，销地销量分别为销地销量分别为2、3、4、6t，试决定总运，试决定总运费最少的调运方案。费最少的调运方案。B1B2B3B4A121134A210359A3781247B1B2B3B4产量产量A1211347A2103595A378122虚拟虚拟产地产地00001销量销量2346483、销量非固定值、销量非固定值w数据见下表，决定运费最少的调拨方案。产量产量A1613221750B14

12、13191560C19202350最低最低需求需求3070010最高最高需求需求507030不限不限49” ” 产产量量A16161322171750B14141319151560C19192023MM50DM0M0M050销销量量302070301050504、转运问题、转运问题w数据见下表，w三个产地的产量分别为7、4、9t，四个销地的销量分别为3、6、5、6t，试决定运费最少的调拨方案。51A1A2A3T1T2T3T4B1B2B3B4A1132143311310A213521928A331 2374105T12311322846T2151114527T3423121824T432321212621194858121B332104222423B41085674621300000000000MMMMMMMM52A1A2A3T1T2T3T4B1B2B3B4产量产量A101