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

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

ГЕОМЕТРИЧНИЙ МЕТОД РОЗВ’ЯЗУВАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

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

Приклад 2.

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

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

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

Для нашого прикладу будуємо наступні прямі:

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

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

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

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

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

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

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

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

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

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

Вершини А12, А23, А34, А45, А51 – опорні розв’язки.

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

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