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

---

Разработана программа поиска оптимального решения задачи с приоритетными назначениями. Результаты работы программы представлены на рисунке 14.



Рисунок 14 – Результаты поиска оптимального решения задачи с приоритетными назначениями
Необходимость учета приоритета назначений в общем случае влечет рост значения целевой функции (рисунок 15).



Рисунок 15 – Результаты поиска оптимального решения простейшей линейной задачи с матрицей затрат С

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

---

Выводы

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

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

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

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

---

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

3. Модели многокритериальных задач о назначениях и алгоритмы их решения

   1. 
      Модель простейшей линейной многокритериальной задачи о назначениях
      

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

nn f1(X)  c1 x min, ijij i1 j1	(70)
nn f2 (X)  c2x min, ijij i1 j1	(71)
…
nn fk(X)  ckx min, ijij i1 j1	(72)
n  xij 1, j 1, n, i1	(73)
n  xij 1, i  1, n, j1	(74)
xij{0,1}, i, j 1, n,	(75)

---

---