表上作业法例题.ppt

,运输问题及表上作业法,运输问题及其数学模型,产销平衡问题的表上作业法,运输问题解的讨论,产销不平衡运输问题,运输问题及其数学模型,下表为调运同一种物资的物资调运表,问题：在满足供需要求的前提下，如何安排调运计划，可使总运费最小。,数学模型：,，则有,V:,s.t.,1 1 1,1 1 1,1 1 1,1 1 1,1 1 1,1 1 1,说明：,产销平衡问题的表上作业法,表上作业法：在前述的运输调运表上直接计算而得到的最优调运方案的方法。,表上作业法的算法步骤流程图：,给出初始运输方案,改进运输方案,yes,no,例1 给出下面的运输问题的最优解。,首先(最小元素法)、Vogel法给出初始运输方案,其次(位势法、闭回路法)检验初始运输方案,Vogel法给出初始方案,2,5,1,3,0,1,1,5,3,2,7,6,7,2,2,10,8,10,位势法检验初始运输方案,闭回路法法给出初始方案,+,-,+,-,+,-,+,-,+,-,+,-,+,-,+,-,+,-,-,+,-,+,-,+,-,+,-,+,+,-,+,-,-,0,2,2,-,1,运输问题解的讨论,对于运输问题的解的讨论，如同单纯形法：,1.惟一解情形,对于表上作业法来讲，若所有空格（非基变元）检验数均小于零，则该问题有惟一解.,2.多解情形,对于表上作业法来讲，若某个空格（非基变元）检验数为零，则该问题有多解.,3.退化解情形,(1)在填(Ai,Bj)格时,若供与需(发与收)量相同,填后应同时划去i行与j列,为使表上有m+n-1格有运量,则需在划去的行或列的某空格处填上“0”,这时所得的解为退化解.,(2)空格(Ai,Bj)处,若调出格(Ak,Bj)与(Ai,Bl)运量相等xkj=xil,调后调整量为a=xkj=xil出现两个空格,此时应一格变空格,另一格填上“0”,这时所得的解为退化解.,产销不平衡运输问题,表上作业法是在“产销平衡”这一前提下进行的,对于产销不平衡问题而言,可虚设产地或销地(它们的单位运价皆为零),以使最终产销平衡.,