第六讲 运输、指派与转运问题.ppt

第六讲 运输、指派与转运问题 物流管理系 薛伟霞 主要内容 运输问题：网络模型与线性规划模型 运输问题 运输问题经常出现在计划货物配送和从某些供给地区到达需求地区之间的服务中，特别是每个供给地区（起点）的货物可获得量是有限的，每个需求地区（目的地）的货物需求量是已知的。 运输问题中最常用的目标是要使货物从起点到目的地的运输成本最低。 案例——福斯特发电机公司的运输问题 从3个加工厂运输一种产品到4个分销中心。福斯特发电机公司在俄亥俄州的克里夫兰、印第安纳州的贝德福德和宾夕法尼亚州的约克有3个工厂，下3个月德计划期内的这个特殊型号的发电机的生产能力如下： 案例——福斯特发电机公司的运输问题 公司通过坐落在波士顿、芝加哥、圣路易斯和莱克星顿的4个分销中心来分销这种发电机；每个分销中心3个月的需求预测如下： 案例——福斯特发电机公司的运输问题 运输成本如下所示： 网络图 建立线性规划模型的步骤 1、全面地了解问题； 2、描述目标； 3、描述约束条件； 4、定义决策变量； 5、用决策变量写出目标函数； 6、用决策变量写出约束条件。 描述目标和约束条件 确定使用哪些路线以及每条线路上的流量是多少时，使得总的运输成本最低。 每个起点的供给能力和每个目的地的特定需求量是有限的。 定义决策变量 运用双下标决策变量。 x11表示起点1(克利夫兰)运送到终点(波士顿)的货物数量，x12表示从起点1(克利夫兰)运送到终点2(芝加哥)的货物数量等等。 一般来说,运输问题的决策变量有m个起点和n个终点，如下: 用决策变量写出目标函数 从克利夫兰运输货物的成本： 3x11＋2x12＋7x13 + 6x14 从贝德福德运输货物德成本： 7x21＋5x22＋2x23 + 3x24 从约克运输货物德成本： 2x31＋5x32＋4x33 + 5x34 这些公式的总和为我们提供了福斯特发电厂运输总成本的目标函数。 用决策变量写出约束条件 每个起点的供给能力和每个目的地的特定需求量是有限的。 供给约束条件和需求约束条件 供给约束条件 克利夫兰的供给约束条件则为: x11＋x12＋x13 + x14≤5000 贝德福德的供给约束条件： x21＋x22＋x23 + x24≤5000 约克的供给约束条件： x31＋x32＋x33 + x34≤2500 需求约束条件 波士顿分销售中心需要量： x11 + x21 + x31= 6000 芝加哥分销售中心需要量： x12 + x22 + x32= 4000 圣.路易斯分销售中心需要量： x13 + x23 + x33= 2000 莱克星顿分销售中心需要量： x14 + x24 + x34= 1500 福斯特公司的线性规划模型 管理科学软件求解 线性规划 运输问题 问题的变化 总供给不等于总需求 最大化目标函数 线路容量或者线路最小量 不可接受的路线 总供给不等于总需求 总供给超过总需求——线性规划模型不需要进行修改。多余的供给总量在线性规划解决方案中表现为松弛。而任何起点的松弛都可以被理解为未使用的供给或者未从起点运输的货物数量。 最大化目标函数 问题——在某些运输问题中，目标是要找到最大化利润或者收入的解决方案。 路线容量和/或路线最小量 运输问题的线性规划模型也能够包含一条或者更多的路线容量或者最小数量问题。 例如：假设在福斯特公司发电机问题中，约克-波士顿路线（起点3到终点1）因为其常规的运输模式中有限空间的限制，只有1000单位的运输能力。用x31表示从约克运到波士顿的货物数量，那么约克—波士顿路线容量的约束条件为 ： x31≤1000 同样,路线的最小量也可以得到说明。例如： x22≥2000，这一条件保证了我们可以在最优解中继续维持先前承诺的至少2000单位的贝德福德—芝加哥路线的交货订单。 不可接受的路线 构建从每一个起点到终点的路线并不都是可能的。 去除网络图中相关的弧和线性规划模型中相关的变量。 运输问题的一般线性规划模型 i——起点下标，i=1，2，……，m； j——终点下标，j=1，2，……，n； xij——从起点i到终点j的运量量； cij——从起点i到终点j的单位运输成本； si——起点i的供应量或者生产能力； dj——终点j的需求量。 运输问题的一般线性规划模型 m个起点，n个终点的运输问题