Визначити найбільше (найменше) значення функції

                                          (1)

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

                                (2)

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

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

Для визначення півплощини за відповідною нерівністю, можна скористатися і таким методом. Перетворимо початкову нерівність до виду:

, або .

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

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

Серед усіх точок многокутника M знайти таку, координати

Якої максимізують (мінімізують) функцію (1).

Геометрична інтерпретація цільової функції.

Нехай  – обмежений многокутник. При фіксованому значенні z рівняння  визначає деяку пряму. При зміні z ця пряма переміщується паралельно самій собі, тому що її кутовий коефіцієнт визначається тільки числами c₁ і c₂ і тому залишається незмінним. Вектор  є градієнтом функції z і паралельне переміщення прямої в напрямку цього вектора веде до збільшення значень цільової функції.

При зростанні z від –¥ до +¥ дана пряма спочатку не має спільних точок з , потім при деякому значенні z, дотикається до многокутника  (у точці A), потім перетинає , знову останній раз дотикається до  (у точці B) і, нарешті, знову не має з  спільних точок (див. малюнок).

Оскільки рух у вказаному напрямку відповідає зростанню значень z, то для точок многокутника  найменше значення функція z буде приймати в точці A, а найбільше – в точці B. Якщо яка-небудь із сторін многокутника паралельна до прямої , то торкання відбувається по всій стороні многокутника  і, виходить, що задача може мати нескінченно багато розв’язків (координати будь-якої точки цієї сторони дають розв’язок задачі). Якщо многокутник  не обмежений, то задача може не мати розв’язків.

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

Можливі випадки різних типів многокутників M і цільової функції для задачі максимізації функції представлені на наступних малюнках: