运筹学09-运输问题-11.pptVIP

求初始方案时退化情况的处理 类似地，若总销量大于总产量，即 ，则增加虚拟产地Am+1，且该产地的产量 例：(产大于销) 注：(1) 添加虚拟销地后，原m+n-1个基变量变为m+n个基变量； (2) 若贮存费用全为零，在求初始方案时，贮存列放在最后考虑， 若贮存费用不全为零，则求初始方案时，贮存列与其他列同 等对待，不再放到最后考虑； (3) 最优性判别及方案调整时，应包括贮存列的空格。 例：现假设甲供应商的产品必须全部运输出去，而乙供应商和丙供应商的单位储存费用分别为2和3 例： 已知运输问题由表给出，试建立运输模型 . Bj Ai B1 B2 B3 ai A1 4 2 5 10 A2 6 3 8 15 bj 8 7 14 解: Bj Ai B1 B2 B3 ai A1 4 2 5 10 A2 6 3 8 15 A3 0 0 0 4 bj 8 7 14 本题产量为25，销量为29，是销大于产问题 虚设一个产地 A3，由于并没有生产，所以运价为零，得运输模型. 如果各销地不满足时，单位缺货费为 4，3，7，则运输模型为 4 3 7 转运问题 转运模型指货物在到达最后的终点之前通过中间或过渡节点来运输。 例：两个汽车制造厂P1和P2，通过两个转运中心T1和T2，供应3个经销商D1，D2，D3，如图所示。制造厂P1和P2的供应量分别为1000和1200辆汽车，经销商D1，D2，D3的需求量分别为800，900，500辆汽车。 P1 P2 T1 T2 D1 D2 D3 3 4 2 5 7 8 6 4 9 5 3 800 900 500 1000 1200 P1 P2 T1 T2 D1 D2 D3 3 4 2 5 7 8 6 4 9 5 3 800 900 500 1000 1200 纯供应节点：只有输出，没有输入 纯需求节点：只有输入，没有输出 转运节点：既有输入，也有输出 P1，P2 D3 T1, T2, D1, D2 这个转运模型可以转化为一个常规的运输模型，有6个起点(P1,P2,T1,T2,D1,D2)和5个终点(T1,T2,D1,D2,D3) 不同类型的节点供应量和需求量，计算方法如下： 纯供应节点的供应量 = 初始供应量 纯需求节点的需求量 = 初始需求量 转运节点的供应量 = 初始供应量 + 缓冲量 转运节点的需求量 = 初始需求量 + 缓冲量 缓冲量应充分大，允许所有的初始供应量(或需求量)能够通过任何一个转运节点。设B为所需要的缓冲量，则 B = 全部供应量(或需求量) = 1000 + 1200 (或800+900+500) = 2200 销地 产地 T1 T2 D1 D2 D3 供应量 P1 3 4 M M M 1000 P2 2 5 M M M 1200 T1 0 7 8 6 M 2200 T2 M 0 M 4 9 2200 D1 M M 0 5 M 2200 D2 M M M 0 3 2200 需求量 2200 2200 3000 3100 500 例：考虑下面的由两个产地分别运送某种物资到三个销地的问题 假定每个产地和每个销地都可以作为转运点。产地及销地间的单位运价如下表。 建立此允许转运的运输模型。 * 第9讲 运输问题 本讲提纲 一、运输问题及其数学模型 二、运输问题的求解——表上作业法 三、运输问题的进一步讨论 一、运输问题及其数学模型 供应商 1 Cleveland 2 Bedford 3 York 2 Chicago 1 Boston 3 St. Louis 4 Lexington 销售商 5,000 2,500 6,000 6,000 1,500 2,000 4,000 3 2 7 6 2 7 5 3 4 2 5 5 x11 x21 x31 x12 x22 x32 x13 x23 x33 x14 x24 x34 xij - 从 i 地到 j 地的运输量 应如何安排运输方案，使得总运费最低？ x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34 Min Z= 3x 11 +2x 12 +7x 13 +6x 14 +7x 21 +5x 22 +2x 23 +3x 24 +2x 31 +5x 32 +4x 33 +5x 34 S. t. x 11 +x 12 +x