глава 2. Линейное программирование

Линейное программирование 1
Определение задачи ЛП
КЗЛП и построение канонической формы
Первая геометрическая интерпретация и графический метод решения
Основные теоремы ЛП
Вторая геометрическая интерпретация и базисные планы
Теоремы о базисных планах

Линейное программирование 2
Симплекс-метод, алгоритм
Модифицированный симплекс-метод
Симплекс-метод, обоснование
Проблема вырожденности
Альтернативные оптимальные планы
Метод минимизации невязок

Общая задача линейного программирования
Общая задача линейного программирования (ОЗЛП)

Каноническая задача линейного программирования 2
Каноническая задача линейного программирования (ОЗЛП)

Построение канонической формы 1

Построение канонической формы 2

Первая геометрическая интерпретация ЗЛП
x2 ≥ 0
x1 ≥ 0
Рассмотрим задачу-базовый пример

Графический метод решения ЗЛП 1

Решение достигается в угловой точке
Принципиальные ситуации, возможные при решении задачи линейного программирования
(a)
(b)
(c)
Целевая
функция не ограничена
Бесконечное
множество
решений

Графический метод решения ЗЛП 2
Рассмотрим задачу

Основные теоремы ЛП 1
☝ Теорема
? Доказательство
Теорема о представлении многогранного выпуклого множества

Основные теоремы ЛП 2

Основные теоремы ЛП 3
- угловые точки

Основные теоремы ЛП 4
- направляющие вектора конуса
(!) рассуждения «от противного»

Основные теоремы ЛП 5
По свойства многогранного выпуклого конуса:
(1)
?

Основные теоремы ЛП 5
(2)
?
(3)
?

Вторая геометрическая интерпретация ЗЛП 1
(!) без ограничения общности
Аx = b
несовместна
существуют линейно-зависимые ограничения

Вторая геометрическая интерпретация ЗЛП 1

Базисный план 1

Базисный план 2

Базисный план 3
☞ базисный план-невырожденный:
вырожденный – в противном случае.

Базисный план 4

Теоремы о свойствах базисных планов 1
☝ Теорема
Каждый допустимый базисный план является угловой точкой множества допустимых планов

Теоремы о свойствах базисных планов 2

Базисные планы (пример)

Симплекс-метод, историческая справка
Джордж Данциг
(1914-2005), 1947
Леонид Витальевич
Канторович
(1912-1986), 1939

Симплекс-метод, геометр. интерпретация 1

Симплекс-метод, геометр. интерпретация 2

Симплекс-метод, геометр. интерпретация 3

Симплекс-метод алгоритм
0-итерация: Определение исходного допустимого базисного плана
Определение выводимого столбца

Симплекс-метод
критерий оптимальности

Симплекс-метод
определение выводимого столбца

Симплекс-метод,
неограниченность

Симплекс-метод, симплекс-таблица
Номера базисных столбцов
Столбец ограничений в текущем базисе
Матрица задачи в текущем базисе
Строка «оценок»
Значение цел.функции на текущем плане
Значения λ, рассч.при определен. выводимого столбца

Симплекс-метод, пример (0)
Исходный
допустимый
базис

Симплекс-метод, пример (1)

Симплекс-метод, пример (2)
35:7=5
8:1=8
Разрешающий
элемент
:7
5:5/7=7
3:9/7=7/3
Разрешающий
элемент

Симплекс-метод, пример (3)
План оптимальный !!!

Симплекс-метод,
метод минимизации невязок

Обоснование симплекс-метода Т1/1

Обоснование симплекс-метода Т1/2

Обоснование симплекс-метода Т2/1
(T2.1)

Обоснование симплекс-метода Т2/2
?
?

Обоснование симплекс-метода Т2/3

Обоснование симплекс-метода Т3/1
(T3.1)

Обоснование симплекс-метода Т4/1

Сходимость симплекс-метода и проблема вырожденности 1
Рассмотрим пример

Сходимость симплекс-метода и проблема вырожденности 2

Сходимость симплекс-метода и проблема вырожденности 3

Сходимость симплекс-метода и проблема вырожденности 4

Сходимость симплекс-метода и проблема вырожденности 5
(☝) Базовая идея: переход к «возмущённой» задаче
(В.1)

(☝) Теорема Чарнса
Сходимость симплекс-метода и проблема вырожденности 6

Альтернативные оптимальные планы 1
Рассмотрим пример

Альтернативные оптимальные планы 2

Альтернативные оптимальные планы 3

Модифицированный симплекс-метод 1

Модифицированный симплекс-метод 2

Модифицированный симплекс-метод, пример 1

Модифицированный симплекс-метод, пример 2

Модифицированный симплекс-метод, пример 3