Симплексный метод

Пример
Множество планов
Оптимальный план

Гипотезы

Гипотезы
В общем многомерном случае эти гипотезы нужно доказать!

4.2. Свойства планов задачи ЛП

Алгебраический подход
Алгебраический подход

Свойство 1

Свойство 2

Опорные планы
Частные решения системы ЛУ
С алгебраической точки зрения решить задачу линейного программирования – значит найти
1) неотрицательное
2) частное решение системы линейных уравнений,
3) дающее экстремум целевой функции
Неотрицательные частные решения (планы)
Неотрицательные базисные решения (опорные планы)
Как найти крайнюю точку чисто алгебраическим способом?
Оптимальный план

Опорные планы
Пример
Гипотеза?

Свойство 3

Свойство 3
Достаточность самостоятельно

Общая схема решения задачи ЛП
Пример
Чем плох этот метод?

4.3. Теория симплексного метода

Общая идея – упорядочение перебора

Ограничение перебора

Ограничение перебора

Ограничение перебора

Ограничение перебора

Ограничение перебора
Пример

Ограничение перебора

Направленность перебора

Направленность перебора

Направленность перебора

Направленность перебора

Критерий оптимальности

Критерий оптимальности

Критерий оптимальности

Критерий оптимальности

Критерий оптимальности

Критерий оптимальности

Схема симплексного метода

Схема симплексного метода

Иллюстрация в трехмерном пространстве

4.4. Практический алгоритм симплексного метода

Симплексная таблица

Алгоритм

Алгоритм

Алгоритм

Пример
Задача о производственном плане
Подготовительный этап

Пример
Итерация 1

4.5. Метод искусственного базиса

Идея
Исходная задача
Расширенная задача

Пример
Расширенная задача

Пример
Первый этап