Математична модель задачі лінійного програмування.
Ми будемо розглядати задачі пошуку екстремуму (мінімуму або максимуму), лінійної функції за умов, які є лінійними нерівностями або рівняннями, інакше кажучи, лінійні оптимізаційні задачі. Загальні методи розв’язання таких задач вивчаються дисципліною, яка зветься лінійне програмування (ЛП), а самі задачі — задачами лінійного програмування (ЗЛП). ЛП є, у свою чергу, підрозділом іншої дисципліни, що має назву математичне програмування.
Методику розв’язання ЗЛП малих розмірностей ми розглянемо на прикладі двовимірної ЗЛП:
4.1.1. Задача планування виробництва в умовах обмежених ресурсів.
Деяка фірма випускає пилососи і вентилятори. Серед матеріалів, потрібних для виготовлення виробів, “критичними” є мідний дріт і трансформаторне залізо (“критичні” - означає, що саме ці матеріали знаходяться в обмеженій кількості і саме вони визначають обсяг продукції). Для виготовлення одного пилососа потрібно 0,6 кг мідного дроту і 0.3 кг трансформаторного заліза, одного вентилятора - 0,3 кг мідного дроту і 0,2 кг трансформаторного заліза. В наявності є 48 кг мідного дроту і 30 кг трансформаторного заліза. Чистий прибуток від реалізації одного пилососа складає 120, а одного вентилятора – 70 умовних грошових одиниць. Треба визначити план випуску пилососів і вентиляторів (кількість пилососів і вентиляторів, яку потрібно виробити) для якого вистачило б запасів дроту і заліза і якому відповідав би максимальний прибуток.
4.1.2. Формалізація задачі планування виробництва в умовах обмежених ресурсів.
Вводимо змінні: - кількість пилососів, - кількість вентиляторів. Тоді потрібна кількість дроту та заліза буде такою:
дріт | залізо | |
х - кількість пилососів у - кількість вентиляторів | 0,6×х 0,3×у | 0,3×х 0,2×у |
(для одного потрібно 0,6 кг, а для х=0,6×х).
Сумарна кількість дроту та заліза не повинна перевищувати їх запасів. Звідси отримуємо умови:
.
Цільова функція задачі - це функція прибутку від реалізації х пилососів і у вентиляторів. Цю функцію ми назвемо :
.
Прибуток (функцію ) ми хочемо максимізувати; отже маємо задачу пошуку екстремуму, а саме, максимуму (max), лінійної функції за умов, які є лінійними нерівностями, тобто лінійну оптимізаційну задачу.
4.1.3. Загальна структура задачі лінійного програмування.
Математична модель задачі ”Планування виробництва” має вигляд:
(цільова функція)
|
|
Розв’язання ЗЛП.
4.2.1. Побудова допустимої області ЗЛП.
Пригадаємо ( див. попередній параграф), що множиною розв’язків лінійної нерівності є півплощина . Якщо ми розглядаємо систему з кількох нерівностей, то множиною розв’язків цієї системи є перетин відповідних півплощин, тобто це є така множина точок, які потрапляють в кожну з півплощин.
Почнемо розгляд ЗЛП з побудови зображення на координатній площині допустимої області (множини) ЗЛП — множини розв’язків системи лінійних нерівностей, у якій об’єднано непрямі і прямі умови ЗЛП.
Зображення множини розв’язків СЛН будуємо за схемою:
· замінюємо в першій нерівності знак нерівності на знак = і отримуємо лінійне рівняння, яке визначає пряму лінію на координатній площині;
· креслимо цю пряму лінію (вона є границею півплощини, яка є множиною розв’язків першої нерівності);
· вибираємо одну, яку завгодно, точку з однієї (якої-небудь) з півплощин, на які розбила площину накреслена пряма; підставляємо координати вибраної точки у першу нерівність; якщо нерівність справджується, то множиною розв’язків нерівності буде та півплощина, де лежить вибрана точка, якщо ні, - інша (“протилежна”) півплощина (часто буває зручно за “пробну” точку брати точку - початок координат);
· описані дії виконуємо з кожною із нерівностей;
· шукана допустима множина ЗЛП є перетином всіх (у нашому випадку чотирьох) півплощин; геометрично - це є многокутник.
Бачимо, що геометричне місце точок, які задовольняють кожну з нерівностей, утворюють чотирикутник . В ньому нам відомі координати всіх вершин, крім точки .
Координати точки знаходимо за такою схемою:
· визначаємо з малюнка, на перетині граничних прямих яких нерівностей знаходиться ця вершина;
· утворюємо систему двох рівнянь з двома невідомими, беручи рівняння двох прямих, визначених на попередньому кроці;
· розв’язуємо утворену систему лінійних рівнянь; знайдений розв’язок - це і є шукані координати розглядуваної вершини.
Обчислюємо за наведеною схемою координати вершини .
|
|
|
Допустима множина побудована і координати всіх вершин відповідного многокутника обчислені.
4.2.2. Пошук оптимального допустимого розв’язку.
Почнемо пошук оптимального розв’язку ЗЛП. Для цього залучимо до розгляду цільову функцію:
.
Розглядувана ЗЛП полягає у знаходженні точки з допустимої множини, у якій цільова функція набуває найбільше значення серед усіх значень в усіх допустимих розв’язках, тобто, серед значень в усіх точках допустимої множини.
Нехай r - це деяке дійсне число, яке ми будемо розглядати як значення (у якійсь точці) цільової функції. З огляду на таку інтерпретацію ми будемо називати число r рівнем цільової функції (отже, нам треба знайти точку допустимої множини з найбільшим рівнем цільової функції).
Нехай r - це деякий рівень. Множина точок координатної площини з даним рівнем r цільової функції, тобто, для яких
,
зветься лінією рівня цільової функції. У нашому конкретному випадку це буде пряма лінія з рівнянням
.
Зобразимо на спільному малюнку допустиму множину і декілька ліній рівня цільової функції, а саме , , :
Всі лінії рівня паралельні, вони мають спільну нормаль, тобто спільний нормальний вектор. Для “конкретизації” цього вектора можна скористатися коефіцієнтами біля невідомих у якому-небудь з рівнянь:
Один з напрямків перпендикуляра, і як раз той, що визначається вибраним нами вектором, перпендикулярним (чому ?), до ліній рівня є напрямком зростання, інший - напрямком спадання цільової функції.
Якщо якась лінія рівня перетинає допустиму множину ЗЛП, це означає, що у допустимій множині є точки, у яких цільова функція набуває відповідного значення.
Отже, для того, щоб знайти оптимальний розв’язок ЗЛП, треба лінію рівня цільової функції пересувати паралельно у напрямку зростання доти, поки вона ще перетинає допустиму множину.
Остання точка перетину лінії рівня з допустимою областю ЗЛП („точка прощання”) є оптимальним розв’язком ЗЛП:
Отже оптимальний план виробництва пилососів і вентиляторів: 20 пилососів і 120 вентиляторів.
4.3. Загальні властивості оптимального розв’язку ЗЛП.
4.3.1. Основна властивість оптимального розв’язку ЗЛП.
Геометричні міркування дають змогу сформулювати загальне положення, що визначає місцезнаходження оптимальної точки ЗЛП у допустимій множині.
Допустима множина ЗЛП, як перетин півплощин, є опуклим многокутником. Отже, якщо взяти яку-небудь внутрішню (тобто яка не лежить на границі) точку допустимої множини і якщо провести через цю точку лінію рівня, то цю лінію рівня можна, хоч трохи, зрушити як у напрямку зростання, так і в напрямку спадання. І вона все ще буде перетинати допустиму множину. Таким чином, внутрішня точка допустимої множини ЗЛП не може бути оптимальним розв’язком ЗЛП.
Звідси висновок: оптимальний розв’язок ЗЛП, якщо він існує, є вершиною допустимої множини ЗЛП.
4.3.2. Знаходження оптимального розв’язку ЗЛП методом перебирання вершин допустимої області.
Інколи, через неточності малюнка, важко визначити, яка саме вершина допустимої області є точкою екстремуму цільової функції ЗЛП. В таких випадках треба обчислити значення цільової функції в декількох “підозрілих” точках:
Точка максимуму — .
4.3.3. Класифікація можливостей щодо “вмісту” множини оптимальних розв’язків ЗЛП.
У загальному випадку можна виділити три якісно різних випадки щодо “вмісту” множини оптимальних розв’язків ЗЛП. Ці випадки однакові як для задачі мінімізації, так і для задачі максимізації. Обмежимось розглядом задачі максимізації.
1) Множина оптимальних розв’язків порожня (ЗЛП не має оптимального розв’язку).
1а) Допустима множина ЗЛП порожня (система обмежень є несумісною).
1б) Допустима множина необмежена у напрямку зростання цільової функції.
2) Множина оптимальних розв’язків містить один-єдиний елемент (точку). В такому випадку оптимальний розв’язок ЗЛП неодмінно є вершиною допустимої області. Прикладом такої ситуації може служити розглянута задача.
3) Множина оптимальних розв’язків нескінчена; це буває в тому випадку, коли лінія рівня паралельна якійсь стороні допустимої множини. Тоді множина оптимальних розв’язків складається із всіх точок цієї сторони, причому ця сторона може бути як відрізком, так і променем:
3а)
3б)
Лінія рівня паралельна стороні допустимої множини.
Дата добавления: 2021-05-28; просмотров: 507;