Algoritmi de soluționare a problemelor neliniare de transport [Teză]

Abstract

Scopul lucrării: constă în soluționarea unui șir de probleme neliniare de transport de dimensiuni mari cu funcții concave de cost. Obiectivele cercetării: cercetarea problemelor de transport și a metodelor de soluționare a lor; elaborarea algoritmilor aproximativi pentru soluționarea problemelor neliniare de transport; elaborarea algoritmilor genetici pentru soluționarea în timp rezonabil a problemelor de transport de dimensiuni mari descrise de rețele cu una sau mai multe surse și una sau mai multe destinații cu funcții concave de cost; elaborarea algoritmilor genetici pentru soluționarea în timp rezonabil a problemelor de transport de dimensiuni mari descrise de rețele cu mai mulți indici și cu funcții concave de cost; testarea și estimarea timpului de execuție a algoritmilor propuși. Noutatea și originalitatea științifică: constă în obținerea rezultatelor noi de ordin teoretico- aplicativ care completează cele cunoscute deja în literatura de specialitate în domeniul problemelor neliniare de transport. Sunt soluționate problemele neliniare de transport cu doi, patru și cinci indici aplicând reduceri consecutive a problemelor neliniare de transport la probleme liniare; este codificată problema neliniară de transport cu o sursă și o destitinație, problema neliniară de transport cu o sursă și câteva destinații, problema neliniară de transport cu câteva surse și câteva destinații, problema neliniară de transport cu 4 indici și cea cu 5 indici pentru a putea fi aplicați algoritmi genetici astfel încât la decodificare să fie obținute soluții admisibile; sunt descriși operatorii de încrucișare și mutație a algoritmilor genetici astfel încât la decodificare se obțin soluții admisibile; este demonstrat practic faptul că fiecare din algoritmii propuși generează o soluție admisibilă locală în timp rezonabil. Rezultatul/rezultatele obținute care contribuie la soluționarea unei probleme științifice importante: consistă în identificarea metodelor de codificare a problemelor neliniare de transport fapt care a condus la crearea unor algoritmi genetici și a unor algoritmi bazați pe reducerea la probleme liniare pentru implementrea ulterioară în soluționarea problemelor aplicative.

Цель исследования: состоит в том, чтобы решить ряд нелинейных транспортных задач больших размеров с вогнутыми функциями стоимости. Задачи исследования: исследование транспортных задач и их методoв решения; разработка приближенных алгоритмов решения нелинейных транспортных задач; разработка генетических алгоритмов для решения за разумное время крупномасштабных транспортных задач, описываемых сетями с одним или несколькими источниками и одним или несколькими пунктами назначения с вогнутыми функциями стоимости; разработка генетических алгоритмов для решения за разумное время крупномасштабных транспортных задач, описываемых сетями с несколькими индексами и вогнутыми функциями стоимости; тестирование и оценка времени выполнения предложенных алгоритмов. Научная новизна и оригинальность: состоит в получении новых теоретико-прикладных результатов, дополняющих уже известные в специализированной литературе области нелинейных транспортных задач. Нелинейные транспортные задачи с двумя, четырьмя и пятью индексами решены путем применения последовательных сведений нелинейных транспортных задач к линейным задачам; была закодирована нелинейная транспортная задача с одним источником и одним стоком, нелинейная транспортная задача с одним источником и несколькими стоками, нелинейная транспортная задача с несколькими источниками и несколькими стоками, нелинейная транспортная задача с 4 и 5 индексами, так что, применяя генетические алгоритмы были получены допустимые решения во время декодирования; описаны операторы скрещивания и мутации генетических алгоритмов чтобы получить допустимые решения после декодирования; практически продемонстрировано что каждый из предложенных алгоритмов генерирует локально допустимое решение за разумное время. Полученные результаты, способствующие решению важной научной проблемы: состоит в определение методов кодирования нелинейных транспортных задач, что привело к разработке генетических алгоритмов и алгоритмов, основанных на сведении к линейным задачам для последующего внедрения при решении прикладных задач. The goal of the thesis: is to study and solve large-scale nonlinear transportation problems with concave cost functions. Research objectives: research of transport problems and methods of their solving; elaboration of approximate algorithms for solving non-linear transportation problems; elaboration of genetic algorithms for solving in a reasonable time the large-scale transportation problems described by networks with one or more sources and one or more destinations with concave cost functions; elaboration of genetic algorithms for solving in a reasonable time the large-scale transportation problems described by networks with several indices and concave cost functions; testing and estimating the execution time of the proposed algorithms. The scientific novelty and originality: consists in new theoretical and applicative results that complete those known from specialized literature in the domain of nonlinear transportation problems. The non-linear transportation problems with two, four and five indices were solved through the application of consecutive reductions of the non-linear problems to linear ones; the non-linear problems with a single source and destination, with a single source and several destinations, with several sources and several destinations, with 4 indices and with 5 indices were codified so that genetic algorithms could be applied and admissible solutions are obtained through decoding; the crossover and mutations operators of the genetic algorithms were described so that admissible solution are obtained through decoding; it has been practically proved that each of the proposed algorithms generates a local admissible solution in reasonable time. The obtained results which contribute to solve some important scientic problem: consists in indentification of methods of coding nonlinear transportation problems, which led to the creation of genetic algorithms and of algorithms based on reduction to a linear problem. These algorithms were then implemented to solve applicative problems.