The transportation problem revisited / S. Haddadi in Journal of the operational research society (JORS), Vol. 63 N° 7 (Juillet 2012)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 63 N° 7 (Juillet 2012) . - pp. 1006–1009 Titre : The transportation problem revisited : preprocessing before using the primal–dual algorithm Type de document : texte imprimé Auteurs : S. Haddadi, Auteur ; O. Slimani, Auteur Année de publication : 2012 Article en page(s) : pp. 1006–1009 Note générale : Operational research Langues : Anglais (eng) Mots-clés : Linear programming Methodology Optimization Transportation problem Primal–dual algorithm Index. décimale : 001.424 Résumé : We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v63/n7/abs/jors2011106a.html [article] The transportation problem revisited : preprocessing before using the primal–dual algorithm [texte imprimé] / S. Haddadi, Auteur ; O. Slimani, Auteur . - 2012 . - pp. 1006–1009. Operational research Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 63 N° 7 (Juillet 2012) . - pp. 1006–1009 Mots-clés : Linear programming Methodology Optimization Transportation problem Primal–dual algorithm Index. décimale : 001.424 Résumé : We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v63/n7/abs/jors2011106a.html

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire