Изследванията на операциите, науката за използване на компютри за вземане на оптимални решения, се използват и прилагат в много области на софтуера. За да дадат някои примери, логистичните компании го използват, за да определят оптималния маршрут за достигане от точка А до точка Б, енергийните компании го използват, за да определят графиците за производство на енергия, а производствените компании го използват, за да намерят оптимални модели на персонал за вашите фабрики.

Днес ще изследваме силата на оперативното изследване, като разгледаме хипотетичен проблем. По-конкретно, ще използваме смесено цяло число програмиране ( MIP ), за да се определи оптималният модел на персонал за хипотетична фабрика.

Алгоритми за изследване на операциите

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

Алгоритми за линейно програмиране

Линейното програмиране е техника за изследване на операциите, използвана за определяне на най-добрия резултат в математически модел, където целта и ограниченията се изразяват като система от линейни уравнения. Пример за модел на линейно програмиране може да изглежда така:

Maximize a + b (objetive) Subject a: a <= 2 (restriction 1) b <= 3 (restriction 2)

В нашия прост пример можем да видим, че оптималният резултат е 5, с a = 2 и b = 3. Въпреки че това е доста тривиален пример, вероятно можете да си представите модел на линейно програмиране, който използва хиляди променливи и стотици ограничения. .

Добър пример може да бъде проблем с инвестиционен портфейл, където може да се окажете с нещо като следното, в псевдокод:

Maximize Subject to: Etc. ...

Което би било доста сложно и трудно за решаване на ръка или чрез проби и грешки. Софтуерът за оперативни изследвания ще използва различни алгоритми за бързо решаване на тези проблеми. Ако се интересувате от основните алгоритми, препоръчвам ви да научите за симплекс метода тук и метода на вътрешната точка тук .

Целочислени алгоритми за програмиране

Целочисленото програмиране е като линейното програмиране с допълнителен толеранс за някои или всички променливи да бъдат целочислени стойности. Макар че в началото това може да не изглежда като голямо подобрение, то ни позволява да решим много проблеми, които биха могли да останат нерешени само с помощта на линейно програмиране.

Един от тези проблеми е проблемът с раницата, при който ни се дава набор от елементи със зададени стойности и тегла и се иска да намерим комбинацията от елементите, която най-много се побира в нашата раница. Модел на линейно програмиране няма да може да реши това, защото няма начин да изразите идеята, че можете да поставите елемент в раницата си или не, но не можете да поставите част от елемент в раницата си - всяка променлива е променлива ! продължавай!

Примерен проблем с раница може да има следните параметри:

Обект	Стойност (единици от $ 10)	Размер (общи единици)
Камера	5	2
Тайнствена фигурка	7	4
Огромна бутилка ябълков сайдер	2	7
валдхорна	10	10

И моделът MIP ще изглежда така:

Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

Оптималното решение в този случай е a = 0, b = 1, c = 0, d = 1, като стойността на общия елемент е 17.

Проблемът, който ще решим днес, също ще изисква цял график, тъй като служител във фабрика може или не може да бъде насрочен за една смяна - за улеснение не можете да планирате служител за 2/3 от смяната в тази фабрика.

Използват се различни математически алгоритми, за да направят възможно целочисленото програмиране. Ако се интересувате от основните алгоритми, препоръчвам ви да проучите алгоритъма на равнината на изрязване и алгоритъма за разклоняване и свързване тук .

Примерен проблем: Програмиране

Описание на проблема

Днес ще изследваме проблема с наемането на персонал във фабрика. Като фабрично управление искаме да сведем до минимум разходите за труд, но искаме да осигурим достатъчно покритие за всяка смяна, за да отговорим на производственото търсене.

Да предположим, че имаме пет смени със следните изисквания към персонала:

Shift 1	Shift 2	Shift 3	Shift 4	Shift 5
1 човек	4 човека	3 човека	5 души	2 човека

И да предположим, че имаме следните работници:

Име	Наличност	Цена на смяна ($)
Мелисандре	1, 2, 5	двайсет
Трици	2. 3. 4. 5	петнадесет
Церсей	3. 4	35
Дейнерис	Четири пет	35
Вкл	2, 4, 5	10
Джон	1, 3, 5	25
Тирион	2, 4, 5	30
Джеймс	2, 3, 5	двайсет
Аря	1, 2, 4	двайсет

За да улесним проблема, нека за момента приемем, че наличността и цената са единствените проблеми.

Нашите инструменти

За днешния проблем ще използваме софтуер за отрязване и разклоняване с отворен код, наречен CBC. Ще взаимодействаме с този софтуер, използвайки PuLP, който е популярна библиотека за моделиране на оперативни изследвания за Python. Можете да намерите информация за него тук .

PuLP ни позволява да изграждаме модели MIP по много питоничен начин и се интегрира много добре със съществуващия код на Python. Това е много полезно, тъй като някои от най-популярните инструменти за манипулиране и анализ на данни са написани на Python, а повечето системи за изследване на бизнес операции изискват обширна обработка на данни преди и след оптимизация.

За да демонстрираме простотата и елегантността на PuLP, ето проблемът с раницата от преди и решен в PuLP:

import pulp as pl # declarar algunas variables # cada variable es una variable binaria que es 0 o 1 # 1 significa que el artículo irá a la mochila a = pl.LpVariable('a', 0, 1, pl.LpInteger) b = pl.LpVariable('b', 0, 1, pl.LpInteger) c = pl.LpVariable('c', 0, 1, pl.LpInteger) d = pl.LpVariable('d', 0, 1, pl.LpInteger) # define el problema prob = pl.LpProblem('knapsack', pl.LpMaximize) # función objetivo - maximizar el valor de los objetos en la mochila prob += 5 * a + 7 * b + 2 * c + 10 * d # restricción: el peso de los objetos no puede exceder 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 estado = prob.solve() # resuelve usando el solucionador predeterminado, que es cbc print(pl.LpStatus[status]) # imprime el estado legible por humanos # imprime los valores print('a', pl.value(a)) print('b', pl.value(b)) print('c', pl.value(c)) print('d', pl.value(d))

Изпълнете това и трябва да получите изхода:

Optimal a 0.0 b 1.0 c 0.0 d 1.0

Сега към нашия проблем с програмирането!

Кодиране на нашето решение

Кодирането на нашето решение е съвсем просто. Първо ще дефинираме нашите данни:

import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { 'Melisandre': { 'availability': [0, 1, 4], 'cost': 20 }, 'Bran': { 'availability': [1, 2, 3, 4], 'cost': 15 }, 'Cersei': { 'availability': [2, 3], 'cost': 35 }, 'Daenerys': { 'availability': [3, 4], 'cost': 35 }, 'Theon': { 'availability': [1, 3, 4], 'cost': 10 }, 'Jon': { 'availability': [0, 2, 4], 'cost': 25 }, 'Tyrion': { 'availability': [1, 3, 4], 'cost': 30 }, 'Jaime': { 'availability': [1, 2, 4], 'cost': 20 }, 'Arya': { 'availability': [0, 1, 3], 'cost': 20 } }

След това трябва да дефинираме модела:

# define el modelo: queremos minimizar el costo prob = pl.LpProblem('scheduling', pl.LpMinimize) # algunos modelos de variable cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable('%s_%s' % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # establece el objetivo para que sea la suma del costo prob += sum(cost) # establece los requerimientos de cambio for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

И сега ви молим да решите и отпечатате резултатите!

status = prob.solve() print('Result:', pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ 'shift': shift, 'workers': [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print('Shift:', result['shift'], 'workers:', ', '.join(result['workers']))

След като стартирате кода, трябва да видите следните изходи:

Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Увеличете леко затрудненията: Допълнителни ограничения

Въпреки че горният модел беше интересен и полезен, той не демонстрира напълно силата на смесеното цяло число програмиране. Също така бихме могли лесно да напишем цикъл for за намиране на работници x най-евтино за всяка смяна, където x е броят на работниците, необходими за смяна. За да демонстрира как MIP може да се използва за решаване на проблем, който би бил трудно решим императивно, нека разгледаме какво би се случило, ако добавим някои допълнителни ограничения.

Допълнителни ограничения

Да предположим, че поради новите трудови разпоредби работниците не могат да бъдат разпределени на повече от 2 смени. За да отчетем увеличаването на работата, ние сме привлекли помощта на Персоналната група на Dothraki, която ще осигури до 10 работници от Dothraki на смяна в размер на $ 40 на смяна.

Да предположим също така, че поради някои продължаващи междуличностни конфликти извън нашата фабрика, Серсей и Хайме не могат да работят на смени нито с Дейнерис, нито с Джон. Също така Хайме и Церсей не могат да работят на смени заедно. И накрая, Arya, който има особено сложни междуличностни отношения, не може да работи същата смяна с Jaime, Cersei или Melisandre.

Добавянето на тези две нови ограничения и ресурси по никакъв начин не прави проблема невъзможен за решаване чрез императивни средства, но прави решението много по-трудно, тъй като ще трябва да се вземат предвид алтернативните разходи за насрочване на работник за определена смяна.

Решение

Със смесено цяло число програмиране обаче е много по-лесно. Просто трябва да променим кода си така:

Определете списъка на забраните и някои ограничения:

ban_list = { ('Daenerys', 'Jaime'), ('Daenerys', 'Cersei'), ('Jon', 'Jaime'), ('Jon', 'Cersei'), ('Arya', 'Jaime'), ('Arya', 'Cersei'), ('Arya', 'Melisandre'), ('Jaime', 'Cersei') } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Попълнете някои променливи, за да приложите ограниченията за забрана и максимална промяна:

for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable('%s_%d' % (worker, shift), 0, 1, pl.LpInteger) # almacena algunos datos variables para que podamos implementar la restricción de prohibición var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # almacena vars por variable para que podamos implementar la restricción de cambio máximo vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Добавете променливите на Dothraki:

for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Ще ни е необходим и малко модифициран цикъл, за да изчислим изискванията за промяна и забрана:

# establece los requerimientos de cambio for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # establece los requerimientos de prohibición for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # establece los estándares de trabajo: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

И накрая, за да отпечатате резултатите:

status = prob.solve() print('Result:', pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ 'shift': shift, 'workers': [var[1][0] for var in vars if var[0].varValue == 1], 'dothrakis': dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print('Shift:', result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

И трябва да сме готови. Изпълнете кода и трябва да видите резултата, както следва:

Resultado: Óptimo Shift: 0 trabajadores: Arya dothrakis contratados: 0 Shift: 1 trabajador: Melisandre, Theon, Tyrion, Jaime dothrakis contratados: 0 Shift: 2 trabajadores: Bran, Jon dothrakis contratados: 1 Shift: 3 trabajadores: Bran, Daenerys, Theon, Tyrion, Arya dothrakis contratados: 0 Shift: 4 trabajadores: Melisandre, Jaime dothrakis contratados: 0

И voila, резултат, който зачита списъка на забранените работници, следва трудовите разпоредби и използва разумно работниците от Dothraki.

заключение

Днес изследваме използването на смесено цяло число програмиране за вземане на по-добри решения. Ние обсъждаме основните алгоритми и техники, използвани в изследванията на операциите, както и разглеждаме примерен проблем, който е представителен за това как се използва смесено цяло число програмиране в реалния свят.

Надявам се тази статия да ви вдъхнови да научите повече за оперативните изследвания и да ви накара да размислите как тази технология може да бъде приложена към вашите проекти. Наистина сме виждали само върха на айсберга, когато става въпрос за вълнуващия свят на алгоритмите за оптимизация и изследванията на операциите.

Можете да намерите целия код, свързан с тази статия на GitHub . Ако искате да обсъдите повече, споделете вашите коментари по-долу!