53 运输问题的求解方法.pptx

该【53 运输问题的求解方法 】是由【小屁孩】上传分享，文档一共【35】页，该文档可以免费在线阅读，需要了解更多关于【53 运输问题的求解方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第3节运输问题的求解方法——表上作业法产销平衡表与单位运价表表上作业法产销不平衡的运输问题的求解方法2021/10/101一、产销平衡表与单位运价表运输问题还可用产销平衡表与单位运价表进行描述。假设某种物资有m个生产地点Ai(i=1,2,…,m),其产量(供应量)分别为ai(i=1,2,…,m),有n个销地Bj(j=1,2,…,n),其销量(需求量)分别为bj(j=1,2,…,n)。从Ai到Bj运输单位物资的运价(单价)为Cij。。2021/10/———表上作业法求解,实质仍是单纯形法,步骤如下:(1)确定初始调运方案,即找出初始基可行解,在产销平衡表上给出m+n-1个数字格。二、表上作业法2021/10/104(2)求非基变量的检验数,即在表上计算空格的检验数,判别是否达到最优解:是否存在负的检验数?如果存在负的检验数,则初始调运方案不是最优方案;如果所有检验数都非负,则初始调运方案已经是最优方案了。如果已经得到最优调运方案,则停止计算,否则转入下一步。(3)确定换入变量和换出变量,找出新的调运方案(新的基可行解),即在表上用闭回路法进行调整。(4)重复(1)~(2),直到求出最优解为止。2021/10/105(一)确定初始可行基的方法最小元素法从单位运价表中最小的运价开始确定供销关系,然后考虑运价次小的,一直到给出初始基可行解为止。伏格尔法采用最小元素法可能造成其他处的更多浪费,伏格尔法考虑最小运费与次小运费之间的差额,差额越大,就按次小运费调运。2021/10/106(二)最优解的判别计算非基变量(空格)的检验数,当所有的检验数时,为最优解。求空格检验数的方法有:闭回路法以某一空格为起点找一条闭回路,用水平或垂直线向前划,每碰到一数字格转900后,继续前进,直到回到起始空格为止。2021/10/(a)、(b)、(c)等所示。从每一个空格出发一定存在并且可以找到唯一的闭回路。因为,m+n-1个数字格(基变量)对应的系数向量是一个基,任一空格(非基变量)对应的系数向量是这个基的线性组合。:可表示为而这些向量构成了闭回路见图2021/10/109位势法一种较为简便的求检验数的方法。设是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量Xa的初始基矩阵。Xa在目标函数中的系数Ca,由线性规划的对偶理论可知而每一个决策变量Xij的系数向量,所以由单纯形法可知,所有基变量的检验数等于0,即2021/10/1010