运筹学-第2章运输问题课件.ppt

关于运输问题的基本结论： 定理1: 设有m个产地n个销地且产销平衡的运输问题，则基变量数为m+n-1。 证明(略) 原因是: 虽有m+n个约束条件，但由于总产量=总销量，导致只有m+n-1个是独立的。因此有一个是多余的。 注：上述定理说明：解中非零变量的个数不超过m+n-1. 因此：非基变量的个数为：mn-(m+n-1) 定理2 运输问题一定有最优解。 原因：有可行解xij=aibj/Q. 且有下界. * * * * * 课堂练习 运价 B1 B2 B3 B4 产量 A1 3 12 3 4 8 A2 11 2 5 9 5 A3 6 7 1 5 5 销量 4 3 8 6 如何安排运输，可使总运费最小？ * * 注意： 有相同的运价，如何选择？ 有相同的需求量和供应量，如何处理？ 进基变量有相同的检验数，如何处理？ 有相同的调整运量，如何处理？（这时需要补一个0，以保证有(m+n-1)个数字格作为基变量） 对最大化的问题，如何处理？等 将极大化问题转化为极小化问题。设极大化问题的运价表为C ，用一个较大的数M（M≥max{cij}）去减每一个cij得到矩阵C′，其中C′ =（M－cij）≥0, 将C′作为极小化问题的运价表，用表上用业法求出最优解。 * * （1）带罚款的运输问题 设有运输问题： From （To）B1 B2 B3 供应量 A1 5 1 7 10 A2 6 4 6 80 A3 5 2 5 15 需求量 70 70 50 若销地B1，B2，B3的需求没有满足，则单位罚款成本为4，3，2，求总费用最小的运输方案。 2.3 应用举例 * * 设 ――从工厂Ai运到销售点Bj的运输量。 如何化为供需平衡的运输问题呢？ * * 求解过程见教科书 销售点 工厂 A1 A2 A3 需求量 B1 B2 B3 供应量 5 6 5 1 4 2 7 6 5 70 70 50 15 80 10 A4 4 3 2 85 转化为供需平衡的运输问题 * * （2）指派问题 现由四人负责承担四家公司的税务工作，规定每个工作人员只能负责一家公司，已知各费用如下： 问如何安排，可使总费用最小。 公司 税务人员 B1 B2 B3 B4 A1 4 8 7 15 A2 7 9 17 14 A3 6 9 12 8 A4 6 7 14 6 * * 设 如何化为供需平衡的运输问题呢？ * * 公司 税务人员 B1 B2 B3 B4 A1 4 8 7 15 1 A2 7 9 17 14 1 A3 6 9 12 8 1 A4 6 7 14 6 1 1 1 1 1 求解过程见教科书 转化为供需平衡的运输问题 * * （3）生产计划问题 某食品加工厂按合同要在今后的两个月内为某商店加工某种食品14500千克，其中第一个月需交货8000千克，其余在第二个月交货。若加工好的食品当月没有交货，则存贮一个月需花费冷藏费用0.1元/千克。该厂的加工能力以及加工费用如表所示。如何设计生产方案，可使总费用最小？ 月份 生产方式 加工能力（千克） 加工费用（元/千克） 1 2 1 2 正常生产 5500 6000 0.60 0.60 加班生产 2000 2500 0.75 0.70 外协生产 2000 2000 0.85 0.80 * * 设xijk――第i个月以j方式生产的供k月交货的数量，i＝1,2，j＝1,2,3，k＝1,2 需求 生产 1 2 1 正常生产 0.60 x111 0.70 x112 5500 加班生产 0.75 x121 0.85 x122 2000 外协生产 0.85 x131 0.95 x132 2000 2 正常生产 － 0.60 x212 6000 加班生产 － 0.70 x222 2500 外协生产 － 0.80 x232 2000 需求量 8000 6500 * * 如何化为供需平衡的运输问题呢？ = * * 需求 生产 1 2 虚点 供应量 1 正常生产 0.60 0.70 0 5500 加班生产 0.75 0.85 0 2000 外协生产 0.85 0.95 0 2000 2 正常生产 M 0.60 0 6000 加班生产 M 0.70 0 2500 外协生产 M 0.80 0 2000 需求量 8000 65