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

Економістам часто потрібно оптимізувати виробничу функцію, максимізувати або мінімізувати її, наприклад, прибуток, збиток або інші дані з урахуванням лінійного обмеження. Розуміння задач лінійного програмування та постановка задач-це вимагає знання основ математики та статистики. Завданням лінійного програмування (LP) є визначення функції для отримання оптимальних даних. Це один з найважливіших інструментів дослідження бізнес-операцій. Він також широко використовується як допомога у прийнятті рішень у багатьох галузях: в галузі економіки, інформатики, математики та інших сучасних практичних досліджень.

Характеристики задач лінійного програмування

Розрізняють наступні характеристики LP:

1. Оптимізація. Основою задач лінійного програмування і постановки задач оптимізації є максимізація або мінімізація деякої бази даних, що є предметом дослідження. Таке часто зустрічається в економіці, бізнесі, рекламі та багатьох інших областях, які вимагають ефективності з метою збереження ресурсів. Сюди відносяться питання отримання прибутку, придбання ресурсів, час виробництва та інші важливі економічні показники.
2. Лінійність. Як випливає з назви, усі завдання LP мають ознаку лінійності. Однак він часом вводить в оману, так як лінійність відноситься тільки до змінних 1 ступеня, виключаючи статечні функції, квадратні корені та інші нелінійні залежності. При цьому вона не означає, що функції завдання LP мають тільки одну змінну. Вона відноситься до змінних як до координат точок на прямій, виключаючи будь-яку кривизну.
3. Об`єктивна функція. Основа задач лінійного програмування і постановки задач об`єктивності-змінні, що змінюються за бажанням, наприклад, час, витрачений на роботу, вироблені одиниці товару. Цільова функція пишеться з великої літери»Z".
4. Обмеження. Усі LP обмежуються змінними всередині функції. Ці обмеження мають форму нерівностей, наприклад « " b<3", де b може представляти одиниці книг, написаних автором на місяць. Ці нерівності встановлюють, як можна максимізувати/мінімізувати цільову функцію, оскільки разом вони визначають області ухвалення рішення.

Умови визначення завдань

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

Умови виконання завдань лінійного програмування і постановки завдань необхідні для отримання максимального чистого прибутку. Для того щоб вирішити задачу LP, вона повинна мати:

1. Обмеження або обмежені ресурси, наприклад, обмежена кількість працівників, максимальна кількість клієнтів або обмеження виробничих втрат.
2. Мета: максимізація доходу або мінімізація витрат.
3. Пропорційну лінійність. Рівняння, які генерують вирішальні змінні, повинні бути лінійними.
4. Однорідність: характеристики змінних рішення та ресурсів однакові. Наприклад, години роботи людини однаково продуктивні або товари, виготовлені на верстаті, ідентичні.
5. Подільність: продукти та ресурси можуть бути показані у вигляді дробу.
6. Відсутність негативності: рішення повинні бути позитивними або нульовими.

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

Це представляється рівнянням зі змінним рішенням, де: X 1, X 2, x 3, ..., X n-змінні рішення; C 1, C 2, c 3, ..., C n-константи.

Кожне обмеження виражається математично з будь-яким із цих ознак:

1. Менше або дорівнює (≤). Коли є верхня межа, наприклад, понаднормова робота не може бути більше 2 годин на день.
2. Рівний (=). Вказує обов`язкові відносини, наприклад, кінцевий запас дорівнює початковому запасу плюс виробництво мінус продажу.
3. Більше або дорівнює (≥). Наприклад, коли існує нижня межа, виробництво певного продукту має бути вищим, ніж прогнозований попит.
4. Загальна постановка задачі лінійного програмування починається з установки обмежень.
5. Будь-яке завдання LP повинно мати одне або кілька обмежень.
6. Позитивність змінних рішення повинна розглядатися в рамках обмежень.

Етапи постановки завдань

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

Кроки постановки задачі цілочисельного лінійного програмування:

1. Визначають число, що виявляє поведінку цільової функції для оптимізації.
2. Знаходять набір обмежень і виражають їх у вигляді лінійних рівнянь або нерівностей. Це встановить область У n-вимірному просторі оптимізованих функцій.
3. Необхідно накласти умова невід`ємності на змінні завдання, тобто всі вони повинні бути позитивними.
4. Виражають функцію у формі лінійного рівняння.
5. Оптимізують функцію графічно або математично, коли виконується математична постановка задачі лінійного програмування.

Графічний спосіб

Графічний метод використовується для виконання завдань LP у двох змінних. Цей метод не застосовується для вирішення проблем, які мають три або більше змінних рішень.

Стандартна задача максимізації невідомих проблем LP, в якій збільшують функцію, за умови обмежень виду:

x ≥ 0, y ≥ 0, z ≥ 0 та подальші обмеження форми:

Ax + By + C z +. , ≤ N,

де A, B, C і N є невід`ємними числами.

Нерівність повинна бути"≤", а не " = " або»≥".

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

1. Встановлюють можливі області графіка.
2. Обчислюють кутові координати точок.
3. Підставляють їх з метою побачити оптимальне значення. Цей момент дає рішення задачі LP.
4. Мінімізують функцію і, якщо її коефіцієнти невід`ємні, рішення існує.

Визначення існуючих рішень:

1. Обмежують область, додавши вертикальну лінію праворуч від крайньої правої кутової точки і горизонтальну лінію вище найвищої кутової точки.
2. Розраховують координати нових кутових точок.
3. Знаходять кутову точку з оптимальним значенням.
4. Якщо воно має місце у вихідній точці необмеженої області, то у задачі LP є рішення в даній точці. Якщо ні, то вона не має оптимального рішення.

Замальовка набору рішень

Вибирають точку відліку і відзначають блокується область.

Малюють область, представлену нерівністю двох змінних при постановці задачі лінійного програмування. Коротко для прикладу:

1. Малюють пряму, отриману шляхом заміни нерівності на рівність.
2. Вибирають контрольну точку, (0,0). Хороший вибір, якщо лінія проходить через початок.
3. Якщо контрольна точка задовольняє нерівності, то множина рішень-це вся область на тій же стороні лінії, що і контрольна точка. В іншому випадку вона знаходиться на іншій стороні лінії.
4. Допустима область визначається набором лінійних нерівностей і є сукупністю точок, що задовольняють всі нерівності.
5. Щоб намалювати її, що визначається набором лінійних нерівностей з двома змінними, виконують області, представлені кожною нерівністю, на одному графіку, не забуваючи затінювати частини площини, які не потрібні.

Симплексний метод для максимізації

Постановку задачі лінійного програмування з математичною моделлю для максимізації можна виконати із застосуванням симплекс-методу:

1. Перетворюють дані в систему рівнянь, вводячи слабкі змінні, щоб перетворити обмеження в рівняння, і переписують функцію в стандартну форму.
2. Записують вихідну таблицю.
3. Вибирають стовпець розвороту, негативне число з найбільшою величиною в нижньому ряду, виключаючи крайню праву запис. Його стовпець є зведеним. Якщо є два кандидати, вибирають один. Якщо всі числа в нижньому ряду дорівнюють нулю або позитивні, виключаючи крайню праву запис, то все готово і базове рішення максимізує цільову функцію.
4. Вибирають стрижень в стовпці. Вісь завжди повинна бути позитивним числом. Для кожного позитивного запису " b "у стовпці зведених даних обчислюють відношення "a» b", де "a" є відповіддю в цьому рядку. З тестових коефіцієнтів вибирають мінімальне, тоді відповідне число " b " буде віссю.
5. Використовують стрижень, щоб очистити стовпець звичайним способом, стежачи за тим, щоб точно виконувати приписи для формулювання операцій з рядками, описаним в керівництві по методу Гаусса-Джордана, а потім міняють місцями стовпець з міткою з колонки.
6. Змінна, яка спочатку позначає рядок резюме, є вихідною, а змінна, що позначає стовпець, є вхідною.

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

Нестандартні обмеження

Для того щоб вирішити задачу LP з обмеженнями виду (Ax + By +. , .≥ N) з позитивним N, віднімають зайву змінну з лівої частини (замість додавання слабкої змінної). Базове рішення, що відповідає вихідній таблиці, не буде здійсненним, оскільки деякі активні змінні будуть негативними. Тому правила початкового повороту відрізняються від наведених вище.

Далі позначають всі рядки, які дають негативне значення для пов`язаної активної змінної, за винятком цільової. Якщо є позначені рядки, потрібно почати з I етапу.

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

II етап використовує симплекс-метод для стандартної задачі максимізації. Якщо в лівому нижньому ряду після I етапу є які-небудь негативні значення, використовують метод стандартних задач максимізації.

Приклад гри, яка може бути вирішена з використанням симплекс-методу.

Онлайн інструмент PHPSimplex

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

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

WanerMath: додатки без кордонів

Warneth надає 2 інструменти для вирішення задач лінійного програмування:

1. Графік лінійного програмування (дві змінні).
2. Симплексний метод.

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

JSimplex-ще один інструмент онлайн. Він дозволяє вирішувати задачі LP без обмеження кількості змінних. Має простий інтерфейс управління, в якому пропонується вказати мету і кількість змінних. Користувач записує коефіцієнти цільової функції, обмеження і натискає на»вирішити". Буде показана інтеграція, розрахунок оптимального варіанту і результати кожної змінної.

Як видно, ці інструменти надзвичайно корисні для легкого вивчення процедур вирішення лінійного програмування.

Простий приклад LP

Компанія випускає портативні і калькулятори для наукових робіт. Довгострокові прогнози вказують на очікувану щоденну потребу в 150 наукових і 100 портативних калькуляторах. Добовий виробнича потужність щодня дозволяє виробляти не більше 250 наукових і 200 портативних калькуляторів.

Для того щоб виконати контракт на доставку, необхідно випустити мінімум 250 калькуляторів. Реалізація одного-призводить до збитку 20 рублів, але кожен ручний калькулятор приносить прибуток в розмірі 50 рублів. Необхідно виконати розрахунок, щоб отримати максимальний чистий прибуток.

Алгоритм виконання прикладу постановки задач лінійного програмування:

1. Змінні рішення. Оскільки було задано оптимальну кількість калькуляторів, саме вони будуть змінними я в цьому завданні: x-кількість наукових калькуляторів, y-кількість портативних.
2. Встановлюють обмеження, оскільки компанія не може виробляти негативну кількість калькуляторів на день, природним обмеженням буде: x ≥ 0, y ≥ 0.
3. Нижня лінія: x ≥ 150, y ≥ 100.
4. Встановлюють верхню межу для цих змінних через обмеження на виробництво компанією: x ≤ 250, y ≤ 200.
5. Спільне обмеження на значення `x` і `y` через Мінімальне замовлення на відправку вантажу: х + у ≥ 250
6. Оптимізують функцію чистого прибутку: P = - 20x + 50y.
7. Рішення задачі: максимізація P = - 20x + 50y за умови, що 150 ≤ x ≤ 250; 100 ≤ y ≤ 200; x + y ≥ 250.

Галузь застосування

Серед застосувань лінійного програмування найбільш поширені:

1. Сукупне планування продажів і операцій. Мета полягає в тому, щоб мінімізувати виробничі витрати в короткостроковій перспективі, наприклад, три і шість місяців, що задовольняють очікуваний попит.
2. Планування продукту: знайти оптимальне поєднання продуктів, враховуючи, що вони вимагають різних ресурсів і мають різні витрати. Як приклад можна знайти оптимальну суміш хімічних елементів для бензину, фарб, дієт для людини і кормів для тварин.
3. Виробничий потік: визначають оптимальний потік для виробництва продукту, який повинен проходити послідовно через кілька робочих процесів, де кожен має свої витрати і виробничі характеристики.
4. Постановка транспортної задачі лінійного програмування, розклад перевезень. Метод використовується для програмування декількох маршрутів певної кількості транспортних засобів для обслуговування клієнтів або отримання матеріалів, які будуть перевозитися між різними місцями. Кожен транспортний засіб може мати різну вантажопідйомність і продуктивність.
5. Управління запасами: визначення оптимальної комбінації продуктів, які будуть в наявності на складі в продажній мережі.
6. Програмування персоналу: розробка плану по кадрам, який дозволяє задовольнити очікуваний змінний попит на фахівців при мінімально можливій кількості співробітників.
7. Контроль відходів: за допомогою лінійного програмування можна розрахувати, як зменшити відходи до мінімуму.

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