Известия РАН. Теория и системы управления, 2020, № 5, стр. 56-59

Введение. Трехиндексная планарная задача о назначениях [1], как известно, относится к классу NP-полных задач [2, 3]. Для ее решения используется метод ветвей и границ [4], “жадные” и эвристические алгоритмы [5]. В [6] предложены улучшения приближенных алгоритмов переходом к вероятностной интерпретации. В данной работе применяется метод последовательной модификации целевой функции [7–9] для решения планарной трехиндексной задачи о назначениях. Алгоритм находит точное решение, и численные эксперименты дают полиномиальную относительно размерности исходной задачи временную оценку.

1. Постановка задачи. Трехиндексная планарная задача о назначениях может быть записана в виде задачи линейного целочисленного программирования:

2. Метод решения задачи. Для начала решим 3n² задач с одним ограничением каждая. Первые n² задач:

при ограничениях (1.1), (1.4). Вторые n² задач: при ограничениях (1.2), (1.4). Третьи n² задач: при ограничениях (1.3), (1.4). Все 3n² задач вида (2.1)–(2.3) легко решаются поиском минимального коэффициента при переменных в соответствующих целевых функциях.

Если в результате решения вышеупомянутых 3n² задач значения переменных удовлетворяют ограничениям (1.1)–(1.3), то тем самым решена исходная задача (1.1)–(1.5). Сумма значений целевых функций в оптимальных решениях задач (2.1)–(2.3) будет значением целевой функции в оптимальном решении задачи (1.1)–(1.5). В противном случае будем говорить, что получено псевдорешение этой задачи. Заметим, что значение целевой функции псевдорешения не превосходит значения целевой функции искомого оптимального решения исходной задачи. Построим последовательность псевдорешений с монотонно возрастающими значениями целевых функций.

Для получения второго псевдорешения решим следующую задачу с тремя ограничениями:

В этой задаче x₁₁₁ – единственная общая переменная в ограничениях (2.4)–(2.6). Обозначим:

Могут иметь место три случая:

(а) ${{c}_{{111}}} < {{M}_{1}} + {{M}_{2}} + {{M}_{3}};$

(б) ${{c}_{{111}}} = {{M}_{1}} + {{M}_{2}} + {{M}_{3}};$

(в) ${{c}_{{111}}} > {{M}_{1}} + {{M}_{2}} + {{M}_{3}}.$

Если получен случай (а), то решением задачи (2.4)–(2.7) является ${{x}_{{111}}} = 1$, остальные переменные равны нулю. Если возник случай (б), то очевидно, что задача (2.4)–(2.7) имеет несколько оптимальных решений, которые могут быть описаны системой из трех линейных ограничений с участием x₁₁₁. Если имеет место (в), то ${{x}_{{111}}} = 0$, а решение задачи (2.4)–(2.7) представляет собой объединение трех задач с ограничениями (2.4)–(2.6) соответственно при условии ${{x}_{{111}}} = 0$.

Решив задачу (2.4)–(2.7), преобразуем ее, сохраняя оптимальное решение, в три независимые задачи с ограничениями (2.4)–(2.6) соответственно. Для этого достаточно в случае (а) исходя из равенства

в ограничении (2.4) вместо ${{c}_{{111}}}{\text{/}}3$ записать ${{M}_{1}} - \delta {\text{/}}3$, в ограничении (2.5) вместо ${{c}_{{111}}}{\text{/}}3$ записать ${{M}_{2}} - \delta {\text{/}}3$, в ограничении (2.6) вместо ${{c}_{{111}}}{\text{/}}3$ записать ${{M}_{3}} - \delta {\text{/}}3$. В случае (б) новые коэффициенты при x₁₁₁ запишутся следующим образом: в ограничении (2.4) будет M₁, в ограничении (2.5) будет M₂, в ограничении (2.6) будет M₃. В случае (в) новые коэффициенты при x₁₁₁ исходя из равенства в ограничении (2.4) будет ${{M}_{1}} + \gamma {\text{/}}3$, в ограничении (2.5) будет ${{M}_{2}} + \gamma {\text{/}}3$, в ограничении (2.6) будет ${{M}_{3}} + \gamma {\text{/}}3$.

В итоге получим второе псевдорешение с возросшим, в общем случае, значением целевой функции. Решая циклически все n³ задач с тремя ограничениями, получаем последовательность псевдорешений с монотонно возрастающей целевой функцией, ограниченной сверху значением целевой функции в оптимальном решении исходной задачи (1.1)–(1.5). Имеет место следующая очевидная теорема.

Теорема 1. Если в предельном псевдорешении все задачи с одним ограничением имеют единственное решение, то тем самым получено оптимальное решение исходной задачи (1.1)–(1.5).

В случае неединственности решения в некоторых задачах с одним ограничением будем говорить, что имеет место вырождение. Заметим, что вся вышеописанная схема решения уже применялась для решения других задач в [8, 9] и там в случае вырождения требовались дополнительные конструкции алгоритма и дополнительные, возможно значительные, объемы вычислений.

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

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

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

3. Включение переменных в решение при вырождении. Пусть при решении задачи с общей переменной ${{x}_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}}$ имеет место вырождение. Тогда кроме ${{x}_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}}$ в задаче с первым ограничением на включение в решение на равных претендуют ${{x}_{{{{i}_{1}}{{j}_{0}}{{k}_{0}}}}}$, ${{x}_{{{{i}_{2}}{{j}_{0}}{{k}_{0}}}}}$ и т.д. В задаче со вторым ограничением на включение в решение претендуют ${{x}_{{{{i}_{0}}{{j}_{1}}{{k}_{0}}}}}$, ${{x}_{{{{i}_{0}}{{j}_{2}}{{k}_{0}}}}}$ и т.д. В задаче с третьим ограничением на включение в решение претендуют ${{x}_{{{{i}_{0}}{{j}_{0}}{{k}_{1}}}}}$, ${{x}_{{{{i}_{0}}{{j}_{0}}{{k}_{2}}}}}$ и т.д. Для выделения одного оптимального решения поступим следующим образом. Выберем произвольное малое ε > 0 и уменьшим $c_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}^{1}$, $c_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}^{2}$ и $c_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}^{3}$ на ε/6. Тогда в рассматриваемой задаче с тремя ограничениями будет ${{x}_{{{{i}_{0}}{{j}_{0}}{{k}_{0}}}}} = 1$, а все остальные переменные равны нулю. Далее уменьшим $c_{{{{i}_{1}}{{j}_{0}}{{k}_{0}}}}^{1}$, $c_{{{{i}_{2}}{{j}_{0}}{{k}_{0}}}}^{1}$ и т.д., $c_{{{{i}_{0}}{{j}_{1}}{{k}_{0}}}}^{2}$, $c_{{{{i}_{0}}{{j}_{2}}{{k}_{0}}}}^{2}$ и т.д., $c_{{{{i}_{0}}{{j}_{0}}{{k}_{1}}}}^{3}$, $c_{{{{i}_{0}}{{j}_{0}}{{k}_{2}}}}^{3}$ и т.д. на ε/12. Это не изменит оптимального решения. Одновременно увеличим на ε/24 соответствующие коэффициенты в двух других уравнениях для каждой из этих переменных, что обеспечит им равенство нулю во всех уравнениях. При рассмотрении следующей переменной, участвующей в вырождении, ее коэффициенты уменьшаем на ε/12 и т.д. Заметим, что, не ограничивая общности, можно считать коэффициенты целевой функции (1.5) целыми числами и поэтому циклический процесс можно остановить, если модуль разности между претендентами меньше 1/n².

4. Результаты численного эксперимента. На персональном компьютере (процессор Intel Core i7-2600, 3.40GHz) была решена серия тестовых задач. Коэффициенты целевой функции выбирались случайным образом в диапазоне от 200 до 500. В таблице дана длительность вычислений в зависимости от размерности задачи.

Аппроксимационная формула зависимости времени расчета в минутах при коэффициенте корреляции 0.98 имеет вид $T = 1.6 \times {{10}^{{ - 9}}}{{n}^{{6.35}}}$.

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