Властивості задачі лінійного програмування

Властивості задачі лінійного програмування
3.1 Форми ЗЛП
3.2 Еквівалентність форм ЗЛП
3.3 Множина допустимих розв’язків ЗЛП (багатогранні множини, багатогранники, вершини, грані)
3.4 Основні властивості ЗЛП і теореми лінійного програмування

Задача лінійного програмування (ЗЛП)

Задача лінійного програмування (ЗЛП)

Економічна інтерпретація ЗЛП

Основні припущення
1) пропорційність,
2) адитивність,
3) невід’ємність
Пропорційність означає, що витрати ресурсів на деякий вид продукції прямо пропорційні його обсягу випуску, а вклад цього виду продукції в ЦФ також прямо пропорційний його обсягу випуску.
Адитивність означає, що загальна величина ресурсу, використовуваного на виробництво всіх видів продукції, дорівнює сумі витрат цього ресурсу на окремі види продукції. Аналогічно інтерпретується і ЦФ.
Самостійно №1 Навести приклади проблемних ситуацій, в яких порушені ці припущення

ФОРМИ ЗЛП
(1)-(5)

Саме для канонічної ЗЛП розроблено метод розв’язання
Далі будемо розглядати задачі на максимум

Еквівалентність форм ЗЛП

Правила перетворення форм ЗЛП ①

Правила перетворення форм ЗЛП ②
залишкова змінна

Правила перетворення форм ЗЛП ③
надлишкова змінна

Правила перетворення форм ЗЛП ④

Правила перетворення форм ЗЛП ⑤

Правила перетворення форм ЗЛП ⑥

Правила перетворення форм ЗЛП ⑥

Правила перетворення форм ЗЛП ⑥

Правила перетворення форм ЗЛП ⑦

Правила перетворення форм ЗЛП ⑧

Приклад №1 (1)
Привести задачу до КФ

Приклад №1 (2)
КАНОНІЧНА ФОРМА
Не відповідають КФ

Приклад №1 (3)

Приклад №1 (3)

Приклад №1 (4)

Приклад №1 (5)

Приклад №1 (5)

Приклад №1 (6)

Приклад №1 (7)

Приклад №1 (7)

Приклад №1 (8)

Приклад №1 (9)
ЗЛП в КФ

Приклад №1 (Відповідь)
ЗЛП в КФ
Вихідна ЗЛП

Зведення ЗЛП в стандартній формі до канонічної

Зведення ЗЛП в стандартній формі до канонічної

Зведення ЗЛП в стандартній формі до канонічної

Зведення ЗЛП в стандартній формі до канонічної

Вихідна ЗЛП в СФ ЗЛП в КФ
Зведення ЗЛП в стандартній формі до канонічної

Приклад №2 зведення до КФ
Вихідна ЗЛП:
z = 5x1 + 6x2 → max
3x1 + 4x2 ≤ 7
2x1 + 1x2 ≥ 10
5x1 + 8x2 ≤ 11
x1, x2 ≥ 0

Приклад №2 зведення до КФ
Вихідна ЗЛП:
z = 5x1 + 6x2 → max
3x1 + 4x2 ≤ 7
2x1 + 1x2 ≥ 10
5x1 + 8x2 ≤ 11
x1, x2 ≥ 0
ЗЛП в канонічній формі:
z = 5x1 + 6x2 + 0s1 + 0s2 + 0s3 → max
3x1 + 4x2 + s1 = 7
2x1 + 1x2 - s2 = 10
5x1 + 8x2 + s3 = 11
x1, x2, s1, s2, s3 ≥ 0

Приклад №3 зведення до КФ
Вихідна ЗЛП:
z = 3x1 + 9x2 → min
2x1 + 6x2 ≤ 9
5x1 + 5x2 ≥ 4
3x1 + 8x2 ≤ 6
x1 ≥ 0

Приклад №3 зведення до КФ
Вихідна ЗЛП:
z = 3x1 + 9x2 → min
2x1 + 6x2 ≤ 9
5x1 + 5x2 ≥ 4
3x1 + 8x2 ≤ 6
x1 ≥ 0
x2 <=> 0 x2 = x2+ - x2-
x2+, x2- ≥ 0
ЗЛП в канонічній формі :
z = 3x1 + 9x2+ - 9x2- + 0s1 + 0s2 + 0s3 → min
2x1 + 6x2+ - 6x2- +s1 = 9
5x1 + 5x2+ - 5x2- -s2 = 4
3x1 + 8x2+ - 8x2- +s3 = 6
x1, x2+, x2-, s1, s2, s3 ≥ 0

Екзаменаційне завдання А
min z = 9x1 − 3x2
2x1 + 8x2 − 9x3 = 5
5x1 − 3x2 + 4x3 = 13
x1 + 2x2 −­ 6x3 = 22
x1 , x2 ≥ 0
Побудувати еквівалентну їй задачу ЛП в стандартній формі з 4 нерівностями

Екзаменаційне завдання Б
min z = 9x1 − 3x2
2x1 + 8x2 − 9x3 = 5
5x1 − 3x2 + 4x3 = 13
x1 + 2x2 −­ 6x3 = 22
Побудувати еквівалентну їй задачу ЛП на максимум в стандартній формі з 5-ма нерівностями і 4-ма з мінними