ЗЛП і її властивості

Основні властивості ЗЛП і теореми лінійного програмування
1. Застосування класичного апарату математичного аналізу для вирішення ЗЛП
2. Теорема про оптимальність вершини багатогранника
3. Базисні розв’язки
4. Теореми ЛП
Теорема «ДБР↔вершина»
Фундаментальна теорема
Теорема про скінченність множини ДБР ЗЛП
Теорема про скінченність координат ДБР

Існування глобального розв’язку

Існування глобального розв’язку

Величина постійна і не залежить від точки обчислення

Теорема про оптимальність вершини багатогранника

Теорема про оптимальність вершини багатогранника
Доведення частини І: «максимум у вершині»

Теорема про оптимальність вершини багатогранника.
Доведення частини І: «максимум у вершині»

Теорема про оптимальність вершини багатогранника.
Доведення частини І: «максимум у вершині»

Теорема про оптимальність вершини багатогранника
Доведення частини І: «максимум у вершині»

Теорема про оптимальність вершини багатогранника
Доведення частини І: «максимум у вершині»

Теорема про оптимальність вершини багатогранника
Доведення частини ІІ

Базисні розв’язки
(Алгебраїчне представлення вершин)
ЗЛП:
ЗЛП в КФ

Базисні розв’язки
(Алгебраїчне представлення вершин)
Кожну точку цієї множини можна визначити за допомогою шести змінних

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)
Щоб система мала єдиний розв’язок, стовпці матриці обмежень повинні бути лінійно незалежними

Базисні розв’язки
(Алгебраїчне представлення вершин)

Базисні розв’язки
(Алгебраїчне представлення вершин)

Процедура знаходження базисних розв’язків (БР)

Допустимі базисні розв’язки (ДБР)

Приклад екзаменаційного завдання (0)
Чи є базисом наступні множини векторів?
Якщо так, то знайти відповідний базисний розв’язок.
Чи є він допустимим?

Приклад екзаменаційного завдання (1)
ДБР

Приклад екзаменаційного завдання (2)
БР не допустимий

Приклад екзаменаційного завдання (3)

Приклад екзаменаційного завдання (4)

Приклад екзаменаційного завдання (5)

ДБР ↔ ВЕРШИНА

Доведення

Теорема (фундаментальна)
Якщо ЗЛП має оптимальний розв’язок (у обмеженій області завжди, а в необмеженій – залежно від обмеженості цільової функції), то він збігається, принаймні, з одним з ДБР системи обмежень.

Теорема про скінченність множини ДБР ЗЛП

Теорема про скінченність множини ДБР ЗЛП

БР vs ДБР vs Вершини (екз.завдання)
Яка кількість БР, ДБР, вершин?
БР: 26 ДБР: 8 Вершин: 3

Теорема про скінченність координат ДБР
(Довести самостійно №)

Приклад екзаменаційного завдання
Знайти верхню межу компонентів ДБР ЗЛП: