Математическое моделирование функций выбора в обобщенном динамическом программировании

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

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
АНАЛИЗ СУЩЕСТВУЮЩИХ МОДЕЛЕЙ ВЫБОРА НА НЕОБОЗРИМОМ
МНОЖЕСТВЕ АЛЬТЕРНАТИВ С ПРИМЕНЕНИЕМ МЕТОДОВ
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
1.1. Актуальные задачи и модели выбора
1.2. Типовые задачи поэтапного выбора
1.3. Многокритериальные задачи динамического программирования
1.4. Исследования по оценке вычислительной сложности алгоритмов
поэтапного выбора
1.5. Выводы. Цель и задачи исследования
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ОБОБЩЕНИЯ СХЕМЫ
ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
2.1. Оптимальные пути в бесконтурном графе
2.2. Оптимальные пути в графе общего вида
2.3 Алгоритмы восстановления оптимальных путей
2.4. Выводы по главе
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ МОДЕЛЕЙ
3.1. Построение БО для составных объектов
3.2. Обобщение БО на непрерывный случай
3.3. Сужение выбора на основе лексикографии бинарных отношений
3.4. Оценка вычислительной сложности алгоритмов поиска паретовских путей в графе
3.5. Выводы по главе
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ
4.1. Функциональная структура специального программного обеспечения
4.2. Информационная структура специального программного обеспечения .
4.3. Маршрутизация компьютерных сетей
4.4. Задачи сетевого планирования и раскроя

4.5. Вычислительные эксперименты
4.6. Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

ВВЕДЕНИЕ

Актуальность проблемы. Повышение эффективности современнных существующих производств и разработка новых наукоёмких технологий в первую очередь достигается за счет оптимизации их структуры и параметров на основе применения информационных технологий и математического моделирования на базе современной вычислительной техники. Особое место в комплексе решаемых при этом задач занимают проблемы выбора и принятия решений, потребность в разрешении которых возникает на всем протяжении жизненного цикла любой, сколько-нибудь сложной системы.
В настоящее время у разработчиков технических, информационных и прочих систем имеется богатый арсенал программных средств для решения оптимизационных задач большой размерности и алгоритмической сложности. Однако применение таких формальных процедур выбора не позволяет сузить количество альтернативных вариантов решения настолько, чтобы лицо, принимающее решение (ЛПР), смогло непосредственно к ним применить какой-либо неформальный механизм выбора и восполнить информационную неполноту исходной постановки задачи своими знаниями, умением и интуицией. В связи с этим возникает фундаментальная научно-практическая проблема сужения множества альтернатив, необозримого для ЛПР, до приемлемых размеров.
Среди широчайшего класса научно-производственных проблем важное место занимают задачи оптимизации управления многоэтапными процессами. Одним из эффективнейших методов решения их дискретных вариантов является схема динамического программирования (ДП), применение которой позволяет на несколько порядков сократить множество альтернативных вариантов, т.е. решить проблему его сужения.
Словосочетание «динамическое программирование» (ДП) впервые было использовано в 1940-х годах Р. Веллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. В 1953 г. он уточнил

В более общем случае граф может иметь циклы, множество вариантов перехода из одного состояния в другое (как через промежуточные вершины, так и без них).
Таким образом, любая система, в которой есть необходимость поэтапного выбора, может быть представлена в виде графа, а набор оптимальных решений в этой системе можно интерпретировать как множество оптимальных путей в нём.
1.4. Исследования по оценке вычислительной сложности алгоритмов
поэтапного выбора
В самой общей постановке вопрос о вычислительной сложности алгоритма выглядит следующим образом. Пусть сформулирована массовая задача [34], или, по терминологии [69], дано семейство оптимизационных задач вместе с доступным для методов источником информации о каждой решаемой задаче из этого семейства. Требуется выяснить, каковы потенциальные нижние границы вычислительной сложности, т. е. трудоемкости всевозможных методов для задач рассматриваемого класса. 'Гочная постановка этого вопроса требует формализации понятий алгоритм и его вычислительной сложности, решение задачи и т.д. Недостающие строгие определения используемых терминов и понятий можно найти в [1, 34, 37, 68, 69, 73].
Используя понятие вычислительная сложность алгоритма, принимаем во внимание известный тезис Черча [68|: любой алгоритм может быть выражен как машина Тьюринга, и любая машина Тьюринга выражает любой алгоритм. В качестве меры вычислительной сложности алгоритма принимается время работы машины в худшем случае, как функции от размера входа.
Под шагом алгоритма понимается машинная команда, и при таком определении шага вычислительная сложность зависит от конкретной системы команд и способа трансляции. Нас же в дальнейшем будет интересовать не точная сложность алгоритма, вычисление которой практически невозможно, а асимптотическая сложность, которая определяется скоростью роста числа