Аннотация

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

Содержание

1. ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ
   • 1. Понятие о сложности решения задач
   • 2. NP-полные (универсальные) задачи
   • 3. Классы сложности. Сильная NP-полнота и псевдополиномиальность
   • 4. Приближенное решение задач комбинаторной оптимизации
2. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
   • 5. Понятие о сложности задачи линейного программирования (ЛП)
   • 6. Метод эллипсоидов
   • 7. Теория двойственности ЛП. Идея метода Кармаркара
3. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
   • 8. Обзор идей математического программирования (МП)
   • 9. Двойственность в МП
4. СПОСОБЫ РЕШЕНИЯ ПЕРЕБОРНЫХ ЗАДАЧ
   • 10. Глобальная оптимизация.Метод ветвей и границ (МВГ)
   • 11. Целочисленное линейное программирование (ЦЛП)
   • 12. Метод динамического программирования (ДП)