运输问题表上作业法.pptx

《运输问题表上作业法.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、表上作业法表上作业法是一类比较特殊的单纯形法。它必须首先确定一个初始方案，也就是找出一个基可行解，然后根据判别准则来检查这个初始方案是不是最优的，如果不是最优的，那么对初始方案加以改进，直到找出最优方案。表上作业法与单纯形法之间的关系：1、表上作业法中的最小元素法和伏格尔法实质上是在求单纯形表中的初始基可行解；2、表上作业法中的“位势法”实质上是在求单纯形表中的检验数；3、调运方案表中数字格的数实质上就是单纯形法中基变量的值；4、调运方案表上的“闭回路法”实质上是在做单纯形表上的换基迭代。确定初始方

2、案(初始基本可行解)改进调整（换基迭代）否判定是否最优？是结束最优方案表上作业法求解运输问题思路图表上作业法步骤：1、找出初始可行解，用最小元素法、西北角法与伏格尔法。2、求出各非基变量的检验数，判别是否达到最优解。如果是停止计算，否则转入下一步。3、改进当前的基本可行解(确定换入、换出变量)，用闭合回路法与位势法调整;4、重复2、3步骤，直到找到最优解为止。1、分别使用最小元素法和西北角法求出初始方案。&最小元素法的基本思想是“就近供应”；&西北角法则不考虑运距（或运价），每次都选剩余表格的左上角

3、（即西北角）元素作为基变量，其它过程与最小元素法相同；&伏格法尔法每次从当前运价表上，计算各行各列中两个最小运价之差值（行差值hi，列差值kj），优先取最大差值的行或列中最小的格来确定运输关系，直到求出初始方案；1、找出最小运价，确定供求关系，最大量的供应；2、划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；3、在剩余的运价表中重复1、2两步，直到得到初始基可行解。最小元素法的基本步骤B1B2B3B4产量（ai）A13113107A219284A37410

4、59销量（bj）3656例：B1B2B3B4产量（ai）A13113107A219284A3741059销量（bj）3656从表中找出最小运价“1”，最小运价所确定的供应关系为（A2，B1），在（A2，B1）的交叉格处填上“3”，并同时划去B1这一列。3B1B2B3B4产量（ai）A13113107A219284A3741059销量（bj）3656在表的未被划掉的元素中再找出最小运价“2”，最小运价所确定的供应关系为（A2，B3），即将A2余下的1个单位产品供应给B3，划去A2行的运价，划去A2行表

5、明A2所生产的产品已全部运出。31B1B2B3B4产量（ai）A1311341037A21392184A374610539销量（bj）3656这样一步步地进行下去，直到单位运价表上的所有元素均被划去为止。得到最终方案，见下表。最后在产销平衡表上得到一个调运方案，这一方案的总运费为86个单位。最小元素法各步在运价表中划掉的行或列是需求得到满足的列或产品被调空的行。一般情况下，每填入一个数相应地划掉一行或一列，这样最终将得到一个具有m+n-1个数字格（基变量）的初始基可行解。在供需关系格（i，j）处填入

6、一数字，刚好使第i个产地的产品调空，同时也使第j个销地的需求得到满足。填入一数字同时划去了一行和一列，那么最终必然无法得到一个具有m+n-1个数字格（基变量）的初始基可行解。应注意的问题为了使在产销平衡表上有m+n-1个数字格，这时需要在第行或第列此前未被划掉的任意一个空格上填一个“0”。填“0”格虽然所反映的运输量同空格没有什么不同；但它所对应的变量却是基变量，而空格所对应的变量是非基变量。调销地运量产地B1B2B3产量A190X1170X12100X13200A280X2165X2275X232

7、50销量100150200450用西北角法确定初始调运方案1001001005050200200得到初始调运方案为：x11=100，x12=100，x22=50，x23=200伏格尔法的基本步骤：伏格尔法1.计算每行、列两个最小运价的差；2.找出最大差所在的行或列；3.找出该行或列的最小运价，确定供求关系，最大量的供应；4.划掉已满足要求的行或(和)列，如果需要同时划去行和列，必须要在该行或列的任意位置填个“0”；5.在剩余的运价表中重复1~4步，直到得到初始基可行解。表4-1B1B2B3B4产量（

8、ai）A13113107A219284A3741059销量（bj）3656计算各行各列的两最小元素差。B1B2B3B4两最小元素之差(R1)A1311310A21928A374105两最小元素之差(C1)1301125选出差额的最大值5，选择它所在B2中最小元素4，可确定A3的产品先供应给B2，及把B2的销量6全部给A3B2。同时将运价表B2列数字划去。B1B2B3B4产量R1A131131070A2192841A37410591销量3656C125136分别计算出各