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

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

Розглянемо задачу :

max L = C = c₁х₁ + c₂х₂

а₁₁х₁+ а₁₂х₂ ≤ b₁

а₂₁х₁+ а₂₂х₂ ≤ b₂

…………………

а_т1х₁+ а_т2х₂ ≤ b_m

x₁ ≥0, x₂ ≥0.

Введемо на площині декартову систему координат і поставимо у відповідність кожній парі чисел (х₁ , х₂) точку площини з кординатами х₁ і х₂. Зясуємо спочатку, який вигляд матиме множина точок, які відповідають допустимим розв'язкам даної задачі.

Кожна із нерівностей визначає на площині одну із двох півплощин, на які відповідна пряма (наприклад, для першого обмеження це є пряма а₁₁х₁+ а₁₂х₂ = b₁) розбиває площину. При цьому відповідна півплощина включає і граничну пряму. Щоб визначити, яку саме із півплощин визначає дана нерівність, досить підставити в неї координати якоїсь точки, що не лежить на граничній прямій (найчастіше такою точкою вибирають точку початку координат O(0,0)). Якщо нерівність задовільняється, то шукана півплощина - та, в якій лежить дана точка, а якщо не задовільняється - то протилежна їй.

Оскільки допустимий розв'язок задачі - це набір значень (вектор) (х₁,х₂), якізадовільняють всім обмеженням одночасно, то геометрично множина допустимих розв'язків задачі складається з точок площини, які належать одночасно всім m півплощинам, які визначаються окремими обмеженнями, тобто є перетином півплощин, які визначаються окремими обмеженнями. Позначимо її R.

Приклад. Множиною допустимих розв'язків задачі лінійного програмування з обмеженнями:

х₁+ 2х₂ ≤ 6

-2х₁+ х₂ ≤ 2

x₁ ≥0, x₂ ≥0,

є заштрихована область R на Рис. 2.

Рис.2. Ілюстрація множини допустимих розвязків ЗЛП.

Обмеженням х₁+ 2х₂ ≥ 6

-2х₁+ х₂ ≤ 2

x₁ ≥0, x₂ ≥0,

відповідає заштрихована область R на Рис.3.

Рис.3. Ілюстрація множини допустимих розвязків ЗЛП.

Обмеженням х₁ - х₂ ≤ 2

х₁ - 2 х₂ ≥ 4

x₁ ≥0, x₂ ≥0,

відповідає порожня множина. (Рис.4.)

Рис. 4. Ілюстрація множини допустимих розвязків ЗЛП.

Ці приклади показують, що множина допустимих розв'язків задачі лінійного програмування геометрично може бути непорожньою і обмеженою (випадок Рис.2), непорожньою і необмеженою (випадок Рис.3), порожньою (випадок Рис.4) множиною. Якщо множина допустимих розв'язків є непорожньою, то геометрично вона представляється многокутником (можливо необмеженим). Очевидно, що відрізок, який з‘єднує будь-які дві точки множини R, повністю їй належить. Множини з такою властивістю як зазначалося в параграфі 1.3. називаються опуклими.

З’ясуємо геометричний зміст цільової функції (1) ЗЛП. Припустимо, що множина R є непорожній обмежений многокутник. Оптимальними є ті точки множини R, кординати яких надають цільовій функції найбільшого значення. Множина точок, в яких цільова функція набуває фіксованого значення d, є прямою лінією, яка задається рівнянням

c₁х₁ + c₂х₂=d.

Ця пряма є перпендикулярною до вектора c=(c₁ , c₂).

Вважаючи d параметром, отримуємо сімейство паралельних прямих, які називаються лініями рівня цільової функції.

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

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

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

Якщо множина R є необмеженою, то максимум цільової функції може не досягатись - скільки б не переміщувати пряму c₁х₁ +c₂х₂=d в напрямку вектора c=(c₁ ,c₂), вона матиме спільні точки з множиною R.

Викладені вище міркування є справедливими і для випадку мінімізації цільової функції, тільки при цьому пряму c₁х₁+c₂х₂=d необхідно переміщати в напрямку протилежному напрямку вектора c=(c₁ ,c₂).

1.5. Методи побудови початкового базисного плану ЗЛП

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

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

Для того, щоб повністю дослідити ЗЛП необхідно:

1.або знайти значення ;

2.або показати, що лінійна форма ЗЛП необмежена на множині своїх планів;

3.або встановити несумісність умов ЗЛП, тобто показати, що область .

У всіх трьох випадках для дослідження ЗЛП необхідно починати перебір вершин області від однієї з них. Будемо називати цю вершину початковим базисним планом.

Таким чином, щоб побудувати початковий базисний план для ЗЛП необхідно:

1. Помножити на , ті умови із області , для яких ;

2. До умов типу „ ” додати доповнюючу змінну ;

3. До умов типу „=” додати штучну змінну ;

4. До умов типу „ ” додати .

Доповнюючі змінні входять в цільову функцію із коефіцієнтом 0, а штучні змінні із коефіцієнтами ( ), де – достатньо велике додатнє число для задачі на і достатньо велике від’ємне число для задачі на .

Приклад. Побудувати початковий базисний план для задачі лінійного програмування заданої у вигляді:

Побудуємо початковий базисний план для цієї задачі використовуючи описані підходи, отримаєм[1] задачу виду:

Таким чином початковий базисний план для отриманої в результаті перетворення задачі очевидний, а саме

Поиск по сайту: