运筹学运输问题求解-方法.ppt

特殊运输问题的求解方法—例5.5 产销不平衡运输问题的求解方法 例5.5 设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区使用效果相同，各化肥厂年产量、各地区年需量及从各化肥厂到各地区运送化肥的单位运价(万元/万t）如5-25所示。试求出总运费最少的化肥调拨方案。 运价 需求 化肥厂 I II III IV 产 量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需求 30 70 0 10 最高需求 50 70 30 不限 运价 需求 化肥厂 I II III IV 产 量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需求 30 70 0 10 110(万t) 不限 最高需求 50 70 30 不限 160万t 分析：产销不平衡；根据现有产量，第IV地区最多能分配到:160-（30+70+0）=60万t(总厂量减去前三个地区最低需求量之和 ). 210万t 60万t 则最大需求量为：50+70+30+60=210万t; 最大需求210万t比供应160万t多50万t,因此需要虚拟一个供应点D，其供应量为50万t，使得供求平衡。 运价 需求 化肥厂 I II III IV 产 量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需求 30 70 0 10 110 万t （210） 最高需求 50 70 30 不限（60） 运价 需求地 供应地 II III 供应 量 A 16 16 50 B 14 14 60 C 19 19 50 D M 0 50 需求量 30 20 M（任意大正数)表示非常高的运价，M不会进入最优解 产销平衡表 运价 需求 化肥厂 I II III IV 产 量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需求 30 70 0 10 110 t （210） 最高需求 50 70 30 不限（60） 运价 需求地 供应地 II III 供应 量 A 16 16 13 50 B 14 14 13 60 C 19 19 20 50 D M 0 M 50 需求量 30 20 70 M（任意大正数)表示非常高的运价，M不会进入最优解 产销平衡表 运价 需求 化肥厂 I II III IV 产 量 A 16 13 22 17 50 B 14 13 19 15 60 C 19 20 23 - 50 最低需求 30 70 0 10 110 t （210） 最高需求 50 70 30 不限（60） 运价 需求地 供应地 II III 供应 量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 需求量 30 20 70 30 10 50 M（任意大正数)表示非常高的运价，M不会进入最优解 产销平衡表 运价 需求地 供应地 II III 供应 量 A 16 16 × 13 22 17 17 50 B 14 14 × 13 19 15 15 60 C 19 19 × 20 23 M M 50 D M 0 M 0 M 0 50 需求量 30 20 70 30 10 50 *解的退化：在用最小元素法求解初始基本可行解时，当产销平衡表上填上一个数后，单位运价表上要同时划去一行和一列，则此时会出现退化。退化分为两种情况。 20 求解步骤：利用最小元素法求解运输问题的初始解 运价 需求地 供应地 II III 供应 量 A 16 16 × 13 22 × 17 17 50 B 14 14 × 13 19 × 15 15 60 C 19 19 × 20 23 × M M 50 D M × 0 M × 0 M × 0 × 50 需求量 30 20 70 30 10 50 20 30 求解步骤：利用最小元素法