管理运筹学 第七章 运输问题之表上作业法
- 格式:ppt
- 大小:523.00 KB
- 文档页数:44
4 运输问题1、运输问题表上作业法的基本步骤。
答:表上作业法的基本步骤可参照单纯形法归纳如下:(1)找出初始基可行解:即要在阶产销平衡表上给出“”个数字格(基变量);(2)求各非基变量(空格)的检验数,判断当前的基可行解是否是最优解,如已得到最优解,则停止计算,否则转到下一步;(3确定入基变量,若,那么选取为入基变量;(4确定出基变量,找出入基变量的闭合回路,在闭合回路上最大限度地增加入基变量的值,那么闭合回路上首先减少为“0”的基变量即为出基变量;(5)在表上用闭合回路法调整运输方案;(6)重复2、3、4、5步骤,直到得到最优解。
2、“最小元素法”和“伏格尔”法的基本思想及基本操作。
答:最小元素法的基本思想是就近供应,即从单位运价表中最小的运价开始确定产销关系,依此类推,一直到给出基本方案为止。
伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差(如果存在两个或两个以上的最小元素费用增量定义为零)。
最大差对应的行或列中的最小元素确定了产品的供应关系,即优先避免最大的费用增量发生。
当产地或销地中的一方在数量上供应完毕或得到满足时,划去运价表中对应的行或列,再重复上述步骤,即可得到一个初始的基可行解。
3、闭合回路的构成以及利用闭合回路法求检验数的基本操作。
答:判断基可行解的最优性,需计算空格(非基变量)的检验数。
闭合回路法即通过闭合回路求空格检验数的方法。
从给定的初始方案的任一空格出发寻找闭合回路,闭合回路顶点所在格括号内的数字是相应的单位运价,单位运价前的“+”、“-”号表示运量的调整方向。
空格处单位运量调整所引起的运费增量就是空格的检验数。
仿照此步骤可以计算初始方案中所有空格的检验数。
4、利用位势法求检验数以及利用闭合回路进行方案调整的基本操作。
答:位势法求解非基变量检验数的基本步骤:第一步:把方案表中基变量格填入其相应的运价并令;让每一个基变量都有,可求得所有的位势;第二步:利用计算各非基变量的检验数方案的优化基本步骤:在负检验数中找出最小的检验数,该检验数所对应的变量即为入基变量。
表上作业法解决运输问题谢荣华、林建、岳钱华、叶俊君【摘要】在物资调运问题中,希望运输费用最少总是人们最为关心的一个目标。
在各种设定条件的约束下,如何寻找使得总运输费用最少的最优的运输方案是运输问题的核心。
为给社会生产(生活)提供既便捷又经济实惠的物资调运方案,运输问题模型的求解方法可以产生最优的决策方案。
因此对运输问题的深入研究具有极其重要的理论意义和实际应用价值。
表上作业法是解决运输问题的重要方法本文讨论了产销平衡运输问题的表上作业法,利用伏格尔法求初始方案,位势法求检验数,闭合回路发对可行解进行调整和改进,直至求出最优解。
【关键词】运筹学、运输问题、改善优化、表上作业法一、理论依据运输问题的表上作业法步骤1、制作初始平衡表用“西北最大运量,然后,每增加角方法”:即在左上角先给予最大运量,然后,每增加一个运量都使一个发量或手里饱。
如果所有运量的数字少于(m+n-1),则补0使之正好(m+n-1)个。
(注:补零时不能使这些书构成圈。
)2、判断初始方案是否最优(1)求位势表:对运价表加一行一列,圈出运价表中相应于有运量的项,在增加的行列上分别添上数,使这些元素之和等于圈内的元素。
这些元素称为位势数。
(2)求检验数,从而得到检验数表。
结论:若对任意检验数小于等于0,则该方案最优,否则进入3进行调整.3、调整(1)找回路:在检验数大于0对应的应量表上对应元素为起点,沿横向或纵向前进,如遇到有运量的点即转向,直至起点,可得到一个回路。
(2)找调整量:沿上述找到的回路,从起点开始,在该回路上奇数步数字的最小者作为调整量ε。
(3)调整方式:在该回路上奇数步-ε,偶数步+ε,得到新回路。
重复上述步骤,使所有检验数小于0,即得到最优方案。
二、背景鉴于市场竞争日益激烈,消费者需求渐趋多样,工厂作为市场消费品的产出源头,唯有对这种趋势深刻理解、深入分析,同事具体的应用于实际中,才能使自身手艺,断发展壮大,不被新新行业所淘汰。
表上作业法什么是表上作业法表上作业法是指用列表的方法求解线性规划问题中运输模型的计算方法。
是线性规划一种求解方法。
当某些线性规划问题采用图上作业法难以进行直观求解时,就可以将各元素列成相关表,作为初始方案,然后采用检验数来验证这个方案,否则就要采用闭合回路法、位势法等方法进行调整,直至得到满意的结果。
这种列表求解方法就是表上作业法。
表上作业法的步骤1、找出初始基本可行解(初始调运方案,一般m+n-1个数字格),用西北角法、最小元素法;(1)西北角法:从西北角(左上角)格开始,在格内的右下角标上允许取得的最大数。
然后按行(列)标下一格的数。
若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。
如此进行下去,直至得到一个基本可行解。
(2)最小元素法:从运价最小的格开始,在格内的右下角标上允许取得的最大数。
然后按运价从小到大顺序填数。
若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。
如此进行下去,直至得到一个基本可行解。
注:应用西北角法和最小元素法,每次填完数,都只划去一行或一列,只有最后一个元例外(同时划去一行和一列)。
当填上一个数后行、列同时饱和时,也应任意划去一行(列),在保留的列(行)中没被划去的格内标一个0。
2、求出各非基变量的检验数,判别是否达到最优解。
如果是停止计算,否则转入下一步,用位势法计算;运输问题的约束条件共有m+n个,其中:m是产地产量的限制;n是销地销量的限制。
其对偶问题也应有m+n个变量,据此:σij = c ij− (u i + v j) ,其中前m个计为,前n个计为由单纯形法可知,基变量的σij = 0c ij− (u i + v j) = 0因此u i,v j可以求出。
3、改进当前的基本可行解(确定换入、换出变量),用闭合回路法调整;(因为目标函数要求最小化)表格中有调运量的地方为基变量,空格处为非基变量。
基变量的检验数σij = 0,非基变量的检验数。