表上作业法例题

运输问题及表上作业法运输问题及其数学模型产销平衡问题的表上作业法运输问题解的讨论产销不平衡运输问题运输问题及其数学模型下表为调运同一种物资的物资调运表收站发站B1B2…Bn发量A1C11C12…C1na1A2C21C22…C2na2AmCm1Cm2…Cmnam收量b1b2…bn收站收量发站发量的单位运价运往表示从jiijBAc问题：在满足供需要求的前提下，如何安排调运计划，可使总运费最小。该问题便称作运输问题。若，则称作产销平衡问题，否则称为产销不平衡问题。njjmiiba11收站发站B1B2…Bn发量A1C11C12…C1na1A2C21C22…C2na2AmCm1Cm2…Cmnam收量b1b2…bn数学模型：的数量调往表示由设jiijBAx11x12xnx121x22xnx21mx2mxmnx，则有V:ijijxcnj1mi1zmins.t.),,2,1(1miaxinjij),,2,1(1njbxjmiij),,1;,,1(0njmixijV:ijijxcmi1zmins.t.),,2,1(1miaxinjij),,2,1(1njbxjmiij),,1;,,1(0njmixijnj1的线性规划问题个约束个变元，nmnmmnmmnnxxxxxxxxx2122221112111111111a2a111ma1111b1112b111nb)()(mnnmA系数矩阵)1()(~mnnmA增广矩阵说明：1)~()()1(nmArAr性无关行组成的行向量组都线中任意1)2(nmA产销平衡问题的表上作业法表上作业法：在前述的运输调运表上直接计算而得到的最优调运方案的方法。表上作业法的算法步骤流程图：开始给出初始运输方案结束检验运输方案是否最优改进运输方案yesno（1）闭回路法（2）位势法例1给出下面的运输问题的最优解。收发B1B2B3B4发量A13113107A219284A3741059收量36563146386首先(最小元素法)、Vogel法给出初始运输方案其次(位势法、闭回路法)检验初始运输方案3收发B1B2B3B4发量A13113107A219284A3741059收量3656Vogel法给出初始方案25130115633237675221081021收发B1B2B3B4发量A1311310752A21928431A374105963收量3656851u2u3u1v2v3v4v01u33v104v22u53u31v92v位势法检验初始运输方案53u22u01u104v33v92v31v收发B1B2B3B4发量A1311310752A21928431A374105963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A13113107052A21928431A374105963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A131131070252A21928431A374105963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A131131070252A219284321A374105963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A131131070252A2192843211A374105963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A131131070252A2192843211A3741059963收量36568553u22u01u104v33v92v31v收发B1B2B3B4发量A131131070252A2192843211A374105996123收量365685闭回路是指从有运量表上某一空格出发，水平或竖直直行，只有遇到有运量的方格方可拐直角(也可不拐)，拐来拐去，若可以回到出发的空格的线路，称为空格闭回路。闭回路法法给出初始方案收发B1B2B3B4发量A1311310743A21928431A374105963收量3656+-+-收发B1B2B3B4发量A13113107143A21928431A374105963收量3656+-+-收发B1B2B3B4发量A131131071243A21928431A374105963收量3656+-+-+-收发B1B2B3B4发量A131131071243A219284311A374105963收量3656+-+-收发B1B2B3B4发量A131131071243A219284311-1A374105963收量3656-+-+-+收发B1B2B3B4发量A131131071243A219284311-1A37410591063收量3656-+-+收发B1B2B3B4发量A131131071243A219284311-1A3741059106123收量3656调整运输方案+-+-收发B1B2B3B4发量A131131071252A219284311A3741059106123收量3656调整运输方案-收发B1B2B3B4发量A1311310752A21928431A374105996123收量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”,这时所得的解为退化解.),(ji),(li),(lk),(jk),(ji),(li),(lk),(jkilxklxkjxkjikxxa调量调整axkla0产销不平衡运输问题表上作业法是在“产销平衡”这一前提下进行的,对于产销不平衡问题而言,可虚设产地或销地(它们的单位运价皆为零),以使最终产销平衡.njjmiiba11产量大于销量0),,1(),,1(.min:1111ijjmiijinjijminjijijxnjbxmiaxtsxcV0),,1(),,1(.min:111111111ijnjjmiimiinjmiijinjijminjijijxbaxnjbxmiaxtsxcVnjjmiiba11产量小于销量0),,1(),,1(.min:1111ijjmiijinjijminjijijxnjbxmiaxtsxcV0),,1(),,1(.min:111111111ijjmiijmiinjjnjjminjijminjijijxnjbxabxmiaxtsxcV