表上作业法例题

表上作业法例题表上作业法例题 运输问题及其数学模型运输问题及其数学模型下表为调运同一种物资的物资调运表 收站 发站B1B2Bn发量发量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam收量收量b1b2bn收站收站收量收量发站发站发量发量问题问题：在满足供需要求的前提下，如何安排调运计划，：在满足供需要求的前提下，如何安排调运计划，可使总运费最小。可使总运费最小。该问题便称作该问题便称作运输问题运输问题。若，。若，则称作则称作产销平产销平衡问题衡问题，否则，否则称为称为产销不平产销不平衡问题衡问题。收站 发站B1B2Bn发量发量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam收量收量b1b2bn数学模型数学模型：，则有V:s.t.V:s.t.1 1 11 1 11 1 11 1 11 1 11 1 1说明：说明：产销平衡问题的表上作业法产销平衡问题的表上作业法 表上作业法表上作业法：在前述的运输调运表上直接计算而得到的：在前述的运输调运表上直接计算而得到的最优调运方案的方法。最优调运方案的方法。表上作业法的算法表上作业法的算法步骤流程图步骤流程图：开始开始给出初始给出初始运输方案运输方案结束结束 检验检验 运输方案是否运输方案是否 最优最优改进运改进运输方案输方案yesno(1)西北角法西北角法(2)最小元素最小元素法法(3)Vogel法法（1）闭回路法）闭回路法（2）位势法）位势法 例例1 给出下面的运输问题的最优解。给出下面的运输问题的最优解。收收发发B1B2B3B4发量发量A13113107A219284A3741059收量收量3656首先首先(最小元素法最小元素法)、Vogel法给出初始运法给出初始运输方案输方案其次其次(位势法、闭回路法位势法、闭回路法)检验初始运输方案检验初始运输方案 收收发发B1B2B3B4发量发量A13113107 A219284 A3741059 收量收量3656Vogel法给出初始方案法给出初始方案25130115327672210810 收收发发B1B2B3B4发量发量A13113107 5 2A219284 3 1A3741059 6 3收量收量3656位势法检验初始运输方案位势法检验初始运输方案 收收发发B1B2B3B4发量发量A13113107 5 2A219284 3 1A3741059 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 5 2A219284 3 1A3741059 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 1A3741059 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1A3741059 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 9 6 3收量收量3656 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 9 6 12 3收量收量3656闭回路闭回路是指从是指从有运量表上某有运量表上某一空格出发，一空格出发，水平或竖直直水平或竖直直行，只有遇到行，只有遇到有运量的方格有运量的方格方可拐直角方可拐直角(也也可不拐可不拐)，拐来，拐来拐去，若可以拐去，若可以回到出发的空回到出发的空格的线路，称格的线路，称为空格为空格闭回路闭回路。闭回路法法给出初始闭回路法法给出初始方案方案 收收发发B1B2B3B4发量发量A13113107 4 3A219284 3 1A3741059 6 3收量收量3656+-+-收收发发B1B2B3B4发量发量A131131071 4 3A219284 3 1A3741059 6 3收量收量3656+-+-收收发发B1B2B3B4发量发量A131131071 2 4 3A219284 3 1A3741059 6 3收量收量3656+-+-+-收收发发B1B2B3B4发量发量A131131071 2 4 3A219284 3 1 1A3741059 6 3收量收量3656+-+-收收发发B1B2B3B4发量发量A131131071 2 4 3A219284 3 1 1 -1A3741059 6 3收量收量3656-+-+-+收收发发B1B2B3B4发量发量A131131071 2 4 3A219284 3 1 1 -1A3741059 10 6 3收量收量3656-+-+收收发发B1B2B3B4发量发量A131131071 2 4 3A219284 3 1 1 -1A3741059 10 6 12 3收量收量3656调整运输方案调整运输方案+-+-收收发发B1B2B3B4发量发量A131131071 25 2A219284 3 1 1A3741059 10 6 12 3收量收量3656调整运输方案调整运输方案-收收发发B1B2B3B4发量发量A13113107 5 2A219284 3 1A3741059 9 6 12 3收量收量3656022-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”,这时所得的解为退化解这时所得的解为退化解.产销不平衡运输问题产销不平衡运输问题 表上作业法是在表上作业法是在“产销平衡产销平衡”这一前提下进行的这一前提下进行的,对于产对于产销不平衡问题而言销不平衡问题而言,可虚设产地或销地可虚设产地或销地(它们的单位运价皆为零它们的单位运价皆为零),以使最终产销平衡以使最终产销平衡.结束语结束语谢谢大家聆听！谢谢大家聆听！29