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

• Автор: Медведева, Ольга Александровна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Воронеж
• Количество страниц: 159 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ РАЗНОВИДНОСТЕЙ ЗАДАЧИ О НАЗНАЧЕНИЯХ

1.1 Обзор моделей и алгоритмов решения существующих разновидностей задачи о назначениях

1.2 Постановка классической задачи о назначениях и венгерский метод её решения

1.3 Открытая (несбалансированная) задача о назначениях

1.4 Двойственный алгоритм Удзавы

1.5 Цели и задачи исследования

Выводы по первой главе

ГЛАВА 2. ЗАДАЧИ О НАЗНАЧЕНИЯХ С ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ

2.1 Задача о назначениях с запретами

2.2 Задача о назначениях с предпочтениями
2.3 Задача о назначениях с запретами и предпочтениями
2.4 Задача о назначениях с конфликтами
Выводы по второй главе
ГЛАВА 3. МНОГОКРИТЕРИАЛЬНЫЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ
3.1 Двухкритериальная задача о назначениях с возможностью обучения претенденто в
3.1.1 Алгоритм решения, основанный на использовании венгерского метода с корректировкой матриц затрат
3.1.2 Алгоритм, основанный на применении двойственного алгоритма Удзавы
3.2 Многокритериальная задача о назначениях с несколькими предприятиями
3.2.1 Алгоритмы решения, основанные на использовании венгерского метода с корректировкой матриц затрат
„ 3.2.2 Алгоритмы, основанные на применении двойственного алгоритма
Удзавы
Выводы по третьей главе
ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РЕШЕНИЯ
ПОСТАВЛЕННЫХ ЗАДАЧ
4.1 Описание программного комплекса
4.2 Вычислительный эксперимент
Выводы по четвёртой главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЯ
Приложение А
Приложение Б
Приложение В
Приложение Г

ВВЕДЕНИЕ
Актуальность темы. Задача о назначениях, её линейные, квадратичные и многоиндексные разновидности привлекают внимание исследователей ввиду своей обширной применимости в различных областях научной и практической деятельности. К ним сводятся задачи, связанные с оптимальным распределением элементов на микросхемах, задачи планирования работы вычислительных, производственных, технологических систем, оптимизации перевозок, а также задачи составления расписаний. Содержательная постановка данной задачи формулируется следующим образом: пусть имеется п работ и п претендентов для выполнения этих работ. Назначение претендента / на работу у связано с затратами сч (/, у = 1,«). Требуется определить назначение, дающее минимальные суммарные затраты, при этом каждого претендента можно назначить только на одну работу, и каждая работа может быть занята только одним кандидатом. С комбинаторной точки зрения допустимое решение этой задачи представляет собой перестановку ж-(ж1,...,жп) чисел 1, ..., п, а соответствия вида г —>■ ж1 (/ = 1,п) описывают произведённые назначения (г, 7т() (у'-й претендент назначен на работу с номером тг,). Тогда задача сводится к определению такой перестановки л , которая

минимизирует линейную целевую функцию ^ст . Данная задача, называемая

линейной закрытой задачей о назначениях, относится к задачам дискретной оптимизации и является частным случаем транспортной задачи. Для неё существуют точные методы решения, такие как венгерский алгоритм, метод потенциалов, метод ветвей и границ. Однако дополнительные требования, обусловленные практическими задачами, приводят к различным модификациям математической модели: изменению стандартных и/или добавлению новых ограничений, а также появлению многокритериальное. Для модифицированных моделей, по-прежнему являющихся задачами дискретной оптимизации, известные методы зачастую не применимы, что требует разработки специальных подходов к нахождению решения - точного или приближённого. Основные исследования

ф' ) + ут ■ fix' ) < ф') + ут • fix') < ф) + у'т ■ fix), xgS, у > 0.
По определению двойственной функции верно, что для любого X е S
ф')<ф) + у'т -fix).
При х = х* имеем ^у')<ф*) + у'т -fix').
Поскольку ф') =a>iy*), то y'T-fix*) >0, но, с другой стороны, у'г>0, fix') <0, откуда у'т -fix') <0. Следовательно, у'т ■ fix') =0.
Получим, что неравенство ф') + ут ■fix')<ф') верно, поскольку /■fix) <0.
Неравенство Теорема доказана.
Теорема 1.7 [47]. Пусть у’>0 - оптимальное решение двойственной задачи, тогда
1) Если исходная задача имеет седловую точку, то существует такое решение х' исходной задачи, что (х*,у*) - седловая точка (тогда х' есть оптимальное решение исходной задачи);
2) Если исходная задача имеет седловую точку и если Ф(х,у') имеет единственный минимум по х в точке x'eS, то точка (х*,у*) обязательно является седловой и х* - оптимальное решение исходной задачи;
3) Если со iy) дифференцируема в точке у', и если х*- единственный минимум по х для Ф(х,У), то исходная задача имеет седловую точку (х*,у*).
Во многих случаях двойственную задачу решить легче, чем исходную. Если седловая точка существует, то решение исходной задачи может быть, таким образом, с выгодой заменено решением двойственной задачи. Заметим, однако, что даже если седловой точки нет, решение исходной задачи может быть заметно упрощено, если использовать информацию, полученную при решении двойственной задачи.