Истраживање операција, наука о коришћењу рачунара за доношење оптималних одлука, користило се и примењивало у многим областима софтвера. Дајући неколико примера, логистичке компаније га користе за одређивање оптималног пута до тачке А до тачке Б, електроенергетске компаније га користе за одређивање распореда производње електричне енергије, а производне компаније га користе за проналажење оптималних образаца запошљавања за своје фабрике.
Данас ћемо истражити моћ оперативног истраживања пролазећи кроз хипотетски проблем. Конкретно, користићемо комбиновано целобројно програмирање (МИП) да бисмо одредили оптималан образац запошљавања за хипотетичку фабрику.
Алгоритми оперативног истраживања
Пре него што заронимо у наш пример проблема, корисно је проћи кроз неке основне концепте у истраживању операција и разумети неке алате које ћемо данас користити.
Алгоритми линеарног програмирања
Линеарно програмирање је техника оперативног истраживања која се користи за одређивање најбољег исхода у математичком моделу где су циљ и ограничења изражени као систем линеарних једначина. Пример модела линеарног програмирања може изгледати овако:
Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2) У нашем врло једноставном примеру можемо видети да је оптимални исход 5, са а = 2 и б = 3. Иако је ово прилично тривијалан пример, вероватно можете замислити модел линеарног програмирања који користи хиљаде променљивих и стотине ограничења .
Добар пример може бити проблем са инвестиционим портфељем, где ћете можда добити нешто попут доле наведеног у псеудо-коду:
Maximize Subject to: Etc. ... Што би било прилично сложено и тешко решити ручно или методом покушаја и грешака. Софтвер за оперативно истраживање користиће неколико алгоритама за брзо решавање ових проблема. Ако сте заинтересовани за основне алгоритме, саветујем вам да се упознате са методом симплекса овде и метода унутрашњих тачака овде .
Целобројни алгоритми програмирања
Целобројно програмирање је попут линеарног програмирања са додатним допуштењем да неке или све променљиве буду целобројне вредности. Иако се ово у почетку можда не чини великим побољшањем, омогућава нам решавање многих проблема који су могли остати нерешени само помоћу линеарног програмирања.
Један од таквих проблема је проблем са напртњачом, где нам се даје скуп предмета са додељеним вредностима и тежинама и од нас се тражи да пронађемо комбинацију предмета са највећом вредношћу коју можемо уклопити у свој ранац. Модел линеарног програмирања то неће моћи да реши јер не постоји начин да изразите идеју да можете ставити предмет у свој ранац или не, али не можете ставити део предмета у свој ранац - свака променљива је континуирана променљива!
Пример проблема са напртњачом може имати следеће параметре:
| Предмет | Вредност (јединице од 10 УСД) | Величина (генеричке јединице) |
|---|---|---|
| Камера | 5 | 2 |
| Тајанствена фигурица | 7 | 4 |
| Огромна бочица јабуковаче | 2 | 7 |
| Француски рог | 10 | 10 |
А МИП модел ће изгледати овако:
Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint) Оптимално решење, у овом случају, је а = 0, б = 1, ц = 0, д = 1, при чему је вредност укупне ставке 17.
колико има ерц20 жетона
Проблем који ћемо данас решити такође ће захтевати целобројно програмирање, јер запослени у фабрици може или да се распореди за смену или не - ради једноставности, не можете да закажете запосленог за 2/3 смене у овој фабрици.
Да би се омогућило целобројно програмирање, користи се неколико математичких алгоритама. Ако сте заинтересовани за основне алгоритме, препоручујем проучавање алгоритма резних равни и алгоритма гранања и веза овде .
Пример проблема: заказивање
Опис проблема
Данас ћемо истражити проблем запошљавања у фабрици. Као руководство фабрике, желећемо да смањимо трошкове радне снаге, али желимо да обезбедимо довољну покривеност за сваку смену како бисмо задовољили потражњу производње.
Претпоставимо да имамо пет смена са следећим кадровским захтевима:
| Смена 1 | Смена 2 | Смена 3 | Смена 4 | Смена 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 | двадесет |
Да би проблем био једноставан, претпоставимо тренутно да су доступност и цена једина брига.
Наши алати
За данашњи проблем користићемо део софтвера отвореног кода за гране и резања под називом ЦБЦ. Повезаћемо се са овим софтвером користећи ПуЛП, који је популарна библиотека за моделирање оперативних истраживања за Питхон. Можете пронаћи информације о томе овде .
ПуЛП нам омогућава да МИП моделе направимо на врло питонски начин и лепо се интегрише са постојећим Питхон кодом. Ово је веома корисно јер су неки од најпопуларнијих алата за манипулацију и анализу података написани на Питхону, а већина комерцијалних система за истраживање операција захтева опсежну обраду података пре и после оптимизације.
Да бисмо демонстрирали једноставност и елеганцију ПуЛП-а, ево проблема са напртњачом из ранијег и решеног у ПуЛП-у:
import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack 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 the problem prob = pl.LpProblem('knapsack', pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values 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 the model: we want to minimize the cost prob = pl.LpProblem('scheduling', pl.LpMinimize) # some model variables 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']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements 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 је број радника потребних за смену. Да бисмо демонстрирали како се МИП може користити за решавање проблема који би императивно било решити, испитајмо шта би се догодило ако додамо неколико додатних ограничења.
Додатна ограничења
Претпоставимо да због нових прописа о раду ниједан радник не може бити распоређен у више од 2 смене. Да бисмо објаснили повећан рад, запослили смо помоћ Дотхраки Стаффинг Гроуп, која ће снабдевати до 10 Дотхраки радника за сваку смену по цени од 40 УСД по смени.
Поред тога, претпоставимо да, због неких сталних међуљудских сукоба изван наше фабрике, Церсеи и Јаиме нису у стању да раде у било којој смени ни заједно са Даенерис или Јон. Поред тога, Јаиме и Церсеи нису у могућности да раде заједно у било којој смени. Коначно, Ариа, која има посебно сложене међуљудске односе, није у могућности да ради у истој смени са Јаиме, Церсеи или Мелисандре.
Додавање ова два нова ограничења и ресурса ни на који начин не чини проблем нерешивим преко императивних средстава, али много отежава решење, јер ће се морати узети у обзир опортунитетни трошкови распоређивања радника у одређену смену.
Решење
Међутим, са програмирањем мешовитих целобројних бројева је много лакше. Једноставно морамо да изменимо наш код на следећи начин:
Дефинишите листу забрана и нека ограничења:
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) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost']) Додајте Дотхраки променљиве:
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 Такође ће нам требати мало измењена петља за рачунарске промене и забране забране:
# set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements 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 # set the labor standards: 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'])) И требали бисмо бити добри. Покрените код и требали бисте видети излаз као испод:
Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0 И ту имамо, резултат који поштује списак забрањених радника, следи радне прописе и разборито користи раднике Дотхракија.
Закључак
Данас смо истраживали коришћење мешовитих целобројних програма за доношење бољих одлука. Разговарали смо о основним алгоритмима и техникама који се користе у оперативним истраживањима и размотрили пример проблема који је репрезентативан за то како се мешовито целобројно програмирање користи у стварном свету.
Надам се да вас је овај чланак инспирисао да сазнате више о оперативним истраживањима и натерао вас да размислите о томе како се ова технологија може применити на ваше пројекте. Врх леденог брега видели смо заиста само када је реч о узбудљивом свету алгоритама за оптимизацију и истраживању операција.
Можете пронаћи сав код везан за овај чланак на ГитХуб-у . Ако желите да разговарате више, поделите своје коментаре у наставку!
шта значи ртл сдр
Разумевање основа
Шта је линеарно програмирање?
Линеарно програмирање је техника оперативног истраживања која се користи за одређивање најбољег исхода у математичком моделу где су циљ и ограничења изражени као систем линеарних једначина.
Шта је целобројно програмирање?
Целобројно програмирање је попут линеарног програмирања са додатним допуштењем да неке или све променљиве буду целобројне вредности.
