[理学]第3章：运输问题.pptVIP

一、确定初始基可行解 根据表上作业法，计算得到该问题的最优调运方案如下表所示： 50 10 30 70 20 30 需求量(万吨) 50 20 30 A4 50 0 20 30 A3 60 30 10 20 A2 50 50 A1 生产量(万吨) 销地 产地 二、转运问题 已知某产品生产地有m个，销售地有n个，中间转运地有r个，产销平衡。从Ai运往Aj单位产品的运价为cij，不可到达的运价为M，本地内的运价为0。若用xij表示从某地Ai运往另一地Aj产品的数量，在产销平衡的条件下，中转运输问题的数学模型为： 【例3-5】某产品有A1、A2、A3三个生产地，A4、A5两个中转地，A6、A7、A8、A9四个销售地，各地之间的单位产品运输单价及各地的生产量和需求量如下图所示，各地之间不能直接运输的运输单价为M。问如何调运这种产品，使总的运输费用最省？ 解：若xij用表示从Ai运往Aj产品的数量，则该问题的目标函数为： 对于供应地A1、A2、A3的供应量约束为： 对于中转地A4、A5的约束： 对于销售地A6、A7、A8、A9需求量的约束： 由此可得该问题的数学模型： 将上述模型化为运输问题的具体做法是：每个中转地对于生产地来说它是销售地，其销量为所有运到该地的生产量之和；每个中转地对于销售地来说它又是生产地，其生产量等于其销售量。 该问题的产销平衡表： 600 600 40 30 40 90 200 200 需求量(万吨) 200 9 2 1 M 0 M A5 200 M 6 3 4 M 0 A4 100 15 M M M 7 8 A3 60 M M M M 2 4 A2 40 M M 2 3 5 2 A1 生产量(万吨) A9 A8 A7 A6 A5 A4 销地 产地 用表上作业法求得最优调运方案： 600 600 40 30 40 90 200 200 需求量(万吨) 200 30 40 130 A5 200 50 150 A4 100 40 10 50 A3 60 60 A2 40 40 A1 生产量(万吨) A9 A8 A7 A6 A5 A4 销地 产地 第四节 WinQSB软件应用 例3-1运输问题的WinQSB软件操作过程是： ⑴启动程序。依次点击“开始→程序→WinQSB→Network Modeling”，系统出现如下图： ⑵建立新的数据文件。点击“File→New Problem”，点选Transportation Problem，系统出现如图 * 第三章 运输问题 (Transportation Problem) 运输问题及其数学模型 表上作业法 运输问题的进一步讨论 WinQSB软件应用 第一节 运输问题及其数学模型 一、运输问题的数学模型 【例1】已知某产品有A1、A2、A3三个生产地，其可供应的产量分别为15、25、5吨；有B1、B2、B3、B4四个销售地可以销售该产品，其对该产品的需求量分别为10、12、15、8吨。从Ai运往Bj单位产品的运价如下表所示。 问如何安排该产品的调运计划，使总的运输费用最省？ 45 8 15 12 10 需求量(吨) 28 16 24 12 5 A3 30 19 17 22 25 A2 21 30 11 20 15 A1 B4 B3 B2 B1 生产量(吨) B4 B3 B2 B1 销地 产地 解：设 表示从生产地Ai运往销售地Bj产品的数量 由于生产总量与需求总量相等，因此从横向上讲，从某生产地运往各销售地的产品总量应等于该生产地能够生产的数量，即： 从纵向上讲，运往某销售地该产品的总量应等于该销售地的需求量，即： 该问题的数学模型为： 将上述问题一般化，可用以下数学语言进行描述。 已知有m个生产地Ai(i=1,2,…,m)可供应某种产品，其生产量为ai；有n个销售地Bj可以销售该产品，其需求量为bj；从Ai运往Bj单位产品的运价(单价)为cij。 设 表示从生产地Ai运往销售地Bj产品的数量 用矩阵形式表示为： 当产销平衡时，其模型如下： 当产大于销时，其模型是： 当产小于销时，其模型是： 1、平衡运输问题必有可行解，也必有最优解； 2、运输问题的基本可行解中应包括 m+n-1个基变量。 二、运输问题的特点 第二节 表上作业法 1、最小元素法 解题步骤： ⑴在运价表中找到最小运价cLk； ⑵将AL的产品给B k； ①若aLb k，则将aL改写为aL-bk，划掉bk，同时将运价表中K列的运价划掉； ②若aLb k，则将bk改写为bk-a