运输问题的数学模型.ppt

《运输问题的数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运输问题的数学模型§3.1运输问题及其数学模型§3.2表上作业法§3.3产销不平衡的运输问题§3.4应用举例本章主要内容:1．掌握运输问题的数学模型、系数矩阵特殊形式2．掌握用西北角法、最小元素法求初始基可行解3．掌握回路、位势法求解过程和表上作业法求解运输问题过程教学要求：一、运输问题及其数学模型在经济建设中，经常碰到物资调拨中的运输问题。例如煤、钢材、粮食、木材等物资，在全国都有若干生产基地，分别将这些物资调到各消费基地去，应如何制定调运方案，使总的运输费用最少？问题的提出:运输问题的一般提法是：设某种物资有m个产地和n个销地。产地Ai的产量为；销地Bj的销量。从第i个产地

2、向第j个销地运输每单位物资的运价为Cij。这就是由多个产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。1、运输问题的一般提法单位运价表（1）。即运输问题的总产量等于其总销量，这样的运输问题称为产销平衡的运输问题。（2）。即运输问题的总产量不等于总销量，这样的运输问题称为产销不平衡的运输问题。分两种情况来讨论：若用xij表示从Ai到Bj的运量，那么在产销平衡的条件下，要求得总运费最小的调运方案，数学模型为：2、运输问题的数学模型其中，ai和bj满足：称为产销平衡条件。将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。上述模型是一个线性规划问

3、题。但是其结构很特殊，特点如下：1.变量多（mn个），但结构简单。技术系数矩阵该系数矩阵中每列只有两个元素为1，其余的都为零。2.m+n个约束中有一个是多余的（因为其间含有一个平衡关系式）所以R(A)=m+n-1，即解的mn个变量中基变量为m+n-1个。二、表上作业法运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。表上作业法，实质上还是单纯形法。其步骤如下：1.确定一个初始可行

4、调运方案。可以通过最小元素法、西北角法、Vogel法来完成；2.检验当前可行方案是否最优，常用的方法有闭回路法和位势法，用这两种方法计算出检验数，从而判别方案是否最优；3.方案调整，从当前方案出发寻找更好方案，常采用闭回路法。二、表上作业法（续）例3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示问应如何调运，可使得总运输费最小?即初始基本可行解的确定，与一般线性规划问题不同，产销平衡运输问题总是存在可行解。1、确定初始方案确定初始基本可行解的方法很多，一般希望方法是既简便，

5、又尽可能接近最优解。下面介绍两种方法：最小元素法，西北角法、Vogel法（1）最小元素法最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的，并以最大限度满足其供销量为原则确定供销业务。同样的方法反复进行直到确定了所有的供销业务，得到一个完整的调运方案即初始基本可行解为止。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求3656201321344653103方案表运价表以此，得到一初始方案：X13=4,X14=3，X21=3，X23=1，X32=6，X34=3（有数格）X11=X31=X12=X22=X33=X24

6、=0（空格）B1B2B3B4A143A231A363注：（ⅰ）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（ⅱ）如果填上一个变量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数格对待。初始方案运费Z0=3×1+6×4+4×3+1×2+3×10+3×5=86(元)（2）西北角法西北角法与最小元素法不同，它不是优先考虑具有最小单位运价的供销业务，而是优先满足运输表中西北角（左上角）上空格的供销需求。销产B1B2B3B4产量B1B2B3B4A17311310A241928A3974105需求365620342

7、236方案表运价表注：应用西北角法和最小元素法，每次填完数，都只划去一行或一列。当填上一个数后行、列同时饱和时，也应任意划去一行(列)。在饱和的列（行）没被划去的格内标一个0,然后划去该列（行）。例3.2某公司下属有生产一种化工产品的三个产地A1、A2、A3，有四个销售点B1、B2、B3、B4销售这种化工产品。各产地的产量、各销地的销量和各产地运往各销地每吨产品的运费（百元）如下表所示。销产B1B2B3B4产量B1B2B3B4A1753859A2402948A3806375需求3540556