Властивості розв’язків задачі лінійного програмування. Геометрична інтерпретація задач лінійного програмування.

Для розв'язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв'язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе. Розглянемо на площині Х10x2 сумісну систему лінійних нерівностей:

(2.9)

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою ai 1 x 1 + ai 2 x 2 = bi (i = 1, 2,..., т). Умови невід’ємності змінних визначають півплощини з граничними прямими х 1 = 0 та х 2 = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис. 2.1)

Сукупність цих точок (розв’язків) називають багатокутником розв’язків, або областю допустимих планів (розв’язків) задачі лінйного програмування. Це може бути точка (єдиний розв’язок), відрізок, промінь, багатокутник, необмежена багатокутна область.

Якщо в системі обмежень (2.9) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть ai 1 x 1 + ai 2 x 2 + ai 3 x 3 = bi(i = 1, 2,..., т), а умови невід’ємності — півпростори з граничними площинами хj = 0 (j = 1, 2, 3), де і — номер обмеження, а j — номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Геометрично задача лінійного програмування являє собою відшукання координат такої точки багатогранника розв’язків, при підстановці яких у цільову лінійну функцію остання набирає максимального (мінімального) значення, причому допустимими розв’язками є усі точки багатогранника розв’язків. Властивості розв’язків задачі лінійного програмування формулюються у вигляді чотирьох теорем (доведення теорем та їх наслідки наведено нижче).

Властивість 1. (Теорема 2.2) Множина всіх планів задачі лінійного програмування опукла.

Властивість 2. (Теорема 2.3) Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин її багатогранника розв’язків. Якщо ж цільова функція набуває екстремального значення більш як в одній вершині цього багатогранника, то вона досягає його і в будь-якій точці, що є лінійною комбінацією таких вершин.

Властивість 3. (Теорема 2.4) Якщо відомо, що система векторів A1, A2, …, Ak (k ≤ n) у розкладі A1x1 +A2x2 + … + Anxn = A0, X ≥ 0 лінійно незалежна і така, що A1x1 + A2x2 + … + Akxk = A0, де всі xj ≥ 0, то точка X = (x1, x2, …, xk, 0, …, 0) є кутовою точкою багатогранника розв’язків.

Властивість 4. (Теорема 2.5) Якщо X = (x1, x2, …, xn) — кутова точка багатогранника розв’язків, то вектори в розкладі A1x1 + + A2x2 + … + Anxn = A0, X ≥ 0, що відповідають додатним xj, є лінійно незалежними.

 

 

30.Алгоритм графічного методу розв’язування задач лінійного програмування.

Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків:

1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв’язків задачі лінійного програмування.

4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5. Будуємо пряму с 1 х 1 + с 2 х 2 = const, перпендикулярну до вектора .

6. Рухаючи пряму с 1 х 1 + с 2 х 2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального зна- чення.

7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.

31.Означення планів задачі лінійного програмування (допустимий, опорний, оптимальний).

Допустимий план Х = (х ₁, х ₂, …, х_n) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (3.2) у вигляді рівностей, а також обмеження (3.3) щодо невід’ємності змінних.
Опорний план Х = (х ₁, х ₂, …, х_n), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.
Опорний план , за якого цільова функція (3.1) досягає масимального (чи мінімального) значення, називається оптимальним розв’язком (планом) задачі лінійного програмування. Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою a_{i 1} x ₁ + a_{i 2} x ₂ = b_i (i = 1, 2,..., т). Умови невід’ємності змінних визначають півплощини з граничними прямими х ₁ = 0 та х ₂ = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи.
Сукупність цих точок (розв’язків) називають багатокутником розв’язків, або областю допустимих планів (розв’язків) задачі лінйного програмування. Це може бути точка (єдиний розв’язок), відрізок, промінь, багатокутник, необмежена багатокутна область.

32.Знаходження оптимального розв’язку задачі лінійного програмування. Алгоритм симплексного методу. Суть симплексного методу полягає в тому, що спочатку отримують допустимий розв'язок, який задовольняє всім обмеженням, але не обов'язково оптимальний (початковий опорний план); оптимальність досягається послідовним поліпшуванням початкового варіанту за декілька ітерацій. Напрямок переходу від одного опорного плану до другого вибирається за критерієм оптимальності (цільової функції).Симплекс-метод основується на властивостях ЗЛП: 1. Якщо є екстремум, то він єдиний. 2. Множина всіх планів ЗЛП опукла.3. Цільова функція досягає свого оптимального значення у вершині багатокутника розв'язків..4. Кожній вершині багатокутника розв'язків відповідає опорний план ЗЛП. Для того, щоб вирішити задачу симплексним методом необхідно виконати наступне:

1)Привести завдання до канонічного виду 2) Знайти початкове опорне рішення з "одиничним базисом" (якщо опорне рішення відсутнє, то завдання не має рішення зважаючи несумісності системи обмежень) 3) Обчислити оцінки розкладів векторів по базису опорного рішення і заповнити таблицю симплексного методуЯкщо виконується ознака єдиності оптимального рішення, то рішення задачі закінчуєтьсяЯкщо виконується умова існування множини оптимальних рішень, то шляхом простого перебору знаходять все оптимальні рішення

Якщо потрібно максимізувати цільову функцію, то можна перейти до мінімуму max Ly = min(-Ly).Зведемо задачу (13.12), (13.13) до канонічного виду шляхом введення додаткових змінних - y5, y6, y7.

Якщо нерівність в системі обмежень ЗЛП має знак " ≤ ", то додаткову змінну вводять зі знаком "+"; якщо нерівність має знак " ≥ ", то додаткову змінну вводять зі знаком "- ".