Презентация Задача лінійного програмування та деякі методи їх розвязування онлайн

Содержание слайда: Дисципліна “Інформаційні технології аналізу систем” Лекція 8-9

Содержание слайда: Загальна задача лiнiйного програмування та її подання в канонічній формі. Загальна задача лiнiйного програмування та її подання в канонічній формі. Поняття плану, опорного плану, невиродженого опорного плану, оптимального плану задачі лінійного програмування. Властивості розв’язків задачі лінійного програмування. Геометричний метод розв’язування задачі лінійного програмування.

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Розглянемо задачу лінійного програмування, записану в канонічній формі: Розглянемо задачу лінійного програмування, записану в канонічній формі:

Содержание слайда: Введемо позначення: Введемо позначення:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Запишемо задачу (5) – (7) у матричному вигляді: Запишемо задачу (5) – (7) у матричному вигляді: (8) (9) (10)

Содержание слайда: Теорема 1. Множина всіх планів задачі (8)–(10) – опукла. Теорема 1. Множина всіх планів задачі (8)–(10) – опукла. Опуклу множину планів задачі лінійного програмування позначимо через М. Зауважимо, що М може бути порожньою множиною, опуклим многогранником або необмеженою опуклою многогранною областю.

Содержание слайда: Нехай лінійна функція задачі лінійного програмування обмежена знизу і зверху на множині планів. Нехай лінійна функція задачі лінійного програмування обмежена знизу і зверху на множині планів. Теорема 2. Лінійна функція задачі лінійного програмування (8) – (10) досягає мінімального (максимального) значення у крайній точці опуклої множини М планів задачі. Якщо лінійна функція набуває мінімального (максимального) значення більш ніж в одній крайній точці, то вона набуває цього ж значення в будь-якій точці, яка є опуклою комбінацією цих точок.

Содержание слайда: Теорема 3 (критерій крайності точки опуклої множини планів). Для того щоб точка Х, яка містить m додатніх координат, була крайньою точкою множини планів М задачі лінійного програмування (8)-(10), необхідно і досить, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему. Теорема 3 (критерій крайності точки опуклої множини планів). Для того щоб точка Х, яка містить m додатніх координат, була крайньою точкою множини планів М задачі лінійного програмування (8)-(10), необхідно і досить, щоб вектори , які відповідають додатним компонентам , утворювали лінійно незалежну систему.

Содержание слайда: Розглянемо двовимiрну задачу мiнiмiзацiї: Розглянемо двовимiрну задачу мiнiмiзацiї: (11) Лiнiєю (поверхнею) рiвня функцiї є множина точок

Содержание слайда:

Содержание слайда:

Содержание слайда: Особливість геометричної інтерпретації двовимірної задачі лінійного програмування Особливість геометричної інтерпретації двовимірної задачі лінійного програмування полягає в тому, що: - допустима множина X являє собою опуклу многокутну область (обмежену) або необмежену;

Содержание слайда: лінія рівня цільової функції є пряма, при цьому градієнт функції - вектор лінія рівня цільової функції є пряма, при цьому градієнт функції - вектор перпендикулярний цій прямій і є напрямом найшвидшого зростання цільової функції в кожній точці допустимої множини X, а антиградієнт (вектор ) є напрямом її найшвидшого спадання; якщо задача має розв’язок, то він досягається обов’язково на межі допустимої множини X, а сам розв’язок задачі є або деяка вершина многокутника або множина точок деякої його сторони.

Содержание слайда:

Содержание слайда:

Содержание слайда: Розглянемо більш детально алгоритм розв'язування двовимірної задачi лiнiйного програмування виду: Розглянемо більш детально алгоритм розв'язування двовимірної задачi лiнiйного програмування виду: (12) (13)

Содержание слайда: 1. Побудувати прямi, рiвняння яких одержуються внаслiдок замiни в обмеженнях (13) знакiв нерiвностей на знаки рiвностей. 1. Побудувати прямi, рiвняння яких одержуються внаслiдок замiни в обмеженнях (13) знакiв нерiвностей на знаки рiвностей. 2. Знайти пiвплощини, якi визначаються кожним з обмежень-нерівностей задачi. 3. Знайти множину допустимих розв”язкiв задачі M, як перетин знайдених півплощин.

Содержание слайда: 4. Побудувати пряму (лінію рівня цільової функції), при цьому величина h підбирається так, щоб лінія рівня проходила через множину допустимих розв”язкiв М. Побудувати вектор . 4. Побудувати пряму (лінію рівня цільової функції), при цьому величина h підбирається так, щоб лінія рівня проходила через множину допустимих розв”язкiв М. Побудувати вектор . 5. Рухаючи пряму в напрямі вектора с при розв”язуванні задачі максимізації (або в зворотньому напрямі при розв”язанні задачі мінімізації), знайти точку (множину точок), де цiльова функцiя приймає максимальне (мiнiмальне) значення, або встановити необмеженiсть зверху (знизу) функцiї на допустимій множинi.

Содержание слайда: 6. Якщо існує єдиний розв’язок задачі, визначити координати знайденої точки як розв’язок системи двох відповідних рівнянь з двома невідомими, i обчислити значення цiльової функцiї в цiй точцi. Якщо існує безліч розв’язків, то визначити координати принаймні однієї екстремальної точки i обчислити значення цiльової функцiї в цiй точцi. 6. Якщо існує єдиний розв’язок задачі, визначити координати знайденої точки як розв’язок системи двох відповідних рівнянь з двома невідомими, i обчислити значення цiльової функцiї в цiй точцi. Якщо існує безліч розв’язків, то визначити координати принаймні однієї екстремальної точки i обчислити значення цiльової функцiї в цiй точцi.

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: