Геометрична інтерпретація лінійних нерівностей та їх систем.
Розглянемо в загальному виді задачу лінійного програмування для функції двох змінних:
Визначити найбільше (найменше) значення функції
(1)
при обмеженнях:
(2)
Відомо, що рівняння 
, визначає в координатній площині пряму лінію. Якщо при цьому 
, то відповідна пряма проходить через початок координат. Кожна пряма виду 
розбиває координатну площину на дві півплощини. Для точок однієї з цих півплощин виконується нерівність виду 
, а для точок другої виконується нерівність виду 
. Пряма є граничною для кожної з цих півплощин.
Для того, щоб визначити, у якій півплощині відносно заданої прямої виконується нерівність виду , достатньо зробити перевірку для довільної, індикаторної точки площини. Якщо нерівність виконується, то ця точка лежить у шуканій півплощині, а інакше шуканою півплощиною буде інша півплощина. Коли 
, точкою для перевірки найкраще обирати точку початку координат.
Для визначення півплощини за відповідною нерівністю, можна скористатися і таким методом. Перетворимо початкову нерівність до виду:
, або 
.
Якщо має місце перша нерівність, то відповідна множина точок знаходиться над відповідною прямою, а інакше під нею (див. малюнок). Нерівність 
(або 
) визначає півплощину з її граничною прямою.
Таким чином, кожна з нерівностей системи (2) визначає на площині 
деяку півплощину. Перетин півплощин, заданих нерівностями системи (2), визначає в площині певний опуклий многокутник 
, який лежить у першій координатній чверті. Цей многокутник може бути і необмеженим (див. приклад 2). Виходячи з геометричного змісту обмежень (2), цю задачу можна сформулювати в такому вигляді:
Серед усіх точок многокутника M знайти таку, координати
Якої максимізують (мінімізують) функцію (1).
Геометрична інтерпретація цільової функції.
Нехай – обмежений многокутник. При фіксованому значенні z рівняння 
визначає деяку пряму. При зміні z ця пряма переміщується паралельно самій собі, тому що її кутовий коефіцієнт визначається тільки числами c1 і c2 і тому залишається незмінним. Вектор 
є градієнтом функції z і паралельне переміщення прямої в напрямку цього вектора веде до збільшення значень цільової функції.
При зростанні z від –¥ до +¥ дана пряма спочатку не має спільних точок з , потім при деякому значенні z, дотикається до многокутника (у точці A), потім перетинає , знову останній раз дотикається до (у точці B) і, нарешті, знову не має з спільних точок (див. малюнок).
Оскільки рух у вказаному напрямку відповідає зростанню значень z, то для точок многокутника найменше значення функція z буде приймати в точці A, а найбільше – в точці B. Якщо яка-небудь із сторін многокутника паралельна до прямої , то торкання відбувається по всій стороні многокутника і, виходить, що задача може мати нескінченно багато розв’язків (координати будь-якої точки цієї сторони дають розв’язок задачі). Якщо многокутник не обмежений, то задача може не мати розв’язків.
Дата добавления: 2018-05-13; просмотров: 409; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!