Основные понятия теории оптимизации

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

Введение………………………………………………………………………....3
1. Основные понятия теории оптимизации……………………………...…5
1.1. Общая постановка задачи оптимизации…………………………………..5
1.2. Ограничения на допустимое множество……………………………...…6
1.3. Классическая задача оптимизации……………………………………….6
1.4. Функция Лагранжа…………………………………………………………6
2. Линейное программирование: формулировка задач и их
графическое решение………………………………………………………….8
2.1. Задача ЛП……………………………………………………………………8
2.2. Графическое решение задачи ЛП………………………………………….9
3. Алгебраический метод решения задач……………………………………11
3.1. Стандартная форма линейных оптимизационных моделей……………...11
3.2. Симплекс-метод………………………………………………………….....12
4. Двойственность………………………………………………………………25
Заключение……………………………………………………………………...29
Библиографический список ……………………………………………...…..30