运筹学运输问题(补充)

2019/8/111运筹学OperationsResearch§1运输问题及其数学模型运输问题（TP，TransportationProblem）：11.mnijijab其中2019/8/112运筹学OperationsResearch供需-运费表：问：应如何组织运输，才能既满足供需关系，又使得运费最省？2019/8/113运筹学OperationsResearch的货物的数量，运往收点从发点解：令jiijBAxnjmi,,2,1,,,2,11111()min,1,2,,..,1,2,,0,1,2,,;1,2,,mnijijijnijijmijjiijTPfcxxaimstxbjnximjn▍2019/8/114运筹学OperationsResearchTmnmmnnxxxxxxxxxx),,,,,,,,,,,,(212222111211令mnmmnncccccccccc212222111211Tnmbbbaaad),,,,,,,(21212019/8/115运筹学OperationsResearch1001001000100100100010010011110000000001110000000001112121212222111211nmmmmDxxxxxxxxxmnmmnn则()min..0TTPfcxDxdstx2019/8/116运筹学OperationsResearch基：.1)(BnmDmnnm阶非奇异子矩阵的任一基的构造：.1得一个基个线性无关的列向量即下的矩阵中选取中删去任一行，再从剩从nmD结论：运输问题总有最优解.2019/8/117运筹学OperationsResearch在实际计算时，鉴于运输问题的特殊性质，其求解过程并不借助于单纯形表，而是借助于运输表来实现.2019/8/118运筹学OperationsResearch格子格子表（集）：对应关系：ijijijPDxt的列向量变量格子令,TS}.|{StPDijijS规定：.)()(关相中的各列向量线性无关相线性无格子集SDS2019/8/119运筹学OperationsResearch.1||记作：称为基本格子集，的线性无关的格子集定义SnmS).()()(1}|{ijijijijijijtxtxBTPnmtPD非基变量为，，且基变量为的一个基即得矩阵去掉一个多余的行个列向量作成的中的是基本格子集时，当令ijijtxdDx,0即得基解01dBx2019/8/1110运筹学OperationsResearch§2初始基可行解运输问题的求解过程并不象一般线性规划问题一样借助于单纯形表，而是借助于运输表来实现；但其算法在理论基础、基本思想、算法步骤等各方面都和单纯形法是一致的.供需平衡型运输问题：njjmiiba112019/8/1111运筹学OperationsResearch一.西北角法基本思想：优先安排运输表中的西北角处的格子（即编号小的格子）对应的发点与收点之间的运输业务.使用条件：已知d2019/8/1112运筹学OperationsResearch2019/8/1113运筹学OperationsResearch1()3,4,(15,25,5,5,15,15,10),().TTPmndTP例设中，求的一个基可行解解：基本格子集为},,,,,{342423221211tttttt2019/8/1114运筹学OperationsResearch相应的基本可行解为,5,5,15,5,10,5342423221211xxxxxx0ijx其它▍二最小元素法基本思想：优先安排运输表中的单位运费最小的格子对应的发点与收点之间的运输业务（当最小单位运费不唯一时，可任选其一）.使用条件：已知dc,2019/8/1115运筹学OperationsResearch2019/8/1116运筹学OperationsResearch例2求（TP）的一个基本可行解，其中,4,3nm,)10,15,15,5,5,25,15(Td18161462097121120610c解：基本格子集为},,,,,{312423141211tttttt2019/8/1117运筹学OperationsResearch相应的基可行解为,5,10,15,0,15,0312423141211xxxxxx0ijx其它▍Ex:求平衡型运输问题：5183,(12,14,4,9,10,11),241367Tmndc的基初始可行解（用两种方法）.2019/8/1118运筹学OperationsResearch三沃格尔（Vogel）法基本思想：若罚数的值不大，当不能按最小单位运价安排运输时造成的运费损失不大；反之，如果罚数的值很大，不按最小运价组织运输就会造成很大损失，故应尽量按最小单位运价安排运输。使用条件：dc,步骤2019/8/1119运筹学OperationsResearch1.分别计算运输表中运价的行罚数和列罚数，并分别填入运输表右边和下边的罚数栏里；2.从所有罚数中找出最大者，选中罚数所在行（或列）中运价最小对应的格，填入尽可能大的运输量；3.当供应量已用完（或需求量已满足），划去相应行（或列）；4.重复上述步骤，直到所有行和列都被划掉.2019/8/1120运筹学OperationsResearch§3最优性的检验对运输问题njmixnjbxmiaxtsxcfTPijmijijinjijminjijij,,2,1;,,2,1,0,,2,1,,,2,1,..min:)(11112019/8/1121运筹学OperationsResearch,,1,2,,;1,2,,ijuvimjn引入对偶变量，得对偶问题为11()max..,1,2,,;1,2,,mniijjijijijDPhaubvstuvcimjn2019/8/1122运筹学OperationsResearch()TPB的一个基本格子集，对应一个基，相应的检验数为ijijijTijijTBijtcPycPBcr,1TTBnmBcvvuuy)(111其中2019/8/1123运筹学OperationsResearch.),,,(),,,(,00,212111vuyvvvvuuuutcvuuuvuTmTmijijjiji，即，得，，解可令是自由变量，定义().uTPv称为关于基本子集的位势格2019/8/1124运筹学OperationsResearchijijjiijnmijijTTijijTijijTijijTBijtcvucjivvvuuucPvucPvucPycPBcr,00100100),,,,,,,(),(21211于是，检验数为2019/8/1125运筹学OperationsResearch小结先求位势：ijijjitcvuu,01再求检验数：ijijjiijtcvur,2019/8/1126运筹学OperationsResearch例1求（TP）的一个基本可行解，其中,4,3nm,)10,15,15,5,5,25,15(Td18161462097121120610c解：基本格子集为},,,,,{312423141211tttttt2019/8/1127运筹学OperationsResearch相应的基可行解为,5,10,15,0,15,0312423141211xxxxxx0ijx其它求位势：求检验数：▍2019/8/1128运筹学OperationsResearch同单纯形法一样，若所有检验数均非负，则当前的基可行解即为最优解；否则，应改进之（转轴），以使之更优..,,,,,,,,,,,,2121132222111是一个闭回路则称互异，互异，，其中中的诸格子排列为，若可将设定义kkjijijijijijijjjiiittttttTkkk闭回路的特点：任意两个相邻的格子的行指标相同时，其列指标必不相同；列指标相同时，其行指标必不相同.即任意两个相邻格子的行（列）指标不能同时相同，也不能同时不同.2019/8/1129运筹学OperationsResearch如.}{)(emmapqpqpqtttTPL，且唯一一个闭回路中必存在，则的一个基本格子集，是设},,,,,{333124211413tttttt2019/8/1130运筹学OperationsResearch例1（续）},,,,,{312423141211tttttt取33ttpq取32ttpq▍2019/8/1131运筹学OperationsResearch..}{,,)(1h和个格子应分属的处在同一行，列的两；：和划分为按如下规则将中的闭回路为，相应的基本开行解为的一个基本格子集为设pqpqpqtttxTPT令ijijtx|min{rkx}}{\}){(rkpqtt().TPx则仍是的一个基本格子集，且是相应的基本可行解▍2019/8/1132运筹学OperationsResearch例1（续）},,,,,{312423141211tttttt取32ttpq划分:2019/8/1133运筹学OperationsResearch315}5,15min{x修正：▍2019/8/1134运筹学OperationsResearch§4算法步骤max2019/8/1135运筹学OperationsResearch例求解运输问题：4,3nmTd)10,15,15,5,5,25,15(18161462097121120610c解：作运输表，并利用最小元素法解之.2019/8/1136运筹学OperationsResearch基本格子集为},,,,,{343124231412tttttt基本可行解为,0,5,10,15,0,15343124231412xxxxxx0ijx其余求位势和检验数：228}9,1,8,4,20,11max{rrpq2019/8/1137运筹学OperationsResearch中找闭回路在}{pqt修正：2410}10,15min{x2019/8/1138运筹学OperationsResearch求检验数：01}1,1,8,12,12,11max{pqr.00,5,15,10,10,5343123221412ijxxxxxxx，其余最优解为最优值为37501856159107101156▍