Programowanie na liczbach mieszanych: przewodnik po obliczeniowym podejmowaniu decyzji

Badania operacyjne, nauka o wykorzystywaniu komputerów do podejmowania optymalnych decyzji, są wykorzystywane i stosowane w wielu obszarach oprogramowania. Aby podać kilka przykładów, firmy logistyczne używają go do określenia optymalnej trasy dotarcia z punktu A do punktu B, przedsiębiorstwa energetyczne używają go do określenia harmonogramów produkcji energii, a firmy produkcyjne używają go do znalezienia optymalnych wzorców kadrowych dla swoich fabryk.

Dzisiaj zbadamy moc badań operacyjnych, przechodząc przez hipotetyczny problem. W szczególności użyjemy programowania mieszanych liczb całkowitych (MIP), aby określić optymalny wzorzec obsady stanowisk dla hipotetycznej fabryki.

Algorytmy badań operacyjnych

Zanim zagłębimy się w nasz przykładowy problem, pomocne jest omówienie podstawowych pojęć w badaniach operacyjnych i zrozumienie narzędzi, których będziemy dzisiaj używać.

Algorytmy programowania liniowego

Programowanie liniowe to technika badań operacyjnych stosowana do określenia najlepszego wyniku w modelu matematycznym, w którym cel i ograniczenia są wyrażone jako układ równań liniowych. Przykładowy liniowy model programowania może wyglądać tak:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

W naszym bardzo prostym przykładzie widzimy, że optymalnym wynikiem jest 5, przy a = 2 i b = 3. Chociaż jest to dość trywialny przykład, prawdopodobnie możesz sobie wyobrazić model programowania liniowego, który wykorzystuje tysiące zmiennych i setki ograniczeń .

Dobrym przykładem może być problem z portfelem inwestycyjnym, w którym możesz otrzymać coś takiego jak poniżej, w pseudokodzie:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

Który byłby dość złożony i trudny do rozwiązania ręcznie lub metodą prób i błędów. Oprogramowanie do badań operacyjnych będzie korzystać z kilku algorytmów, aby szybko rozwiązać te problemy. Jeśli interesują Cię podstawowe algorytmy, polecam zapoznanie się z metodą simplex tutaj i metodą punktu wewnętrznego tutaj.

Algorytmy programowania liczb całkowitych

Programowanie całkowitoliczbowe jest jak programowanie liniowe z dodatkowym dopuszczeniem, aby niektóre lub wszystkie zmienne były wartościami całkowitymi. Chociaż na początku może to nie wydawać się dużym ulepszeniem, pozwala nam rozwiązać wiele problemów, które mogły pozostać nierozwiązane za pomocą samego programowania liniowego.

Jednym z takich problemów jest problem z plecakiem, w którym otrzymujemy zestaw przedmiotów z przypisanymi wartościami i wagami i jesteśmy proszeni o znalezienie kombinacji przedmiotów o najwyższej wartości, jaką możemy zmieścić w naszym plecaku. Model programowania liniowego nie będzie w stanie rozwiązać tego problemu, ponieważ nie ma sposobu na wyrażenie idei, że można włożyć przedmiot do plecaka lub nie, ale nie można włożyć części przedmiotu do plecaka — każda zmienna jest ciągła zmienny!

Przykładowy problem z plecakiem może mieć następujące parametry:

A model MIP będzie wyglądał tak:

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

Optymalnym rozwiązaniem w tym przypadku jest a=0, b=1, c=0, d=1, przy wartości całkowitej pozycji wynoszącej 17.

Problem, który dzisiaj rozwiążemy, będzie również wymagał programowania liczb całkowitych, ponieważ pracownik w fabryce może być zaplanowany na zmianę lub nie — dla uproszczenia nie można zaplanować pracownika na 2/3 zmiany w tej fabryce.

Aby umożliwić programowanie liczb całkowitych, stosuje się kilka algorytmów matematycznych. Jeśli interesują Cię podstawowe algorytmy, polecam przestudiować tutaj algorytm płaszczyzn tnących i algorytm rozgałęzienia i ograniczenia.

Przykładowy problem: planowanie

opis problemu

Dzisiaj zajmiemy się problemem obsady kadrowej fabryki. Jako zarząd fabryki będziemy chcieli minimalizować koszty pracy, ale chcemy zapewnić wystarczające pokrycie na każdą zmianę, aby zaspokoić zapotrzebowanie produkcyjne.

Załóżmy, że mamy pięć zmian z następującymi wymaganiami kadrowymi:

Załóżmy, że mamy następujących pracowników:

Aby problem był prosty, załóżmy na chwilę, że jedynym problemem jest dostępność i koszt.

Nasze narzędzia

W dzisiejszym problemie użyjemy oprogramowania typu branch-and-cut o otwartym kodzie źródłowym o nazwie CBC. Będziemy łączyć się z tym oprogramowaniem za pomocą PuLP, która jest popularną biblioteką modelowania badań operacyjnych dla Pythona. Informacje na ten temat znajdziesz tutaj.

PuLP pozwala nam konstruować modele MIP w bardzo Pythonowy sposób i ładnie integruje się z istniejącym kodem Pythona. Jest to bardzo przydatne, ponieważ niektóre z najpopularniejszych narzędzi do manipulacji i analizy danych są napisane w Pythonie, a większość komercyjnych systemów do badań operacyjnych wymaga intensywnego przetwarzania danych przed i po optymalizacji.

Aby zademonstrować prostotę i elegancję PuLP, oto wcześniejszy problem plecakowy, który został rozwiązany w PuLP:

 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))

Uruchom to, a powinieneś otrzymać dane wyjściowe:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Teraz przejdźmy do naszego problemu z planowaniem!

Kodowanie naszego rozwiązania

Kodowanie naszego rozwiązania jest dość proste. Najpierw będziemy chcieli zdefiniować nasze dane:

 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 } }

Następnie będziemy chcieli zdefiniować model:

 # 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

A teraz po prostu prosimy go o rozwiązanie i wydrukowanie wyników!

 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']))

Po uruchomieniu kodu powinieneś zobaczyć następujące dane wyjściowe:

 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

Podkręć nieco poziom trudności: dodatkowe ograniczenia

Mimo że poprzedni model był interesujący i użyteczny, nie pokazuje on w pełni możliwości programowania mieszanych liczb całkowitych. Moglibyśmy również łatwo napisać pętlę for , aby znaleźć najtańszych x pracowników na każdą zmianę, gdzie x to liczba pracowników potrzebnych na zmianę. Aby zademonstrować, jak MIP można wykorzystać do rozwiązania problemu, który byłby trudny do rozwiązania w sposób imperatywny, przeanalizujmy, co by się stało, gdybyśmy dodali kilka dodatkowych ograniczeń.

Dodatkowe ograniczenia

Załóżmy, że ze względu na nowe przepisy prawa pracy żaden pracownik nie może być przydzielony na więcej niż 2 zmiany. Aby uwzględnić wzmożoną pracę, zrekrutowaliśmy pomoc Dothraki Staffing Group, która dostarczy do 10 pracowników Dothraki na każdą zmianę po stawce 40 USD na zmianę.

Załóżmy ponadto, że z powodu pewnych konfliktów międzyludzkich trwających poza naszą fabryką Cersei i Jaime nie są w stanie pracować na żadnych zmianach u boku Daenerys lub Jona. Ponadto Jaime i Cersei nie są w stanie pracować razem na żadnych zmianach. Wreszcie Arya, która ma szczególnie złożone relacje międzyludzkie, nie jest w stanie pracować na tej samej zmianie z Jaime, Cersei czy Melisandre.

Dodanie tych dwóch nowych ograniczeń i zasobów w żadnym wypadku nie czyni problemu niemożliwym do rozwiązania za pomocą imperatywnych środków, ale znacznie utrudnia rozwiązanie, ponieważ trzeba będzie uwzględnić koszty alternatywne związane z zaplanowaniem pracownika na określoną zmianę.

Rozwiązanie

Jednak przy programowaniu na liczbach mieszanych jest to znacznie prostsze. Po prostu musimy zmienić nasz kod w następujący sposób:

Zdefiniuj listę banów i niektóre ograniczenia:

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

Wypełnij zmienne w celu wdrożenia ograniczeń dotyczących zakazu i maksymalnej zmiany:

 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'])

Dodaj zmienne 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

Będziemy również potrzebować nieco zmodyfikowanej pętli do obliczania wymagań dotyczących zmian i banów:

 # 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

I na koniec, aby wydrukować wyniki:

 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']))

I powinniśmy już iść. Uruchom kod i powinieneś zobaczyć dane wyjściowe jak poniżej:

 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

I oto mamy to, wynik, który szanuje listę zakazanych pracowników, przestrzega przepisów pracy i rozsądnie wykorzystuje pracowników Dothraków.

Wniosek

Dzisiaj przyjrzeliśmy się użyciu programowania mieszanych liczb całkowitych, aby podejmować lepsze decyzje. Omówiliśmy podstawowe algorytmy i techniki stosowane w badaniach operacyjnych i przyjrzeliśmy się przykładowemu problemowi, który jest reprezentatywny dla tego, jak programowanie na liczbach mieszanych jest używane w świecie rzeczywistym.

Mam nadzieję, że ten artykuł zainspirował Cię do głębszego zapoznania się z badaniami operacyjnymi i zastanowił się, jak tę technologię można zastosować w Twoich projektach. Tak naprawdę widzieliśmy tylko wierzchołek góry lodowej, jeśli chodzi o ekscytujący świat algorytmów optymalizacji i badań operacyjnych.

Cały kod związany z tym artykułem można znaleźć w serwisie GitHub. Jeśli chcesz omówić więcej, podziel się swoimi komentarzami poniżej!