Файл: пензенский государственный университет политехнический институт.docx

По размерности неизвестных можно выделить следующие классы задач:

• 
  двухиндексные задачи о назначениях;
  
• 
  многоиндексные задачи о назначениях.
  

Типичной является постановка двухиндексной задачи о назначениях, решением которой является матрица. Двухиндексные задачи, в свою очередь, можно подразделить на закрытые и открытые. В закрытых моделях количество работ равно количеству исполнителей, в открытых моделях – не равно. Открытые модели часто моделируют наличие конкуренции [5, 52, 53] и легко сводятся к закрытым путем дополнения матрицы затрат нулями до квадратной, что соответствует правилам приведения открытой модели транспортной задачи к закрытой.

Многоиндексные задачи о назначениях возникают при оптимизации работы последовательно-параллельной системы обслуживания [54], в области технического анализа данных при сопровождении объектов в многосенсорных системах [55], при назначении целей для нанесения максимального поражения противнику [56] и др.

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

так, чтобы в каждом еѐ сечении было выбрано ровно nэлементов и при этом сумма выбранных элементов минимальна [57].

И аксиальные и планарные трехиндексные задачи являются NP- трудными. Исследованы свойства многогранника ограничений этих задач, ставшие основой для разработки алгоритмов локального поиска и частичного перебора типа метода ветвей и границ [10, 58, 59, 60]. Известны эвристические алгоритмы решения [61, 62, 63], многие из которых являются модификациями

---

точных методов, примененных как приближенные. В [64, 65] представлен асимптотически точный подход к построению алгоритмов решения аксиальных многоиндексных задач большой размерности на случайных входах. В [66] предложен адаптивный алгоритм решения трѐхиндексной аксиальной задачи о назначениях, основанный на переходе к задачи в вероятностной постановке. В [67] описан асимптотически точный алгоритм решения модифицированной трѐхиндексной планарной задачи о назначениях. В [68] рассмотрена многокритериальная трехиндексная планарная задача о назначениях, для которой предложен и обоснован полиномиальный алгоритм нахождения асимптотически идеального решения, векторная оценка которого стремится (в смысле относительной погрешности) к идеальной точке.

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

6. 1   2   3   4   5   6   7   8   9   ...   21

---

Анализ эквивалентных преобразований моделей задач о назначениях

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

максимум [7, 10, 30], открытой задачи [5, 48, 53], задачи матрицей затрат, на элементы которой не накладывается условие неотрицательности [69], задачи с запретами на отдельные назначения [7, 45, 48]. Анализ этих задач позволяет сформулировать эквивалентные преобразования, специфические для задачи о назначениях, а также построить обобщенные линейные задачи, модели которых эквивалентны простейшей линейной модели.

Рассмотрим задачу о назначениях, целевая функция которой стремится к максимуму. Пусть математическая модель задачи имеет вид:

nn f(X)  cijxij max, i1 j1	(5)
n  xij 1, j 1, n, i1	(6)
n  xij 1, i 1, n, j1	(7)
xij{0,1}, i, j 1, n.	(8)

---

Эквивалентное преобразование направления целевой функции формулируется так:

1. 
   в каждой строке матрицы С найти наибольший элемент
   

x_ij{0,1}, i, j 1, n. ₍₁₂₎

Модели (5) – (8) и (9) – (12) эквивалентны друг другу, при этом модель

(9) – (12) является простейшей линейной. Отсюда можно сформулировать алгоритм решения задачи о назначениях (5) – (8).

1. 
   Применить к модели (5) – (8) эквивалентное преобразование направления целевой функции. Результатом является получение эквивалентной модели (9) – (10).
   
2. 
   Решить задачу, описываемую соотношениями (9) – (10), венгерским методом или методом Мака.
   

Средствами математического пакета «Mathcad» разработана программа поиска решения задачи о назначениях с целевой функцией на максимум (листинг 2).

---

Листинг 2 – Поиск решения задачи о назначениях с целевой функцией на максимум




С помощью предложенного алгоритма найдено оптимальное решение задачи о назначениях.


Рисунок 3 – Оптимальное решение задачи о назначениях на максимум
Найденное решение совпадает с решением задачи (5) – (8) симплекс- методом, оптимальные значения целевых функций также совпадают (рисунок 4).



Рисунок 4 – Решение исходной задачи

Рассмотрим открытую задачу о назначениях. Такая задача

---