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

Лекція №2.3

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

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

 

Озн.1 Загальною задачею лінійного програмування називається задача, що полягає у визначенні максимального (мінімального) значення функції

(1)

при обмеженнях

, (2)

 

Озн.2. Канонічною задачею ЛП називається задача (1)-(2) у випадку і .

 

Озн.3. Сукупність чисел , що задовольняють обмеженням (2) задачі ЛП називається допустимим розв’язком (планом) задачі ЛП.

 

Озн.4. План , при якому цільова функція (1) приймає своє максимальне (мінімальне) значення називається оптимальним.

 

Заув. Дві форми задачі ЛП – загальна і канонічна - є еквівалентними в тому сенсі, що кожна з них, шляхом певних перетворень може бути зведена до іншої. Вкажемо шлях зведення загальної задачі ЛП до канонічної форми. Щоб виконати зведення необхідно:

1. Кожне обмеження у вигляді нерівності перетворити на обмеження у формі рівності. Нехай є обмеження: . Щоб перетворити нерівність у рівність додамо у ліву частину нерівності невід’ємну змінну , тоді .

2. Якщо деякі з змінних не підкоряються умові невід’ємності, тобто , то такі змінні слід замінити різницею двох невід’ємних: .

Ці два правила дозволяють легко звести загальну задачу ЛП до канонічної форми.

 

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

Спочатку розглянемо розв’язання задачі ЛП у випадку двох незалежних змінних.

Нехай маємо задачу ЛП

 

(3)

 

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

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

У випадку рис.1б. - це вершина багатокутника з координатами .

 

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

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

З проведеного геометричного аналізу випливає важливий висновок:

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

У випадку рис.1 цей розв’язок є єдиним, у випадку рис.2 – ні, проте і у цьому випадку розв’язок досягається в двох вершинах багатокутника. Цей висновок залишається справедливим і у випадку задачі ЛП при незалежних змінних.