Методы оптимизации




НазваниеМетоды оптимизации
Дата04.02.2016
Размер7.4 Kb.
ТипДокументы
Методы оптимизации


1. Введение в теорию сложности.


Понятие о сложности решения задач.

Основные определения: индивидуальная и массовая задачи, кодировка, алгоритм решения массовой задачи, временная сложность алгоритма. Классы Р и NР (формальные определения, примеры).

NР-полные (универсальные) задачи.

Теорема об экспоненциальной временной оценке для задач из класса NP. Класс со-NP. Задачи, допускающие хорошую характеризацию. Определение полиномиальной сводимости. Класс NPC. Теорема Кука /без док-ва/. Критерий NР-полноты. Док-во NP-полноты задачи ЦЛН.

Сильная NP-полнота и псевдополиномиальность.

Доказательство NP-подноты задачи 3-выполнимость. HP-трудные задачи. Взаимоотношение классов Р, NP и NPC, NP и co-NP. Класс PSPACE. Псевдополиномиальные алгоритмы. Пример для задачи о рюкзаке. Сильная NP-полнота. Теорема о связи сильной NP-полноты задачи с существованием псевдополиномиального алгоритма ее решения.

Приближенное решение задач комбинаторной оптимизации.

Определение комбинаторной задачи оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке. Определение е-приближенного алгоритма и полностью полиномиальной приближенной схемы /ПППС/. Связь между существованием ПППС и псевдополиномиальностью. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания. Пример задачи о коммивояжере.


2. Методы линейного программирования (ЛП).

Понятие о сложности задач ЛП.

Определение основной задачи ДП (озЛП). Принцип граничных решений и геометрическое описание симплекс-метода. Алгебраическая и битовая сложность ЛП. Результаты о сложности для задач, близких к ЛП.

Метод эллипсоидов.

Теорема о границах решений задач ЛП с целыми коэффициентами. Теорема о мере несовместности систем линейных неравенств с целыми коэффициентами. Полиномиальный алгоритм округления e1-приближенного решения системы линейных неравенств. Метод эллипсоидов е-приближенного решения озЛП. Оценка сложности метода эллипсоидов. Полиномиальность ЛП.

Теория двойственности ЛП.

Следствия систем линейных неравенств. Афинная лемма Фаркаша /без док-ва/. Лемма Фаркаша о неразрешимости. Теорема двойственности ЛП. Сведение озЛП к однородной системе уравнений с ограничением положительности.


3. Элементы математического программирования (МП).

Метод Кармаркара решения задач ЛП и обзор идей МП.

Метод Кармаркара - метод внутренней точки (в отличие от симплекс-метода). Понятие о градиентных и Ньютоновских методах минимизации. Условная оптимизация, способы освобождение от ограничений (методы барьеров и штрафов). Классификация задач МП. Преимущества выпуклого случая.

Двойственность в МП.

Необходимые условия локального минимума при ограничениях-неравенствах для дифференцируемых функций. Теорема Куна-Таккера. Понятие о регулярности ограничений-неравенств в задаче МП. Метод множителей Лагранжа.

4. Основные способы решения переборных задач.

Метод ветвей и границ (МВГ).

МВГ в глобальной оптимизации. Общее описание метода. Стратегии МВГ. МВГ для булева программирования (БД).

Целочисленное линейное программирование (ЦЛП).

Отличие задач ЦЛП и ЛП: существенная нелинейность ограничений типа целочисленности. Неэффективность округления решения ЛП до ближайшего целого. Случай вполне унимодулярной матрицы ограничений. МВГ в ЦЛП.

Метод динамического программирования (ДП).

Общая схема метода. Пример для задачи о рюкзаке. Теоретические основы ДП. Метод ДП для БП с неотрицательными коэффициентами. Связь с МВГ.


Литература:

  1. М. Гэри, Д. Джонсон "Вычислительные машины и труднорешаемые задачи", М.: МИР, 1902.

  2. Х-Пападимитриу, К-Стайглиц "Комбинаторная оптимизация", М.: Мир, 1985.

  3. Л.Г.Хачиян "Сложность задач ЛП", Знание, 1987, No .10.

  4. А.Г. Сухарев, А.В. Тимохов, В.В. Федоров "Курс методов оптимизации", М.: Наука, 1985.

  5. В.Г. Карманов "Математическое программирование". М.: Наука, 1986.

  6. А.Г. Сухарев, А.В. Тимохов, В.В. Федоров "Курс методов оптимизации", М.: Наука, 1985.

  7. М. Мину "Математическое программирование", М.: Наука, 1990.

  8. Х. Пападимитриу, К. Стайглиц "Комбинаторная оптимизация", М.: Мир, 1985.

Похожие:

Методы оптимизации icon«Методы оптимизации»
Изучение основ теории оптимизации и методов решения некоторых задач оптимизации аналитическими методами
Методы оптимизации icon1. Цель занятия
...
Методы оптимизации iconСписок литературы ахназарова С. Л., Кафаров В. В. Методы оптимизации эксперимента в химической технологии. М.: Высшая школа, 1985. Бахвалов Н. С. Численные методы. М.: Наука, 1975
Методы оптимизации эксперимента в химической технологии. М.: Высшая школа, 1985
Методы оптимизации iconОтчет по дисциплине «методы оптимизации и принятия решения»
«лабораторная работа №4. Программная реализация методов оптимизации функции одной переменной (метод ломаных)»
Методы оптимизации iconИнструментарий основные приёмы и методы работы с информацией. Методы оптимизации информации (ОИ)
В основе методов ои (уменьшения) лежит целенаправленность и целеобусловленность деятельности, в соответствии с которыми формируется...
Методы оптимизации iconМетоды оптимизации
Специальность 351500 – математическое обеспечение и администрирование информационных систем
Методы оптимизации iconБиблиографический список
Аттетков А. В., Галкин С. В., Зарубин В. С. Методы оптимизации. – М.: Изд-во мгту им. Н. Э. Баумана, 2001 –440 с
Методы оптимизации iconРабочая программа дисциплины опд. Ф. 12 «Прикладные методы оптимизации»
Государственного образовательного стандарта высшего профессионального образования 27. 12. 2005г
Методы оптимизации iconРабочая программа учебной дисциплины «Исследование операций в задачах оптимизации»
«Теория и математические методы системного анализа и управления в технических и социально-экономических системах»
Методы оптимизации iconПрикладные задачи оптимального управления и численные методы их решения
Краевая задача принципа максимума и ее анализ. Численные методы решения краевой задачи принципа максимума – метод стрельбы и метод...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib2.znate.ru 2012
обратиться к администрации
Библиотека
Главная страница