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

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

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

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

Приклад 2.

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

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

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

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

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

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

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

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

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

(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)

Дата добавления: 2014-10-15