《运筹学》课程教学课件（PPT电子教案）第六章 运输、指派和转运问题

凌晨: 运输、指派和转运问题 运输、指派和转运问题,实际上都可以用 LP.模型加以描述,所以可以认为它们是LP. 的特例 单列一章的原因在于:应用面极广,实践性 很强,而特有的数学结构使得人们设计出了 特别有效的方法对此类模型进行求解 本章的重点在:掌握表格化方法求解运输 指派、转运问题的模型

Ling Xueling 运输、指派和转运问题，实际上都可以用 L.P. 模型加以描述，所以可以认为它们是 L.P. 的特例 单列一章的原因在于：应用面极广，实践性 很强，而特有的数学结构使得人们设计出了 特别有效的方法对此类模型进行求解 本章的重点在：掌握表格化方法求解运输、 指派、转运问题的模型。 第六章 运输、指派和转运问题 凌晨: 凌晨:

凌晨: 第一节运输问题 运输问题及其常规解法 运输问题的概念 问题一一从m个起运点( origin)到n个目的地( destination)的货物和服务的分配计划 起运点特征一一可供量有限,无法(不能)超过 目的地特征一一需求量有限,满足即可 分配一一因为不同路径往往成本不相同,才有优化的 必要 优化目标一一成本最低、运费最小,或利润最大

Ling Xueling 一、运输问题及其常规解法 1、运输问题的概念 问题－－从 m 个起运点（origin）到 n 个目的地（ destination）的货物和服务的分配计划 起运点特征－－可供量有限，无法（不能）超过 目的地特征－－需求量有限，满足即可 分配－－因为不同路径往往成本不相同，才有优化的 必要 优化目标－－成本最低、运费最小，或利润最大。 第一节 运输问题 凌晨: 凌晨:

P&T公司分销问题:地图 CANNERY 1rT Bellingham WAREHOUSE 3 CANNERY 2 Eugene Rapid City CANNERY 3 Albert lea WAREHOUSE 2 Sait Lake City WAREHOUSE 1 Sacramento WAREHOUSE 4 Albuq uerq

Ling Xueling P&T 公司分销问题: 地图 CANNERY 1 Bellingham CANNERY 2 Eugene WAREHOUSE 1 Sacramento WAREHOUSE 2 Salt Lake City WAREHOUSE 3 Rapid City WAREHOUSE 4 Albuquerque CANNERY 3 Albert Lea

P&T公司分销问题:运输量与成本数据 罐头加工厂 产量 仓库 分配量 Bellingham 75车 Sacramento 80车 Eugene 125车 Salt lake City 65车 Albert lea 100车 Rapid city 0车 合计 300车 Albuquerque 85车 合计 00车 仓库 Salt lake 从 Sacramento City Rapid City Albuquerque 罐头加工厂 Bellingham $464 $867 Eugene 352 416 690 791 Albert lea 995 682 388 685

Ling Xueling P&T 公司分销问题: 运输量与成本数据 合计 300 车 合计 300 车 Albuquerque 85 车 Albert Lea 100 车 Rapid City 70 车 Eugene 125 车 Salt Lake City 65 车 Bellingham 75 车 Sacramento 80 车 罐头加工厂 产量 仓库 分配量 Albert Lea 995 682 388 685 Eugene 352 416 690 791 Bellingham $464 $513 $654 $867 罐头加工厂 Rapid City Albuquerque Salt Lake City 从 \ Sacramento 到 仓库

P&T公司分销问题:无算法的方案 决策模型:就近原则(观察运输成本) Bellingham加工厂离仓库最远,将其产品运到最近仓库 Sacramento 若 Bellingham加工厂有剩余,则送到 Salt Lake City Albuquerque仓库离加工厂最远,从距其最近的 Albert Lea加工厂产品送货 若 Albert Lea加工厂有剩余,则送到 Rapid City。 Eugene加工厂的产品满足其它仓库的剩余需求 仓库 到 Salt lake Sacramento Rapid City Albuquerque 罐头加工厂 Bellingham Eugene Albert lea 15 总运输成本=75($464)+5($352)+65($416)+55(690)+15($388)+85($685)=$165,595

Ling Xueling P&T 公司分销问题: 无算法的方案 Albert Lea 0 0 15 85 Eugene 5 65 55 0 Bellingham 75 0 0 0 罐头加工厂 Rapid City Albuquerque Salt Lake City 从 \ Sacramento 到 仓 库 • 决策模型：就近原则（观察运输成本） – Bellingham加工厂离仓库最远，将其产品运到最近仓库Sacramento； 若Bellingham加工厂有剩余，则送到Salt Lake City。 – Albuquerque仓库离加工厂最远，从距其最近的Albert Lea加工厂产品送货； 若Albert Lea加工厂有剩余，则送到Rapid City。 – Eugene加工厂的产品满足其它仓库的剩余需求。 总运输成本= 75($464) + 5($352) + 65($416) + 55($690) + 15($388) + 85($685) = $165,595

P&T公司分销问题:还有成本更低的方案吗? P&T公司配送问题 单位成本 目的地(仓库) 萨克拉门托 盐湖城 赖皮特城奥尔巴古 出发地 贝林翰 464 513 S654 867 罐头工 尤基尼 352 416 $690 $791 682 s685 运输量 目的地(仓库) 卡车装载 萨克拉门托盐湖城 赖皮特城 尔巴古 总运出量 出发地 贝林翰 艾尔贝·李 100 总运入量 80 65 85 需求量 80 65 70 85 总运输成本 20($513)+55($867)+80($352)+45($416)+70($388)+35($685) 降低$13060,约8%

Ling Xueling P&T 公司分销问题: 还有成本更低的方案吗? 总运输成本 = 20($513) + 55($867) + 80($352) + 45($416) + 70($388) + 35($685) = $152,535 降低$13060, 约8%! P&T公司配送问题 单位成本 目的地（仓库） 萨克拉门托 盐湖城 赖皮特城 奥尔巴古 出发地 贝林翰 $464 $513 $654 $867 (罐头工厂) 尤基尼 $352 $416 $690 $791 艾尔贝·李 $995 $682 $388 $685 运输量 目的地（仓库） 卡车装载 萨克拉门托 盐湖城 赖皮特城 奥尔巴古 总运出量 出发地 贝林翰 0 20 0 55 75 (罐头工厂) 尤基尼 80 45 0 0 125 艾尔贝·李 0 0 70 30 100 总运入量 80 65 70 85 = = = = 需求量 80 65 70 85

凌晨: 第一节运输问题 运输问题及其常规解法 2、例子 1)有关数据 Foster公司在全国不同地方有三家工厂O1、O2、O3,四家 地区零售中心D1、D2、D3、D,未来3个月供需数据如下 个月 销售中心三个月 生产能力 需求预测 O 5000 6000 6000 2500 DDDD 4000 2000 13500 1500 13500

Ling Xueling 一、运输问题及其常规解法 2、例子 1）有关数据 Foster 公司在全国不同地方有三家工厂 O1、O2、O3，四家 地区零售中心 D1、D2、D3、D4，未来 3 个月供需数据如下 工厂 三个月 销售中心 三个月 生产能力 需求预测 O1 5000 D1 6000 O2 6000 D2 4000 O3 2500 D3 2000 13500 D4 1500 13500 第一节 运输问题 凌晨: 凌晨:

凌晨: 第一节运输问题 运输问题及其常规解法 2)可用运输路径(由结点、弧构成的网络图) NETWORK 目的结点 源结点 1)6000 ARCS NODES 50001 2)4000 60002 32000 2500(3 1500

Ling Xueling 一、运输问题及其常规解法 2）可用运输路径（由结点、弧构成的网络图） 第一节 运输问题 凌晨: 凌晨: 1 2 3 1 2 3 4 5000 6000 2500 6000 4000 2000 1500 arcs nodes network 源结点 目的结点

凌晨: 第一节运输问题 运输问题及其常规解法 3)各路径单位运输成本数据(C数据一一弧之权 目的地 起运点D1 D Ooo 255 D-635 4)假定(以后再逐步放松) (1)三家工厂的生产成本一样,仅仅运输成本可变 (2)(隐含假定)∑O=∑D

Ling Xueling 一、运输问题及其常规解法 3）各路径单位运输成本数据 (Cij 数据－－弧之权) 目的地 起运点 D1 D2 D3 D4 O1 3 2 7 6 O2 7 5 2 3 O3 2 5 4 5 4 ）假定 ( 以后再逐步放松 ) （1） 三家工厂的生产成本一样, 仅仅运输成本可变 （2） ( 隐含假定) 。 第一节 运输问题 凌晨: 凌晨: Oi =Dj

凌晨: 第一节运输问题 运输问题及其常规解法 3、模型(运输问题的LP 建模一般原则:为每一弧指定一个变量,为每一结点指定 个约束式 1)决策变量 从O1到D的运输量 2)o.f Min ∑∑C 3)约束供方—-“≤”需方

Ling Xueling 一、运输问题及其常规解法 3 、模型 ( 运输问题的 L.P.) 建模一般原则: 为每一弧指定一个变量, 为每一结点指定一 个约束式 1）决策变量 xij －－从 Oi 到 Dj 的运输量 2）o.f. Min 3）约束 供方－－“” 需方－－“＝” 。 第一节 运输问题 凌晨: 凌晨:  ij i j c x