Линейното и цяло число програмиране са ключови техники за дискретни оптимизационни проблеми и те се появяват почти навсякъде в съвременния бизнес и технологичен сектор. Ще обсъдим как да се справим с такива проблеми с помощта на библиотеката на Python PuLP и ще получим бързо и стабилно решение.
Тиртхаджиоти Саркар
20 април 2019 г. · 11 минути четене
Дискретна оптимизация е клон на методологията за оптимизация, който се занимава с дискретни величини, т.е.непрекъснати функции. Той е доста повсеместен, тъй като разнообразни приложения като финансови инвестиции, диетично планиране, производствени процеси и избор на играч или график за професионални спортове.
Линейно и (смесено) цяло число програмиране са техники за решаване на проблеми, които могат да бъдат формулирани в рамките на дискретна оптимизация.
Познаването на такива техники за оптимизация е изключително полезно за изследователите на данни и специалистите в областта на машинното обучение (ML), тъй като дискретната и непрекъсната оптимизация лежи в основата на съвременните системи за ML и AI, както и процесите на бизнес анализ, управлявани от данни.
Има много инструменти за комерсиален оптимизатор, но наличието на практически опит с програмен начин за оптимизация е безценно.
Това е дълга и богата история на теоретичното разработване на стабилни и ефективни решения за оптимизационни проблеми. Въпреки това, фокусирайки се върху практически приложения, ще пропуснем тази история и ще преминем направо към частта от обучението как да използваме програмни инструменти за формулиране и решаване на такива оптимизационни проблеми.
В Python има много отлични пакети за оптимизация. В тази статия ще говорим специално за PuLP. Но преди да отидем в библиотеката на Python, нека да разберем какъв проблем можем да решим с него.
Да предположим, че отговаряте за диетичния план за обяд в гимназията. Вашата задача е да се уверите, че учениците получават правилния баланс на хранене от избраната храна.
Има обаче някои ограничения по отношение на бюджета и разнообразието от храни, които трябва да бъдат в диетата, за да бъде интересно. Следващата таблица показва подробно пълната хранителна стойност за всеки хранителен продукт и техния максимален/минимален дневен прием.
Проблемът с дискретната оптимизация е прост: Минимизирайте разходите за обяда, като се имат предвид тези ограничения (за общите калории, но също така и за всеки хранителен компонент, напр. холестерол, витамин А, калций и др.
По същество проблемът е в небрежния математически език,
Забележете, че всички отношения на неравенството имат линеен характер, т.е.променливите f се умножават по постоянни коефициенти и получените членове са ограничени от постоянни граници и това прави този проблем решим чрез LP техника.
Можете да си представите, че този вид проблем може да се появи в бизнес стратегията изключително често. Вместо хранителни стойности ще имате печалби и други видове бизнес доходност, а вместо цена/обслужване може да имате разходи по проекта в хиляди долари. Като мениджър вашата работа ще бъде да изберете проектите, които дават максимална възвръщаемост на инвестицията, без да надвишават общия бюджет за финансиране на проекта.
Подобен проблем с оптимизацията може да се появи в заводски производствен план също, където максималният производствен капацитет ще бъде функция на използваните машини, а отделните продукти ще имат различни характеристики на печалба. Като производствен инженер вашата работа може да бъде да разпределяте внимателно машинни и трудови ресурси, за да увеличите максимално печалбата, като същевременно отговаряте на всички ограничения на капацитета.
По същество, общото между тези проблеми от различни домейни е, че те включват максимизиране или минимизиране на линейна целева функция, подчинени на набор от линейни ограничения на неравенството или равенството.
За проблема с диетата целевата функция е общите разходи, които се опитваме да сведем до минимум. Ограниченията за неравенство се дават от минималните и максималните граници на всеки от хранителните компоненти.
Има много библиотеки в екосистемата на Python за този вид проблеми с оптимизацията. PuLP е линейно програмиране с отворен код (LP) пакет, който до голяма степен използва синтаксиса на Python и се доставя с много решаващи за индустрията решения. Той също така се интегрира добре с редица решаващи LP и търговски LP решения.
Можете да го инсталирате с помощта на pip (а също и някои допълнителни решения)
Вижте хубаво видео за решаване на линейно програмиране тук.
Първо, ние създаваме LP проблем с метода LpProblem в PuLP.
След това трябва да създадем куп обекти на речника на Python с информацията, която имаме от таблицата. Кодът е показан по-долу,
За краткост тук не показахме пълния код. Можете да вземете всички хранителни компоненти и да създадете отделни речници за тях.
След това създаваме речник на променливите на хранителните продукти с долна граница = 0 и категория непрекъснато т.е.решението за оптимизация може да приеме всяка реално номерирана стойност, по-голяма от нула.
Обърнете внимание на особената важност на долната граница.
В нашия ум не можем да мислим, че част от храната е нещо различно от неотрицателно, ограничено количество, но математиката не знае това.
Без изрична декларация за тази обвързаност, решението може да е нечувствително, тъй като решаващият може да се опита да излезе с отрицателни количества избор на храна, за да намали общите разходи, като същевременно отговаря на хранителните изисквания!
След това започваме да изграждаме проблема с LP чрез добавяне на основната целева функция. Обърнете внимание на използването на lpSum метод.
Допълнително надграждаме върху това, като добавяме калорични ограничения,
Можем да натрупаме всички хранителни ограничения. За простота просто добавяме четири ограничения върху мазнините, въглехидратите, фибрите и протеините. Кодът е показан по-долу,
И приключихме с формулирането на проблема!
Във всеки сценарий за оптимизация трудната част е формулирането на проблема по структуриран начин, който е представим за решаващ.
Направихме трудната част. Сега това е относително по-лесната част от стартирането на решател и изследването на решението.
PuLP има доста възможности за избор на алгоритми за решаване (напр. COIN_MP, Gurobi, CPLEX и др.). За този проблем не посочваме никакъв избор и оставяме програмата да се зададе по свой избор в зависимост от структурата на проблема.
Можем да отпечатаме състоянието от разтвора. Имайте предвид, че в този случай състоянието е оптимално, не е необходимо да е така. В случай че проблемът е неправилно формулиран или няма достатъчно информация, решението може да е невъзможно или неограничено.
Пълното решение съдържа всички променливи, включително тези с нулеви тегла. Но за нас са интересни само онези променливи, които имат ненулеви коефициенти т.е. които трябва да бъдат включени в оптималния хранителен план. Така че, можем да сканираме през проблемните променливи и да разпечатаме само ако променливото количество е положително.
И така, оптималното решение е да се изядат 6.923 порции замразени броколи, 6.06 порции бъркани яйца и 1.08 порции печен картоф!
Можете да изтеглите целия бележник, файла с данни и да експериментирате с различни ограничения, за да промените диетичния си план. Кодът е тук в моето хранилище на Github.
Накрая можем да отпечатаме целевата функция, т.е. цената на диетата в такъв случай,
Както виждаме, оптималният резултат се върна с набор от частичен брой порции за хранителните продукти. Това може да не е практично и може да искаме решението да бъде принудено да има само цели числа като порции.
Това ни представя техниката на цяло число програмиране. Алгоритъмът, използван за предишната оптимизация, е просто линейно програмиране, където на променливите беше позволено да приемат всяка реална числова стойност. Целочисленото програмиране принуждава някои или всички променливи да приемат само цели числа.
Всъщност целочисленото програмиране е по-труден изчислителен проблем от линейното програмиране. Целочислените променливи правят проблема с оптимизацията неизпъкнал и следователно много по-труден за решаване. Времето на паметта и решението може да се увеличи експоненциално, когато добавяте повече целочислени променливи.
За щастие, PuLP може да реши проблем с оптимизацията и с този вид ограничения.
Кодът е почти идентичен както преди, така че тук не се повтаря. Единствената разлика е, че променливите се определят като принадлежащи към Integer категория за разлика от Непрекъснато .
За този проблем той леко променя оптималното решение, добавя маруля айсберг към диетата и увеличава цената с 0,06 долара. Също така ще забележите значително увеличение на времето за изчисление за процеса на решение.
Готиното приложение на цялостно програмиране решава проблема с планирането на драйвери което може да бъде NP-труден проблем. Вижте тази статия (забележете също в статията как те изчисляват разходите за различни действия и ги използват в задачата за оптимизация),
- Линейно програмиране Още проблеми с думи
- Линейно чуждо тяло в болница за животни за котки VCA
- Японската звезда на Netflix Хана Кимура вероятно е отнела живота си, използвайки токсичен газ
- IJMS Безплатен пълен текст NAD метаболомен анализ в човешки клетки с помощта на 1H NMR спектроскопия
- Влияние на затлъстяването при майките върху феталното програмиране на физиологията на сърдечно-съдовите заболявания