Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ММДО_конспект.doc
Скачиваний:
9
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

Тема 4 «Геометрична інтерпретація злп»

План лекції

1. Графічний метод розв'язання ЗЛП. Умови графічного розв'язання ЗЛП.

2. З’ясування основних особливостей та властивостей розв’язків ЗЛП за допомогою геометричної інтерпретації.

3. Основні етапи графічного розв'язання ЗЛП (Алгоритм геометричної інтерпретації ЗЛП).

1. Графічний метод розв'язання злп. Умови графічного розв'язання злп.

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

Нехай дана задача

(1)

(2)

(3)

Дамо геометричну інтерпретацію елементів цієї задачі. Кожне з обмежень (2), (3) задає на площині деяку напівплощину. Напівплощина - опукла множина. Але перетинання будь-якого числа опуклих множин є опуклою множиною. Звідси видно, що область припустимих рішень задачі (1) - (3) є опуклу множина.

Перейдемо до геометричної інтерпретації цільової функції. Нехай область припустимих рішень ЗЛП – непуста множина, наприклад багатокутник .

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

Знайдемо частки похідні цільової функції по й

(4)

(5)

Частинна похідна (4) – (5) функції показує швидкість її зростання уздовж даної осі. Отже, і – швидкості зростання відповідно уздовж осей і . Вектор називається градієнтом функції. Він показує напрямок найшвидшого зростання цільової функції:

.

Вектор указує напрямок найшвидшого убування цільової функції. Його називають антиградієнтом.

Вектор перпендикулярний до прямих сімейства .

2. З’ясування основних особливостей та властивостей розв’язків злп за допомогою геометричної інтерпретації.

При знаходженні графічних розв’язків задачі ЛП можуть зустрітися випадки, коли:

а) цільова функція приймає максимальне значення в єдиній точці припустимої множини (єдине рішення);

б) цільова функція приймає максимальне значення в будь-якій точці відрізка (якщо лінія рівня збігається з обмеженням, тоді маємо випадок нескінченної множини рішень);

в) цільова функція може бути необмежена на множині припустимих рішень (тобто fmax = + ∞ – це також випадок нескінченної множини рішень);

г) рішення ЗЛП не існує, оскільки система обмежень цієї задачі несумісна.