Графічний метод розв’язання задачі лінійного програмування

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

Існують два найпоширеніших способи рішення задач такого типу: графічний метод і симплекс-методГрафічний метод дає істотно наочніше і, зазвичай, простіше для розуміння рішення. Також цей метод дозволяє практично одночасно знайти рішення на мінімум і максимум. Основні етапи щодо рішення задач лінійного програмування графічним методом наступні: побудова області допустимих рішень задачі і знаходження, серед усіх точок даної області, такої точки , в якій цільова функція  приймає свого оптимального значення.

На відміну від графічного методу, симплекс-метод є більш універсальним, тобто дозволяє знайти розв’язок будь-якої задачі лінійного програмування. При рішенні задачі симплексним методом, обчислення ведуться в таблицях. Рішення задачі даним методом дає не тільки оптимальне рішення, але і рішення двоїстої задачі, залишки ресурсів і тому подібне.

Розглянемо алгоритм рішення задачі лінійного програмування за графічним методом. Для цього, запишемо стандартну задачу лінійного програмування з двома змінними:

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

Графічний метод

Можливі випадки області допустимих рішень

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

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

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

Графічний метод

Функція F приймає максимальне значення в точці  C

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

Зауваження: при рішенні задачі лінійного програмування графічним способом можуть зустрінеться наступні випадки:

    1. задача має єдине рішення (випадок на рисунку вище);
    2. задача лінійного програмування не має оптимальних планів:

Графічний метод

Функція F не має екстремального значення

    1. задача має безліч рішень:

Графічний метод

Функція F приймає максимальне значення в будь-якій точці відрізка ВС
Рішення задачі лінійного програмування графічним методом – приклад:

Для виготовлення товару і підприємство використовує три види сировини . Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару  а також загальна кількість сировини наведені в наступній таблиці:

Графічний метод приклад

Норми витрат сировини на виготовлення одиниці продукції

Потрібно організувати випуск даної продукції таким чином, щоб прибуток від її реалізації був максимальним.

Позначимо через — кількість товару типу  і через — кількість товару типу . Тоді математична модель даної задачі полягає у визначенні максимального значення функції мети:

при наступних обмеженнях:

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

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

Графічний метод приклад

Рішення задачі лінійного програмування графічним методом

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

Таким чином прибуток буде максимальним у розмірі 6 умовних одиниць, якщо реалізувати дві одиниці продукції типу  і нуль одиниць продукції типу .

Блок-схема алгоритму знаходження рішення задачі лінійного програмування графічним методом

Графічний метод блок-схема

Залишити коментар

Your email address will not be published. Required fields are marked *

*