第2讲 运输经济学问题ppt课件.ppt

《第2讲 运输经济学问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2讲运输问题的经济学分析1例：某运输问题的资料如下：单位销地运价产地产量311310719284741059销量36562020§1运输问题的数学模型2设表示由产地i到销地j的运量约束条件目标函数3单销产量产地产量销量数学模型的一般形式4当产销平衡时，其模型如下：5表运输问题单位运价表销地产地B1B2…Bn产量A1A2┇Amc11c12…c1nc21c22…c2n┇┇┇┇cm1cm2…cmna1a2┇am销量b1b2…bn设xij为从产地Ai运往销地Bj的运输量，根据这个运输问题的要求，可以建立运输变量表。6表运输问题变量表销地产地B1B2…Bn产量A1A2┇A

2、mx11x12…x1nx21x22…x2n┇┇┇┇xm1xm2…xmna1a2┇am销量b1b2…bn7当产大于销时，其模型是：8当产小于销时，其模型是：9产销平衡运输问题的一般特点1．运输问题是一个具有m×n个变量和n+m个约束条件的线性规划问题。写出系数矩阵A，形式如下：m行n行102.运输问题的基变量总数是m+n-1可以证明系数矩阵及其增广矩阵的秩是m+n-1。对于系数矩阵，一方面，前m行相加之和减去后n行相加之和结果是零向量，这说明这m+n个行向量线性相关，因此的秩一定小于m+n；另一方面取出矩阵的前m+n-1行和前n列及对应列的元素构成m+n-1阶方阵D

3、：n-1行m行不难看出，D的行列式的值是不为0的，亦即D的秩应该等于m+n-1，又因为D本身就含于A中，故A的秩也等于m+n-1。可以证明m+n个约束方程中的任意m+n-1个都是线性无关的。11产销平衡运输模型系数矩阵特征：1.共有m+n行，分别表示各产地和销地；mn列，分别表示各决策变量；2.每列只有两个1，其余为0，分别表示只有一个产地和一个销地被使用；3.对于产销平衡运输模型系数矩阵的秩r(A)=m+n-112⑷重复⑵，⑶，直到找到最优解为止。步骤：⑴找出初始基本可行解（初始调运方案，一般m+n-1个数字格），用最小元素法、Vogel法；⑵求出各非基变量的

4、检验数，判别是否达到最优解。如果是停止计算，否则转入下一步，用闭回路法、位势法计算；⑶改进当前的基本可行解（确定换入、换出变量），用闭合回路法调整；§2表上作业法13基本可行解是否最优解结束换基是否运输问题的求解思路14运输问题的基变量共有m+n-1个，A的秩为m+n-1。运输问题的m+n-1个变量构成基变量的充分必要条件是不含闭回路。重要概念:闭回路、闭回路的顶点特点运输问题基变量的15闭回路是运输问题求解过程中非常重要的一个基本概念。如表所示，变量组x11x13x23x21即称作为一个闭回路，其中每一个变量称作该闭回路的一个顶点。同样，变量组x11x12x22

5、x21和x13x14x34x32x22x23也都是闭回路。闭回路在表中的表示法B1B2B3B4A1X11X12X13X14A2X21X22X23X24A3X31X32X33X34闭回路具有一个很重要的性质，即闭回路上的变量组对应的系数列向量线性相关，换言之即m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。这一性质是运用表上作业法求解运输问题的理论基础。16根据定义可以看出闭回路的一些明显特点：(1)闭回路均为一封闭折线，它的每一条边，或为水平的，或为垂直的；(2)闭回路的每一条边（水平的或垂直的）均有且仅有两个闭回路的顶点（变量格）；(3)回路中顶点的个

6、数一定是偶数，回路遇到顶点必须转90度与另一顶点连接。推论产销平衡运输问题的m+n-1个变量构成基变量的充分必要条件是它不含闭回路。17某运输资料如下表所示：单位销地运价产地产量311310719284741059销量3656案例1：18B1B2B3B4产量A17A24A39销量36563113101927410583416331、寻找初始解(1)最小元素法基本思想是就近供应，即从运价最小的地方开始供应（调运），然后次小，直到最后供完为止。19B1B2B3B4产量A17A24A39销量3656311310192741058341633总的运输费用＝（3×1）＋（6

7、×4）＋（4×3）＋（1×2）＋（3×10）＋（3×5）＝86元于是得到初始方案为20（2）差值法（伏格法）伏格法考虑到：一个产地的产品若不能按照最小运费就近供应，就考虑次小运费，这样就有一个差额。此差额越大，说明若不能按最小运费供应，运费增加就越多。21伏格法步骤：每次从当前运价表上，计算各行各列中两个最小运价和次小运价之差值，再从差值最大的行或列中找出最小的运费来确定供应关系，直到求出初始方案。22B1B2B3B4产量A17A24A39销量36563113101927410580112513601221330121237612512B1B2B3B4产量A17A

8、24A39