KDnuggets

Блог/Новини
Думки
Підручники
Найкращі історії
Компанії
Курси
Набори даних
Освіта
Події (онлайн)
Робота
Програмне забезпечення
Вебінари

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

Вступ

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

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

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

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

У Python є багато чудових пакетів оптимізації. У цій статті ми конкретно поговоримо про PuLP. Але перед тим, як перейти до бібліотеки Python, давайте зрозуміємо, яку проблему ми можемо вирішити за допомогою неї.

Приклад проблеми (або дві)

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

Однак існують певні обмеження щодо бюджету та різноманітності їжі, яка повинна бути в раціоні, щоб зробити її цікавою. У наступній таблиці детально наведена повна харчова цінність кожного продукту та їх максимальна/мінімальна добова доза.

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

По суті, у випадковій математичній мові проблема полягає,

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

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

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

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

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

PuLP - бібліотека Python для лінійної оптимізації

У екосистемі Python існує багато бібліотек для вирішення таких проблем оптимізації. PuLP є відкритим кодом лінійне програмування Пакет (LP), який здебільшого використовує синтаксис Python та постачається з багатьма стандартними вирішувачами. Він також чудово інтегрується з цілим рядом відкритих та комерційних вирішувачів LP.
Ви можете встановити його за допомогою pip (а також деяких додаткових вирішувачів)

Дивіться чудове відео про вирішення лінійного програмування тут.