1.4.Геометричний зміст і графічний метод розв'язування задачі лінійного програмування
В найпростішому випадку, коли задача лінійного програмування містить всього дві або три змінних, можна отримати її геометричну інтерпретацію і розв‘язати задачу графічним методом.
Розглянемо задачу :
max L = C = c1х1 + c2х2
а11х1+ а12х2 ≤ b1
а21х1+ а22х2 ≤ b2
…………………
ат1х1+ ат2х2 ≤ bm
x1 ≥0, x2 ≥0.
Введемо на площині декартову систему координат і поставимо у відповідність кожній парі чисел (х1 , х2) точку площини з кординатами х1 і х2. Зясуємо спочатку, який вигляд матиме множина точок, які відповідають допустимим розв'язкам даної задачі.
Кожна із нерівностей визначає на площині одну із двох півплощин, на які відповідна пряма (наприклад, для першого обмеження це є пряма а11х1+ а12х2 = b1) розбиває площину. При цьому відповідна півплощина включає і граничну пряму. Щоб визначити, яку саме із півплощин визначає дана нерівність, досить підставити в неї координати якоїсь точки, що не лежить на граничній прямій (найчастіше такою точкою вибирають точку початку координат O(0,0)). Якщо нерівність задовільняється, то шукана півплощина - та, в якій лежить дана точка, а якщо не задовільняється - то протилежна їй.
Оскільки допустимий розв'язок задачі - це набір значень (вектор) (х1,х2), які задовільняють всім обмеженням одночасно, то геометрично множина допустимих розв'язків задачі складається з точок площини, які належать одночасно всім m півплощинам, які визначаються окремими обмеженнями, тобто є перетином півплощин, які визначаються окремими обмеженнями. Позначимо її R.
Приклад. Множиною допустимих розв'язків задачі лінійного програмування з обмеженнями:
х1+ 2х2 ≤ 6
-2х1+ х2 ≤ 2
x1 ≥0, x2 ≥0,
є заштрихована область R на Рис. 2.
Рис.2. Ілюстрація множини допустимих розвязків ЗЛП.
Обмеженням х1+ 2х2 ≥ 6
-2х1+ х2 ≤ 2
x1 ≥0, x2 ≥0,
відповідає заштрихована область R на Рис.3.
Рис.3. Ілюстрація множини допустимих розвязків ЗЛП.
Обмеженням х1 - х2 ≤ 2
х1 - 2 х2 ≥ 4
x1 ≥0, x2 ≥0,
відповідає порожня множина. (Рис.4.)
Рис. 4. Ілюстрація множини допустимих розвязків ЗЛП.
Ці приклади показують, що множина допустимих розв'язків задачі лінійного програмування геометрично може бути непорожньою і обмеженою (випадок Рис.2), непорожньою і необмеженою (випадок Рис.3), порожньою (випадок Рис.4) множиною. Якщо множина допустимих розв'язків є непорожньою, то геометрично вона представляється многокутником (можливо необмеженим). Очевидно, що відрізок, який з‘єднує будь-які дві точки множини R, повністю їй належить. Множини з такою властивістю як зазначалося в параграфі 1.3. називаються опуклими.
З’ясуємо геометричний зміст цільової функції (1) ЗЛП. Припустимо, що множина R є непорожній обмежений многокутник. Оптимальними є ті точки множини R, кординати яких надають цільовій функції найбільшого значення. Множина точок, в яких цільова функція набуває фіксованого значення d, є прямою лінією, яка задається рівнянням
c1х1 + c2х2=d.
Ця пряма є перпендикулярною до вектора c=(c1 , c2).
Вважаючи d параметром, отримуємо сімейство паралельних прямих, які називаються лініями рівня цільової функції.
Легко бачити, що значення d (а отже і значення цільової функції) зростають, якщо пересувати пряму c1х1 + c2х2=d в напрямку її нормалі (градієнта) вектора c=(c1 ,c2).
Отже, щоб знайти оптимальний розв‘язок задачі, треба пересувати пряму c1х1 + c2х2=d в напрямку вектора c=(c1,c2) (тобто, паралельно самій собі), починаючи з деякого фіксованого положення, при якому вона перетинається з множиною R до тих пір, поки вона не перестане перетинатись з нею. Перетин множини R з лінією рівня в тому її положенні, коли подальше пересування приводить до того, що лінія рівня і множина R не мають спільної точки, і буде множиною оптимальних точок для задачі лінійного програмування (це може бути і одна точка).
Оскільки R - опуклий многокутник, то оптимальне значення цільової функції досягається або в одній із його вершин, або в точках, що належать його стороні (включно з двома вершинами многокутника). Координати відповідної вершини - це координати точки перетину відповідних граничних прямих, які її утворюють.
Якщо множина R є необмеженою, то максимум цільової функції може не досягатись - скільки б не переміщувати пряму c1х1 +c2х2=d в напрямку вектора c=(c1 ,c2), вона матиме спільні точки з множиною R.
Викладені вище міркування є справедливими і для випадку мінімізації цільової функції, тільки при цьому пряму c1х1+c2х2=d необхідно переміщати в напрямку протилежному напрямку вектора c=(c1 ,c2).