《运筹学课件 第三节运输问题的进一步讨论.ppt》由会员分享，可在线阅读，更多相关《运筹学课件 第三节运输问题的进一步讨论.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、运筹学教程第三节 运输问题的进一步讨论一、产销不平衡的运输问题供大于求供不应求增加虚拟销地增加虚拟销地 增加虚拟产地增加虚拟产地 产销平衡的运输问题对应的运价？转化运筹学教程各地之间的运价在原问题运价表基础上进行扩展：增加虚拟销地，增加虚拟销地，就地贮存的物品的不经过运输，运价等于零；增加虚拟产地，增加虚拟产地，各个销地所欠缺的物品，其运价等于零；考虑转运，考虑转运，从一地运往自身的单位运价记为零或为负；不存在运输线路的则记为M（一个足够大的正数）；运筹学教程供应大于需求：数学模型 供应大于需求：数学模型增加一个假想的目的地 增加一个假想的目的地运筹学教程B1B2BnBn+1(贮存)产量A1x
2、11x12x1nX 1,n+1 a1A2x21x22x2nX 2,n+1 a2:Amxm1xm2Xmn X m,n+1 am销量b1 b2bn产地销地c11c1nc2n000cmncm2cm1c22c21c12运筹学教程二、有转运的运输问题特 点 是 所 调 运 的 物 资 不 是 由 产 地 直 接 运 送到销地，而是经过若干中转站送达。求 解 思 路：转 化 成 一 个 等 价 的 产 销 平 衡 运输 问 题，再 用 表 上 作 业 法 求 出 最 优 调 运 方案。运筹学教程第 一 步，将 产 地、转 运 点、销 地 重 新 编 排，转运点既作为产地又作为销地；第 二 步，各 地 之
3、间 的 运 价 在 原 问 题 运 价 表基 础 上 进 行 扩 展：从 一 地 运 往 自 身 的 单 位运 价 记 为 零 或 为 负，不 存 在 运 输 线 路 的 则记为M（一个足够大的正数）；运筹学教程第 三 步，由 于 经 过 转 运 点 的 物 资 量 既是 该 点 作 为 销 地 的 需 求 量，又 是 该 点作 为 产 地 时 的 供 应 量，但 事 先 又 无 法获 取 该 数 量 的 确 切 值，因 此 通 常 将 调运总量作为该数值的上界。对于产地和销地也作类似的处理。运筹学教程 例1:某 公 司 有 A1、A2 两 个 分 厂 生 产 某 种 产品，分 别 供 应 B
4、1、B2、B3 三 个 地 区 的 销 售公 司 销 售。假 设 两 个 分 厂 的 产 品 质 量 相 同，假 设 有 两 个 中 转 站 T1、T2，并 且 物 资 的 运 输允 许 在 各 产 地、各 销 地 及 各 转 运 站 之 间，即可 以 在 A1、A2、B1、B2、B3、T1、T2 之 间 相互 转 运。有 关 数 据 如 下 表 所 示，试 求 总 费 用为最少的调运方案。运筹学教程产 地 中转站 销 地产量A1A2T1T2B1B2B3产地A1 1 2 1 3 11 3 7A21 3 5 1 9 2 9中转T12 3 1 2 8 4T21 5 1 4 5 2销地B13 1 2
5、 4 1 4B211 9 8 5 1 2B33 2 4 2 4 2 需求量4 7 5 产地、销地及中转站的有关数据、运价（元/kg）发送接受运筹学教程 解：从 表 可 以 看 出，从 A1 到 B2 直 接 运 费 单价 为 11 元/kg；但 从 A1 经 A2 到 B2，运 价 为 1+9=10元/kg；而 从 A1 经 T2 到 B2 只 需 l+5=6元/kg；若 从A1 到 A2 再 经 B1 到 B2 仅 仅需 l+1+1=3元/kg。可 见 转 运 问 题 比 一 般 运输 问 题 复 杂。现 在 我 们 把 此 转 运 问 题 化 成 一般运输问题，要做如下处理：运筹学教程 由
6、 于 问 题 中 的 所 有 产 地、中 转 站、销 地 都可 以 看 成 产 地，也 可 以 看 成 销 地，因 此 整 个问 题 可 以 看 成 一 个 有7个 产 地 有7个 销 地 的 扩大的运输问题；对 扩 大 了 的 运 输 问 题 建 立 运 价 表，将 表 中不可能的运输方案用任意大的正数M 代替；所 有 中 转 站 的 产 量 等 于 销 量，也 即 流 入 量等于流出量。运筹学教程每 个 中 转 站 的 转 运 量 不 会 超 过 16 kg，可 以 规 定 T1，T2 的产量和销量均为 16 kg。由于实际的转运量：这 里si表 示i 点 的 流 出 量，dj表 示j 点
7、 的 流 入 量，对中转点来说，因此si=dj=16。运筹学教程 这 样 可 以 在 每 个 约 束 条 件 中 增 加 一 个 松 弛 变量xii，xii 相 当 于 一 个 虚 构 的 中 转 站，其 意 义就 是 自 己 运 给 自 己。(16-xii)就 是 每 个 中 转站的实际转运量，xii 的对应运价cii=0；扩 大 了 的 运 输 问 题 中 原 来 的 产 地 与 销 地 由 于也 具 有 转 运 作 用，所 以 同 样 在 原 来 的 产 量 与 销量 的 数 字 上 加 上16 kg，即 两 个 分 厂 的 产 量 改 为23、25 kg，销量均为16 kg；三个销地运
8、筹学教程的 每 天 销 量 改 为20、23、21 kg，产 量 均 为16 kg，同时引进xii 为松弛变量。于是得到带有中转运输的产销平衡运输表运筹学教程产 地 中转站 销 地产量A1A2T1T2B1B2B3产地A1 0 1 2 1 3 11 3 23A21 0 3 5 1 9 2 25中转T12 3 0 1 2 8 4 16T21 5 1 0 4 5 2 16销地B13 1 2 4 0 1 4 16B211 9 8 5 1 0 2 16B33 2 4 2 4 2 0 16需求量16 16 16 16 20 23 21128带有中转站的产销平衡运输表 发送接受产 地 中转站 销 地产量A1
9、A2T1T2B1B2B3产地A1 1 2 1 3 11 3 7A21 3 5 1 9 2 9中转T12 3 1 2 8 4T21 5 1 4 5 2销地B13 1 2 4 1 4B211 9 8 5 1 2B33 2 4 2 4 2 需求量4 7 5运筹学教程 使用生产B1 B2 B3生产量A1 2 4 3 6a1 11A2 1 5 6 a2=7A3 3 2 4 a34使用量10 4 6例 例2 2：产地：产地A1 A1 至少发出 至少发出6 6 个单位物品，最多能生产 个单位物品，最多能生产11 11 单位物品；单位物品；A2 A2 必须发出 必须发出7 7 个单位物品；个单位物品；A3 A
10、3 至少发出 至少发出4 4 个单位物品；确定最 个单位物品；确定最优方案。优方案。运筹学教程 使用生产B1 B2 B3 B4（虚拟）生产量A1 2 4 3 M 6（必须发出的）A1 2 4 3 0 5A2 1 5 6 M 7（必须发出的）A3 3 2 4 M 4（必须发出的）A3 3 2 4 0 3使用量 10 4 6 5解：当A1的产量a1=6（min)，A1,A2的产量之和=13，总需求量为20，所以在产销平衡的情况下 A3的产量最大为7；如果A1,A3的产量均取最大11，7，则总产量大于总需求20，此时应增加一个虚销地B4,需求量为5。运筹学教程例3：某公司承担4条航线运输任务，已知（
11、1）各条航线的起点和终点以及每天的航班数；各个城市之间的航行时间；每次装船、卸船时间均为1天；问题：公司至少需要配备多少条船才能满足需要？航线 起点城市 终点城市 每天航班数量1234EBADDCFB3211运筹学教程从 至A B C D E FABCDEF0121477103138823015551413150172078517037852030运筹学教程航线 装船（天）卸船（天）航行（天）小记（天）航班数量 所需船数12341111111117371319591532115710915所需要船只共91条船。城市 A B C D E F每天到达每天需要余缺数01-112-120231203-
12、3101各个港口之间调度。每天到达某一个港口的船只数量与它所需要发出船 各个港口之间调度。每天到达某一个港口的船只数量与它所需要发出船只数量不相等而产生的。将多余船只调往需要的港口，应采用合理的运 只数量不相等而产生的。将多余船只调往需要的港口，应采用合理的运输方案，单位运价为一对港口城市之间的航行时间。输方案，单位运价为一对港口城市之间的航行时间。运筹学教程 至由A B E多余船只C 2 3 5 2D 14 13 17 2F 7 8 3 1缺少船只1 1 35用 用 表上作业方法求解运输问题，得到最优解 表上作业方法求解运输问题，得到最优解按照这两 按照这两个方案调 个方案调运船只，运船只，
13、其目标函 其目标函数等于 数等于40 40。，说明各，说明各个港口之 个港口之间调度所 间调度所需要船只 需要船只至少 至少40 40 艘。艘。所以，总的 所以，总的需求：需求：91+40=131 91+40=131运筹学教程 有 有m m 个产地 个产地A A1 1,A,A2 2,A,Am m和 和n n 个目的地 个目的地B B1 1,B,B2 2,B,B3 3,B Bn n都 都可以作为中间转运站使用，因此，发送和接受物品的地 可以作为中间转运站使用，因此，发送和接受物品的地点有 点有m+n m+n 个。个。a ai i:第 第i i 个产地的产量 个产地的产量b bj j:第 第j j
14、 个目的地的需求量 个目的地的需求量x xij ij:第 第i i 个产地运到第 个产地运到第j j 个目的地数量 个目的地数量C Cij ij：第：第i i 个产地运到第 个产地运到第j j 个目的地的单位运价 个目的地的单位运价C Ci i：第：第i i 个 个 地点转运单位物品的费用 地点转运单位物品的费用t ti i:第 第i i 个地点转运物品的数量 个地点转运物品的数量产地与目的地统一编号，产地在前，目的地在后 产地与目的地统一编号，产地在前，目的地在后运筹学教程4个约束条件两边均加上Q;令xii=Q-ti,xjj=Q-tj运筹学教程运筹学教程xij0(i,j=1,2,m+n)说明
15、:当i=j 时,所有的cij=-ci运筹学教程产地 销地 发送量1.m m+1.m+n产地1.mx11.x1m.Xm1.xmmX1,m+1.x1,m+n.Xm,m+1xm,m+nQ+a1Q+am目的地m+1.m+nxm+1,1xm+1,m.Xm+n,1xm+n,mXm+1,m+1.xm+1,m+n.Xm+n,m+1.xm+n,m+nQQ接受量Q QQ+b m+1.Q+b m+n发送接受运筹学教程 接受发送产地 销地 发送量1.m m+1.m+n产地1.m-c1.c1m.cm1.-cmc1,m+1.c1,m+n.cm,m+1cm,m+nQ+a1Q+am目的地m+1.m+ncm+1,1cm+1,m
16、.cm+n,1 cm+n,m-cm+1.cm+1,m+n.cm+n,m+1.-cm+nQQ接受量Q QQ+b m+1.Q+b m+n运筹学教程12345104020305225643543153运输系统，2个产地1，2；一个中间转运站3；2个目的地4，5；产地的产量a1=10,a2=40,a3=a4=a5=0;目的地接受量b1=b2=b3=0,b4=30,b5=20例4：运筹学教程 接受发送产地 转运 销地 发送量1 2 3 4 5产 地1-4 5 3 2 M 602 5-1 2 M 4 90转 运3 3 2-3 5 5 50销 地4 2 M 5-3 6 505 M 4 5 6-5 50接受量
17、50 50 50 80 70运筹学教程 接受发送产地 转运 销地 发送量1 2 3 4 5产 地1 50 10 602 50 20 20 90转 运3 50 0 50销 地4 50 505 50 50接受量50 50 50 80 70用最小元素法求解初始运输方案运筹学教程 接受发送产地 转运 销地 发送量1 2 3 4 5产 地1 50 10 602 50 20 20 90转 运3 30 20 50销 地4 50 505 50 50接受量50 50 50 80 70经过 经过2 2 次迭代得到最优解，其运输方案：由 次迭代得到最优解，其运输方案：由1 1 地运输 地运输10 10 单位物品到 单位物品到4 4 地；由 地；由2 2 地 地运输 运输20 20 单位物品到 单位物品到5 5 地；由 地；由2 2 地运输 地运输20 20 单位物品到 单位物品到3 3 地，再由 地，再由3 3 地转到 地转到4 4 地；地；Z=C14x14+c25x25+c23x23+c3x34+c34x34=2X10+4X20+2X20+3X20+5X20=300运筹学教程小结:产 销 不 平 衡 的 运 输 问 题 和 有 转 运 的 运输问题。