Задачі лінійного програмування постановка задачі: методи рішення і формування
Для економістів часто необхідно оптимізувати виробничу функцію, максимізувати або мінімізувати її, наприклад, прибуток, збиток або інші дані з урахуванням лінійного обмеження. Розуміння завдань лінійного програмування і постановка завдань — це вимагає знання основ математики і статистики. Задачею лінійного програмування (LP) є визначення функції для отримання оптимальних даних. Це один з найважливіших інструментів дослідження бізнес-операцій. Він також широко використовується в якості допомоги при прийнятті рішень у багатьох галузях: у галузях економіки, комп’ютерних наук, математики та інших сучасних практичних дослідженнях.
Характеристики задач лінійного програмування
Розрізняють наступні характеристики LP:
Оптимізація. Основою задач лінійного програмування і постановки задач оптимізації є максимізація або мінімізація деякої бази даних, яка є предметом дослідження. Таке часто зустрічається в економіці, бізнесі, рекламі і багатьох інших областях, які вимагають ефективності з метою збереження ресурсів. Сюди належать питання отримання прибутку, придбання ресурсів, виробництва та інші важливі економічні показники.
Лінійність. Як випливає з назви, всі завдання LP мають ознаку лінійності. Однак він іноді вводить в оману, так як лінійність відноситься тільки до змінним 1 ступеня, крім степеневі функції, квадратні коріння та інші нелінійні залежності. При цьому вона не означає, що функції задачі LP мають лише одну змінну. Вона відноситься до змінних як до координат точок на прямій, виключаючи будь-яку кривизну.
Об’єктивна функція. Основа завдань лінійного програмування і постановки завдань об’єктивності — змінні, що змінюються за бажанням, наприклад, час, витрачений на роботу, вироблені одиниці товару. Цільова функція пишеться з великої літери «Z».
Обмеження. Всі LP обмежуються змінними всередині функції. Ці обмеження приймають форму нерівностей, наприклад, «b<3», де b може представляти одиниці книг, написаних автором у місяць. Ці нерівності встановлюють, як можна максимізувати/мінімізувати цільову функцію, оскільки разом вони визначають області прийняття рішення.
Умови визначення завдань
Компанії прагнуть отримати найбільшу прибутковість своєї діяльності, тому повинні максимально використовувати наявні у них ресурси: людський, матеріали, обладнання, кошти та інші. LP представляється як корисний інструмент, що допомагає визначенню кращого рішення в компанії.
Умови виконання завдань лінійного програмування і постановки задач необхідні для отримання максимального чистого прибутку. Для того щоб вирішити завдання LP, вона повинна мати:
Обмеження або обмежені ресурси, наприклад, обмежена кількість працівників, максимальну кількість клієнтів або обмеження виробничих втрат.
Мета: максимізація прибутку чи мінімізація витрат.
Пропорційну лінійність. Рівняння, які генерують вирішальні змінні, повинні бути лінійними.
Однорідність: характеристики змінних рішення і ресурсів однакові. Наприклад, години роботи людини однаково продуктивні або товари, виготовлені на верстаті, ідентичні.
Подільність: продукти і ресурси можуть бути показані у вигляді дробу.
Відсутність отрицательности: рішення повинні бути позитивними або рівними нулю.
Об’єктивність функції при постановці основної задачі лінійного програмування математично виражає мету, яка повинна бути досягнута у вирішенні проблеми. Наприклад, максимізувати прибуток або мінімізувати виробничі витрати.
Це представляється рівнянням з перемінним рішенням, де: X 1, X 2, X 3, …, X n — змінні рішення; C 1, C 2, C 3, …, C n — константи.
Кожне обмеження виражається математично з будь-яким з цих ознак:
Менше або дорівнює (≤). Коли є верхня межа, наприклад, понаднормова робота не може бути більше 2 годин на день.
Дорівнює (=). Вказує обов’язкові відносини, наприклад, кінцевий запас дорівнює початкового запасу плюс виробництво мінус продажу.
Більше або дорівнює (≥). Наприклад, коли існує нижня межа, виробництво певного продукту повинна бути вище, ніж прогнозований попит.
Загальна постановка задачі лінійного програмування починається з встановлення обмежень.
Будь-яка задача LP повинна мати одне або кілька обмежень.
Позитивність змінних рішення повинна розглядатися в рамках обмежень.
Етапи постановки завдань
Загальна постановка задачі лінійного програмування та її формулювання ставиться до перекладу реальної проблеми до виду математичних рівнянь, які можуть бути вирішені.
Визначають число, яке виявляє поведінку цільової функції для оптимізації.
Знаходять набір обмежень і виражають їх у вигляді лінійних рівнянь або нерівностей. Це встановить область в n-мірному просторі оптимізованих функцій.
Необхідно накласти умову неотрицательности на змінні задачі, тобто всі вони повинні бути позитивними.
Виражають функцію у формі лінійного рівняння.
Оптимізують функцію графічно або математично, коли виконується математична постановка задачі лінійного програмування.
Графічний спосіб
Графічний метод використовується для виконання завдань LP двох змінних. Цей метод не застосовується для вирішення проблем, які мають три або більше змінних рішень.
Стандартна задача максимізації невідомих проблем LP, в якій збільшують функцію, за умови обмежень виду:
x ≥ 0, y ≥ 0, z ≥ 0 і подальші обмеження форми:
Ax + By + C z +. , ≤ N,
де А, В, С і N є неотрицательными числами.
Нерівність має бути «≤», а не «=» або «≥».
Графічний метод LP з двома невідомими полягає в наступному:
Встановлюють можливі області графіка.
Обчислюють кутові координати точок.
Підставляють їх з метою побачити оптимальне значення. Цей момент дає рішення задачі LP.
Мінімізують функцію і, якщо її невід’ємні коефіцієнти, рішення існує.
Визначення існуючих рішень:
Обмежують область, додавши вертикальну лінію праворуч від крайньої правої кутової точки і горизонтальну лінію вище найвищої кутової точки.
Розраховують координати нових кутових точок.
Знаходять кутову точку з оптимальним значенням.
Якщо воно має місце у вихідній точці необмеженої області, то у завдання LP є рішення в даній точці. Якщо ні, то вона не має оптимального рішення.
Замальовка набору рішень
Вибирають точку відліку і відзначають, заблокованих область.
Малюють область, представлену нерівністю двох змінних при постановці задачі лінійного програмування. Коротко для прикладу:
Малюють пряму, отриману шляхом заміни нерівності на рівності.
Вибирають контрольну точку (0,0). Хороший вибір, якщо лінія проходить через початок.
Якщо контрольна точка задовольняє нерівності, то безліч рішень — це вся область на тій же стороні лінії, що і контрольна точка. В іншому випадку вона знаходиться на іншій стороні лінії.
Допустима область визначається набором лінійних нерівностей і є сукупністю точок, що задовольняють всі нерівності.
Щоб намалювати її, що визначається набором лінійних нерівностей з двома змінними, виконують області, представлені кожним нерівністю, на одному графіку, не забуваючи затінювати частини площини, які не потрібні.
Симплексний метод для максимізації
Постановку задачі лінійного програмування з математичною моделлю для максимізації можна виконати із застосуванням симплекс-методу:
Перетворюють дані в систему рівнянь, вводячи слабкі змінні, щоб перетворити обмеження в рівняння, і переписують функцію в стандартну форму.
Записують початкову таблицю.
Вибирають стовпець розвороту, від’ємне число з найбільшою величиною в нижньому ряду, виключаючи крайню праву запис. Його стовпець є зведеним. Якщо є два кандидати, які вибирають один. Якщо всі числа в нижньому ряду дорівнюють нулю або позитивні, виключаючи крайню праву запис, то все готово і базове рішення максимізує цільову функцію.
Вибирають стрижень у стовпці. Вісь завжди має бути додатним числом. Для кожної позитивної запису «b» у стовпці зведених даних обчислюють відношення «a/b», де “a” є відповіддю у цьому рядку. З тестових коефіцієнтів вибирають мінімальне, тоді відповідне число «b» буде віссю.
Використовують стрижень, щоб очистити стовпець звичайним способом, стежачи за тим, щоб точно виконувати приписи для формулювання операцій зі рядками, описаним у керівництві за методом Гауса-Джордана, а потім міняють місцями стовпчик з міткою з колонки.
Змінна, спочатку позначає рядок зведення, є вихідною, а змінна, що позначає стовпець, є вхідною.
Для того щоб отримати базове рішення, відповідне до будь-якої таблиці в симплекс-методі, встановлюють в нуль всі змінні, які не відображаються, як мітки рядків. Значення відображається мітки рядка (активна змінна) — число в крайньому правому стовпці в рядку, поділена на число в цьому рядку в стовпці з номером тієї ж змінної.
Нестандартні обмеження
Для того щоб вирішити завдання LP з обмеженнями виду (Ax + By +. , .≥ N) з позитивним N, забирають зайву змінну з лівої частини (замість додавання слабкої змінної). Базове рішення, відповідне вихідній таблиці, не буде здійснимо, оскільки деякі з активних змінних будуть негативними. Тому правила початкового повороту відрізняються від наведених вище.
Далі позначають всі рядки, які дають негативне значення для пов’язаної активної змінної, за винятком цільової. Якщо є помічені рядки, потрібно почати з I етапу.
I етап. У першій рядку знаходять найбільше додатне число. Використовують тестові коефіцієнти, як у попередньому розділі, щоб знайти зведення в цьому стовпці, а потім розгортають цей запис. Повторюють до тих пір, поки не залишиться позначених рядків, потім переходять до етапу II.
II етап використовує симплекс-метод для стандартної задачі максимізації. Якщо в лівому нижньому ряду після I етапу є які-небудь негативні значення, використовують метод стандартних завдань максимізації.
Приклад гри, яка може бути вирішена з використанням симплекс-методу.
Онлайн інструмент PHPSimplex
В даний час технологічні інструменти полегшують багато видів професійної діяльності житті і методи вирішення завдань LP не є винятком. Перевага їх полягає в тому, що можна отримати оптимальне рішення з будь-якого комп’ютера з доступом в інтернеті.
PHPSimplex — відмінний онлайн-інструмент для вирішення завдань LP. Це додаток може вирішувати проблеми без обмежень по кількості змінних і обмежень. Для задач із двома змінними він демонструє графічне рішення і представляє весь процес обчислення оптимального рішення простим і зрозумілим способом. Він має дружній інтерфейс, близький до користувача, простий у використанні і інтуїтивно зрозумілий, доступний на декількох мовах.
WanerMath: додатки без кордонів
Warneth надає 2 інструменту для вирішення завдань лінійного програмування:
Графік лінійного програмування (дві змінні).
Симплексний метод.
На відміну від інших інструментів, де розміщують тільки коефіцієнти, тут включаються всі функції з змінними. Це не являє великі труднощі для початківців користувачів, так як на профільному сайті є інструкція по використанню. На додаток, на сайті є функція «Приклади», яка автоматично створює завдання, щоб користувач міг оцінити його роботу, наприклад, при постановці транспортної задачі лінійного програмування.
JSimplex — ще один інструмент онлайн. Він дозволяє вирішувати завдання LP без обмеження кількості змінних. Має простий інтерфейс управління, в якому пропонується вказати мету і кількість змінних. Користувач записує коефіцієнти цільової функції, обмеження і натискає на «вирішити». Буде показана інтеграція, розрахунок оптимального варіанта і результати кожної змінної.
Як видно, ці інструменти надзвичайно корисні для легкого вивчення процедур розв’язання лінійного програмування.
Простий приклад LP
Компанія випускає портативні і калькулятори для наукових робіт. Довгострокові прогнози вказують на очікувану щоденну потребу в 150 наукових і 100 портативних калькуляторах. Добова виробнича потужність щодня дозволяє виробляти не більше 250 наукових і 200 портативних калькуляторів.
Для того щоб виконати контракт на доставку, необхідно випустити мінімум 250 калькуляторів. Реалізація одного — призводить до збитку 20 рублів, але кожен ручний калькулятор приносить прибуток в розмірі 50 рублів. Необхідно виконати розрахунок, щоб отримати максимальну чистий прибуток.
Алгоритм виконання приклад постановки задач лінійного програмування:
Змінні рішення. Оскільки було задано оптимальна кількість калькуляторів, саме вони будуть змінними я в цій задачі: x — кількість наукових калькуляторів, y — кількість портативних.
Встановлюють обмеження, оскільки компанія не може справити негативний кількість калькуляторів в день, природним обмеженням буде: x ≥ 0, y ≥ 0.
Нижня межа: x ≥ 150, y ≥ 100.
Встановлюють верхню межу для цих змінних із-за обмежень на виробництво компанією: x ≤ 250, y ≤ 200.
Спільне обмеження на значення ‘x’ та ‘y’ з-за мінімального замовлення на відправку вантажу: х + у ≥ 250
Оптимізують функцію чистого прибутку: P = -20x + 50y.
Рішення завдання: максимізація P = -20x + 50y за умови, що 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.
Області застосування
Серед застосувань лінійного програмування найбільш поширені:
Сукупне планування продажів і операцій. Мета полягає в тому, щоб мінімізувати виробничі витрати в короткостроковій перспективі, наприклад, три і шість місяців, що задовольняють очікуваний попит.
Планування продукту: знаходять оптимальне поєднання продуктів, враховуючи, що вони потребують різних ресурсів і мають різні витрати. В якості прикладу можна знайти оптимальну суміш хімічних елементів для бензину, фарб, дієт для людей і кормів для тварин.
Виробничий потік: визначають оптимальний потік для виробництва продукту, який повинен проходити послідовно через кілька робочих процесів, де кожен має свої витрати та виробничі характеристики.
Постановка транспортної задачі лінійного програмування, розклад перевезень. Метод використовується для програмування декількох маршрутів певної кількості транспортних засобів для обслуговування клієнтів або отримання матеріалів, які будуть перевозитися між різними місцями. Кожний транспортний засіб може мати різну вантажопідйомність і продуктивність.
Управління запасами: визначення оптимальної комбінації продуктів, які будуть в наявності на складі в продажної мережі.
Програмування персоналу: розробка плану по кадрам, який дозволяє задовольнити очікуваний змінний попит на фахівців при мінімально можливій кількості співробітників.
Контроль відходів: за допомогою лінійного програмування можна розрахувати, як скоротити відходи до мінімуму.
Це деякі з найбільш поширених застосувань, де використовується лінійне програмування. Загалом, будь-яка задача оптимізації, яка задовольняє вищезазначеним умовам, можуть бути вирішені з його допомогою.
