Об универсальной организации вложенныхциклов на примере сегментации транспортной задачи

В теории исследования операций и методов оптимизации выделяются так называемые транспортные задачи (ТЗ) как в классическом, так и в различных модифицированных вариантах. Суть этой задачи заключается в поиске оптимального в смысле минимизации полных затрат на перевозку однотипных грузов от N производителей c различными мощностями к M потребителям с различными объемами запросов при известных затратах на перевозки по различным участкам { a ij }.

ТЗ известна около 100 лет и допускает целый ряд способов решения, как излагавшихся в [2], так и обсуждаемых ниже.

ТЗ обычно решаются методами линейного программирования и широко применяются в логистике, планировании поставок и распределении ресурсов. Выбор подходящего алгоритма зависит от размеров M*N матрицы спроса-предложения, требований к точности и вычислительной эффективности.

Известно несколько алгоритмических подходов, каждый из которых имеет свои преимущества и недостатки. Выбор оптимального метода зависит от размера задачи, наличия дополнительных ограничений. Эти подходы обеспечивают высокую точность и гибкость , однако для больших размеров эффективны методы минимальной стоимости и методы разбиения. В дальнейшем развитие направлено на интеграцию этих подходов с параллельными вычислениями и комбинированными алгоритмами, чтобы обеспечить быстрые и надёжные решения даже при сложных ограничениях.

Современные требования к эффективности и гибкости логистических систем привели к расширению классической модели. Важными расширениями являются ТЗ с центрами расщепления, ограничениями по маршруту, многокомпонентной поставкой, динамическими изменениями спроса-предложения и стохастическими параметрами. Каждое из этих расширений влечёт за собой новые сложности: необходимость введения искусственных переменных, добавление ограничений на ребра графа, решение систем линейных уравнений с несколькими потоками, а также учёт неопределённости и времени.

В результате возникло множество специализированных алгоритмов, способных эффективно решать расширенные задачи. Несмотря на это, существует потребность в систематическом обзоре существующих методов, их сравнительном анализе и формулировке рекомендаций по выбору подходящего алгоритма в зависимости от конкретных ограничений и размеров задачи.

Кратко опишем существующие методы. Для небольших и средних ТЗ наиболее эффективным сочетанием является метод Фогеля , который обеспечивает быстрое и точное решение без сложной реализации. Выбор конкретного метода зависит от конкретных ограничений задачи, доступных вычислительных ресурсов и требований к точности.

Классический симплекс-метод для ТЗ основан на принципе построения начального базисного решения, (например, по правилу «северо-западного угла») и последующего улучшения через циклические операции. Преимущества этого метода заключаются в быстроте получения решения для небольших и средних размеров и использовании структуры задачи. Ограничение в том, что требуется начальное базисное решение; в худшем случае может иметь экспоненциальную зависимость сложности [5; 6].

Алгоритм наименьшей стоимости основан на принципе представления ТЗ в виде сети с вершинами (поставщиками и потребителями) и центральным узлом; поиске потока с минимальной стоимостью (например, с помощью алгоритма Дейкстры с приоритетной очередью). Преимущество — в возможности использовать готовые библиотеки сетевого потока; масштабируется на большие сети, ограничение в требовании более сложной модели (потоки, ограничения на ребра).

Метод потенциалов является модификацией симплекс-метода решения задач линейного программирования применительно к ТЗ. Он позволяет, отправляясь от некоторого допустимого решения , получить оптимальное решение за конечное число шагов . Основан на принципе предпочтений строк/столбцов по разнице между двумя наименьшими стоимостями с дальнейшим применением транспортного симплекс-метода. Преимущество — в быстроте приближения, по этой причине частое использование в качестве начального решения, однако не гарантирует оптимальность.

Ступенчатый метод (метод циклов) Используется для улучшения плана в случае его неоптимальности. В свободной ячейке строится цикл и перераспределяются поставки для уменьшения общей стоимости. Проводится анализ циклов в матрице после получения базисного решения для локальных улучшений. Этот метод позволяет улучшать решение до оптимального, однако требует полного перебора циклов, хотя обычно быстро сходится.

Модифицированный метод распределений ос но ван на принципе использования индексов (U- и V-потенциалов) для оценки потенциалов и последующего улучшения решения. Его преимущество — в достаточно быстрой сходимости и широком применении в практике, однако сильно зависит от степени корректности начальных шагов.

Итеративные алгоритмы основаны на принципе задания начального приближения (например, случайного распределения) и корректировки через линейные программные шаги. Преимущество заключается в возможности комбинировать их с другими методами, а ограничение — в возможном требовании многих итераций для сходимости.

Генетические (эволюционные) методы основаны на принципе поиска оптимального решения в пространстве распределений через специальные алгоритмы, они шире по области применения (например, с дополни- тельными ограничениями), однако не гарантируют глобальную оптимальность решения

Смешанные целочисленные приемы программирования добавляют целочисленные ограничения (например, целочисленность поставок товаров). Они позволяют решать задачи с дискретными переменными, однако подходят лишь для небольших размеров задач.

Метод simplex для случая сегментации ТЗ реализован А. С. Удовиченко на языке Python при помощи библиотек numpy и scipy :

Алгоритм:

• 1.    Ищутся любые «самодостаточные» группы (subset-sum + backtracking).

• 2.    Для каждой найденной группы формируется подзадача и затем решается.

• 3.    Выводятся решения каждой подзадачи и их сумма.

Функция “_find_balanced_groups” ищет любые подмножества производителей и потребителей, где сумма поставок равна сумме потребностей. Для небольших их наборов она использует полный перебор подсетов, а для больших — ограничивает глубину поиска, чтобы избежать чрезмерно сложных вычислений.

При помощи линейного программирования (scipy.optimize.linprog).

“solve_transport_subproblem” формирует линейную задачу и решает её с помощью “linprog” (метод “simplex”). Возвращается матрица распределения и общая стоимость

“segment_and_solve” разбивает исходную задачу на найденные группы, решает каждую подзадачу отдельно и сохраняет решения в глобальной матрице распределения для удобства просмотра.

Ограничения метода:

Для больших задач (несколько сотен производителей/потребителей) поиск групп может стать узким местом. В таком случае можно применить более продвинутые эвристики (например, жадный алгоритм разбиения по суммам, кластеризация) или использовать MILP для поиска оптимального разбиения.

Общим признаком практически всех перечисленных методов является то, что их трудоемкость сильно возрастает с увеличением числа участников. Поэтому является актуальным поиск возможностей сегментации ТЗ [1], когда некоторая часть производителей может точно обеспечить суммарные запросы части потребителей, что позволяет разбить исходную задачу на несколько независимых, более мелких подзадач. При значительных размерах исходной ТЗ выявление таких подзадач «вручную» становится довольно трудоемким, желательно эти комбинаторные поиски осуществлять с помощью специального компьютерного алгоритма.

Поскольку актуальность такого подхода высока, известны попытки его реализации, например, где сначала ищут любые «самодостаточные» группы (сумма поставок равна сумме потребностей) с помощью функций “find_balanced_groups”. Для небольших наборов используется полный перебор «подсетов», а для больших — ограничивается глубина поиска, чтобы избежать объемных вычислений. Для больших задач (несколько сотен производителей или потребителей) поиск групп может стать узким местом.

Поэтому здесь предложены пути прямого решения ТЗ с помощью достаточно простой и «прозрачной» сегментации без использования не всегда доступных и недостаточно изученных процедур. Разработке таких алгоритмов посвящена данная работа, кратко изложенная в [4].

Алгоритм предполагает 2 этапа:

1-й этап . Сначала требуется создать множество (2 N -1 (или 2 M -1)) занумерованных «фильтрующих» N - (или M)- мерных векторов (ФВ), состоящих из нулей и единиц, после попарного перемножения элементов которых на элементы вектора мощностей (и емкостей) подобно скалярному произведению получаются пробные выборки элементов таблицы ТЗ меньших размеров.

Упорядоченная система (матрица) ФВ размером ((2 ^N -1), N ) сначала содержит только нули, затем поочередно (в цикле) на все N позиций устанавливается первая “ a ” единица, сначала как одиночная (единственная в ФВ:), затем (в новом вложенном цикле) справа от нее на каждую из свободных позиций до N -й включительно поочередно устанавливаются вторые в ФВ “ b ” единицы. Далее после вторых единиц устанавливаются третьи в ФВ “ c ” единицы, также сначала как одиночные, после чего в очередном вложенном цикле везде справа от третьих единиц устанавливаются четвертые единицы « d» и т.д.

При создании очередного ФВ всегда сразу ему присваивается увеличивающийся на единицу порядковый номер ФВ в системе. Процесс завершается, когда последняя установленная единица оказывается на N- й позиции в ФВ.

В табл. 1 представлен пример реализации 1-го этапа предложенного алгоритма для создания ФВ с упорядоченной установкой (слева направо) первых « а », вторых « b », третьих « с » единиц в трехпозиционных ( N =3) ФВ.

Таблица 1

Пример построения системы ФВ для трехпозиционного

(трехразрядного) вектора

Порядковый номер создаваемого ФВ	1 -я позиция в ФВ	2-я позиция в ФВ	3-я позиция в ФВ
№ 1	1 a
№ 2		1 a
№ 3			1 a
№ 4	1 a	1 b
№ 5	1 a		1 b
№ 6		1 a	1 b
№ 7	1 a	1 b	1 c

2-й этап. Для каждой из усеченных таким образом выборок мощностей (и емкостей) подсчитывается суммарное значение их элементов, в случае их равенства выделяется малая замкнутая подзадача. В оставшейся части ТЗ можно снова попытаться этим же методом найти новую малую подзадачу (либо она сразу выделяется алгоритмом), что приводит к фрагментации ТЗ с уменьшением объема работы по решению ТЗ.

Так, при A = ( 30,10,20 ), В Г = ( 10,10,40 ) алгоритм выбирает следующие возможные комбинации ФВ (табл. 2)

Таблица 2

Пример подлежащей фрагментации ТЗ			размером (3*3)
A IB	10	10	40
30	an	a 12	a 13
10	a 21	a 22	a 23
20	а з1	а з2	a 33

Для производителей и потребителей в ТЗ из примера табл. 2 с помощью построенных систем ФВ алгоритм выделяет следующие варианты замкнутых подзадач (табл. 3)

Таблица 3

Пример выделенных с помощью ФВ подзадач ТЗ размером (3*3) (табл. 2)

Производители			Потребители
1	0	1	0	1	1
1	0	1	1	0	1
1	1	0	0	0	1
0	0	1	1	1	0
0	1	0	1	0	0
0	1	0	0	1	0

Рассмотренный метод вложенных циклов для построения «фильтрующих» векторов с монотонно увеличивающимися номерами позиций прост и нагляден. Однако на этом пути при изменении числа участников (производителей или потребителей), т. е. соответствующих длин векторов, требуется построение новой программы под новое число вложенных циклов.

Поэтому здесь предлагается рассматривать «фильтрующие» векторы в виде N -позиционных ( N – число участников) 2 ^N -1 чисел в N -ричной системе счисления со значениями:

a

s , j

= E

Z

- N * E N^J- 1

Z

N ^j

+1

для j- й позиции s -го ФВ. Единица в конце выражения добавлена потому, что в N -ричной системе счисления используются числа от 0 до ( N -1), в то время как позиции (разряды) в N -разрядном числе должны нумероваться от 1 до N . Здесь функция E[…] — «антье» (entier) — означает выбор наибольшего целого, не превосходящего указанного в скобках аргумента. Каждый выделяемый таким образом разряд соответствует счетчику конкретного вложенного цикла в первом методе.

Среди полученных таким образом ФВ следует отбросить, например, те, у которых значения в отдельных позициях не обнаруживают строго монотонного роста (возможно, наоборот, строго монотонное убывание). Числа в отобранных ФВ указывают места (позиции) расположения единиц. Для трехмерного примера (табл. 1) это векторы: 1, 2, 3, 12,13, 23, 123.

Множество этих ФВ для вектора мощностей { A i } представляет собой выборки для сравнения с аналогично полученными выборками потребностей { B j }и фрагментации, т.е. выбора малых замкнутых подзадач в исходной ТЗ (см. 2-й этап в изложенном ранее методе с вложенными циклами).

Существенно, что на этом пути можно работать с одной неизменной программой, в которой остается лишь соответствующим образом изменять числовые значения параметров N и M (количество производителей или потребителей).

Представление ряда натуральных чисел в N -ричной системе счисления создает пространство с равномерным распределением. С его помощью можно организовать, например, вычисление определителей произвольного порядка «по определению» [3], когда требуется перебрать и просуммировать все возможные произведения N элементов матрицы, в которых ровно по одному разу (без повторений) представлены каждая строка и каждый столбец со знаковым коэффициентом, равным минус единице в степени числа «нарушений порядка» по одному из измерений после упорядочения по другому измерению. Для этого из всех N -ричных чисел требуется исключить те, которые содержат повторяющиеся значения в разрядах.

Заключение

Предложено два пути автоматической фрагментации ТЗ (выбор малых замкнутых подзадач ТЗ произвольных размеров). При этом указан общий путь перехода от задач с большим количеством вложенных циклов к одномерной задаче с единственным переменным параметром, соответствующим количеству вложенных циклов.