运筹学章3运输问题(增补)课件.ppt

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

1、运输问题第一节运输问题的基本理论运输问题通用模型决策变量列的特点表上作业法（重点）运输问题的实例某大米销售公司有2个仓库，3个商店。根据3个店的订货需求，供货方已经把大米运到了2个仓库。公司希望以最小的总运费把大米运走满足三个商店的需求，问应该如何确定运输方案。数据如表所示：B1B2B3库存A134210A23534需求3562个产地，3个销地。在产销平衡的条件下，确定最小运费运输方案。单位运价：从某仓库到某商店，每吨大米的运价从仓库A2到商店B2，每吨大米的运价是5（千元）运输问题的一般描述m个产地，各地产量为ai。n个销地，各地销量为bj。总需求=总供给最小运费方案？B1…Bn库存A

2、1a11…a1na1Amam1…amnam需求b1…bn实例的线规模型B1B2B3供A110A24需356Xij产地i到销地j的运量342353x11x12x13x21x22x23供给的要求，大米都运走x11+x12+x13=10x21+x22+x23=4需求的要求，大米都运到x11+x21=3x12+x22=5x13+x23=6运价最低MINZ=3x11+4x12+2x13+3x21+5x22+3x23MINZ=3x11+4x12+2x13+3x21+5x22+3x23供x11+x12+x13=10x21+x22+x23=4需x11+x21=3x12+x22=5x13+x23=6多余约

3、束？秩（2+3-1）=(m+n-1)运输问题通用模型秩为(m+n-1)Xij列向量特点Z=3x11+4x12+2x13+3x21+5x22+3x23x11+x12+x13=10x21+x22+x23=4x11+x21=3=5=6x12+x22x13+x23每列只有两个1第一个1在第i行第二个1在第m+j行第1行第2+3行设某运输问题有m个产地，n个销地。每个Xij的列向量只有两个1第一个在第i行第二个在第m+j行运输问题的表上作业法运输问题总是有解，且总是有最优解。找初始解：最小元素法，差额元素法。求检验数：闭回路法，位势法。判优：无负检验数调整：闭回路法。返回②求初始解：最小元素法B1

4、B2B3B4供A1311107A2984A3741059需3656从运价最小的地方开始运。131234633B1B2B3B4供A1437A2314A3639需3656每填一个数，或划掉一行，或划掉一列。最后既划掉一行又划掉一列。因此一共有M+N-1个求初始解：差额元素法计算每行、列的最低和次低运价差。以此作为罚数罚数意味着，如果不用最低运价，而用次低运价会遭受的损失。因此应从罚数最大处起运。求初始解：差额元素法首先计算行列差额：次小减最小B1B2B3B4供行差A13113107A219284A371059需3656列差0112135从差额最大处的最小运价处起运否则将受到惩罚4(6)重新计

5、算行列差额，填下一个数012(3)B1B2B3B4供A1527A2314A3639需3656判优：闭回路法闭回路的特点：是以单元格为顶点的封闭回路每行、列有且仅有两个顶点顶点对应的系数列向量线性相关。闭回路可能的图形如教材图3-1练习，寻找闭回路B1B2B3B4供A1437A2314A3639需3656从空格出发（非基变量）,以数字格（基变量）为顶点。总能找到唯一的闭回路。用闭回路计算检验数B1B2B3B4供A1311433107A23191284A374410359需3656表中黑色数字为单位运价，红色数字为初始调运方案。计算检验数不要用运量，应该用运价++--(1)(2)(1)(-1

6、)(10)(12)判优：位势法位势法原理对应产地的方程有m个，分别对应U1到Um对应销地的方程有n个，分别对应V1到Vn先引入对偶变量对偶变量取值为CBB-1于是有CBB-1=(U1,U2,…Um;V1,V2,…Vn)可知检验数σij=Cij-CBB-1Pij=Cij-CBB-1(ei+em+j)=Cij-(Ui+Vj)于是问题转化为求Ui和Vj如何求得Ui和Vj利用基变量检验数为零的特点基变量Xij检验数=0，则有Cij-(Ui+Vj)=0这样的方程有M+N-1个，而对偶变量有M+N个。因此解不唯一。常令U1或V1=0来求解。位势法举例:令U1=0B1B2B3B4UiA13114331

7、0A2319128A37441035Vj0310-12-59σ12=C12-(U1+V2)=11-(0+9)=2(2)改进：闭回路法B1B2B3B4A1311310A231928A37441035对负检验数单元格，沿闭回路调整。(1)(2)(1)(10)(12)(-1)++--显然调整量只能为1143152表上作业法的问题无穷多最优基：某一非基变量检验数为零，可沿闭回路调整找到其他解。表上作业法的问题退化：保持基变量个数M+N-1不