[管理学]运输问题

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

1、第4章运输问题14.1运输问题模型及有关概念4.1.1问题的提出一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。2例4.1:某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？3解：产销平衡问题：总产量=总销量设xij为从产地Ai运往销地Bj的运输量，得到下列运输量表：4Minf=6x11+4x12+6x13+6x21+5x22+5

2、x23s.t.x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0(i=1,2；j=1,2,3）4.1运输问题模型及有关概念5111000000111100100010010001001系数矩阵6模型系数矩阵特征1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用。3.系数矩阵的秩为m+n-17运输问题是一种特殊的线性规划问题，在求解时依然可以采用单纯形法的思路，如图4-1所示。由于运输规划系数矩阵的特殊性，

3、如果直接使用线性规划单纯形法求解计算，则无法利用这些有利条件。人们在分析运输规划系数矩阵特征的基础上建立了针对运输问题的表上作业法。下面主要讨论基本可行解、检验数以及基的转换等问题。续下页8表上作业法表上作业法求解运输问题的思想和单纯形法完全类似：确定一个初始基本可行解——根据最优性判别准则来检查这个基本可行解是不是最优的？如果是，则计算结束；如果不是，则进行换基。——直至求出最优解为止。9基本可行解是否最优解结束换基是否图4-1运输问题的求解思路返回10产销平衡问题，我们把运费和运量放在同一个表中：11销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na

4、1A2c21x21c22x22…c2nx2na2┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bn12主要内容：一、确定初始基本可行解二、最优解的判别三、改进运输方案的办法——闭回路调整法13运输问题的基变量共有m+n-1个（A的秩为m+n-1）。方法：西北角法最小元素法一、确定初始基本可行解1415销地产地B1B2…Bn产量A1c11x11c12x12…c1nx1na1A2c21x21c22x22…c2nx2na2┇┇┇┇┇Amcm1xm1cm2xm2…cmnxmnam销量b1b2…bn161718基本可行解是否最优解结束换基是否运输问题的求解思路

5、西北角法最小元素法位势法闭回路调整法4.2运输问题求解—表上作业法19位势：设对应基变量xij的m+n-1个ij，存在ui,vj满足ui+vj=cij，i=1,2…,m;j=1,2…,n.称这些ui,vj为该基本可行解对应的位势。二、最优解的判别—位势法20由于有m+n个变量（ui,vj），m+n-1个方程（基变量个数），故有一个自由变量，位势不唯一。利用位势求检验数：ij=cij-ui-vji=1,…,m;j=1,…,n最优解的判别—位势法21前例，位势法求检验数：step1从任意基变量对应的cij开始,任取ui或vj，然后利用公式cij=ui+vj依次找出m+n个ui

6、,vj,从c14=10开始step2计算非基变量的检验数ij=cij-ui-vj；填入括号内最优解的判别—位势法22当非基变量的检验数均为正，则当前解就是最优解；当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。最优解的判别—位势法23当非基变量的检验数出现负值时，则表明当前的基本可行解不是最优解。这时，应该对基本可行解进行调整，即找到一个新的基本可行解使目标函数值下降，这一过程通常称为换基(或主元变换)过程改进运输方案的办法（即求新的基本可行解）——闭回路调整法24例如，x13,x16,x36,x34,x24,x23；x23,x53,x55,x45,x41

7、,x21；x11,x14,x34,x31等都是闭回路。若把闭回路的各变量格看作节点，在表中可以画出如下形式的闭回路：闭回路的概念闭回路示意图25根据定义可以看出闭回路的一些明显特点：(1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；(2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）。闭回路的概念26关于闭回路有如下的一些重要结论：(1)设xab,xac,xdc,xde,…,xst,xsb是一个闭回路，那么该闭回路中变量所对应的系数列向量pab,pac,pdc,pde,…,p