.
Задачу на мінімум (формула 1.6) можна вирішувати як завдання на максимум. Досить знаки цільової функції поміняти на протилежні (формула 1.7). У результаті необхідно знак цільової функції поміняти на протилежний.
(1.6)
(1.7)
Аналогічно можна змінити знак нерівності менше або дорівнює (формула 1.8) на більше або дорівнює (формула 1.9). br/>
(1.8)
(1.9)
Цільова функція задачі лінійного програмування досягає свого екстремуму (мінімуму або максимуму) у вершині допустимої області. Якщо цільова функція досягає екстремального значення більш ніж на одній вершині, то вона досягає того ж значення в будь-якій точці, що є опуклою комбінацією цих вершин (альтернативний оптимум).
Ця теорема має найважливіші значення, так як вона вказує шлях вирішення задачі лінійного програмування. Зовсім не треба перебирати всі крапки допустимої області. Досить перебрати вершини допустимої області, адже їх кінцеве число. Крім того, не потрібно перебирати всі вершини, можна цей перебір істотно скоротити.
Будь набір чисел, що задовольняє обмеженням завдання, називають планом, а безліч всіх планів допустимої областю. Той план, який доставляє екстремум (мінімум або максимум) цільової функції, називають оптимальним планом або просто рішенням завдання лінійного програмування. [3 c.7-8]
Завдання лінійного програмування вирішуються кількома методами:
1. графічний метод;
2. симплексний метод;
3. подвійність в ЛП;
4.двойственний симплексний метод.
Завдання лінійного програмування з двома змінними завжди можна вирішити графічно. Проте вже в тривимірному просторі таке рішення ускладнюється, а в просторах, розмірність яких більше трьох, графічне рішення неможливо.
Графічний метод досить простий і наочний. Він заснований на геометричному поданні допустимих рішень задачі. Кожне з нерівностей задачі ЛП визначає на координатної площині деяку напівплощина, а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто володіє наступною властивістю: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлений опуклим багатокутником, необмеженою опуклою багатокутної областю, відрізком, променем і т.д. У разі несумісності системи обмежень задачі ОДР є порожнім безліччю.
При пошуку оптимального вирішення завдань лінійного програмування можливі такі ситуації: існує єдине рішення задачі, існує нескінченна безліч рішень (альтернативний оптимум); ЦФ не обмежена; область допустимих рішень-єдина точка; задача не має рішень. [3 c.55-57]
Будь-яка задача лінійного програмування, незалежно від виду запису, може бути приведена до стандартної і канонічній формі і вирішена симплексним методом, який в певному сенсі є універсальним метод...
