《运筹学运输问题》PPT课件

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

1、第三章运输问题运输问题约束条件的系数矩阵具有特殊的结构，有更为简单的求解方法，从而节约大量的计算时间和费用。1产地--------m个,Ai表示，i=1,2,,m；产量ai,i=1,2,,m销地产地B1B2Bn产量A1c11c12c1na1A2c21c22c2na2Amcm1cm2cmnam销量b1b2bn表3.1要求使总运费最小的调运方案。Cij:-----从Ai到Bj运输单位物资的运价销售地-----n个，Bj表示，j=1,2,,n；销售量

2、bj，j=1,2,,n，3.1、运输问题的数学模型2产销平衡运输问题数学模型解:假设xij表示从Ai到Bj的运量,则所求的数学模型为:总产量等于其总销量，即3LP问题--------mn个变量，m+n个约束条件.单纯形法求解，在每个约束上加入一个人工变量若m=4，n=5，变量个数就有29个之多，非常复杂。41、基本概念与重要结论系数矩阵特点：（1）元素等于0或1；（2）每列只有两个元素为1，其余都是0；（3）每一个变量，在前m个约束方程中只出现一次，在后n个约束方程中也只出现一次。3.2表上作业法5运输问题的解---代表着一个运输方案变量xij的值--由Ai调运数量为xij的物品给B

3、j。基变量---m+n-1个，只有m+n-1个约束条件是线性独立的。进一步我们想知道，怎样的m+n-1个变量会构成一组基变量？67基本概念闭回路凡是能排成互不相同，且形成的变量的集合顶点---出现在闭回路中的变量闭回路的边--相邻两个变量用一条直线相连例3.1设m=3，n=4，表3.2x34x32A3x24x21A2x12x11A1B4B3B2B1销地产地x11、x12、x32、x34、x24、x21构成一个闭回路。8x34x32A3A2x14x12A1B4B3B2B1销地产地9定理3.1：m+n-1个变量构成基变量的充分必要条件是它不包含有任何闭回路。10求解运输问题的一种简化方法，实质是

4、单纯形法。（1）找初始基可行解----即在(mn)产销平衡表上给出m+n-1个数字格--不能构成闭回路，且行和等于产量，列和等于销售量；（2）求非基变量检验数---在表上求出空格的检验数，判别是否达到最优解。如果达到最优解，则停止计算，否则转入下一步；（3）确定换入变量和换出变量，找出新的基可行解，在表上用闭回路法进行调整。（4）重复（2）、（3）步，直到求得最优解为止。2、表上作业法11基本思想----就近供应。即从单位运价表中最小的运价开始确定产销关系，依次类推，直到给出初始方案为止。（1）确定初始基可行解①方法一：最小元素法例3.2某公司有3个生产同类产品的工厂，生产的产品由4个销售

5、点销售，各工厂的生产量、各销售点的销售量以及各工厂到各销售点的单位产品运价如表3.5所示。问该公司应如何调运产品，在满足各销售点的需要量的前提下，使总的运费为最小。12表3.5销地产地B1B2B3B4产量A13113107A219284A3741059销量36563113方案的总运费为86元运价表B1B2B3B4产量A13113107A219284A3741059销量3656表3.7B1B2B3B4产量A1437A2314A3639销量365614两种特殊情况：、多个元素同时最小，任选一个作基变量、对于最小元素，发现该元素所在行的剩余产量等于该元素所在列的剩余销售量。这时在产销平衡表相应的位

6、置填上一个数，而在单位运价表中就要同时划去一行和一列。为了使调运方案中有数字的格仍为（m+n–1）个，需要在同时划去的行或列的任一空格位置添上一个“0”，这个“0”表示该变量是基变量，只不过它取值为0，即此时的调运方案是一个退化的基可行解。15单位产品运价如表3.8所示。利用最小元素法，求初始调运方案销地产地B1B2B3B4产量A1531049A216964A32010577销量3584例3.3表3.9B1B2B3B4产量A15049A2314A377销量3584初始调运方案。如表3.916伏格尔法一产地的产品，假如不能按最小运费就近供应，就考虑次小运费。这就有一个差额，差额越大，说明不能按

7、最小运费调运时，运费增加就越多。因此，对于差额最大处，就优先采用最小运费调运。②方法二伏格尔法最小元素法缺点为节省一处的费用，有时造成在其它地方要花多几倍的运费。17销地产地B1B2B3B4行差额产量A131131007A2192814A37410519列差额2513销量3656表3.1018销地产地B1B2B3B4行差额产量A131131007A2192814A37410519列差额2513销量365663