Programare cu numere întregi mixte: un ghid pentru luarea deciziilor computaționale

Cercetarea operațională, știința utilizării computerelor pentru a lua decizii optime, a fost folosită și aplicată în multe domenii ale software-ului. Pentru a da câteva exemple, companiile de logistică îl folosesc pentru a determina ruta optimă pentru a ajunge de la punctul A la punctul B, companiile energetice îl folosesc pentru a determina programele de producție a energiei, iar companiile de producție îl folosesc pentru a găsi modele optime de personal pentru fabricile lor.

Astăzi, vom explora puterea cercetării operaționale trecând printr-o problemă ipotetică. Mai exact, vom folosi programarea cu numere întregi mixte (MIP) pentru a determina modelul optim de personal pentru o fabrică ipotetică.

Algoritmi de cercetare operațională

Înainte de a aborda problema noastră exemplu, este util să trecem peste câteva concepte de bază în cercetarea operațională și să înțelegem câteva dintre instrumentele pe care le vom folosi astăzi.

Algoritmi de programare liniară

Programarea liniară este o tehnică de cercetare operațională utilizată pentru a determina cel mai bun rezultat într-un model matematic în care obiectivul și constrângerile sunt exprimate ca un sistem de ecuații liniare. Un exemplu de model de programare liniară ar putea arăta astfel:

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

În exemplul nostru foarte simplu, putem vedea că rezultatul optim este 5, cu a = 2 și b = 3. Deși acesta este un exemplu destul de trivial, probabil vă puteți imagina un model de programare liniară care utilizează mii de variabile și sute de constrângeri. .

Un exemplu bun ar putea fi o problemă a portofoliului de investiții, în care s-ar putea să ajungeți cu ceva ca cel de mai jos, în pseudo-cod:

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

Ceea ce ar fi destul de complex și dificil de rezolvat manual sau prin încercare și eroare. Software-ul de cercetare operațională va folosi mai mulți algoritmi pentru a rezolva rapid aceste probleme. Dacă sunteți interesat de algoritmii de bază, vă recomand să aflați despre metoda simplex aici și despre metoda punctului interior aici.

Algoritmi de programare cu numere întregi

Programarea cu numere întregi este ca programarea liniară, cu o alocație suplimentară pentru ca unele sau toate variabilele să fie valori întregi. Deși acest lucru poate să nu pară o îmbunătățire mare la început, ne permite să rezolvăm multe probleme care ar fi putut rămâne nerezolvate folosind doar programarea liniară.

O astfel de problemă este problema rucsacului, în care ni se oferă un set de articole cu valori și greutăți atribuite și ni se cere să găsim cea mai mare combinație de articole pe care o putem încăpea în rucsac. Un model de programare liniară nu va putea rezolva acest lucru, deoarece nu există nicio modalitate de a exprima ideea că fie puteți pune un articol în rucsac sau nu, dar nu puteți pune o parte dintr-un articol în rucsac - fiecare variabilă este continuă. variabil!

Un exemplu de problemă de rucsac poate avea următorii parametri:

Și modelul MIP va arăta astfel:

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

Soluția optimă, în acest caz, este a=0, b=1, c=0, d=1, valoarea articolului total fiind 17.

Problema pe care o vom rezolva astăzi va necesita, de asemenea, programare cu numere întregi, deoarece un angajat dintr-o fabrică poate fi fie programat pentru o tură, fie nu - de dragul simplității, nu puteți programa un angajat pentru 2/3 din tură la această fabrică.

Pentru a face posibilă programarea cu numere întregi, sunt utilizați mai mulți algoritmi matematici. Dacă sunteți interesat de algoritmii de bază, vă recomand să studiați algoritmul cu planuri de tăiere și algoritmul de ramificare și legătură aici.

Exemplu de problemă: programare

Descrierea problemei

Astăzi, vom explora problema angajării personalului unei fabrici. În calitate de conducere a fabricii, vom dori să minimizăm costurile cu forța de muncă, dar dorim să asigurăm o acoperire suficientă pentru fiecare schimb pentru a satisface cererea de producție.

Să presupunem că avem cinci schimburi cu următoarele cerințe de personal:

Și, să presupunem că avem următorii lucrători:

Pentru a menține problema simplă, să presupunem pentru moment că disponibilitatea și costul sunt singurele preocupări.

Instrumentele noastre

Pentru problema de astăzi, vom folosi o bucată de software open source de ramificare și tăiere numit CBC. Vom interfața cu acest software folosind PuLP, care este o bibliotecă populară de modelare a cercetării operaționale pentru Python. Puteți găsi informații despre el aici.

PuLP ne permite să construim modele MIP într-un mod foarte Python și se integrează frumos cu codul Python existent. Acest lucru este foarte util, deoarece unele dintre cele mai populare instrumente de manipulare și analiză a datelor sunt scrise în Python, iar majoritatea sistemelor comerciale de cercetare operațională necesită o prelucrare extinsă a datelor înainte și după optimizare.

Pentru a demonstra simplitatea și eleganța PuLP, iată problema rucsacului de mai devreme și rezolvată în 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))

Rulați acest lucru și ar trebui să obțineți rezultatul:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Acum trecem la problema noastră de programare!

Codificarea soluției noastre

Codarea soluției noastre este destul de simplă. În primul rând, vom dori să ne definim datele:

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

În continuare, vom dori să definim modelul:

 # 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

Și acum îi cerem doar să rezolve și să imprime rezultatele!

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

Odată ce rulați codul, ar trebui să vedeți următoarele rezultate:

 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

Măriți puțin dificultatea: constrângeri suplimentare

Chiar dacă modelul anterior a fost interesant și util, nu demonstrează pe deplin puterea programării cu numere întregi mixte. De asemenea, am putea scrie cu ușurință o buclă for pentru a găsi cei mai ieftini x lucrători pentru fiecare schimb, unde x este numărul de lucrători necesari pentru o tură. Pentru a demonstra cum MIP poate fi folosit pentru a rezolva o problemă care ar fi dificil de rezolvat într-un mod imperativ, să examinăm ce s-ar întâmpla dacă adăugăm câteva constrângeri suplimentare.

Constrângeri suplimentare

Să presupunem că, din cauza noilor reglementări de muncă, niciun lucrător nu poate fi repartizat în mai mult de 2 schimburi. Pentru a ține seama de creșterea muncii, am recrutat ajutorul Dothraki Staffing Group, care va furniza până la 10 lucrători Dothraki pentru fiecare tură, la o rată de 40 USD pe tură.

În plus, să presupunem că, din cauza unor conflicte interpersonale în desfășurare în afara fabricii noastre, Cersei și Jaime nu pot lucra în nicio tură alături de Daenerys sau Jon. În plus, Jaime și Cersei nu pot lucra împreună. În cele din urmă, Arya, care are relații interpersonale deosebit de complexe, nu poate lucra în aceeași tură cu Jaime, Cersei sau Melisandre.

Adăugarea acestor două noi constrângeri și resurse în niciun caz nu face problema de nerezolvată prin mijloace imperative, dar face soluția mult mai dificilă, deoarece va trebui să luați în considerare costurile de oportunitate ale programării unui lucrător la o anumită tură.

Soluţie

Cu programarea cu numere întregi mixte, totuși, este mult mai ușor. Trebuie doar să ne modificăm codul astfel:

Definiți lista de interdicții și câteva constrângeri:

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

Populați variabile pentru implementarea constrângerilor de interdicție și de schimbare maximă:

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

Adăugați variabilele 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

De asemenea, vom avea nevoie de o buclă ușor modificată pentru calcularea cerințelor privind schimbarea și interzicerea:

 # 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 în sfârșit, pentru a tipări rezultatele:

 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 ar trebui să fim gata de plecare. Rulați codul și ar trebui să vedeți rezultatul ca mai jos:

 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 iată-l, un rezultat care respectă lista lucrătorilor interziși, respectă reglementările muncii și îi folosește judicios pe lucrătorii Dothraki.

Concluzie

Astăzi, am explorat utilizarea programării cu numere întregi mixte pentru a lua decizii mai bune. Am discutat despre algoritmii și tehnicile de bază utilizate în cercetarea operațională și am analizat un exemplu de problemă care este reprezentativă pentru modul în care este utilizată programarea cu numere întregi mixte în lumea reală.

Sper că acest articol te-a inspirat să afli mai multe despre cercetarea operațională și te-a făcut să te gândești la modul în care această tehnologie poate fi aplicată proiectelor tale. Am văzut doar vârful aisbergului când vine vorba de lumea captivantă a algoritmilor de optimizare și a cercetării operaționale.

Puteți găsi tot codul legat de acest articol pe GitHub. Dacă doriți să discutați mai multe, împărtășiți comentariile voastre mai jos!