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

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

Приклад 2.

Використовуючи графічний метод, знайти мінімум і максимум функції L = 2 х₁ + х₂ + 5 при обмеженнях х₁ - х₂ ≥ -5, х₁ + 3х₂ ≥ 15, х₁ - х₂ ≤ 7, х₁ ≤ 10, х₂ ≤ 10, х₁ , х₂ ≥ 0.

Розв’язання:

З находження розв’язку задачі лінійного програмування графічним методом включає до свого складу наступні етапи.

1. Будуємо прямі, рівняння яких отримуються внаслідок заміни в обмеженнях знаків нерівностей на знаки точних рівностей. Для нашого прикладу будуємо наступні прямі:

х1 - х2 = -5, х1 + 3х2 = 15, х1 - х2 = 7, х1 = 10, х2 = 10,

(1) (2) (3) (4) (5)

у системі координат (Ох₁х₂) (рис.1).

2. Знаходимо півплощини, що визначаються нерівностями.

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

Визначаємо півплощини для нашого випадку:

(0 – 0) = 0 ≥ -5, отже обмеження х₁ - х₂ ≥ -5 визначає півплощину якій належить початок координат і вона лежить нижче за пряму х₁ - х₂ = -5 , включаючи її саму.

(0 + 3*0) = 0 15, тому нерівність х₁ + 3х₂ ≥ 15 визначає півплощину вище за пряму х₁ + 3х₂ = 15 і в якій не лежить точка О(0; 0).

Аналогічно, так як початок координат задовольняє кожну з нерівностей (0 – 0) = 0 ≤ 7, 0 ≤ 10 та 0 ≤ 10, то обмеження х₁ - х₂ ≤ 7, х₁ ≤ 10 та х₂ ≤ 10 визначають ті півплощини відносно прямих х₁ - х₂ = 7, х₁ = 10, х₂ = 10 в яких лежить точка О(0;0).

Остання умова х₁ , х₂ ≥ 0 означає, що многокутник розв’язків розташований у І квадранті координатної площини (Ох₁х₂).

3 . Знаходимо многокутник розв’язків. Він визначається як перетин усіх півплощин (рис.2).

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

В ершини А₁₂, А₂₃, А₃₄, А₄₅, А₅₁ – опорні розв’язки.

4 . Від початку координат відкладаємо вектор = (L'_x1; L'_x2) – вектор напрямку, який визначає напрям зростання чи спадання значень заданої функції. Координати вектора L'_x1; L'_x2 – частинні похідні функції цілі L по змінним x₁ та x₂ відповідно.(рис.3)

В нашому прикладі L'_x1 = 2, L'_x2 = 1, тому = (2; 1)

5. Побудуємо лінію рівня lo , яка перпендикулярна до вектора напрямку і проходить через початок координат.

6. Переміщуємо l_o у напрямку вектора ĉ паралельно самій собі до співпадання з найближчою (точка мінімуму) та найдальшою (точка максимуму) вершинами многокутника.

У результаті, пряма l_min пройшла через вершину А₁₂, а пряма l_max через А₄₅.

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

Для вершини А12:	(1), (2),	х1 - х2 = -5, х1 + 3х2 = 15,	х1 = 0, х2 = 5,	А12(0;5),
Для вершини А45:	(4), (5),	х1 = 10, х2 = 10,	А45(10;10).