Алгоритмы равноценного распределения элементов множеств

• Автор: Бычков, Владимир Порфирьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Казань
• Количество страниц: 194 с.

Содержание
Введение
Глава 1. Модели комбинаторных задач оптимизации с квадратичным функционалом от линейных функций и их свойства
1.1. Формулировка конкретных задач, приводящих к комбинаторным задачам оптимизации с квадратичным функционалом от линейных функций

1.1.1. Задача равноценного распределения ресурсов

1.1.2. Задача использования неделимого ресурса

1.1.3. Задача упаковки

1.1.4. Задача конкурентной борьбы за общие интересы

1.1.5. Модель теории абстрактного вопросника

1.2. Задача равноценного распределения элементов множеств и ее свойства

1.2.1. Постановка задачи
1.2.2. Пример поиска наилучших элементов множеств..
1.2.3. Математическая формулировка задачи
1.2.4.Свойства задач равноценного распределения элементов множеств
1.2.5. Графовая интерпретация задачи о назначениях с квадратичным функционалом от линейных функций
Глава 2. Методы решения задач о назначениях с квадратичным
функционалом от линейных функций
2.1. Дискретный метод функциональных уравнений
2.1.1. Функциональные уравнения задачи о назначени-

2.1.1.1. Динамическая постановка задачи о назначениях
2.1.1.2. Вывод функциональных уравнений задачи
о назначениях
2.1.2. Схема решения задачи о назначениях дискретным методом функциональных уравнений
2.1.3. Решение тестового примера дискретным методом функциональных уравнений
2.1.4. Сложность дискретного метода функциональных уравнений
2.1.5. Блок-схема дискретного метода функциональных уравнений
2.1.6. Выводы
2.2. Непрерывный метод функциональных уравнений
2.2.1. Вывод уравнений непрерывного метода функциональных уравнений для задачи о назначениях
2.2.2. Схема решения задачи о назначениях непрерывным методом функциональных уравнений
2.2.3. Решение тестового примера непрерывным методом функциональных уравнений
2.2.4. Блок-схема непрерывного метода функциональных уравнений
2.2.5. Выводы
2.3. Метод распределения избыточных оценок
2.3.1. Необходимые условия допустимости решений

задачи о назначениях
2.3.2. Метризация, согласованная с задачей о назначениях
2.3.3. Оптимальность решений задачи о назначениях
2.3.4. Алгоритм метода распределения избыточных оценок
2.3.5. Некоторые оценки сложности метода распределения избыточных оценок
2.3.6. Решение тестового примера методом распределения избыточных оценок
2.4. Метод однократных замещений
2.4.1. Представления допустимых решений
2.4.2. Алгоритм метода однократных замещений
2.4.3. Решение тестового примера методом однократных замещений
Заключение
Литература
Приложения
Приложение 1. Решение тестового примера дискретным методом функциональных уравнений
Приложение 2. Программа “Dinam_progr” на языке Turbo Pascal
7.0 для решения задачи о назначениях дискретным методом
функциональных уравнений
Приложение 3. Решение тестового примера программой «Di-nam_progr»

Следовательно,
N (т(1) Л1 ГтО) Л
2М*>аЖ0)-Л°) =щ ЁЛ^Х^В-Ф) • О-19)
А=1 (=1 ) V ,=1 /
Таким образом, в качестве м>(/) можно взять функционал вида
/ м
40= Ес(/,/,Ж/))-с(о) . (1.20)
1=1 /
Хотя задача значительно упростилась, но необходимость в решении задачи на минимизацию не исчезла. Она свелась к задаче ми-
нимизации функционала вида:
^ т Л
ЁФЛОЬФ) С1-21)

на матрице С = (с(*,у))> г = 1,2j = 1,2,..., N. В данном случае структура решения будет иметь тот же вид, что и в утверждениях 1.1-1.2. Кроме того, из структуры функционала и матрицы оценок
видно, что как комбинаторная задача она оказалась переборной зада-
чей. В этом можно убедиться, сведя ее к задаче математического программирования.
Конечно, в практических задачах, типа сформулированных в пп. 1.1-1.5 отображение ц/ не является произвольным, а обладает дополнительными свойствами. Поэтому перейдем к рассмотрению таких задач.
Так, при взаимной однозначности отображения у (что соответствует многим практическим задачам) с{1,][1,к)) зависит от к (и, следовательно, с(г,/,/(*,/,£)) зависит от к для любого г = 1, 2,..., т(/); / = 1, 2,..., п ). Тогда / -я таблица оценок имеет вид: