运筹学电子教案-LP运输.ppt

商店 1 2 3 需求量（件/周） 50 60 30 工厂 1 2 3 供应量（件/周） 50 70 20 u 运输问题的一般描述 模型的一般形式 u引例 u 这里有三家工厂，都将产品运往三个不同的商店（见下图）。每 个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量 见下表2。 线性规划Linear Programming（LP ） 特殊线性规划运输问题 工厂1 工厂3 工厂2 商店1 商店3 商店2 表1 表2 1 u 但是，由于运货距离不同，各个工厂运往各商店的货物的运输费 用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件 产品到哪家商店。 u能否列出线性最优化模型？ u决策存在什么样的约束条件？ u模型评价涉及什么样的准则？ u有那些决策变量？ 线性规划Linear Programming（LP ） 特殊线性规划运输问题 由工厂 每件产品运往各商店的费用（元） 1 2 3 1 3 2 3 2 10 5 8 3 1 3 10 2 u模型建立 u决策变量有待确定的是从每家工厂i（i=1，2，3）运输多少件产 品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表 示决策变量即 Xij。 u目标函数利用运输费用表中的数据，我们希望其值为最小的是： u Min Z =由工厂1运出产品的总费用- 3X11+ 2X12+ 3X13 u +由工厂2运出产品的总费用-10X21+ 5X22+ 8X23 u +由工厂3运出产品的总费用- X31+ 3X32+10X33 u即：Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 u约束条件需要把决策变量的约束条件当作方案生成源。 u 对工厂1必须有 X11+X12+X13 50 （对工厂1的供应约束） u 对工厂2必须有 X21+X22+X23 70 （对工厂2的供应约束） u 对工厂3必须有 X31+X32+X33 20 （对工厂3的供应约束） 线性规划Linear Programming（LP ） 特殊线性规划运输问题 3 u对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的 产品总数应等于每周的需求量。 u 对商店1必须有 X11+X21+X31 =50 u 对商店2必须有 X12+X22+X32 =60 u 对商店3必须有 X13+X23+X33 =30 u于是，用于解此问题的线性最优化模型是： uMin Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23 + X31+ 3X32+10X33 u X11+X12+X13 50 u X21+X22+X23 70 u X31+X32+X33 20 u X11+ X21+ X31 = 50 Xij0 且为整数 u X12+ X22+ X32 = 60 i=1，2，3 u X13+ X23+ X33 = 30 j=1，2，3 线性规划Linear Programming（LP ） 特殊线性规划运输问题 s. t. 4 u运输问题模型分析 u一般形式： u 某种物资有m个产地Ai，产量（供应量）是ai（i=1，2，m） ，有n个销地Bj，销量（需求量）是bj（j=1，2，n）。从运到的单 位运价为cij（i=1，2，m；j=1，2，n），如何安排运输可使 总运费最小？ 线性规划Linear Programming（LP ） 特殊线性规划运输问题 产大于销 ai bj Min Z= CijXij xijai （i=1，2，m） xij =bj （j=1，2，n） xij0 （i=1，2，m； j=1，2，n） 销大于产 ai bj Min Z= CijXij xij=ai （i=1，2，m） xijbj （j=1，2，n） xij0 （i=1，2，m； j=1，2，n） 5 u产销平衡 ai = bj u注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数 均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特性 表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用来 解这个问题这是解这类模型的特别有效的一种方法。而且上述特 性还表明，可以给这类线性最优化模型以一种象网络模型式的形象化 的说明。 线性规划Linear Programming（LP ） 特殊线性规划运输问题 Min Z= CijXij xij =ai （i=1，2，m） xij =bj （j=1，2，n） xij0 （i=1，2，m；j=1，2，n） j j i i 6 u运输问题的求解方法 u求解此问题的一个十分有效的方法是表上作业法： u（1）产销平衡问题总产量等于总销量的运输问题 u a、建立作业表 u b、确定初始调运方案（最小元素法） u c、现行方案的最优性检验（位势法） u d、现行方案的调整（闭回路法） 线性规划Linear Programming（LP ） 特殊线性规划运输问题 7 u例1 u 甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三 个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元 万吨），请制订使总运费最小的调运计划。 产地 A1 A2 A3 销量 B1 B2 B3 B4 产量 3 7 6 4 5 2 4 3 2 2 4 3 8 5 3 3 3 2 2 线性规划Linear Programming（LP ） 特殊线性规划运输问题 8 ua、建立平衡调运作业表 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 产量 销量 3322 5 2 3 3运价 Xij 调运量，当其 为非基变量时 不予填写 ij 检验数，当 其为基变量 的检验数时 不予填写 线性规划Linear Programming（LP ） 特殊线性规划运输问题 9 ub、确定初始调运方案（最小元素法） 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 产量 销量 3322 5 2 3 3运价 Xij 调运量，当其 为非基变量时 不予填写 ij 检验数，当 其为基变量 的检验数时 不予填写 2 1 1 4 3 02 2 2 线性规划Linear Programming（LP ） 特殊线性规划运输问题 10 uc、现行方案的最优性检验（位势法） 1022 2 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 由ij=Cij-（Ui+Vj） 计算位势Ui ， Vj ， 因对基变量而言有 ij=0，即 Cij-（Ui+Vj） = 0 令U1=0 0 3764 -1 -4 再由ij=Cij-（Ui+ Vj）计算非基变 量的检验数ij -2-2-1 565 当存在非基变量的检验数kl 0 且kl =minij时，令Xkl 进基。从表中知可选X23进基。 线性规划Linear Programming（LP ） 特殊线性规划运输问题 11 ud、现行方案的调整（闭回路法） 1022 2 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 0 3764 -1 -4 -2-2-1 565 调整量 = 从进基 变量X23出发的闭回 路中偶拐点上基变 量的最小值=2。 调整步骤为闭回路 上奇拐点变量的值 + 偶拐点变量的值 - 2 3 0 线性规划Linear Programming（LP ） 特殊线性规划运输问题 12 ud、现行方案的调整（闭回路法） 1022 22 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 重复步骤C、检验 当前调运方案（基 可行解）的最优性 如非最优方案，则 擦去Ui、Vj和ij然 后重新计算。 3 0 0 37 -1 44 -4 2 -2-1 585 0 线性规划Linear Programming（LP ） 特殊线性规划运输问题 13 ud、现行方案的调整（闭回路法） 1022 02 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 重复步骤C、检验 当前调运方案（基 可行解）的最优性 如非最优方案，则 擦去Ui、Vj和ij然 后重新计算。 3 0 374 -3 -4 6 0 21 565 当所有非基变量的 检验数均非负时， 则当前调运方案即 为最优方案，如表 此时最小总运费 min Z =9+0+8+0+ 6+9 = 32 线性规划Linear Programming（LP ） 特殊线性规划运输问题 14 u（2）产销不平衡问题总产量小于总销量的运输问题 u例2有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使 用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案 。 A1 A2 A3 最低需求（万吨） 最高需求（万吨） B1 B2 B3 B4 产量（万吨） 16 13 22 17 50 14 13 19 15 60 19 20 23 - 50 30 70 0 10 50 70 30 不限 线性规划Linear Programming（LP ） 特殊线性规划运输问题 化肥厂 需求地区 运价：万元/万吨 15 u分析： u 这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的 最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最 多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得 平衡，在产销平衡表中增加一个虚拟的化肥厂D ，其年产量为50万吨 。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低 需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意 大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的 化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。对凡 是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建 立这个问题的产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 16 u例2 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 产量 销量 1717 141413191515 19192023MM M0M0M0 50 60 50 50 302070301050 16162213 20 30 20 30 50 20 20 40 30 10 100 30 20 20 17 u 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 Ui Vj 13 50 14 30 13 20 19 0 15 10 23 30 M 20 0 20 0 30 0 13 0 141915 4 -4+M 4-M -4+M 220-M3221-M 18-M19-M 119-M3M-19 2M-182M-17M-232M-19 16221717 1415 191920M MM0M 16 0 3020 2030 18 u 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 Ui Vj 50 14 30 14 0 13 20 15 10 23 30 M 20 0 20 0 30 0 0 -14+M -14 14141337-M1514 22-15+M23 -18+M1 19-M19-M21-M-1 M1+M-23+M-1+M 1020 0 50 20 1613221717 1915 191920M MM0M 16 19 u 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 Ui Vj 1613 50 221717 14 10 14 20 13 20 1915 10 15 19 20 192023 30 MM 0 M0M0M0 50 16 0 0 5 5-M 1414131815-5+M 224222-M 120-M 02-20+M -19+2M-19+M-18+M-23+M-20+2M 10 20 0 20 u 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 Ui Vj 1613 50 221717 14 10 14 20 13 20 1915 10 15 0 19 20 192023 30 MM M0M0M0 50 16 0 0 6 0 141413171515 22522 2 -11-21+M-21+M -14+M-14-13+M-17-15+M 10 10 3020 40 21 u 产销平衡表 线性规划Linear Programming（LP ） 特殊线性规划运输问题 A1 A2 A3 D B1 B1 B2 B3 B4 B4 Ui Vj 13 50 14 20 13 20 15 10 15 10 19 30 23 20 0 10 0 40 0 0 8 -15 111413151515 52722 34 -3-1M-23M-23 M+41M+2M 30 0 3020 20 16221717 1419 1920MM M0MM 16 22 u 产销平