7第七章运输问题qgk.pptx

《7第七章运输问题qgk.pptx》由会员分享，可在线阅读，更多相关《7第七章运输问题qgk.pptx（79页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、管理运筹学第七章 运输问题运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容1234 1运 输 模 型例 1.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A16 4 6 200A26 5 5 300销量/件150 150 200 1运 输 模 型 解：产销平衡问题：总产量=总销量设 xij 为从产地 Ai 运往销地 Bj 的运输量，得到运输量表 销地 运输量产地B1B2B3产量/件A1x11x12x1320

2、0A2x21x22x23300销量/件150 150 200 500 1运 输 模 型 min f=6x11+4x12+6x13+6x21+5x22+5x23 s.t.x11+x12+x13=200（产地A1）x21+x22+x23=300（产地A2）x11+x21=150（销地B1）x12+x22=150（销地B2）x13+x23=200（销地B3）xij 0(i=1、2；j=1、2、3）1运 输 模 型 一般运输问题的线性规划模型：产销平衡 A1、A2、Am 表示某物资的 m 个产地；B1、B2、Bn 表示某物资的 n 个销地；si 表示产地Ai 的产量；dj 表示销地 Bj 的销量；ci

3、j 表示把物资从产地 Ai 运往销地 Bj 的单位运价。1运 输 模 型 设 xij 为从产地 Ai 运往销地 Bj 的运输量，则一般运输问题模型：(产地Ai)(销地Bj)1运 输 模 型变化：（1）求目标函数最大：利润最大或营业额最大。（2）运输线路上有能力限制时，模型中加入约束条件（等式或不等式约束)。（3）产销不平衡时，加入假想的产地（销大于产）或假想销地（产大于销）。运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容2341 2运输问题的计算机求解例 2.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地

4、每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A16 4 6 300A26 5 5 300销量/件150 150 200 600500 2运输问题的计算机求解解：销地 运费单价/元产地B1B2B3产量/件A16 4 6 300A26 5 5 300销量/件150 150 200 60000100B4600 500产销平衡运输费用？增加一个虚设的销地B4，即增加一个仓库进行货物存储增加一个虚设的销地B4 2运输问题的计算机求解 数据输入“管理运筹学”软件 2运输问题的计算机求解由软件得，最优解为：X11=50,X12=150,X13=0,X1

5、4=100,X21=100,X22=0,X23=200,X24=0.min f=2500.2运输问题的计算机求解例 3.某公司从两个产地 A1、A2 将物品运往三个销地 B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示，问：应如何调运可使总运输费用最小？销地 运费单价/元产地B1B2B3产量/件A16 4 6 200A26 5 5 300销量/件250 200 200 500650 2运输问题的计算机求解解：销地 运费单价/元产地B1B2B3产量/件A16 4 6 200A26 5 5 300销量/件250 200 200 650增加一个虚设的产地A3 50

6、0 6500 150 A30 0产销平衡运输费用？增加一个虚设的产地A3，即缺货 2运输问题的计算机求解 数据输入“管理运筹学”软件 2运输问题的计算机求解由软件得，最优解为：X11=0,X12=200,X13=0,X21=100,X22=0,X23=200,X31=150,X32=0,X33=0.min f=2400.运输模型运输问题的计算机求解运输问题的应用运输问题的表上作业法本章内容3412 3运输问题的应用例 4.石家庄北方研究院有三个区，即一区，二区，三区，每年分别需要用煤 3 000 t、1 000 t、2 000 t，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力

7、分别为 1 500 t、4 000 t，运价如表所示。销地 运费单价产地一区 二区 三区山西盂县1.80 1.70 1.55河北临城1.60 1.50 1.75一、产销不平衡的运输问题 单位/(百元/t)3运输问题的应用 由于需大于供，经院研究决定一区供应量可减少 0-300 t，二区必须满足需求量，三区供应量不少于 1 500 t，试求总费用为最低的调运方案。3运输问题的应用解：根据题意，作出产销平衡与运价表。销地 运费单价/百元产地一区1一区2二区 三区1三区2供应量/t山西盂县1.80 1.80 1.70 1.55 1.55 4000河北临城1.60 1.60 1.50 1.75 1.7

8、5 1500需求量/t2700 300 1000 1500 500 6000需求必须满足需求必须满足需求必须满足55006000500产销平衡0 M M M 0假想生产点运输费用？这里 M 代表一个很大的正数，其作用是强迫相应的 x31、x33、x34 取值为 0。非必须满足非必须满足 3运输问题的应用由软件计算可得，最优解为：X11=2200,X14=1500,X15=300,X21=500,X23=1000,X32=300,X35=200总运费为9050百元 3运输问题的应用例 5.设有 A、B、C 三个化肥厂供应四个地区的农用化肥。假设等量的化肥在这些地区使用效果相同，有关数据如表。试求

9、总费用为最低的化肥调拨方案。销地 运费单价/（元/吨)产地I II III IV 产量/万吨A16 13 22 17 50B14 13 19 15 60C19 20 23-50最低需求/万吨30 70 0 10最高需求/万吨50 70 30不限 3运输问题的应用解：根据题意，作出产销平衡与运价表。销地 运费单价/（元/吨)产地I I II III IV IV 产量/万吨A16 16 13 22 17 17 50B14 14 13 19 15 15 60C19 19 20 23 M M 50D 50销量/万吨30 20 70 30 10 210210必须满足必须满足必须满足虚设产地运费为050M

10、 M M 0 0 0虚设产地运费为0虚设产地运费为0运输费用？3运输问题的应用应用软件计算，最优解如表。单位/万吨最小总费用为2460万元。销地 运输量产地I I II III IV IV 产量A50 50B20 10 30 60C30 20 0 50D 30 20 50销量30 20 70 30 10 50 210210 3运输问题的应用例 6.某运输问题如下表所示，并假设各个产地的货物储存都发生费用，其中1、2、3产地的单位存储费用分别为3、2、1元。假定产地2的物资必须至少运出28个单位，产地3至少运出17个单位，试求费用最少的运输方案。单位：元 销地 运费单价/元产地1 2 3产量1

11、4 5 3 202 5 3 4 303 3 5 2 20销量20 30 10 7060 3运输问题的应用产大于销问题，构造产销平衡与运价表。销地 运费单价产地1 2 3产量14 5 32025 3 42825 3 4233 5 21733 5 23销量20 30 10 70必须满足必须满足10MM32160704（库存）运输费用？存储费用存储费用存储费用产销平衡 3运输问题的应用由软件计算可得，最优解为：X11=13,X14=7,X22=28,X32=2,X41=7,X43=10,X54=3.总运费为207元。3运输问题的应用例7.造船厂根据合同从当年起连续三年末各提供五条规格型号相同的大型客

12、货轮。该厂这三年内生产大型客货轮的能力及每艘客户轮的成本如下：年度正常生产能力/台加班生产能力/台正常生产单位成本/万元1 3 3 6002 4 2 7003 2 3 650二、生产与储存问题 3运输问题的应用 已知加班生产时，每艘客货轮成本比正常高出10%，造出的客货轮如当年不交货，每艘每积压一年所造成的积压损失为60万元。在签合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年末完成合同后还能存储一艘。问该厂应如何安排每年客货轮的生产量，使在满足上述各项要求的情况下，总的生产费用为最少？3运输问题的应用解：化为运输问题。考虑：每年生产与交货分别视为产地和销地（1）1-3年合计生产能力

13、（包括第1年初积压量）为 19 艘，销量为 16艘。设一假想销地销量为 3艘；（2）第1年初积压量 2艘，只有积压损失费，列为第 0 行；（4）1-3表示 1-3年正常生产情况，1-3表示 1-3年加班生产情况。（3）第3年的需求除 5艘销量外，还要1艘库存，其需求为 5+1=6 艘；3运输问题的应用产销平衡与运价表：销售年 单价/万元生产年1 2 3正常产量/艘加班产量/艘0 60 120 180 21 600 660 720 31 660 720 780 32 M 700 760 42 M 770 830 23 M M 650 23 M M 715 3销量/台5 5 6 19虚拟的销地，即

14、为仓库假想 销地产销平衡运输费用？316 190000000 3运输问题的应用用管理运筹学软件解得：1-3年最低生产费用为 9665 万元，每年的生产销售安排如下。单位/艘 销售年 运输量生产年1 2 3假想 销量0 1 11 31 2 12 42 23 23 3 3运输问题的应用例8.某厂按合同规定须于当年每个季度末分别提供 10、15、25、20 台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用 0.15 万元。试求在完成合同的情况下，该厂全年生产总费用最小的决策方案。3运输问题的应用 季度 生

15、产能力/台 单位成本/万元I 25 10.8II 35 11.1III 30 11.0IV 10 11.3解：设 xij 为第 i 季度生产的第 j 季度交货的柴油机数目 3运输问题的应用设 cij 为第 i 季度生产的第 j 季度交货的柴油机的实际成本，应是第i季度生产单位成本加上存储、维护费用。单位/万元 j iI II III IVI 10.8 10.95 11.10 11.25II 11.10 11.25 11.40III 11.00 11.15IV 11.30不可能的情况，费用？MM MMM M 3运输问题的应用构造假想的需求D，产销平衡与运价表：销地 运费单价/万元产地I II I

16、II IV 产量/台I 10.8 10.95 11.10 11.2525II M 11.10 11.25 11.4035III M M 11.00 11.1530IV M M M 11.3010销量/台10 15 25 20 100虚拟的销地，即为仓库30100D产销平衡运输费用？700000 3运输问题的应用运用软件计算，最优解：单位/台 最优值为773万元。销地 运输量产地I II III IVD产量I 10 15 025II 0 530 35III 25 530IV 1010销量10 15 25 20 30 3运输问题的应用三、转运问题 发点：发货量收货量 中转站：发货量=收货量 收点：

17、发货量收货量 3运输问题的应用 在原运输问题上增加若干中转站：允许物品从一个发点运往另一个发点或中转站或收点；允许物品从一个中转站运往另外一个中转站或发点或收点；允许物品从一个收点运往另外一个收点或中转站或发点。3运输问题的应用例9.腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产 400 台，广州分厂每月生产600 台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因大连距青岛较近，公司同意大连分厂向青岛直接供货，运输费用如图，单位百元。问应该如何调运仪器，可使总运输费用最低？3运输问题的应用 腾飞公司运输网络图 1广州2大连3上海

18、4天津5南京6济南7南昌8青岛2331426364465600400200150350300供应量需求量 3运输问题的应用 解：设 xij 为从 i 到 j 的运输量，线性规划模型：目标函数：min f=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量 输入量=产量对转运站（中转点）：输入量 输出量=0对销地（收点）j：输入量 输出量=销量 3运输问题的应用 目标函数 min f=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48约束条件 s.t x13+x14 600（广州分厂供应量限

19、制）x23+x24+x28 400（大连分厂供应量限制）x13 x23+x35+x36+x37+x38=0（上海销售公司，转运站）x14 x24+x45+x46+x47+x48=0（天津销售公司，转运站）x35+x45=200（南京的销量）xij 0,i,j=1,2,3,4,5,6,7,8 x36+x46=150（济南的销量）x37+x47=350（南昌的销量）x38+x48+x28=300（青岛的销量）3运输问题的应用用管理运筹学软件解得：x13=550,x14=50,x23=0,x24=100,x35=200,x36=0,x37=350,x38=0,x45=0,x46=150,x47=0,

20、x48=0,x28=300最小运输费用为：4 600 百元 3运输问题的应用 例10.某公司有 A1、A2、A3 三个分厂生产某种物资，分别供应 B1、B2、B3、B4 四个地区的销售公司销售。假设质量相同，有关数据如下表，试求总费用为最少的调运方案。销地 运费单价/百元产地B1B2B3B4产量/tA13 11 3 10 7A21 9 2 8 4A37 4 10 5 9销量/t3 6 5 6 2020 3运输问题的应用假设：每个分厂的物资可以运到其他分厂、转运站、销地；每个销地的物资可以运到其他销地、转运站、分厂；每个中转站的物资可以运到其他转运站、产地、销地。3运输问题的应用运价表：A1 A

21、2 A3 T1 T2 T3 T4 B1 B2 B3 B410856746213A1A2A3T1T2T3T4B1B2B3B43-1-2374105231132284615-11145274-231218243232121-2631724111421194858-121321042224231321433113101-35-21928 3运输问题的应用解：转化为一般运输问题（1）把所有产地、销地、转运站同时看作产地和销地。（2）运输表中不可能方案的运费取作 M，自身对自身的运费为 0。（3）Ai：产量为 20+原产量，销量为 20；Ti：产量、销量均为 20；Bi：产量为 20，销量为 20+原销

22、量，其中 20 为各点可能变化的最大流量。（4）对于最优方案，其中 xii为自身对自身的运量，实际上不进行运作。3运输问题的应用解：扩大的运输问题产销平衡与运价表：A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4产量/tA1A2A3T1T2T3T4B1B2B3B4销量/t3M01M237410520231013228462015M10114527204M2310218242032321201M262031724110142231194858M102126321042224203251085674621302627242920202020202020202400132143311

23、3102010M35M2192820 3运输问题的应用应用软件计算，最优解：A1 A2 A3 T1 T2 T3 T4 B1 B2 B3 B4产量A1A2A3T1T2T3T4B1B2B3B4销量20 20317202020 20 20 20 20 6 314 236 20 26 520 256 20262724292020202020202020240202071320 3运输问题的应用最佳运输方案：最优值（最小运费）：68百元A17A24T1B13B26B35B4676A39636 产地（产量）35 销地（销量）3运输问题的应用产地直接运输至销地的最小费用：85百元运输模型运输问题的计算机求解

24、运输问题的应用运输问题的表上作业法本章内容4123 4运输问题的表上作业法 表上作业法是一种求解运输问题的特殊方法，其实质是单纯形法。运输问题都存在最优解。4运输问题的表上作业法 基本可行解（m+n-1个基变量）非基变量检验数检验数大于等于0 唯一最优解闭回路法调整方案是否计算过程（假设产销平衡）非基变量检验数等于0多个最优解否 4运输问题的表上作业法 例11.喜庆食品公司有三个生产面包的分厂 A1、A2、A3，有四个销售公司 B1，B2，B3，B4，其各分厂每日的产量、各销售公司每日的销量以及各分厂到各销售公司的单位运价如表，在表中产量与销量的单位为吨，运价的单位为百元/吨。问该公司应如何调

25、运产品在满足各销点的需求量的前提下总运费最少？4运输问题的表上作业法 销地 运价 百元/t产地B1B2B3B4产量/tA13 11 3 10 7A21 9 2 8 4A37 4 10 5 9销量/t3 6 5 6 2020 4运输问题的表上作业法一、确定初始基本可行解 为了把初始基本可行解与运价区分开，我们把运价放在每一栏的右上角，每一栏的中间写上初始基本可行解（调运量）。销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 6 5 6 4运输问题的表上作业法1.西北角法 先从表的左上角（即西北角）的变量x11开始分配运输量，并

26、使x11取尽可能大的值，即x11=min(7,3)=3,则x21与x31必为零。同时把B1的销量与A1的产量都减去3填入销量和产量处，划去原来的销量和产量。同理可得余下的初始基本可行解。对西北角的变量分配运输量 使运输量最大 至少使一产地或销地的剩余量为0 4运输问题的表上作业法 销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 6 5 63 42 23 6x11=min(7,3)=3 x12=min(4,6)=40 40 20 60203 0 x22=min(4,2)=2x23=min(2,5)=2x33=min(3,9)

27、=3x34=min(6,6)=60 4运输问题的表上作业法 2最小元素法 西北角法是对西北角的变量分配运输量，而最小元素法是就近供应，即对单位运价最小的变量分配运输量。在表上找到单位运价最小的x21，并使x21取尽可能大的值，即x21=min(4,3)=3,把A2的产量改为1，B1的销量改为0，并把B1列划去。在剩下的33矩阵中再找最小运价，同理可得其他的基本可行解。一般来说用最小元素法求得的初始基本可行解比西北角法求得的总运价要少。这样从用最小元素法求得的初始基本可行解出发求最优解的迭代次数可能少一些。对单位运价最小的变量分配运输量使运输量最大至少使一产地或销地的剩余量为0 4运输问题的表上

28、作业法 销地 产地B1B2B3B4产量A1 3 11 3 10 7 A2 1 9 2 8 4A3 7 4 10 5 9销量 3 6 5 6346133x11=min(4,3)=3x23=min(1,5)=1 0 30 10 30 3040 x32=min(9,6)=6x34=min(3,6)=3x13=min(7,4)=4x14=min(3,3)=30 4运输问题的表上作业法在求初始基本可行解时要注意的两个问题：l 1.当取定xij的值之后，会出现Ai的产量与Bj的销量都改为零的情况，这时只能划去Ai行或Bj列，但不能同时划去Ai行与Bj列。l 2.用最小元素法时，可能会出现只剩下一行或一列的

29、所有格均未填数或未被划掉的情况，此时在这一行或者一列中除去已填上的数外均填上零，不能按空格划掉。这样可以保证填过数或零的格为m+n-1个，即保证基变量的个数为m+n-1个。l 即初始基本可行解一定满足：每一行（列）至少有一个格子被填上数字；每一行（列）一定被划掉。4运输问题的表上作业法二、最优解的判别1闭回路法 从非基变量的空格出发，沿水平或垂直方向前进，只有碰到基变量的格才能垂直拐弯（或穿过），直至回到发点，形成的封闭折线叫做闭回路。一个空格存在唯一的闭回路 4运输问题的表上作业法 闭回路法：对闭回路各顶点进行编号，非基变量（编号为1）调运量调整为加 1，并对闭回路上顶点的调运量加1（奇数顶

30、点）或减少 1（偶数顶点），以保持产销平衡的要求。非基变量检验数：调整运输方案引起费用的变化。为了区别调整量，把检验数圈起来。检验数都大于等于零，则已求得最优解。4运输问题的表上作业法寻找非基变量x11的检验数：销地 产地B1B2B3B4产量A1 3 4 3 7 A2 3 1 1 2 4 A39 销量3 6 5 6非基变量x11x11调运量增加1t，运费增加3百元保持A1产量平衡，x13减少1t，运费减少3百元保持B3销量平衡，x23增加1t，运费增加2百元保持A2与B1平衡，x21减少1t，运费减少1百元调整后运费增加3-3+2-1=1百元 4运输问题的表上作业法2位势法运输表上的每一行赋予

31、数值 ui，每一列赋予数值vj。数值由基变量 xij 的检验数 ij=cijuivj=0 决定。非基变量 xij的检验数为ij=cij uivj。4运输问题的表上作业法 销地 产地B1B2B3B4uiA1 3 11 4 3 3 10 A2 3 1 9 1 2 8A3 7 6 4 10 3 5vj12-10-1-52 9 3 10令u1=0v3=c13 u1=3-0=3令13=0令14=0v4=c14 u1=10-0=10令23=0u2=c23 v3=2-3=-1令34=0u3=c34 v4=5-10=-5令21=0v1=c21 u2=1-(-1)=2令32=0v2=c32 u3=4-(-5)=

32、911=c11 u1 v1=3 0 2=112=c12 u1 v2=11 09=222=c22 u2 v2=9(1)-9=124=c24 u2 v4=8(1)-10=-131=c31 u3 v1=7(5)-2=1033=c33 u3 v3=103(5)=12 4运输问题的表上作业法三、改进运输方案的办法闭回路调整法调整判别准则：存在检验数小于零调整方法：选取所有负检验数最小的非基变量作为入基变量在以x24为出发点的闭回路中，找出所有偶数的顶点的调运量：x14=3，x23=1，x24=min(3,1)=1。把所有闭回路上为偶数顶点的运输量都减少这个值，奇数顶点的运输量都增加这个值(见下表)。4运

33、输问题的表上作业法 销地 产地B1B2B3B4uiA1 3 11 4 3 3 10 A2 3 1 9 1 2 8A3 7 6 4 10 3 5vj12-10-1-52 9 3 10非基变量检验数最小为-1，对应非基变量为x24基，为入基变量，作闭回路 4运输问题的表上作业法 销地 产地B1B2B3B4产量A1 4 3 7 A2 3 1 4 A36 3 9 销量3 6 5 6x24=min(3,1)=1(+1)(-1)(-1)(+1)4运输问题的表上作业法调整后的运输方案：销地 产地B1B2B3B4产量A1 5 2 7 A2 3 1 4 A36 3 9 销量3 6 5 6 4运输问题的表上作业法

34、 销地 产地B1B2B3B4uiA1 3 11 5 3 2 10 A2 3 1 9 2 1 8A3 7 6 4 10 3 5vj120-2-53 9 3 10令u1=0v3=c13 u1=3-0=3令13=0令14=0v4=c14 u1=10-0=10令24=0u2=c24 v4=8-10=-2令34=0u3=c34 v4=5-10=-5令21=0v1=c21 u2=1-(-2)=3令32=0v2=c32 u3=4(5)=911=c11 u1 v1=3 0 3=012=c12 u1 v2=11 09=222=c22 u2 v2=9(2)9=223=c23 u2 v3=2(2)3=131=c31

35、 u3 v1=7(5)3=933=c33 u3 v3=103(5)=120所有非基变量检验数都大于等于零，基变量的检验数等于零，此解释最优解。最小总费用为85百元。4运输问题的表上作业法四、如何找多个最优方案 多个最优解的判别：最优方案中存在非基变量的检验数为零。如在本题中给出的最优运输方案中x11的检验数为0，可知此运输问题有多个最优解。只要把x11作为入基变量，调整运输方案，就可得到另一个最优方案。4运输问题的表上作业法 销地 产地B1B2B3B4产量A1 5 2 7 A2 3 1 4 A36 3 9 销量3 6 5 6x11=min(2,3)=2（+2）（-2）（-2）（+2）4运输问题的表上作业法最优方案 最小费用为85百元。销地 产地B1B2B3B4A12 5A2 1 3A36 3谢 谢！谢谢观看/欢迎下载BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES.BY FAITH I BY FAITH