Главная | Обратная связь | Поможем написать вашу работу!

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

Розглянемо основну задачу лінійного програмування. Як було відзначено в § 1.2, вона полягає у визначенні максимального значення функції

при умовах

Перепишемо цю задачу у векторній формі: знайти максимум функції

F=СХ (15)

при умовах

х₁Р₁+х₂Р₂+...+х_nР_n=Р₀,(16)

X ≥ 0, (17)

де C= (c₁; c₂;...; с_п), Х= (х₁; х₂;...; х_п); СХ – скалярний добуток; Р₁,..., Р_п і Р₀ – т -мірні вектори-стовпці, що складаються з коефіцієнтів при невідомих і вільних членах системи рівнянь задачі:

Визначення 1.7. План Х= (х₁; х₂;...; х_п)називається опорним планом основної задачі лінійного програмування, якщо система векторів Р_j, що входять у розклад (16) з додатними коефіцієнтами х_j,лінійно незалежна.

Так як вектори Р_j є т -мірними, то з визначення опорного плану випливає, що число його додатних компонентів не може бути більше, ніж т.

Визначення 1.8. Опорний план називається не виродженим, якщо він містить рівно т позитивних компонентів, у противному випадку він називається виродженим.

Властивості основної задачі лінійного програмування (15)-(17) тісним чином пов’язані із властивостями випуклих множин.

Визначення 1.9. Нехай X₁, X₂,..., X_п – довільні точки евклідового простору Е_п. Випуклою лінійною комбінацією цих точок називається сума α₁X₁+α₂X₂+…+ α_nX_n,де α_i, – довільні невід’ємні числа, сума яких дорівнює 1:

Визначення 1.10. Множина називається випуклою,якщо разом з будь-якими двома своїми точками вона містить і їх довільну випуклу лінійну комбінацію.

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

Теорема 1.1. Множина планів основної задачі лінійного програмування є випуклою (якщо вона не порожня).

Визначення 1.12. Непуста множина планів основної задачі лінійного програмування називається багатогранником розв’язків, а всяка кутова точка багатогранника розв’язків – вершиною.

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

Теорема 1.3. Якщо система векторів Р₁, Р₂,..., Р_k (k ≤ n) у розкладі (16) лінійно незалежна і така, що

х₁Р₁+х₂Р₂+...+х_kР_k=Р₀,(18)

де всі х_j ≥ 0, то точка Х= (х₁; х₂;...; х_k;0;...; 0) є вершиною багатогранника розв’язків.

Теорема 1.4. Якщо Х= (х₁; х₂;...; х_n)– вершина багатогранника розв’язків, то вектори Р_j, що відповідають позитивним x_j в розкладі (16), лінійно незалежні.

Сформульовані теореми дозволяють зробити наступні висновки.

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

Вершину багатогранника розв’язків, у якій цільова функція приймає максимальне значення, знайти порівняно просто, якщо задача, записана у формі стандартної, містить не більше двох змінних або задача, записана у формі основної, містить не більше двох вільних змінних, тобто n-r ≤ 2, де п – число змінних, r – ранг матриці, складеної з коефіцієнтів у системі обмежень задачі.

Знайдемо розв’язок задачі, що полягає у визначенні максимального значення функції

F = c₁x₁ + c₂x₂ (19)

при умовах

a_i₁x₁ + a_i₂x₂ ≤ b_i (i = ), (20)

х_j ≥ 0 (j= 1,2) (21)

Кожна з нерівностей (20), (21) системи обмежень задачі геометрично визначає півплощину відповідно із граничними прямими a_i₁x₁ + a_i₂x₂ = b_i (i = ), x₁ =0 і х₂ =0. У тому випадку, якщо система нерівностей (20), (21) сумісна, область її розв’язків є множиною точок, що належать всім зазначеним півплощинам. Так як множина точок перетину даних півплощин – випукла, то областю припустимих розв’язків задачі (19) - (21) є опукла множина, що називається багатокутником розв’язків (введений раніше термін «багатогранник розв’язків» зазвичай вживається, якщо п ≥ 3). Сторони цього багатокутника лежать на прямих, рівняння яких отримують із вихідної системи обмежень заміною знаків нерівностей на знаки точних рівностей.

Таким чином, вихідна задача лінійного програмування полягає у знаходженні такої точки багатокутника розв’язків, у якій цільова функція F приймає максимальне значення. Ця точка існує тоді, коли багатокутник розв’язків не порожній і на ньому цільова функція обмежена зверху. При зазначених умовах в одній з вершин багатокутника розв’язків цільова функція приймає максимальне значення. Для визначення даної вершини побудуємо лінію рівня c₁x₁ + c₂x₂=h (де h – деяка постійна), що проходить через багатокутник розв’язків, і будемо пересувати її в напрямку вектора = (с₁; с₂) доти, поки вона не пройде через останню її спільну точку з багатокутником розв’язків. Координати зазначеної точки і визначають оптимальний план даної задачі.

Закінчуючи розгляд геометричної інтерпретації задачі (9)-(21), відзначимо, що при знаходженні її розв’язок можуть зустрітися випадки, зображені на рис. 1.1—1.4. Рис. 1.1 характеризує такий випадок, коли цільова функція приймає максимальне значення в єдиній точці А. З рис. 1.2 видно, що максимальне значення цільова функція приймає в будь-якій точці відрізка АВ. На рис. 1.3 зображений випадок, коли цільова функція не обмежена зверху на множині припустимих розв’язків, а на рис. 1.4 – випадок, коли система обмежень задачі несумісна.

Рис. 1.1 Рис. 1.2

Рис. 1.3 Рис. 1.4

Відзначимо, що знаходження мінімального значення лінійної функції при даній системі обмежень відрізняється від знаходження її максимального значення при тих же обмеженнях лише тим, що лінія рівня c₁x₁ + c₂x₂=h пересувається не в напрямку вектора = (с₁; с₂), а в протилежному напрямку. Таким чином, відзначені вище випадки, що зустрічаються при знаходженні максимального значення цільової функції, мають місце і при визначенні її мінімального значення.

Отже, знаходження розв’язку задачі лінійного програмування (19)-(21) на основі її геометричної інтерпретації включає наступні етапи:

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

2. Знаходять півплощини, обумовлені кожним з обмежень задачі.

3. Знаходять багатокутник розв’язків.

4. Будують вектор = (с₁; с₂).

5. Будують пряму c₁x₁ + c₂x₂=h, що проходить через багатокутник розв’язків.

6. Пересувають пряму c₁x₁ + c₂x₂=h у напрямку вектора , у результаті чого або знаходять точку (точки), у якій цільова функція приймає максимальне значення, або встановлюють необмеженість зверху функції на множині планів.

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

1.28. Для виробництва двох видів виробів А і В підприємство використовує три види сировини. Норми витрати сировини кожного виду на виготовлення одиниці продукції даного виду наведені в табл. 1.2. У ній же зазначені прибуток від реалізації одного виробу кожного виду і загальна кількість сировини даного виду, що може бути використана підприємством.

Таблиця 1.2

Вид сировини	Норми витрати сировини (кг) на один виріб	Загальна кількість сировини (кг)
А	В
І II III
Прибуток від реалізації одного виробу (грн.)

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

Розв’язок. Припустимо, що підприємство виготовить x₁ виробів виду А і х₂ виробів виду В. Оскільки виробництво продукції обмежене наявною у розпорядженні підприємства сировиною кожного виду і кількість виготовлених виробів не може бути від’ємною, повинні виконуватися нерівності

Загальний прибуток від реалізації х₁ виробів виду А і х₂ виробів виду В складе F= 30 х₁+ 40 х₂.

Таким чином, ми приходимо до наступної математичної задачі: серед всіх невід’ємних розв’язків даної системи лінійних нерівностей потрібно знайти таке, при якому функція F приймає максимальне значення.

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

Ці прямі зображені на рис. 1.5. Кожна з побудованих прямих ділить площину на дві півплощини. Координати точок однієї півплощини задовольняють вихідній нерівності, а іншої – ні. Щоб визначити шукану півплощину, потрібно взяти яку-небудь точку, що належить одній з півплощин, і перевірити, чи задовольняють її координати даній нерівності. Якщо координати взятої точки задовольняють даній нерівності, то шуканою є та півплощина, якій належить ця точка, у протилежному випадку – інша півплощина.

Знайдемо, наприклад, півплощину, обумовлену нерівністю 12 x₁ +4 x₂ <300. Для цього, побудувавши пряму 12 x₁ +4 x₂ =300 (на рис. 1.5 ця пряма І), візьмемо яку-небудь точку, що належить одній з двох отриманих півплощин, наприклад точку О (0; 0). Координати цієї точки задовольняють нерівності 12·0+4·0<300; виходить, півплощина, який належить точка О (0; 0), визначається нерівністю 12 x₁ +4 x₂ ≤300. Це і показано стрілками на рис. 1.5.

Рис. 1.5.

Перетин отриманих півплощин і визначає багатокутник розв’язків даної задачі.

Як видно з рис. 1.5, багатокутником розв’язків є п’ятикутник ОАВСD. Координати будь-якої точки, що належить цьому п’ятикутнику, задовольняють даній системі нерівностей і умові невід’ємності змінних. Тому сформульована задача буде вирішена, якщо ми зможемо знайти точку, що належить п’ятикутнику ОАВСD, у якій функція F приймає максимальне значення. Щоб знайти зазначену точку, побудуємо вектор =(30; 40) і пряму 30 x₁ +40 x₂ = h, де h – деяка постійна така, що пряма 30 x₁ +40 x₂ = h має спільні точки з багатокутником розв’язків. Покладемо, наприклад, h =480 і побудуємо пряму 30 x₁ +40 x₂ =480 (рис. 1.5).

Якщо тепер взяти яку-небудь точку, що належить побудованій прямій і багатокутнику розв’язків, то її координати визначають такий план виробництва виробів А і В,при якому прибуток від їхньої реалізації дорівнює 480 грн. Далі, покладаючи h рівним деякому числу, більшому ніж 480, ми будемо одержувати різні паралельні прямі. Якщо вони мають спільні точки з багатокутником розв’язків, то ці точки визначають плани виробництва виробів А і В, при яких прибуток від їхньої реалізації перевершить 480 грн.

Переміщаючи побудовану пряму 30 x₁ +40 x₂ =480 у напрямку вектора , бачимо, що останньою спільною точкою її з багатокутником розв’язків задачі служить точка В. Координати цієї точки і визначають план випуску виробів А і В, при якому прибуток від їхньої реалізації є максимальним.

Знайдемо координати точки В як точки перетину прямих II і III. Отже, її координати задовольняють рівнянням цих прямих

Вирішивши цю систему рівнянь, одержимо х₁*= 12, х₂*= 18. Отже, якщо підприємство виготовить 12 виробів виду А і 18 виробів виду В, то воно отримає максимальний прибуток, рівний F_тах =30·12+40·18=1080 грн.

⇐ Предыдущая 1 234 5 6 7 8 9 10 Следующая ⇒