运输问题的数学模型

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

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

2、产地供应多个销地的单品种物资运输问题。问如何调运这些物资才能使总运费达到最小。21miai21njbj销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn1。即运输问题的总产量等于其总销量这样的运输问题称为产销平衡的运输问题。2。即运输问题的总产量不等于总销量这样的运输问题称为产销不平衡的运输问题。njjmiiba11njjmiiba11若用xij表示从Ai到Bj的运量那么在产销平衡的条件下要求得总运费最小的调运方案数学模型为0211321..min1111ijnjiijmijij

3、minjijijxmiaxnjbxtsxcz其中ai和bj满足称为产销平衡条件。njjmiiba11将约束方程式展开可得11112122111211112222nnmmnmmmxxaxxaxxaxxxbxxx212nnmnnbxxxb约束方程式中共mn个变量mn个约束。行行nmAxxxxxxxxxmnmmnn111111111111111111212222111211上述模型是一个线性规划问题。但是其结构很特殊特点如下1.变量多mn个但结构简单。技术系数矩阵该系数矩阵中每列只有两个元素为1其余的都为零。ijab2.mn个约束中有一鍪嵌嘤嗟囊蛭浼浜幸桓銎胶夤叵凳剿

4、訰Amn-1即解的mn个变量中基变量为mn-1个。运输问题仍然是线性规划问题可以用线性规划法中的单纯形法来解决。但是1.运输问题所涉及的变量多造成单纯形表太大2.若把技术系数矩阵A中的0迭代成非0会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法——表上作业法。表上作业法实质上还是单纯形法。其步骤如下1.确定一个初始可行调运方案。可以通过最小元素法、西北角法、Vogel法来完成2.检验当前可行方案是否最优常用的方法有闭回路法和位势法用这两种方法计算出检验数从而判别方案是否最优3.方案调整从当前方案出发寻找更好方案常采用闭回路法。例例33.

5、.11某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表3-4所示销地产地B1B2B3B4产量A13113107A219284A3741059销量365620产销平衡问应如何调运可使得总运输费最小即初始基本可行解的确定与一般线性规划问题不同产销平衡运输问题总是存在可行解。确定初始基本可行解的方法很多一般希望方法是既简便又尽可能接近最优解。下面介绍两种方法最小元素法西北角法、Vogel法最小元素法的基本思想是优先满足单位运价最小的供销业务。首先找出运价最小的并以最大限度满足其供销量为原

6、则确定供销业务。同样的方法反复进行直到确定了所有的供销业务得到一个完整的调运方案即初始基本可行解为止。销产BB11BB22BB33BB44产量产量BB11BB22BB33BB44A17311310A241928A3974105需求3656201321344653103方案表运价表以此得到一初始方案X134X143X213X231X326X343有数格X11X31X12X22X33X240空格B1B2B3B4A143A231A363注ⅰ有数格是基变量共mn-134-16个。空格是非基变量共划去mn7条线ⅱ如果填上一个变量之后能同时划去两条线一行与一列就须在所划去的该行或

7、该列填一个0此0格当有数格对待。初始方案运费Z03×16×44×31×23×103×586元西北角法与最小元素法不同它不是优先考虑具有最小单位运价的供销业务而是优先满足运输表中西北角左上角上空格的供销需求。销产BB11BB22BB33BB44产量产量BB11BB22BB33BB44A17311310A241928A3974105需求365620342236方案表运价表注注应用西北角法和最小元素法每次填完数都只划去一行或一列。当填上一个数后行、列同时饱和时也应任意划去一行列。在饱和的列行没被划去的格内标一个0然后划去该列行。例例33..22某公司下属有