Дано систему т лінійних нерівностей з двома змінними
(3.1)
Знак деяких або всіх нерівностей може бути „ ”.
Розглянемо першу нерівність системи (3.1) у системі координат . Побудуємо пряму
, яка є граничною прямою. Ця пряма ділить площину на дві півплощини (1) і (2).
Напівплощина (1) вміщує початок координат. Для визначення, з якого боку від граничної прямої розміщена задана напівплощина необхідно взяти довільну точку на площині (краще початок координат) і підставити координати цієї точки у нерівність. Якщо нерівність справедлива, то напівплощина звернена у бік цієї точки, якщо не справедлива – то у протилежний бік від точки. Напрямок напівплощини на малюнку позначається стрілкою.
Розв’язком кожної нерівності системи є напівплощина, яка вміщує граничну пряму і розміщена по одну сторону від неї.
Перетином напівплощин, кожна з яких визначається відповідною нерівністю системи, називається областю розв’язків системи (ОР).
Область розв’язків системи, яка задовольняє умовам невід’ємності (), називається областю невід’ємних або припустимих розв’язків (ОПР).
Приклад. Знайти ОР і ОПР системи нерівностей і визначити координати кутових точок ОПР.
Знайдемо ОР системи. Для цього побудуємо граничну пряму і підставимо координати точки
у нерівність (1):
Координати точки
не задовольняють нерівності (1), тому розв’язком цієї нерівності є напівплощина, що не вміщує точки
.
(1) При
При
(2) При
При
(3) При
При
(4) При
При
Областю розв’язків і областю припустимих розв’язків є чотирьохкутник . Знайдемо кутові точки чотирьохкутника.
.
;
.
.
.
Графічний метод
Найбільш простим і наочним методом лінійного програмування є графічний метод. Він застосовується для розв’язання задач лінійного програмування, які задано у неканонічній формі і багатьма змінними у канонічній формі при умові, що вони вміщують не більше двох вільних змінних.
З геометричної точки зору у задачах лінійного програмування відшукується така кутова точка або набір точок із припустимої множини розв’язків, на якій досягається сама верхня (нижня) лінія рівня, розміщена далі (ближче) інших у напрямку найбільш швидкого зростання.
Для знаходження екстремального значення цільової функції при графічному розв’язанні задач лінійного програмування використовують вектор на площині
.
З курсу вищої математики відомо, що для функції двох змінних , що є диференційованою у точці
, градієнтом функції
називається вектор, координатами якого є значення частинних похідних у точці
.
Градієнт функції характеризує напрямок і величину максимальної швидкості зростання цієї функції у точці.
Для визначення геометричного змісту градієнта функції введемо поняття поверхні рівня.
Поверхнею рівня функції називається поверхня, на якій ця функція зберігає постійне значення.
Градієнт функції у даній точці ортогональний до цієї поверхні.
У випадку функції двох змінних, замість поверхні рівня будуть фігурувати лінії рівня.
Надалі будемо позначати градієнт цільової функції . Цей вектор показує напрямок найшвидшої зміни цільової функції.
,
де - одиничні вектори за осями
та
відповідно.
Таким чином . Координатами вектора
є коефіцієнти цільової функції
.
Алгоритм розв’язання задачі
1. Знаходимо область припустимих розв’язків системи обмежень задачі.
2. Будуємо вектор .
3. Проведемо лінію рівня , яка ортогональна до вектора
.
4. Лінію рівня переміщуємо за напрямком вектора для задач на максимум і в напрямку протилежному
- для задач на мінімум.
Переміщення лінії рівня здійснюється до тих пір, доки у неї не буде тільки однієї спільної точки з областю припустимих розв’язків. Ця точка визначає єдиний розв’язок задачі лінійного програмування і буде точкою екстремуму. Якщо ж лінія рівня буде паралельною одній з сторін області припустимих розв’язків, то у цьому випадку екстремум розглядається у всіх точках відповідної сторони, а задача лінійного програмування буде мати нескінчену множину рішень. У цьому випадку говорять, що така задача має альтернативний оптимум і її розв’язок знаходиться за формулою
де , а
,
- оптимальні рішення у кутових точках області припустимих розв’язків.
Задача лінійного програмування може бути нерозв’язаною, коли обмеження, що її визначають, будуть суперечними.
5. Знайдемо координати точки екстремуму і значення цільової функції в ній.
Симплексний метод
Симплексний метод є універсальним, оскільки дозволяє розв’язати практично будь-яку задачу лінійного програмування, яка записана у канонічному вигляді.
Ідея симплекс-методу або методу послідовного покращення плану полягає у тому, що починаючи з деякого початкового опорного рішення здійснюється послідовно спрямоване переміщення по опорним рішенням задачі до оптимального. Значення цільової функції при цьому переміщенні для задач на максимум не спадає. Оскільки число опорних рішень є скінченим, то через скінчене число кроків одержують оптимальний опорний розв’язок.
Опорним розв’язком називають базисний невід’ємний розв’язок.
Алгоритм симплексного методу
1. Математична модель задачі повинна бути канонічною.
2. Відшукується вихідний опорний розв’язок і здійснюється перевірка його на оптимальність. Для цього заповнюється симплексна таблиця. Всі рядки таблиці першого кроку за виключенням рядка (індексний рядок) заповнюються за даними системи обмежень та цільової функції.
БЗ – базисна змінна.
Індексний рядок для змінних визначається за формулою
,
,
![]() | БЗ | ![]() | ![]() | ... | ![]() | ![]() ![]() |
![]() | ![]() | ... | ![]() | |||
![]() | ![]() | ![]() | ![]() | ... | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ... | ![]() | ![]() |
... | ... | ... | ... | ... | ... | ... |
![]() | ![]() | ![]() | ![]() | ... | ![]() | ![]() |
![]() | ![]() | ![]() | ... | ![]() | ![]() |
для вільного члена за формулою
.
Можливі наступні випадки при розв’язанні задачі на максимум:
- якщо всі оцінки , то знайдений розв’язок є оптимальним;
- якщо хоча б одна оцінка , але при відповідній змінній немає жодного додатного коефіцієнта, розв’язання задачі припиняється, тому що
, тобто цільова функція є необмеженою у області припустимих розв’язків;
- якщо хоча б одна оцінка від’ємна, а при відповідній змінній є хоча б один додатній коефіцієнт, то необхідно переходити до другого опорного розв’язку;
- якщо від’ємних оцінок в індексному рядку декілька, то у стовпець базисної змінної (БЗ) вводять ту змінну, якій відповідає найбільша за абсолютною величиною від’ємна оцінка.
Якщо хоча б одна оцінка , то
-й стовпець приймається за ключовий. За ключовий рядок приймається такий, якому відповідає мінімальне відношення вільних членів
до додатних елементів
-го стовпця. Елемент, який знаходиться на перетині ключових рядка і стовпця називається ключовим елементом.
3. Заповнюється симплексна таблиця другого кроку:
- переписується ключовий рядок, з діленням кожного його елемента на ключовий елемент;
- заповнюється базисний стовпець, при цьому всі елементи окрім ключового дорівнюють нулю;
- решта коефіцієнтів таблиці знаходяться за правилом прямокутника.
Наприклад, якщо є ключовим елементом, тоді у симплексній таблиці другого кроку
.
Альтернативний оптимум
При розв’язанні задач лінійного програмування симплексним методом за критерій оптимальності приймають умову: оцінка вільних змінних для задач на максимум і умова
для задач на мінімум.
Якщо на будь-якому кроці хоча б одна з оцінок вільної змінної , а решта
для задач на максимум (
для задач на мінімум), то прийнявши за ключовий стовпець той стовпець, де
та знайдемо новий оптимальний розв’язок, при якому значення цільової функції не змінюється. У цьому випадку задача має альтернативний оптимум.
Критерієм альтернативного оптимуму при розв’язанні задач симплексним методом є рівність нулю хоча б однієї оцінки вільної змінної .
Якщо тільки одна оцінка вільної змінної дорівнює нулю, тоді розв’язок задачі знаходиться за формулою
, де
.
Якщо дві оцінки і більше, наприклад , вільних змінних дорівнюють нулю, тоді оптимальний розв’язок знаходиться за формулою
, де
Транспортна задача
Транспортна задача – одна з розповсюджених задач лінійного програмування. Її мета – розробка найбільш раціональних шляхів і способів транспортування товарів, усунення найбільш віддалених, зустрічних, повторних перевезень. Все це скорочує час просування товарів, зменшує витрати підприємств, пов’язаних із здійсненням процесів забезпечення сировиною, матеріалами, паливом, обладнанням тощо.
У загальному вигляді задачу можна представити наступним чином: у т пунктах виробництва маємо однорідний вантаж відповідно у кількості
. Цей вантаж необхідно доставити у п пунктів призначення
відповідно у кількості
. Вартість перевезення одиниці вантажу (тариф) із пункту
до пункту
дорівнює
.
Необхідно скласти план перевезень, яких дозволяє перевезти весь вантаж при мінімальних транспортних витратах.
У залежності від співвідношення між сумарними запасами вантажу і сумарними потребами у них, транспортні задачі можуть бути закритими і відкритими.
Якщо , тоді транспортна задача називається закритою.
Якщо , тоді транспортна задача називається відкритою.
Позначимо через кількість вантажу, який перевозять з пункту
до пункту
.
Відкрита транспортна задача
Умову даної задачі запишемо у вигляді розподільчої таблиці.
Математична модель закритої транспортної задачі має наступний вид
при обмеженнях
![]() ![]() | ![]() | ![]() | ... | ![]() | ... | ![]() | |
![]() | ![]() | ... | ![]() | ... | ![]() | ||
![]() | ![]() | ![]() ![]() | ![]() ![]() | ... | ![]() ![]() | ... | ![]() ![]() |
![]() | ![]() | ![]() ![]() | ![]() ![]() | ... | ![]() ![]() | ... | ![]() ![]() |
... | ... | ... | ... | ... | ... | ... | ... |
![]() | ![]() | ![]() ![]() | ![]() ![]() | ... | ![]() ![]() | ... | ![]() ![]() |
... | ... | ... | ... | ... | ... | ... | ... |
![]() | ![]() | ![]() ![]() | ![]() ![]() | ... | ![]() ![]() | ... | ![]() ![]() |
Оптимальним розв’язком задачі є матриця , яка задовольняє системі обмежень і дозволяє мінімізувати цільову функцію.
Транспортна задача, яка є задачею лінійного програмування, може бути розв’язана симплексним методом, але наявність великої кількості змінних і обмежень робить обчислення громіздкими. Тому для розв’язання транспортних задач розроблено спеціальний метод, який має ті ж самі етапи, що і симплексний метод, а саме:
- знаходження вихідного опорного розв’язку;
- перевірка цього розв’язку на оптимальність;
- перехід від одного опорного розв’язку до іншого.
Знаходження вихідного опорного розв’язку
У розподільчій таблиці клітини, у яких помістимо вантажі, називаються зайнятими і їм відповідають базисні змінні опорного розв’язку. Інші клітини називаються незайнятими або пустими і їм відповідають вільні клітини. У верхньому правому куті кожної клітини будемо записувати тарифи. Існують декілька способів знаходження вихідного опорного розв’язку.
Розглянемо метод мінімального тарифу. Згідно з цим методом, вантажі розподіляються у першу чергу в ті клітини, в яких знаходиться мінімальний тариф перевезень . У подальшому поставки розподіляються у незайнятих клітинах з найменшими тарифами з урахуванням запасів, що залишилися у постачальників, і задоволення попиту споживачів. Процес розподілу продовжують до тих пір, доки всі вантажі від постачальників не будуть вивезеними, а споживачі не будуть задоволеними. При розподілі вантажів може бути, що кількість зайнятих клітин менше, ніж
. У цьому випадку недостатня їх кількість заповнюється клітинами з нульовими поставками, такі клітини називаються умовно зайнятими.
Нульові поставки розміщують у незайняті клітини з урахуванням найменшого тарифу таким чином, щоб у кожному рядку і стовпці було не менше, ніж по одній зайнятій клітині.
Покращення отриманого опорного плану методом потенціалів
Після завершення першого етапу розв’язку задачі знайдені невідомі можна розбити на дві групи – базисні (зайняті) і вільні.
Представимо цільову функцію наступним чином
,
де - вільні змінні;
- знайдений опорний план, а значення
отримаємо за допомогою методів потенціалів.
Поставимо у відповідність кожному з пунктів відправлення вантажів деяку величину
- „потенціал” пункту
. Аналогічно кожному пункту призначення
величину
- „потенціалу” пункту
.
Для кожного базисного невідомого складаємо рівняння
, де
- вартість перевезення з пункту
до пункту
. Розв’язуємо систему рівнянь і знаходимо всі потенціали
та
.
Тепер для кожної вільної змінної обчислюємо суму
- посередні вартості та заносимо до таблиці.
Наступним кроком є визначення різниць між справжніми вартостями перевезень та посередніми вартостями, які відповідають вільним клітинам.
Якщо всі величини невід’ємні, то початковий знайдений розв’язок є оптимальним. Якщо
, тоді необхідно перейти до іншого базису.
Альтернативний оптимум у транспортних задачах
Ознакою наявності альтернативного оптимуму у транспортних задачах є рівність нулю хоча б однієї з оцінок вільних змінних у оптимальному розв’язку . Зробивши перерозподіл вантажів відносно клітини, що має
, одержимо новий оптимальний розв’язок
, при цьому значення цільової функції (транспортних витрат) не зміниться.
Якщо одна різниця дорівнює нулю, тоді оптимальний розв’язок знаходиться за формулою
, де
.
Виродженість у транспортних задачах
При розв’язанні транспортної задачі може бути, що кількість зайнятих клітин менша за . У цьому випадку транспортна задача може мати вироджений розв’язок. Для можливого його виключення, доцільно поміняти місцями постачальників і споживачів або ввести у вільну клітину з найменшим тарифом нульову поставку. Нуль вміщують у таку клітину, щоб у кожному рядку і кожному стовпці було не менше однієї зайнятої клітини.
Відкрита транспортна задача
При відкритій транспортній задачі сума запасів не співпадає з сумою потреб, тобто .
При цьому:
а). Якщо , тоді обсяг запасів перевищує обсяг споживання, всі споживачі будуть задоволені повністю і частина запасів залишається не вивезеною. Для розв’язання такої задачі вводять фіктивного (
-го) споживача, потреби якого
.
Модель такої задачі набуває вигляду
при обмеженнях
б). Якщо , тоді обсяги споживання перевищують обсяги запасів і частина споживачів залишається незадоволеною. Для розв’язання такої задачі вводять фіктивного (
-го) постачальника, обсяги поставок якого
.
Модель такої задачі набуває вигляду
при обмеженнях
При введенні фіктивного постачальника або споживача, задача стає закритою і розв’язується за раніше розглянутим алгоритмом, причому тарифи, що відповідають фіктивному постачальнику або споживачу більше або дорівнюють найбільшому з усіх тарифів. У цільовій функції фіктивний постачальник або споживач не враховується.
ЦІЛОЧИСЛОВЕ ПРОГРАМУВАННЯ