Равномерность и минимальность стоимости в задаче о назначениях

• Автор: Кропанов, Владимир Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Ярославль
• Количество страниц: 76 с.

Оглавление
1. Введение

2. Задача о равномерном назначении.

Формулировка и обобщения.

3. Задача о равномерном назначении работ относительно матрицы обязательных назначений

3.1. Постановка задачи

3.2. Постановка А1-задачи

3.3. Характеристическое свойство

решения задачи РНМО

4. Задача о равномерном назначении работ относительно вектора желательных назначений.

4.1. Постановка задачи

4.2. Эквивалентность задач РНОВ и РНМО
4.3. Взаимное сведение и обобщение задач РНМО и РНОВ.
5. Задача о равномерном назначении минимальной стоимости.
6. План равномерного назначения работ.
6.1. Определение и основные свойства плана назначений.
6.2. Основное свойство плана
равномерного назначения работ
7. Задача о минимальной стоимости равномерного назначения работ
7.1. Решение задачи МСРН для
однокомпонентного плана
7.2. Решение задачи МСРН
для двухкомпонентного плана

7.3. Свойства решения задачи МСРН
8. Заключение.
9. Литература

1. Введение
Диссертационная работа посвящена изучению некоторых обобщений задачи о назначениях - одной из классических задач дис7 кретной математики. Классическая задача о назначениях формулируется следующим образом. Имеется конечное число исполнителей
каждый из которых должен быть занят в некоторый из дней
d, д'2,, dn.
Стоимость занятости в день dj исполнителя bi равна Cij. Нужно распределить исполнителей по дням, то есть назначить по одному работнику на каждый день так, чтобы, во-первых, были заняты все дни и, во-вторых, минимизировать затраты. Данная задача широко исследована в работах таких известных математиков как Х.Кун (см. [28]), Н.Кристофидес (см. [11]), Э. Эгервари (см. [24]) и многих других. Были получены эффективные алгоритмы решения классической задачи о назначениях, в частности Венгерский метод решения, усовершенствованная схема алгоритма глобального поиска для квадратичной задачи о назначениях приведена в работах Васильева И.Л. и Киселева В.Д. (см. [2], [7]). Многие задачи дискретной оптимизации, сводятся к классической задаче о назначениях, классификации таких задач посвящены работы Abreu N., Netto Р., (см. [20]) Angel Е. (см. [21]-[23]), Korvin А. (см. [26], [27]) и других. Кроме того были сформулированы и исследованы свойства различных ее обобщений, которые невозможно свести к классической, и решение которых не является тривиальным.
Одним из таких обобщений является задача азьтернативного распределения разнотипных средств (АРРС) исследованная Коротким Ю.Г. Селютиным В.А. и др. (см.[4], [9], [10], [17]). Внешне

Отбросив последние три столбца, мы получим матрицу Х+, которая, согласно доказанному выше, будет являться решением исходной задачи РНОВ.
'0 0 1 0^
0 1 0
0 1 1
И 0 0 Ч
Теперь мы можем сформулировать задачу, которая является обобщением задач РНМО и РНОВ. В задаче о назначениях заданы: матрица А обязательных назначений, удовлетворяющая (7) — (8), и вектор желательных назначений Н. Требуется построить матрицу назначений X такую, что
Оу = 1 =Ф> Ту = 1 (г Є 1, п, і Є 1, т), и минимизирующую функционал
Г(х) = -^(Кі(х)-к)2.

На основании Теоремы 3.1 и правил сведения такая задача может быть сведена либо к задаче РНМО, либо к задаче РНОВ.