3-2运输问题表上作业法课件.ppt

1、1、单纯形法（为什麽？）、单纯形法（为什麽？）2、表上作业法、表上作业法 确定初始确定初始方案方案( ( 初初 始始 基本可行解基本可行解) ) 改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案图图1 运输问题求解思路图运输问题求解思路图 表表2是两个产地、三个销地的运输问题作业表。是两个产地、三个销地的运输问题作业表。 调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 c11 X11 c12 X12 c13 X13 a1 A2 c21 X21 c22 X22 c23 X23 a2 销销 量量 b1 b2 b33

2、121jjiiba表表2 运输问题作业表（产销平衡表）运输问题作业表（产销平衡表） 个销地需求满足第个销地第个产地的产量全部运到第jjbjiia3、 表表3-4 例例3-2有关信息表有关信息表 450 200 150 100 日销量（需求量） 250 75 65 80 乙 200 100 70 90 甲 日产量日产量（供应量）（供应量） C B A运距运距 城市城市煤矿煤矿; 3 , 2 , 1; 2 , 1, 0200150100250200. .7565801007090min231322122111232221131211232221131211jixxxxxxxxxxxxxt sxxx

3、xxxZij需求约束日产量约束总运输量调调 销地销地 运运 量量产地产地 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初始调运方案初始调运方案 150100100100100100100调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450 用西

4、北角法确定例用西北角法确定例3-2初始调运方案初始调运方案 100100100 50 50200200 现在，在现在，在用最小元素法确定例用最小元素法确定例3-2初始调运初始调运方案的基础上，方案的基础上，计算非基变量计算非基变量X12的检验数的检验数 ：ij（3-6）调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 4501001001001501221 iujv7565100902332222213311111cvucvucv

5、ucvu（3-7）例例3-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 v3100100100150位势位势变量变量 ui u1 u2 ij ij调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量

6、 100 150 200 450100100100150+- 调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450100100200 50调调 销地销地 运运 量量产地产地 B1 B2 B3 产产 量量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销销 量量 100 150 200 450150 50200 50运输问题的计算机求解运输问题的计算机求解表上作

7、业法表上作业法1、适用软件、适用软件Transportation/Transshipment Problem（TRP）2、输入数据：、输入数据：Maximize 1 minimize 2 Number of sources? Number of destinations? Number of transshipment point? Use the default names(S1 Sn ,D1 Dn ,T1Tn) Press the Space Bar to continue if your entries are correct Capacities of SourcesS1: 200 S

8、2: 250 Demands of destinationsD1: 100 D2: 150 D3: 200ENTER THE Cost/Profit Coefficients of the TRP Model -Minimization-From To S1 D1: 90 D2: 70 D3: 100 S2 D1: 80 D2: 65 D3: 80(注意：该例的输入数据与前例不同注意：该例的输入数据与前例不同)3、计算过程中的初始表、计算过程中的初始表 Initial solution by 0 0 0 V(j) +200 +150 +100Demands 0 +250 +80 +200 +6

9、5 +80 +50 S2 0 +200 +100 +70+150 90 +50 S1 U(I)Supplies D3 D2 D1SNDN4、求解结果报告、求解结果报告 Summary of Results for TR2 Page :1 FromToShipmentcostOpp.ct.FromToShipmentcostOpp.ct.S1S1S1D1D2D3+50.000+150.00 0+90.00+70.00+100.0 0 0 +10.00S2S2S2D1D2D3+50.000 0+200.00+80+65+80050Minimized OBJ = 35000 Iteration = 0 Elapsed CPU second = 53.3906 ？转化转化