Слайд 2Властивості задачі лінійного програмування
3.1 Форми ЗЛП
3.2 Еквівалентність форм ЗЛП
3.3 Множина допустимих розв’язків
![Властивості задачі лінійного програмування 3.1 Форми ЗЛП 3.2 Еквівалентність форм ЗЛП 3.3](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-1.jpg)
ЗЛП (багатогранні множини, багатогранники, вершини, грані)
3.4 Основні властивості ЗЛП і теореми лінійного програмування
Слайд 3Задача лінійного програмування (ЗЛП)
![Задача лінійного програмування (ЗЛП)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-2.jpg)
Слайд 4Задача лінійного програмування (ЗЛП)
![Задача лінійного програмування (ЗЛП)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-3.jpg)
Слайд 5Економічна інтерпретація ЗЛП
![Економічна інтерпретація ЗЛП](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-4.jpg)
Слайд 6Основні припущення
1) пропорційність,
2) адитивність,
3) невід’ємність
Пропорційність означає, що витрати ресурсів на деякий вид
![Основні припущення 1) пропорційність, 2) адитивність, 3) невід’ємність Пропорційність означає, що витрати](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-5.jpg)
продукції прямо пропорційні його обсягу випуску, а вклад цього виду продукції в ЦФ також прямо пропорційний його обсягу випуску.
Адитивність означає, що загальна величина ресурсу, використовуваного на виробництво всіх видів продукції, дорівнює сумі витрат цього ресурсу на окремі види продукції. Аналогічно інтерпретується і ЦФ.
Самостійно №1 Навести приклади проблемних ситуацій, в яких порушені ці припущення
Слайд 11Саме для канонічної ЗЛП розроблено метод розв’язання
Далі будемо розглядати задачі на максимум
![Саме для канонічної ЗЛП розроблено метод розв’язання Далі будемо розглядати задачі на максимум](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-10.jpg)
Слайд 15Правила перетворення форм ЗЛП ②
залишкова змінна
![Правила перетворення форм ЗЛП ② залишкова змінна](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-14.jpg)
Слайд 16Правила перетворення форм ЗЛП ③
надлишкова змінна
![Правила перетворення форм ЗЛП ③ надлишкова змінна](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-15.jpg)
Слайд 24Приклад №1 (1)
Привести задачу до КФ
![Приклад №1 (1) Привести задачу до КФ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-23.jpg)
Слайд 25Приклад №1 (2)
КАНОНІЧНА ФОРМА
Не відповідають КФ
![Приклад №1 (2) КАНОНІЧНА ФОРМА Не відповідають КФ](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-24.jpg)
Слайд 36Приклад №1 (Відповідь)
ЗЛП в КФ
Вихідна ЗЛП
![Приклад №1 (Відповідь) ЗЛП в КФ Вихідна ЗЛП](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-35.jpg)
Слайд 37
Зведення ЗЛП в стандартній формі до канонічної
![Зведення ЗЛП в стандартній формі до канонічної](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-36.jpg)
Слайд 38Зведення ЗЛП в стандартній формі до канонічної
![Зведення ЗЛП в стандартній формі до канонічної](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-37.jpg)
Слайд 39
Зведення ЗЛП в стандартній формі до канонічної
![Зведення ЗЛП в стандартній формі до канонічної](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-38.jpg)
Слайд 40
Зведення ЗЛП в стандартній формі до канонічної
![Зведення ЗЛП в стандартній формі до канонічної](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-39.jpg)
Слайд 41Вихідна ЗЛП в СФ ЗЛП в КФ
Зведення ЗЛП в стандартній формі до
![Вихідна ЗЛП в СФ ЗЛП в КФ Зведення ЗЛП в стандартній формі до канонічної](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-40.jpg)
канонічної
Слайд 42Приклад №2 зведення до КФ
Вихідна ЗЛП:
z = 5x1 + 6x2 → max
![Приклад №2 зведення до КФ Вихідна ЗЛП: z = 5x1 + 6x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-41.jpg)
3x1 + 4x2 ≤ 7
2x1 + 1x2 ≥ 10
5x1 + 8x2 ≤ 11
x1, x2 ≥ 0
Слайд 43Приклад №2 зведення до КФ
Вихідна ЗЛП:
z = 5x1 + 6x2 → max
![Приклад №2 зведення до КФ Вихідна ЗЛП: z = 5x1 + 6x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-42.jpg)
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
Слайд 44Приклад №3 зведення до КФ
Вихідна ЗЛП:
z = 3x1 + 9x2 → min
![Приклад №3 зведення до КФ Вихідна ЗЛП: z = 3x1 + 9x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-43.jpg)
2x1 + 6x2 ≤ 9
5x1 + 5x2 ≥ 4
3x1 + 8x2 ≤ 6
x1 ≥ 0
Слайд 45Приклад №3 зведення до КФ
Вихідна ЗЛП:
z = 3x1 + 9x2 → min
![Приклад №3 зведення до КФ Вихідна ЗЛП: z = 3x1 + 9x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-44.jpg)
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
Слайд 46Екзаменаційне завдання А
min z = 9x1 − 3x2
2x1 + 8x2 −
![Екзаменаційне завдання А min z = 9x1 − 3x2 2x1 + 8x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-45.jpg)
9x3 = 5
5x1 − 3x2 + 4x3 = 13
x1 + 2x2 − 6x3 = 22
x1 , x2 ≥ 0
Побудувати еквівалентну їй задачу ЛП в стандартній формі з 4 нерівностями
Слайд 47Екзаменаційне завдання Б
min z = 9x1 − 3x2
2x1 + 8x2 −
![Екзаменаційне завдання Б min z = 9x1 − 3x2 2x1 + 8x2](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1039142/slide-46.jpg)
9x3 = 5
5x1 − 3x2 + 4x3 = 13
x1 + 2x2 − 6x3 = 22
Побудувати еквівалентну їй задачу ЛП на максимум в стандартній формі з 5-ма нерівностями і 4-ма з мінними