表上作业法例题[青松教学]

1、运输问题及表上作业法运输问题及表上作业法 运输问题及其数学模型运输问题及其数学模型 产销平衡问题的表上作业法产销平衡问题的表上作业法 运输问题解的讨论运输问题解的讨论 产销不平衡运输问题产销不平衡运输问题 运输问题及其数学模型运输问题及其数学模型下表为调运同一种物资的物资调运表 收站 发站B1B2Bn发量发量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam收量收量b1b2bn收站收站收量收量发站发站发量发量的单位运价运往表示从jiijBAc问题问题：在满足供需要求的前提下，如何安排调运计划，：在满足供需要求的前提下，如何安排调运计划， 可使总运费最小。可使总运费最

2、小。该问题便称作该问题便称作运输问题运输问题。若，。若，则称作则称作产销平产销平衡问题衡问题，否则，否则称为称为产销不平产销不平衡问题衡问题。njjmiiba11 收站 发站B1B2Bn发量发量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam收量收量b1b2bn数学模型数学模型：的数量调往表示由设jiijBAx11x12xnx121x22xnx21mx2mxmnx，则有V:ijijxcnj 1mi 1zmins.t.), 2 , 1(1miaxinjij), 2 , 1(1njbxjmiij), 1;, 1(0njmixijV:ijijxcmi 1zmins.t.

3、), 2 , 1(1miaxinjij), 2 , 1(1njbxjmiij), 1;, 1(0njmixijnj 1的线性规划问题个约束个变元，nmnmmnmmnnxxxxxxxxx2122221112111 1 11 1 11a2a1 1 1ma1 1 11b1 1 12b1 1 1nb)()(mnnmA系数矩阵)1()(mnnmA增广矩阵说明：说明：1)()() 1 (nmArAr性无关行组成的行向量组都线中任意1)2(nmA 产销平衡问题的表上作业法产销平衡问题的表上作业法 表上作业法表上作业法：在前述的运输调运表上直接计算而得到的：在前述的运输调运表上直接计算而得到的最优调运方案的方

4、法。最优调运方案的方法。表上作业法的算法表上作业法的算法步骤流程图步骤流程图：开始开始给出初始给出初始运输方案运输方案结束结束 检验检验 运输方案是否运输方案是否 最优最优改进运改进运输方案输方案yesno(1) 西北角法西北角法(2) 最小元素法最小元素法(3) Vogel法法（1）闭回路法）闭回路法（2）位势法）位势法 例例1 给出下面的运输问题的最优解。给出下面的运输问题的最优解。 收收发发B1B2B3B4发量发量A13113107A219284A3741059收量收量36563146386首先首先(最小元素法最小元素法)、Vogel法给出初始运法给出初始运输方案输方案其次其次(位势法、

5、闭回路法位势法、闭回路法)检验初始运输方案检验初始运输方案3 收收发发B1B2B3B4发量发量A13113107 A219284 A3741059 收量收量3656Vogel法给出初始方案法给出初始方案25130115633237675221081021 收收发发B1B2B3B4发量发量A13113107 5 2A219284 3 1A3741059 6 3收量收量3656851u2u3u1v2v3v4v01u33v104v22u53u31v92v位势法检验初始运输方案位势法检验初始运输方案53u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A13113107 5 2

6、A219284 3 1A3741059 6 3收量收量36568553u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 5 2A219284 3 1A3741059 6 3收量收量36568553u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 1A3741059 6 3收量收量36568553u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1A3741059 6 3收量收量36568553u

7、22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 6 3收量收量36568553u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 9 6 3收量收量36568553u22u01u104v33v92v31v 收收发发B1B2B3B4发量发量A131131070 2 5 2A219284 3 2 1 1A3741059 9 6 12 3收量收量365685闭回路闭回路是指从是指从有运量表上某有运

8、量表上某一空格出发，一空格出发，水平或竖直直水平或竖直直行，只有遇到行，只有遇到有运量的方格有运量的方格方可拐直角方可拐直角(也也可不拐可不拐)，拐来，拐来拐去，若可以拐去，若可以回到出发的空回到出发的空格的线路，称格的线路，称为空格为空格闭回路闭回路。闭回路法法给出初始闭回路法法给出初始方案方案 收收发发B1B2B3B4发量发量A13113107 4 3A219284 3 1A3741059 6 3收量收量3656+- -+- - 收收发发B1B2B3B4发量发量A131131071 4 3A219284 3 1A3741059 6 3收量收量3656+- -+- - 收收发发B1B2B3B

9、4发量发量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-

10、 -+ +- -+ + 收收发发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 运输问题解的讨论运输问题解的讨论 对于运输问题的解的讨论，如同单纯形

11、法：对于运输问题的解的讨论，如同单纯形法： 1. 惟一解情形惟一解情形 对于表上作业法来讲，若所有空格（非基变元）检验数均对于表上作业法来讲，若所有空格（非基变元）检验数均小于零，则该问题有惟一解小于零，则该问题有惟一解. 2. 多解情形多解情形 对于表上作业法来讲，若某个空格（非基变元）检验数为对于表上作业法来讲，若某个空格（非基变元）检验数为零，则该问题有多解零，则该问题有多解. 3. 退化解情形退化解情形 (1) 在填在填(Ai,Bj)格时格时,若供与需若供与需(发与收发与收)量相同量相同,填后应同时填后应同时划去划去i行与行与j列列,为使表上有为使表上有m+n-1格有运量格有运量,则需

12、在划去的行或列则需在划去的行或列的某空格处填上的某空格处填上“0”,这时所得的解为退化解这时所得的解为退化解. (2) 空格空格(Ai,Bj)处处,若调出格若调出格(Ak,Bj)与与(Ai,Bl)运量相等运量相等xkj=xil,调后调整量为调后调整量为a= xkj=xil出现两个空格出现两个空格,此时应一格变空格此时应一格变空格,另一格另一格填上填上“0”,这时所得的解为退化解这时所得的解为退化解.),(ji),( li),(lk),(jk),(ji),( li),(lk),(jkilxklxkjxkjikxxa调量调整axkla0 产销不平衡运输问题产销不平衡运输问题 表上作业法是在表上作业法是在“产销平衡产销平衡”这一前提下进行的这一前提下进行的,对于产销对于产销不平衡问题而言不平衡问题而言,可虚设产地或销地可虚设产地或销地(它们的单位运价皆为零它们的单位运价皆为零),以以使最终产销平衡使最终产销平衡.njjmiiba11产量大于销量0), 1(), 1(.min:1111ijjmiijinjijminjijijxnjbxmiaxtsxcV0), 1(), 1(.min