Труды КНЦ (Технические науки) 2/2022(13).

Труды Кольского научного центра РАН. Серия: Технические науки. 2022. Т. 13, № 2. С. 144-150. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2022. Vol. 13, No. 2. P. 144-150. Тогда математическая постановка задачи заключается в нахождении величины потока, в котором сумма потоков из источников максимальна: \f\ = ^Ls,v e v f s v ^ max. (6) Также, должны быть удовлетворены основные условия: поток по ребру не может быть больше, чем его пропускная способность; количество вещества, вытекающего из истока, совпадает с общим количеством вещества, поступающего в сток; поток \/\ должен быть положительным, в противном случае исток может оказаться стоком. Для решения задачи о максимальном потоке используются методы линейного программирования, основанные на симплекс-методе, алгоритм Форда — Фалкерсона, алгоритм Эдмондса — Карпа, алгоритм проталкивания предпотока, алгоритм Диница и т. д. Постановка и методы решения задачи коммивояжера Задача коммивояжера заключается в построении такого маршрута, при котором будет найдено минимальное расстояние между определенными парами городов при условии, что начальный город должен являться конечным, а также каждый город маршрут проходит строго единожды. Задача коммивояжера может быть смоделирована с помощью неориентированного взвешенного графа, где города являются вершинами графа, пути — ребрами графа, а расстояния между вершинами — весами ребер. Часто модель представляет собой полный граф (то есть каждая пара вершин соединена ребром). Если между двумя городами не существует пути, то ребру приписывается достаточно большой вес. Задачу коммивояжера можно описать как задачу целочисленного линейного программирования [14]. Пусть имеются города 1, ..., n и расстояние между городами > 0, где i — один город, j — другой. Таким образом основные переменные можно представить в виде: _ ( 1 —если х принадлежит маршруту из города і в город j Xli = {0 —если х не принадлежит маршруту из города і в город j, ( ) тогда задача состоит в минимизации суммарного пройденного расстояния: min £ ”= !£”*£,_,■=!Суху ; (8) а) £ ”=і,і *,-,*у = 1 b ) Z”=i,7- фі ,Х іі = 1 i j = 1,^ , n; (9) Y>iEQY>j*i,jEQXij < \0\ —1 VQC{1..... n } ,M> 2 . (10) Первый набор равенств (9a) требует, чтобы в каждый город прибывали ровно из одного другого города, а второй набор (9b) — чтобы из каждого города было отправление ровно в один другой город. Последнее ограничение (10) гарантирует, что никакое надлежащее подмножество Q не может сформировать подмаршрут, поэтому возвращаемое решение представляет собой один маршрут, а не объединение меньших маршрутов, иначе это приводит к экспоненциальному числу возможных решений. К простейшим методам решения задачи относятся: полный перебор, случайный перебор, жадные алгоритмы, метод ближайшего соседа, метод включения ближайшего города, метод самого дешёвого включения, метод минимального остовного дерева, метод имитации отжига. Алгоритмы решения, которые направленны на сокращения полного перебора, являются эвристическими, или «субоптимальными». Методы, использующие подобные алгоритмы, за разумное время способны дать приближенное решение. Методы точных алгоритмов позволяют находить решения достаточно быстро, однако это относится только к задачам малой размерности. Поэтому целесообразно использовать модификации алгоритма муравьиной колонии, метода ветвей и границ и метода генетических алгоритмов. Заключение Логистические информационные системы представляют собой автоматизированные системы управления логистическими процессами. Несмотря на высокую востребованность в промышленности эффективных методов решения логистических задач, а также достигнутый уровень элементной базы современных компьютеров, многие прикладные задачи логистики решаются с использованием эксклюзивных программных решений. Тем не менее, основу подобных решений, как правило, составляет развитие рассмотренных в статье математических постановок задач логистики. © Шестаков А. В., Зуенко А. А., 2022 148