Software & Systems

В данной статье рассматривается задача определения оптимальных планов назначения на базе транспортной задачи (ТЗ) о групповом назначении (ГН). В отличие от существующей ТЗ с фиксированными добавками по критерию минимума стоимости [1] предлагается постановка по максимизации суммы эффективности ГН.

В исследовании [2] показано, что ε-оптимальная версия метода ветвей и границ имеет полиномиальную по n оценку ветвлений, однако численная реализация этой версии – непростая задача и ее решение даже при небольшой размерности может потребовать значительных вычислительных ресурсов.

В работе [3] описывается подход к решению многомерной задачи о рюкзаке с помощью модифицированной версии метода ветвей и границ, используя сортировку ранжированных элементов по полезности: отдельные элементы, вероятно, те, что будут частью оптимального решения, фиксируются, а другие, ко-торые навряд ли будут таковыми, больше не рассматриваются (псевдопробелы). В [4] предложен итеративный алгоритм, улучшающий решение задачи путем поиска псевдопробелов. Эти два подхода сравниваются в [4], однако класс задачи при использовании данных алгоритмов остается NP, а в работе [2] установлено, что для некоторого класса задач переход от поиска точного решения к ε-оптимальному позволяет перейти от задачи класса NP к задаче класса P.

В статье [5] рассматривается способ аппроксимации при помощи поиска не более первых k компонент, удовлетворяющих всем требованиям, а затем поиска полиномиальной схемы для аппроксимации по времени.

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

Для проверки гипотезы о полиномиальности ε-оптимальной версии метода ветвей и границ в рассматриваемой задаче использован статистический эксперимент по аналогии с [7]. Была выбрана подходящая модельная задача, согласованы параметры генерации случайных коэфициентов и разработана общая программа решения поставленной задачи при любых значениях коэфициентов, причем для определенности время работы алгоритма ограничено одним часом.

Постановка ТЗ о ГН по эффективности назначения

Пусть, как в обычной ТЗ, i = 1, 2, ..., m обозначает пункты производства некоторого однородного товара, j = 1, 2, …, n – пункты его потребления. Даны величины: Xi > 0 – объем производства в пункте производства i; Yj > 0 – объем потребления в пункте потребления j, отнесенные к одному дню (горизонту планирования).

Найдем величины xij > 0 (объем перевозок из пункта i в пункт j), удовлетворяющие обычным транспортным ограничениям с неуравновешенным балансом:

                    (1)

i Î I = 1, 2, ..., m, j Î J = 1, 2, …, n,

где в общем случае

                                         (2)

и максимизирующие функцию:

                        (3)

где Aij – эффективность назначения i-го типа исполнителей на j-го типа заказчиков.

Замечание. Условия (1) всегда являются совместными, поскольку им удовлетворяют нулевые значения переменных.

Положим xij = Yjzij. Тогда задача (1)–(3) превратится в многомерную задачу о рюкзаке:

                        (4)

при ограничениях

 i = 1, 2, ..., m,                     (5)

 j = 1, 2, …, n, zij  ≥ 0.                 (6)

Смешанные решения ТЗ о ГН

Предположим, что сумма слева в ограничении (6) равна либо нулю, либо единице, а сами переменные zij могут принимать дробные значения и, таким образом, интерпретироваться как вероятности того, что вся групповая заявка Yj назначается i-му исполнителю. Такое решение назовем смешанным в отличие от классического. Ограничения (5) для смешанного решения выполняются как бы в среднем. Погрузим задачу в семейство задач, отличающихся подмножеством ω  J групповых заявок, выбранных для назначения:

                        (7)

при ограничениях

 i = 1, 2, ..., m,                     (8)

                             (9)

Замечание. Более общей является задача планирования огневого поражения:

                   (10)

при ограничениях

,                            (11)

                         (12)

Связь между решениями семейств задач (7)–(9) и (10)–(12) определяется формулой xij = Yjzij.

Здесь Mij – математическое ожидание количества пораженных целей обороны j-го типа нарядом i-го типа средств нападения; Zij ≥ 1 – соответствующий наряд; Xi – количество средств нападения i-го типа; Yj – количество целей обороны j-го типа; Aj – важность j-го типа целей обороны; xij – матрица назначения разнотипных средств нападения по разнотипным целям.

Субмодулярность задачи

Для построения эффективных верхних оценок в методе ветвей и границ для решения задачи огневого поражения можно использовать свойство субмодулярности функции C = C(ω), которое установлено в работе [8].

Если ω = f – пустое множество или огра-ничения задачи несовместны, то положим C = C(ω) = 0.

Напомним, что функция C = C(ω), определенная на 2J, называется субмодулярной, если для любых δ, ν  2J выполняется неравенство

.

Используя свойство субмодулярности, для решения задачи максимизации C = C(ω) на множестве 2J подмножеств J можно использовать методы субмодулярного программирования из работы [1], представляющие собой комбинацию метода ветвей и границ с критериями предварительного отсева заведомо неоптимальных вариантов.

Построение верхних оценок  в методе ветвей и границ

Главная проблема использования метода ветвей и границ – построение верхних оценок критерия в узле ω  J поискового безконтурного орграфа G. Если функция C = C(ω), определенная на 2J, является субмодулярной, то для  в качестве верхней оценки можно взять любое из следующих выражений [1]:

или

,

где  – нижняя срезка величины x. Это эквивалентно тому, что в верхней оценке учитываются только такие j, которые увеличивают функцию C(ω1) (C(ω2) – соответственно). Наличие двух формул для верхней оценки дает возможность распараллеливания процесса, осуществляя одновременно работу алгоритма метода ветвей и границ соответственно от f и J навстречу друг другу. Такого рода алгоритмы называются методами последовательного анализа вариантов [9].

Метод Поляка для решения промежуточных ТЗ о ГН с равенствами

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

При этом

Замечание. В случае пустого множества допустимых стратегий алгоритм перейдет на максимизацию агрегированного ограничения, что можно увидеть через его отрицательное предельное значение функции в левой части. Таким образом, метод Поляка [10] достаточно пускать один раз в каждом узле.

Числовой пример

Приведем модельный пример для проверки практической сходимости метода Поляка во вспомогательной задаче целераспределения с неуравновешенным балансом. Исходные данные задачи представлены в таблицах 1 и 2.

Таблица 1

Матрица Mij

Table 1

Mij matrix

Таблица 2

Матрица Zij

Table 2

Zij matrix

На основании этих данных проверим работу метода ветвей и границ, построим орграф с узлами, раскрытыми в ходе работы алгоритма (рис. 1).

На рисунке 1 первое число над каждым из узлов соответствует значению критерия в этом узле, а второе означает верхнюю оценку критерия в узле. Исходная размерность задачи J = 4, значит, общее количество узлов в числовом примере определяется как 2J = 16.

Идея согласования параметров численного эксперимента

Положим в задаче (7)–(9) Mij = Pij Î (0, 1), Zij Î [1, 5], Yj Î [1, 5], Aj = 1, m = 1/2n. Тогда математическое ожидание  равно 3n, математическое ожидание  равно 10m = 5n, и они находятся в соотношении

обеспечивающем нетривиальность решения в среднем. При этом для половины целей имеем:

то есть половина целей может быть в среднем обстреляна. В частности, одна цель может быть обстреляна при n/2 ≥ 1, то есть при n ≥ 2.

Замечание. Все величины предполагаются случайными, равномерно распределенными на соответствующих отрезках.

В ходе работы была создана программа на языке С++17, способная решить данную задачу ε-оптимальным методом ветвей и границ. Для оптимизации выбора необходимых узлов использован контейнер set стандартной библиотеки STL [11]. Использование данного контейнера позволяет уменьшить расход памяти за счет устранения повторяющихся узлов в каждом из раскрытий нового узла.

Для проведения численного эксперимента с использованием разработанной программы было решено запускать алгоритм по 10 раз для каждой из размерностей и подсчитывать среднее количество раскрытых вершин с макси-мально допустимым практическим значением относительной точности ε = 0,1. При увеличении размерности увеличивается и количество раскрытых узлов поискового орграфа, что продлевает вычислительный процесс и замедляет время работы программы.

Замечание. В рамках численного эксперимента ограничимся размерностью, при которой решение находится в пределах одного часа.

На рисунке 2 график c1 отражает зависимость среднего количества раскрытых вершин в ε-оптимальной версии метода ветвей и границ от размерности m+n задачи, график c2 – логарифмический масштаб графика с1, который должен быть линейным в случае экспоненциальной сложности алгоритма и логарифмическим в полиномиальном случае. В этом состоит качественный критерий полиномиальности алгоритма.

Анализ результатов эксперимента

По результатам численного эксперимента были составлены два графика (рис. 2 и 3), из которых видно, что логарифмический масштаб, отображенный на рисунке 2 (график c2), линейный. Это означает, что ε-оптимальная версия метода ветвей и границ экспоненциальна.

Заметим, что с увеличением размерности процент раскрытия вершин для данной задачи с ε-оптимальной версией метода ветвей и границ убывает, как показано на рисунке 3 (график c3), однако количество раскрытых вершин растет с увеличением размерности, как показано на рисунке 2 (график с1). Тем не менее процент раскрытых вершин убывает достаточно быстро, что говорит о практической значимости алгоритма.

Заключение

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

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

Проведен статистический эксперимент по проверке практической сходимости ε-опти­мальной версии метода ветвей и границ. Результаты его показали, что ε-оптимальная версия метода ветвей и границ экспоненциальна, однако процент раскрытых вершин убывает достаточно быстро, что говорит об эффективности алгоритма.

Список литературы

1. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368 c.

2. Финкельштейн Ю.Ю. Подход к многомерной задаче о ранце: полиномиальный рост дерева ветвления // Журнал вычислительной математики и математической физики. 1977. Т. 17. № 4. С. 1040–1042. doi: 10.1016/0041-5553(77)90120-3.

3. Kress A., Kiel F., Metternich J. A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Stored Branch and Bound Algorithm. Technical University Darmstadt. TU Darmstadt, 2021. URL: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404 (дата обращения: 10.12.2022).

4. Gao C., Lu G., Yao X., Li J. An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem. EJOR, 2017, vol. 260, no. 1, pp. 1–11. doi: 10.1016/j.ejor.2016.11.042.

5. Aardal K., van den Berg P.L., Gijswijt D., Li S. Approximation algorithms for hard capacitated k-faculty location problems. EJOR, 2015, vol. 242, no. 2, pp. 358–368.

6. Li W., Lee J., Shroff N. A faster FPTAS for knapsack problem with cardinality constraint. Discrete Applied Mathematics, 2022, vol. 315, pp. 71–85. doi: 10.1016/j.dam.2022.03.005.

7. Wu T., Chen L., Hui P., Zhang C.J., Li W. Hear the whole story: Towards the diversity of opinion in crowdsourcing markets. PVLDB, 2015, vol. 8, no. 5, pp. 485–496.

8. Монтлевич В.М. О субмодулярности функции прибыли в одной из задач планирования перевозок // Вестн. СамГУ. 2014. № 10. С. 48–54.

9. Хачатуров В.Р., Веселовский В.Е., Злотов А.В. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности. М.: Наука, 2000. 353 c.

10. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 c.

11. Адильшаева Э.И., Халилова З.Э. Особенности реализации способов хранения и обработки данных на языках программирования С++ и Java // Информационно-компьютерные технологии в экономике, образовании и социальной сфере. 2018. № 1. С. 76–84.

Reference List

1. Korbut, A.A., Finkelshtein, Yu.Yu. (1969) Discrete Programming, Moscow, 368 p. (in Russ.).

2. Finkelshtein, Yu.Yu. (1977) ‘The ε-approach to the multidimensional knapsack problem: The polynomial growth of the branching tree’, USSR Computational Math. and Math. Phys., 17(4), pp. 1040–1042. doi: 10.1016/0041-5553(77)90120-3 (in Russ.).

3. Kress, A., Kiel, F., Metternich, J. (2021) ‘A new exact algorithm to solve the Multiple-Choice Multidimensional Knapsack Problem: The Utility Stored Branch and Bound Algorithm. Technical University Darmstadt’, TU Darmstadt, available at: https://tuprints.ulb.tu-darmstadt.de/id/eprint/19404 (accessed December 10, 2022).

4. Gao, C., Lu, G., Yao, X., Li, J. (2017) ‘An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem’, EJOR, 260(1), pp. 1–11. doi: 10.1016/j.ejor.2016.11.042.

5. Aardal, K., van den Berg, P.L., Gijswijt, D., Li, S. (2015) ‘Approximation algorithms for hard capacitated k-faculty location problems’, EJOR, 242(2), pp. 358–368.

6. Li, W., Lee, J., Shroff, N. (2022) ‘A faster FPTAS for knapsack problem with cardinality constraint’, Discrete Applied Mathematics, 315, pp. 71–85. doi: 10.1016/j.dam.2022.03.005.

7. Wu, T., Chen, L., Hui, P., Zhang, C.J., Li, W. (2015) ‘Hear the whole story: Towards the diversity of opinion in crowdsourcing markets’, PVLDB, 8(5), pp. 485–496.

8. Montlevich, V.M. (2014) ‘On the submodularity of the profit function in a problem of transport planning’, Vestn. SamGU, (10), pp. 48–54 (in Russ.).

9. Khachaturov, V.R., Veselovsky, V.E., Zlotov, A.V. et al. (2000) Combinatorial Methods and Algorithms for Sol-ving Problems of Discrete Optimization of Large Dimension, Moscow, 353 p.

10. Polyak, B.T. (1983) Introduction to Optimization, Moscow, 384 p. (in Russ.).

11. Adilshayeva, E.I., Khalilova, Z.E. (2018) ‘Features of the implementation of data storage and processing methods in the C++ and Java programming languages’, Information and Computer Technologies in the Economy, Education and Social Sphere, (1), pp. 76–84 (in Russ.).