Расширенная задача о равномерном назначении

• Автор: Чаплыгина, Надежда Борисовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Ярославль
• Количество страниц: 104 с.

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

2. Задача о равномерном назначении различающих

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

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

2.3. Характеристическое свойство оптимального

решения А задачи

2.4. Алгоритм решения Азадачи

2.5. Учет желательного числа назначений НА

задача

2.6. Анализ сложности алгоритма нахождения

равномерного назначения
3. Равномерное назначение минимальной стоимости
3.1. Постановка задачи
3.2. Улучшающие контуры
3.3. Частичная сеть, порожденная потоками, и
дополняющая их сеть
3.4. Построение равномерного потока минималь
ной стоимости
3.5. Решение задачи с ненулевой матрицей
обязательных назначений
3.6. Еще один алгоритм решения задачи
равномерного назначения
3.7. Анализ сложности алгоритма нахождения
равномерного назначения минимальной стоимости
4. Минимальная стоимость равномерного назначения
4.1. Постановка задачи.
4.2. Свойство оптимального решения.
4.3. Алгоритм нахождения оптимального решения
4.4. Оптимальность решения по двум критериям
5. О выборе наилучшего критерия равномерности
5.1. Постановка задачи.
5.2. Свойства критерия равномерности.
5.3. Оптимальный критерий равномерности .
5.4. Свойства задачи, влияющие на оптимальность
критерия
6. Заключение
А. Приложение к главе 2. Реализация алгоритма решения 1задачи
Литература


Как правило, принимая решение в той или иной задаче управления, приходится иметь дело с несколькими критериями и оценивать решение не по одному параметру. Так последнее время большое внимание уделяется исследованию многокритериальных задач, которые характеризуются наличием нескольких целевых функций вместо одной в однокритериальных задачах. Сложность нахождения решения многокритериальных оптимизационных задач связана с тем, что целевые функции, выступающие в качестве критериев оптимизации, во многих случаях конфликтуют между собой. Таким образом, оптимизировать решение сразу по всем целевым функциям возможно далеко не всегда. Для того, чтобы отбирать более предпочтительные решения, надо уметь их сравнивать. В лучшем случае можно было бы ввести отношение линейного порядка на множестве значений критериев. Отношение линейного порядка можно ввести с помощью метода, называемого сверткой критериев. И если у - вектор значений критериев, то оптимизация на множестве допустимых решений х приводит к получению решения /^-критериальной задачи. В практических приложениях часто осуществить этот метод довольно сложно из-за сложности отношений между критериями, если критериев достаточное число. Однако можно ввести отношение частичного порядка на том же множестве значений критериев, которое, возможно, и не даст возможность определить среди всех допустимых решений элемент с максимальным (в смысле введенного частичного порядка) значением многомерного критерия, но может позволить определить элемент со значением критерия, над которым нет большего, т. Пусть у(х) = (у1(х), у2(х), . Ук(х)) - ^-мерная критериальная функция на множестве допустимых значений X со значениями в Як. Д, уиу2 € У. Тогда у недоминируется на Z, если не существует такого у ? Z, что у -< у и у ф у. Согласно введенного отношения частичного порядка -< можно поставить задачу найти решение для которого значение критерия является недоминируемым. Такое решение называется эффективным или оптимальным по Парето. Нахождение эффективных решений имеет большое значение, так как только эти решения являются претендентами на оптимальность, если оптимальное решение вообще существует на множестве допустимых решений. В зависимости от вводимого отношения порядка на множестве значений критериев можно получить различные оптимальные решения. Решению и исследованию многокритериальных оптимизационных задач посвящен довольно широкий ряд работ И. И. Мелам еда и И. Х.Сигала []-[]. В этих работах кроме полученных общих теоретических результатов: методов нахождения оптимальных по Парето решений, метода линейной свертки критериев и др. МШБШМ и МШМАХ. В том числе представлены результаты работы алгоритма нахождения решения бикритериальной задачи о назначениях и приведена статистическая обработка полученных экспериментальных данных, исследованы зависимости числа значений вектора критериев на решениях задачи от объема задачи, от вида входных данных задачи, распределение критериальных значений по виду линейной свертки критериев. Общие теоретические положения теории принятия решений при многокритериальной оптимизации можно найти в работах Р. Што-йера [], Р. Л.Кини и X. Райфы []. Лексикографической многокритериальной оптимизации и сложности алгоритмов решения оптимизационных задач со многими критериями посвящены исследования Бондаренко В. А., Клоедена П. Е., Краснова М. В. [], []. В настоящей работе рассматривается расширение задачи о назначениях, связанное с усложнением структуры плана работ, рассчитанного на период в несколько дней, в связи с чем любой работник может выполнять несколько работ плана при условии, что ежедневно любой работник не может выполнять более одной работы. Таким образом, необходимо разрешить систему задач о назначениях на каждый день плана, 1 причем в качестве исполнителей в ” ежедневных” задачах о назначениях берется одно и то же множество. Здесь имеются в виду задами без учета стоимости назначения, так что можно было би говорить о "ежедневных” задачах поиска максимальных паросочетаний. Но название задачи ”о назначениях” отражает практический се смысл.