Труды КНЦ (Технические науки) 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. Постановка и методы решения транспортной задачи Необходимо сформировать план перевозок, в котором при минимальных затратах товары будут доставлены потребителям и будут покрыты их потребности в данном продукте: Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей обычно применяются другие методы [9-11]. Для этого определяется опорный план и находится оптимальное решение посредством последовательных операций. Для нахождения опорного плана можно использовать методы, представленные ниже. Метод северо-западного угла (диагональный или улучшенный). В таблице необходимо заполнить верхнюю левую клетку самым крупным числом из доступных на данном шаге, то есть заполнение сводится к тому, что полностью вывозится груз из а, или полностью удовлетворяется потребность bj [12]. Метод наименьшего элемента. В данном методе задача сводится к максимальному уменьшению сторонних распределений продукции между потребителями. Это происходит следующим образом [13]: 1) выбирается клетка с наименьшей стоимостью из таблицы; 2) в нее заносится максимальное из доступных значений; 3) исключаются из рассмотрения строки и столбцы потребителей с полностью удовлетворенными потребностями, а также строки и столбцы поставщиков с полностью использованными товарами; 4) в случае наличия неисключенных строк и столбцов переход к пункту 1; 5) задача решена. Решение с помощью теории графов. Пусть имеется двудольный граф. В нем пункты потребления находятся в нижней части. К ним присоединен сток, также пропускная способность пункта потребления в сток равна потребности в продукте в этом пункте. Пункты производства находятся в верхней части. К ним присоединен исток. Пропускная способность рёбер из истока в каждый пункт производства равна запасу продукта в этом пункте. Ребра имеют бесконечную пропускную способность и цены за единицу потока Cj. В последствии необходимо решить задачу по поиску максимального потока минимальной стоимости (mincost maxflow). Постановка и методы решения задачи о максимальном потоке Задача о максимальном потоке состоит в поиске такого потока (рис. 2), что сумма потоков из истоков или стоков достигает максимального значения [13]. Рис. 2. Максимальный поток в транспортной сети. Числа обозначают потоки и пропускные способности Пусть есть G = (V, E) — транспортная сеть, которая представляет собой связанный, ацикличный, ориентированный граф; Е — множество ребер; s , t ЕѴ являются истоком и стоком с пропускной способностью с ■Е —R+; и,ѵ — вершины графа. Е”= 1 ХІ] = aj ’i = 1,2,....т; 'ZT=ixii = bJ,J = 1 ,2 ,., ^; YIj=iYIy=iCijxij ^ min . (3) (4) (5) © Шестаков А. В., Зуенко А. А., 2022 147