《运筹学电子教案-LP运输.ppt》由会员分享，可在线阅读，更多相关《运筹学电子教案-LP运输.ppt（25页珍藏版）》请在三一办公上搜索。
1、1,商店 1 2 3 需求量（件/周）50 60 30,工厂 1 2 3 供应量（件/周）50 70 20,运输问题的一般描述 模型的一般形式引例 这里有三家工厂，都将产品运往三个不同的商店（见下图）。每个工厂以产品件数表示出每周生产能力见下表1。每家商店平均需求量见下表2。,线性规划Linear Programming（LP）特殊线性规划运输问题,工厂1,工厂3,工厂2,商店1,商店3,商店2,表1,表2,2,但是，由于运货距离不同，各个工厂运往各商店的货物的运输费用是不同的。费用如下表，我们的问题是确定由哪家工厂运送多少件产品到哪家商店。能否列出线性最优化模型？决策存在什么样的约束条件？模
2、型评价涉及什么样的准则？有那些决策变量？,线性规划Linear Programming（LP）特殊线性规划运输问题,由工厂,每件产品运往各商店的费用（元）1 2 3,1 3 2 32 10 5 83 1 3 10,3,模型建立决策变量有待确定的是从每家工厂i（i=1，2，3）运输多少件产品到每家商店j（j=1，2，3）去。因此，方便的办法是用双下标来表示决策变量即 Xij。目标函数利用运输费用表中的数据，我们希望其值为最小的是：Min Z=由工厂1运出产品的总费用-3X11+2X12+3X13+由工厂2运出产品的总费用-10X21+5X22+8X23+由工厂3运出产品的总费用-X31+3X32
3、+10X33即：Min Z=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33约束条件需要把决策变量的约束条件当作方案生成源。对工厂1必须有 X11+X12+X13 50（对工厂1的供应约束）对工厂2必须有 X21+X22+X23 70（对工厂2的供应约束）对工厂3必须有 X31+X32+X33 20（对工厂3的供应约束）,线性规划Linear Programming（LP）特殊线性规划运输问题,4,对每家商店来说，也需要一个逻辑关系式来说明每个星期运到的产品总数应等于每周的需求量。对商店1必须有 X11+X21+X31=50 对商店2必须有 X12+X
4、22+X32=60 对商店3必须有 X13+X23+X33=30于是，用于解此问题的线性最优化模型是：Min Z=3X11+2X12+3X13+10X21+5X22+8X23+X31+3X32+10X33 X11+X12+X13 50 X21+X22+X23 70 X31+X32+X33 20 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个产地Ai，产量（供应量）是ai（i
5、=1，2，m），有n个销地Bj，销量（需求量）是bj（j=1，2，n）。从运到的单位运价为cij（i=1，2，m；j=1，2，n），如何安排运输可使总运费最小？,线性规划Linear Programming（LP）特殊线性规划运输问题,产大于销 ai bjMin Z=CijXij xijai（i=1，2，m）xij=bj（j=1，2，n）xij0（i=1，2，m；j=1，2，n）,销大于产 ai bjMin Z=CijXij xij=ai（i=1，2，m）xijbj（j=1，2，n）xij0（i=1，2，m；j=1，2，n）,6,产销平衡 ai=bj注意！这种模型具有特殊的形式：所有决策变量的
6、约束条件，其系数均等于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,7,运输问题的求解方法求解此问题的一个十分有效的方法是表上作业法：（1）产销平衡问题总产量等于总销量的运输问题 a、
7、建立作业表 b、确定初始调运方案（最小元素法）c、现行方案的最优性检验（位势法）d、现行方案的调整（闭回路法）,线性规划Linear Programming（LP）特殊线性规划运输问题,8,例1 甲（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）特殊线性规划运输问题,9,a、建立平衡调运作业表
8、,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,B1 B2 B3 B4 产量,销量,3,3,2,2,5,2,3,3,运价,Xij,调运量，当其为非基变量时不予填写,ij,检验数，当其为基变量的检验数时不予填写,线性规划Linear Programming（LP）特殊线性规划运输问题,10,b、确定初始调运方案（最小元素法）,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,B1 B2 B3 B4 产量,销量,3,3,2,2,5,2,3,3,运价,Xij,调运量，当其为非基变量时不予填写,ij,检验数，当其为基变量的检验数时不予填写,2,1,1,4,3,0,2,2,2
9、,线性规划Linear Programming（LP）特殊线性规划运输问题,11,c、现行方案的最优性检验（位势法）,1,0,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,B1 B2 B3 B4 Ui,Vj,由ij=Cij-（Ui+Vj）计算位势Ui，Vj，因对基变量而言有ij=0，即Cij-（Ui+Vj）=0令U1=0,0,3,7,6,4,-1,-4,再由ij=Cij-（Ui+Vj）计算非基变量的检验数ij,-2,-2,-1,5,6,5,当存在非基变量的检验数kl 0 且kl=minij时，令Xkl 进基。从表中知可选X23进基。,线性规划Linear Pro
10、gramming（LP）特殊线性规划运输问题,12,d、现行方案的调整（闭回路法）,1,0,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,B1 B2 B3 B4 Ui,Vj,0,3,7,6,4,-1,-4,-2,-2,-1,5,6,5,调整量=从进基变量X23出发的闭回路中偶拐点上基变量的最小值=2。调整步骤为闭回路上奇拐点变量的值+偶拐点变量的值-,2,3,0,线性规划Linear Programming（LP）特殊线性规划运输问题,13,d、现行方案的调整（闭回路法）,1,0,2,2,2,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,
11、B1 B2 B3 B4 Ui,Vj,重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和ij然后重新计算。,3,0,0,3,7,-1,4,4,-4,2,-2,-1,5,8,5,0,线性规划Linear Programming（LP）特殊线性规划运输问题,14,d、现行方案的调整（闭回路法）,1,0,2,2,0,2,3,3,7,6,4,2,4,3,2,4,3,8,5,A1A2A3,B1 B2 B3 B4 Ui,Vj,重复步骤C、检验当前调运方案（基可行解）的最优性如非最优方案，则擦去Ui、Vj和ij然后重新计算。,3,0,3,7,4,-3,-4,6,0,2,1,5,6
12、,5,当所有非基变量的检验数均非负时，则当前调运方案即为最优方案，如表此时最小总运费min Z=9+0+8+0+6+9=32,线性规划Linear Programming（LP）特殊线性规划运输问题,15,（2）产销不平衡问题总产量小于总销量的运输问题例2有三个化肥厂供应四个地区的农用化肥。等量化肥在这些地区使用效果相同。相关数据如下表，试分析总运费最节省的化肥调运方案。,A1A2A3最低需求（万吨）最高需求（万吨）,B1 B2 B3 B4 产量（万吨）,16 13 22 17 50,14 13 19 15 60,19 20 23-50,30 70 0 1050 70 30 不限,线性规划Li
13、near Programming（LP）特殊线性规划运输问题,化肥厂,需求地区,运价：万元/万吨,16,分析：这是一个产销不平衡的运输问题，总产量为160万吨，四个地区的最低需求为110万吨，最高需求为无限。根据现有产量，地区B4每年最多能分配到60万吨，这样最高总需求为210万吨，大于产量。为了求得平衡，在产销平衡表中增加一个虚拟的化肥厂D，其年产量为50万吨。由于各个地区的需要量包含两部分，如地区B1，其中30万吨是最低需求，故不能由虚拟的化肥厂D供给，令其相应的运输价格为M（任意大正数），而另一部分20万吨满足或不满足均可，因此可以由虚拟的化肥厂D供给，并令其相应的运输价格为0（没有发生
14、的运输）。对凡是需求分两种情况的地区，实际上可按照两个地区看待。这样可以建立这个问题的产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,17,例2 产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,B1 B1 B2 B3 B4 B4 产量,销量,17,17,14,14,13,19,15,15,19,19,20,23,M,M,M,0,M,0,M,0,50,60,50,50,30,20,70,30,10,50,16,16,22,13,20,30,20,30,50,20,20,40,30,10,10,0,30,2
15、0,20,18,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,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,14,19,15,4,-4+M,4-M,-4+M,2,20-M,3,2,21-M,18-M,19-M,1,19-M,3,M-19,2M-18,2M-17,M-23,2M-19,16,22,17,17,14,15,19,19,20,M,M,M,0,M,16,0,30,20,20,30,19,产销平衡表,线性规划Linea
16、r Programming（LP）特殊线性规划运输问题,A1A2A3D,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,14,14,13,37-M,15,14,2,2,-15+M,2,3,-18+M,1,19-M,19-M,21-M,-1,M,1+M,-23+M,-1+M,10,20,0,50,20,16,13,22,17,17,19,15,19,19,20,M,M,M,0,M,16,20,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题
17、,A1A2A3D,B1 B1 B2 B3 B4 B4 Ui,Vj,16,13,50,22,17,17,14,10,14,20,13,20,19,15,10,15,19,20,19,20,23,30,M,M,0,M,0,M,0,M,0,50,16,0,0,5,5-M,14,14,13,18,15,-5+M,2,2,4,2,22-M,1,20-M,0,2,-20+M,-19+2M,-19+M,-18+M,-23+M,-20+2M,10,20,0,21,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,B1 B1 B2 B3 B4 B4 Ui,Vj
18、,16,13,50,22,17,17,14,10,14,20,13,20,19,15,10,15,0,19,20,19,20,23,30,M,M,M,0,M,0,M,0,50,16,0,0,6,0,14,14,13,17,15,15,2,2,5,2,2,2,-1,1,-21+M,-21+M,-14+M,-14,-13+M,-17,-15+M,10,10,30,20,40,22,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,B1 B1 B2 B3 B4 B4 Ui,Vj,13,50,14,20,13,20,15,10,15,10,19,30
19、,23,20,0,10,0,40,0,0,8,-15,11,14,13,15,15,15,5,2,7,2,2,3,4,-3,-1,M-23,M-23,M+4,1,M+2,M,30,0,30,20,20,16,22,17,17,14,19,19,20,M,M,M,0,M,M,16,23,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,B1 B1 B2 B3 B4 B4 Ui,Vj,16,13,50,22,17,17,14,14,13,20,19,15,10,15,30,19,30,19,20,20,23,0,M,M,M,0,M,0,30,M,
20、0,20,16,0,0,8,-15,11,11,13,15,15,15,5,5,7,2,2,3,3,4,-1,M-23,M-23,M+4,4,M+2,M,20,30,30,20,0,24,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,B1 B1 B2 B3 B4 B4 Ui,Vj,13,50,13,20,15,10,15,30,19,30,19,20,20,0,0,30,0,20,0,0,7,-15,12,12,13,15,15,15,4,4,7,2,2,2,2,4,1,M-22,M-22,M+3,3,M+2,M,16,22,17,17,14,14,19,23,M,M,M,0,M,M,16,25,产销平衡表,线性规划Linear Programming（LP）特殊线性规划运输问题,A1A2A3D,16,13,50,22,17,17,14,14,13,20,19,15,10,15,30,19,30,19,20,20,0,23,M,M,M,0,M,0,30,M,0,20,50,60,50,50,30,20,70,30,10,50,16,B1 B1 B2 B3 B4 B4 产量,销量,
