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

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

Приклад. Розв’язати задачу лінійного програмування

Q (x)= x ₁+3 x ₂®min.

x ₁+2 x ₂£10

x ₁£6

x ₁+ x ₂³2

x ₁³0, x ₂³0,

Для випадку двох змінних не обов’язково переходити від нерівностей до рівнянь, тому що існує інтерпретація розв’язків нерівностей як півплощини, обмежені даними прямими. Побудуємо допустиму область (Рис. 2.1).

Рис. 2.1. Допустима область задачі лінійного програмування.

Для побудови розв’язку цієї задачі скористаємося лініями рівня – прямими x ₁+3 x ₂=С. Для цього будемо паралельно переносити будь-яку з прямих x ₁+3 x ₂=С та знаходити значення С, при яких ця лінія перетинатиме допустиму область. При мінімальному значенні С (це значення – мінімальне значення функції мети) координати точки (x ₁, x ₂), що задовольняє рівняння лінії рівня та належить допустимій області, будуть розв’язками задачі лінійного програмування. Цей мінімум досягається при С=2 (рис. 2.2) в точці Р(2;0).

Рис. 2.2. Графічний розв’язок задачі лінійного програмування.

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

У випадку більшої кількості змінних допустимою областю є деякий многогранник, обмежений площинами (гіперплощинами), а оптимальний розв’язок (точка чи декілька точок) отримується внаслідок перетину многогранника площиною (гіперплощиною)

p ₁ x ₁+…+ p_nx_n =С,

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

Окремим питанням є дослідження допустимої області, яка може бути, як зазначалося, обмеженою, необмеженою, або навіть порожньою. В останньому випадку не існує розв’язку задачі лінійного програмування.

Таким чином, розв’язок задачі лінійного програмування слід шукати серед вершин допустимої області, на чому і ґрунтується один із методів її розв’язку – симплекс-метод.