д неї. Перетин півплощини, кожна з яких визначається відповідним нерівністю системи, називається областю допустимих рішень або областю визначення. Необхідно пам'ятати, що область допустимих рішень задовольняє умовам неотрицательности (xj Ві 0, j = 1, ..., n). Координати будь-якої точки, що належить області визначення є допустимим рішенням задачі. p> Для знаходження екстремального значення цільової функції при графічному рішенні завдань ЛЗ використовують вектор-градієнт, координати якого є приватними похідними цільової функції, тобто
.
Цей вектор показує напрямок найшвидшого зміни цільової функції. Пряма, полягає в тому, що при паралельному зміщенні лінії в одну сторону рівень перпендикулярна вектору-градієнту, є лінією рівня цільової функції. У будь-якій точці лінії рівня цільова функція приймає одне і те ж значення. Прирівняємо цільову функцію постійної величиною В«aВ». Міняючи значення В«aВ» , отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня. p align="justify"> Важлива властивість лінії рівня лінійної функції тільки зростає, а при зміщенні в інший бік - убуває.
З геометричної точки зору в задачі лінійного програмування шукається така кутова точка або набір точок з допустимого безлічі рішень, на якому досягається сама верхня (нижня) лінія рівня, розташована далі (ближче) інших у напрямку найшвидшого зростання.
Графічний метод розв'язання ЗЛП складається з наступних етапів:
Будується багатокутна область допустимих рішень ЗЛП - ОДР,
Будується вектор-градієнт ЦФ в якій-небудь точці Х 0 належить ОДР -
.
. Лінія рівня C 1 x 1 + C 2 x 2 = а (а -постійна величина) - пряма, перпендикулярна вектору - градієнту - пересувається в напрямку цього вектора у разі максимізації f (x 1, x 2 ) до тих пір, поки не покине меж ОДР . Гранична точка (або точки) області при цьому русі і є точкою максимуму f (x 1, x 2 ) .
. Для знаходження її координат досить вирішити два рівняння прямих, одержуваних з відповідних обмежень і дають в перетині точку максимуму. Значення f (x 1, x 2 ), знайдене в одержуваної точці, є максимальним.
При мінімізації f (x 1, x 2 ) лінія рівня переміщається в напрямку, протилежному вектору- градієнту. Якщо пряма при своєму русі не покидає ОДР, то відповідний максимум або мінімум f (x 1, x 2 < i>) не існує.
Якщо лінія рівня паралельна якомусь функціональному обмеженню задачі, то оптимальне значення ЦФ буде дос...