运筹学电子教案lp运输

1、1 商店 1 2 3 需求量（件/周） 50 60 30 工厂 1 2 3 供应量（件/周） 50 70 20 运输问题的一般描述模型的一般形式 引例 这里有三家工厂，都将产品运往三个不同的商店（见下图）。每这里有三家工厂，都将产品运往三个不同的商店（见下图）。每 个工厂以产品件数表示出每周生产能力见下表个工厂以产品件数表示出每周生产能力见下表1 1。每家商店平均需求量。每家商店平均需求量 见下表2。 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 工厂1 工厂3 工厂2 商店1 商店3 商店2 表1 表2 2 但是，由于运货距离不同，各个工厂运

2、往各商店的货物的运输费 用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件 产品到哪家商店。 能否列出线性最优化模型？ 决策存在什么样的约束条件？ 模型评价涉及什么样的准则？ 有那些决策变量？ 线性规划Linear Programming（LP） 特殊线性规划运输问题 由工厂 每件产品运往各商店的费用（元） 1 2 3 1 3 2 3 2 10 5 8 3 1 3 10 3 模型建立 决策变量有待确定的是从每家工厂有待确定的是从每家工厂i i（i=1i=1，2 2，3 3）运输多少件产）运输多少件产 品到每家商店j j（j=1j=1，2 2，3 3）去。因此，方便的办法是用双下标来表

3、）去。因此，方便的办法是用双下标来表 示决策变量即Xij。 目标函数利用运输费用表中的数据，我们希望其值为最小的是： Min Z =Min Z =由工厂1 1运出产品的总费用运出产品的总费用- 3X11+ 2X12+ 3X13 + +由工厂2 2运出产品的总费用-10X21+ 5X22+ 8X23 + +由工厂3 3运出产品的总费用-X31+ 3X32+10X33 即：Min Z = Min Z = 3X11+ 2X12+ 3X13 + 10X21+ 5X22+ 8X23+ X31+ 3X32+10X33 约束条件需要把决策变量的约束条件当作方案生成源。需要把决策变量的约束条件当作方案生成源。

4、 对工厂1 1必须有X11+X12+X1350（对工厂1 1的供应约束） 对工厂2必须有X21+X22+X2370（对工厂2的供应约束） 对工厂3 3必须有X31+X32+X3320（对工厂3 3的供应约束） 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 4 对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的 产品总数应等于每周的需求量。 对商店1必须有X11+X21+X31=50 对商店2必须有X12+X22+X32=60 对商店3必须有X13+X23+X33=30 于是，用于解此问题的线性最优化模型是： Min Z = 3X11+ 2

5、X12+ 3X13 + 10X21+ 5X22+ 8X23+ X31+ 3X32+10X33 X11+X12+X1350 X21+X22+X2370 X31+X32+X3320 X11+ X21+ X31= 50 Xij0 且为整数 X12+ X22+ X32= 60 i=1，2，3 X13+ X23+ X33= 30 j=1，2，3 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 s. t. 5 运输问题模型分析 一般形式： 某种物资有m m个产地A Ai，产量（供应量）是a ai（i=1，2 2，m m），）， 有有n n个销地B Bj，销量

6、（需求量）是b bj（j=1，2 2，n n）。从运到的单）。从运到的单 位运价为cij（i=1，2，m；j=1，2，n），如何安排运输可使 总运费最小？ 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 产大于销 ? a ai ? b bj Min Z= ?CijXij ? x xija ai（i=1，2，m） ? x xij=b bj（j=1，2，n） xij0 （i=1，2，m； j=1，2，n） 销大于产 ? a ai ? b bj Min Z= ?CijXij ? x xij=a ai（i=1，2，m） ? x xijb bj（j=1，2

7、，n） xij0 （i=1，2，m； j=1，2，n） 6 产销平衡?ai = ?bj 注意！这种模型具有特殊的形式：所有决策变量的约束条件，其系数 均等于1；而且，每个决策变量仅出现于两个约束条件之中。这些特 性表明，解这类线性最优化模型的单纯形法中有一种特殊的方法可用 来解这个问题这是解这类模型的特别有效的一种方法。而且上述 特性还表明，可以给这类线性最优化模型以一种象网络模型式的形象 化的说明。 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 Min Z= ? ?CijXij ? xij=ai（i=1，2，m） ? xij=bj（j=1，2

8、，n） xij0 （i=1，2，m；j=1，2，n） j j i i 7 运输问题的求解方法 求解此问题的一个十分有效的方法是表上作业法： （1）产销平衡问题总产量等于总销量的运输问题 a、建立作业表 b、确定初始调运方案（最小元素法） c、现行方案的最优性检验（位势法） d、现行方案的调整（闭回路法） 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 8 例1 甲（B1）、乙（B2）、丙（B3）、丁（B4）三城市所需煤炭由三 个煤矿A1、A2、A3供应，有关数据如表，表中数字为单位运费（万元 万吨），请制订使总运费最小的调运计划。 产地 A1 A

9、 2 A 3 销量 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） 特殊线性规划特殊线性规划运输问题运输问题 9 a、建立平衡调运作业表 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 产 量 销量 3322 5 2 3 3运价运价 Xij 调运量，当其 为非基变量时 不予填写 ? ij 检验数，当 其为基变量 的检验数时 不予填写 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 10 b、确定初始调运方案（最小

10、元素法） 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） 特殊线性规划特殊线性规划运输问题运输问题 11 c、现行方案的最优性检验（位势法） 1022 2 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 由? ij=Cij- （Ui+Vj） 计算位势Ui，Vj， 因对基变量而言有 ? ij=0 ，即

11、Cij-（Ui+Vj）= 0 令U1=0 0 3764 -1 -4 再由?ij=Cij-（Ui+ Vj）计算非基变 量的检验数?ij -2-2-1 565 当存在非基变量的检验数 ? kl 0 且? kl =min ? ij时，令 Xkl 进基。从表中知可选X23进基。 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 12 d、现行方案的调整（闭回路法） 1022 2 3 3764 2432 4385 A1 A2 A3 B1 B2 B3 B4 Ui Vj 0 3764 -1 -4 -2-2-1 565 调整量? = 从进基 变量X23出发的闭回

12、路中偶拐点上基变 量的最小值=2。 调整步骤为闭回路 上奇拐点变量的值 + ? 偶拐点变量的值 -? 2 3 0 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 13 d、现行方案的调整（闭回路法） 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、殊线性规划特殊线性规划运输问题运输问题 14 d、现行方案的调整（闭回路法） 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） 特殊线性规划特殊线性规划运输问题运输问题 15 （2）产销不平

14、衡问题总产量小于总销量的运输问题总产量小于总销量的运输问题 例2 有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区 使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方 案。 A 1 A 2 A 3 最低需求（万吨） 最高需求（万吨） 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） 特殊线性规划特殊线性规划运输问题运输问题 化肥厂 需求地区 运价：万元/万吨 16 分析： 这是一个产销不平衡的运输问题，总产

15、量为这是一个产销不平衡的运输问题，总产量为160万吨，四个地区 的最低需求为110万吨，最高需求为无限。根据现有产量，地区万吨，最高需求为无限。根据现有产量，地区B4每年每年 最多能分配到60万吨，这样最高总需求为万吨，这样最高总需求为210万吨，大于产量。为了 求得平衡，在产销平衡表中增加一个虚拟的化肥厂D ，其年产量为50 万吨。由于各个地区的需要量包含两部分，如地区万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是万吨是 最低需求，故不能由虚拟的化肥厂最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为供给，令其相应的运输价格为M （任意大正数），而另一部分20万吨满

16、足或不满足均可，因此可以由万吨满足或不满足均可，因此可以由 虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生的运输）。 对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可 以建立这个问题的产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 17 例2 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 A1 A2 A3 D B 1 B 1 B 2 B 3 B4B 4 产量 销量 1717 1414131915

17、15 19192023MM M0M0M0 50 60 50 50 302070301050 16162213 20 30 20 30 50 20 20 40 30 10 100 30 20 20 18 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 A1 A2 A3 D B1B 1 B2B3B4 B 4 Ui Vj 13 50 14 30 13 20 19 0 15 10 23M 00 0 13 0 141915 4 -4+M 4-M -4+M 220-M3221-M 18-M19-M 119-M3M-19 2M-182M-17M-2

18、32M-19 16221717 1415 191920M MM0M 16 0 3020 2030 19 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 A1 A2 A3 D B1B 1 B2B3B4 B 4 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 M

19、M0M 16 20 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 A1 A2 A3 D B1B 1 B2B3B4 B 4 Ui Vj 1613 50 221717 1414 20 13 20 1915 10 15 19192023 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 21 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划

20、运输问题运输问题 A1 A2 A3 D B1B 1 B2B3B4 B 4 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 22 产销平衡表 线性规划Linear Programming（LP） 特殊线性规划特殊线性规划运输问题运输问题 A1 A2 A3 D B1B 1 B2B3B4 B 4 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