Operointitutkimusta, tieteitä tietokoneiden käytöstä optimaalisten päätösten tekemiseksi, on käytetty ja sovellettu monilla ohjelmistoalueilla. Joitakin esimerkkejä, logistiikkayritykset käyttävät sitä määrittäessään optimaalisen reitin päästä pisteestä A pisteeseen B, sähköyhtiöt käyttävät sitä energiantuotannon aikataulujen määrittelemiseen ja valmistusyritykset löytävät siitä optimaalisen henkilöstömallin.

Tänään tutkimme operaatiotutkimuksen voimaa käymällä läpi hypoteettisen ongelman. Erityisesti käytämme sekoitettua kokonaislukuohjelmointia ( MIP ) optimaalisen henkilöstömallin määrittämiseksi hypoteettiselle tehtaalle.

Operaatiotutkimusalgoritmit

Ennen kuin syvennämme esimerkkiongelmaamme, on hyödyllistä käydä läpi joitain operaatiotutkimuksen perusteita ja ymmärtää joitain työkaluja, joita käytämme tänään.

Lineaariset ohjelmointialgoritmit

Lineaarinen ohjelmointi on operaatiotutkimustekniikka, jolla määritetään paras tulos matemaattisessa mallissa, jossa tavoite ja rajoitukset ilmaistaan ​​lineaaristen yhtälöiden järjestelmänä. Esimerkki lineaarisesta ohjelmointimallista saattaa näyttää tältä:

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

Yksinkertaisessa esimerkissämme voimme nähdä, että optimaalinen tulos on 5, a = 2 ja b = 3. Vaikka tämä on melko triviaali esimerkki, voit todennäköisesti kuvitella lineaarisen ohjelmointimallin, joka käyttää tuhansia muuttujia ja satoja rajoituksia. .

Hyvä esimerkki voi olla sijoitusportfolio-ongelma, jossa saatat päätyä jotain seuraavaan, pseudokoodina:

Maximize Subject to: Etc. ...

Mikä olisi melko monimutkaista ja vaikea ratkaista käsin tai erehdyksellä. Operaatiotutkimusohjelmisto käyttää erilaisia ​​algoritmeja näiden ongelmien ratkaisemiseksi nopeasti. Jos olet kiinnostunut taustalla olevista algoritmeista, suosittelen oppimaan simplex-menetelmästä tässä ja sisäpistemenetelmä tässä .

Kokonaislukuohjelmointialgoritmit

Kokonaislukuohjelmointi on kuin lineaarinen ohjelmointi, jossa lisätoleranssi joillekin tai kaikille muuttujille on kokonaislukuarvoja. Vaikka tämä ei ehkä vaikuta aluksi suurelta parannukselta, se antaa meille mahdollisuuden ratkaista monia ongelmia, jotka olisi voitu jättää ratkaisematta pelkästään lineaarisen ohjelmoinnin avulla.

Yksi näistä ongelmista on reppuongelma, jossa meille annetaan joukko esineitä, joille on annettu määritetyt arvot ja painot, ja meitä pyydetään löytämään yhdistelmä esineitä, jotka sopivat parhaiten reppuun. Lineaarinen ohjelmointimalli ei pysty ratkaisemaan tätä, koska ei ole mitään tapaa ilmaista ajatusta siitä, että voit laittaa kohteen reppuun tai ei, mutta et voi laittaa osan esineestä reppuusi - jokainen muuttuja on muuttuja jatka!

Esimerkkireppuongelmalla voi olla seuraavat parametrit:

Esine	Arvo (10 dollarin yksikköä)	Koko (yleiset yksiköt)
Kamera	5	2
Salaperäinen hahmo	7	4
Valtava pullo omenasiideriä	2	7
käyrätorvi	10	10

Ja malli MIP se näyttää tältä:

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

Optimaalinen ratkaisu on tässä tapauksessa a = 0, b = 1, c = 0, d = 1, jolloin kohteen kokonaisarvo on 17.

Tänään ratkaistavamme ongelma vaatii myös koko aikataulun, koska työntekijä tehtaalle voidaan ajoittaa tai olla määräämättä yhdeksi vuoroksi - yksinkertaisuuden vuoksi et voi suunnitella työntekijää 2/3 vuorosta tässä tehtaassa.

Eri matemaattisia algoritmeja käytetään tekemään kokonaislukuohjelmointi. Jos olet kiinnostunut taustalla olevista algoritmeista, suosittelen, että tutkit leikkaustason algoritmin sekä haarautuvan ja linkittävän algoritmin tässä .

Esimerkkiongelma: Ohjelmointi

Ongelman kuvaus

Tänään tutkimme tehtaan henkilöstöongelmaa. Tehtaan johtoina haluamme minimoida työvoimakustannukset, mutta haluamme varmistaa jokaisen vuoron riittävän kattavuuden tuotannon kysynnän tyydyttämiseksi.

Oletetaan, että meillä on viisi vuoroa seuraavilla henkilöstövaatimuksilla:

Vaihto 1	Vaihto 2	Vaihto 3	Vaihto 4	Vaihto 5
1 henkilö	4 henkilöä	3 henkilöä	5 henkilöä	2 ihmistä

Oletetaan, että meillä on seuraavat työntekijät:

Nimi	Saatavuus	Vuorokohtainen hinta ($)
Melisandre	1, 2, 5	kaksikymmentä
Leseet	2. 3. 4. 5	viisitoista
Cersei	3. 4	35
Daenerys	Neljä viisi	35
Theon	2, 4, 5	10
Jon	1, 3, 5	25
Tyrion	2, 4, 5	30
James	2, 3, 5	kaksikymmentä
Arya	1, 2, 4	kaksikymmentä

Oletetaan, että ongelma on yksinkertainen, mutta toistaiseksi vain saatavuus ja hinta ovat huolenaiheita.

Työkalumme

Tämän päivän ongelmaan käytämme avoimen lähdekoodin leikkaus- ja haaroitusohjelmistoa nimeltä CBC. Olemme vuorovaikutuksessa tämän ohjelmiston kanssa käyttämällä PuLP: tä, joka on suosittu operaatiotutkimuksen mallintamiskirjasto Pythonille. Löydät tietoa siitä tässä .

PuLP antaa meille mahdollisuuden rakentaa malleja MIP hyvin Pythonin tavalla ja integroituu hyvin olemassa olevaan Python-koodiin. Tämä on erittäin hyödyllistä, koska jotkut suosituimmista datankäsittely- ja analyysityökaluista on kirjoitettu Pythonissa, ja useimmat liiketoiminnan tutkimusjärjestelmät edellyttävät laajaa tietojenkäsittelyä ennen optimointia ja sen jälkeen.

PuLP: n yksinkertaisuuden ja tyylikkyyden osoittamiseksi tässä on reppuongelma, joka on ratkaistu PuLP: ssä:

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

Suorita tämä, ja sinun pitäisi saada tulos:

Optimal a 0.0 b 1.0 c 0.0 d 1.0

Nyt ohjelmointiongelmamme!

Ratkaisumme koodaus

Ratkaisumme koodaus on melko yksinkertainen. Ensin määritämme tietomme:

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

Seuraavaksi meidän on määriteltävä malli:

# 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

Ja nyt pyydämme sinua ratkaisemaan ja tulostamaan tulokset!

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

Kun olet suorittanut koodin, sinun pitäisi nähdä seuraavat lähdöt:

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

Lisää vaikeuksia hieman: Lisärajoitukset

Vaikka yllä oleva malli oli mielenkiintoinen ja hyödyllinen, se ei osoita täysin kokonaislukuohjelmoinnin tehoa. Voisimme myös helposti kirjoittaa silmukan for löytää työntekijöitä x halvin jokaiselle vuorolle, missä x on vuorossa tarvittavien työntekijöiden määrä. Osoittaa miten MIP voidaan käyttää ongelman ratkaisemiseen, jota olisi vaikea ratkaista pakollisesti, tutkitaan, mitä tapahtuisi, jos lisäämme joitain lisärajoituksia.

Lisärajoitukset

Oletetaan, että uusien työsäännösten vuoksi työntekijöitä ei voida siirtää yli kahteen vuoroon. Lisääntyneen työn huomioon ottamiseksi olemme pyytäneet Dothrakin henkilöstöryhmän apua, joka tarjoaa jopa 10 Dothrakin työntekijää kustakin vuorosta 40 dollaria vuoroa kohden.

Oletetaan myös, että tehtaamme ulkopuolella olevien jatkuvien ihmissuhdekonfliktien vuoksi Cersei ja Jaime eivät pysty työskentelemään vuoroissa joko Daenerysin tai Jonin kanssa. Jaime ja Cersei eivät myöskään voi tehdä mitään vuoroja yhdessä. Lopuksi, Arya, jolla on erityisen monimutkaiset ihmissuhteet, ei voi työskennellä samassa vuorossa Jaimen, Cersei tai Melisandren kanssa.

Näiden kahden uuden rajoitteen ja resurssien lisääminen ei millään tavalla tee ongelmaa mahdottomaksi ratkaista pakottavin keinoin, mutta tekee ratkaisun paljon vaikeammaksi, koska on otettava huomioon työntekijän aikataulutuksen vaihtoehtoiset kustannukset tietylle työlle.

Ratkaisu

Sekoitettu kokonaislukuohjelmointi on kuitenkin paljon helpompaa. Meidän on yksinkertaisesti muutettava koodia näin:

Määritä kieltojen ja rajoitusten luettelo:

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

Täytä joitain muuttujia kielto- ja enimmäismuutosrajoitusten toteuttamiseksi:

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

Lisää Dothraki-muuttujat:

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

Tarvitsemme myös hieman muokatun silmukan muutos- ja kieltovaatimusten laskemiseksi:

# 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

Ja lopuksi tulosta tulokset:

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

Ja meidän pitäisi olla valmiita. Suorita koodi ja sinun pitäisi nähdä tulos seuraavasti:

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

Ja voila, tulos, joka kunnioittaa kiellettyjen työntekijöiden luetteloa, noudattaa työehtoja ja käyttää Dothrakin työntekijöitä järkevästi.

johtopäätös

Tänään tutkitaan yhdistetyn kokonaislukuohjelmoinnin käyttöä parempien päätösten tekemiseksi. Keskustelemme operaatiotutkimuksessa käytetyistä algoritmeista ja tekniikoista sekä tarkastelemme esimerkkiongelmaa, joka edustaa sekalukuisten ohjelmointien käyttöä todellisessa maailmassa.

Toivon, että tämä artikkeli innostaa sinua oppimaan lisää operaatiotutkimuksesta ja saa sinut pohtimaan, miten tätä tekniikkaa voidaan soveltaa projekteihisi. Olemme todellakin nähneet jäävuoren kärjen vain optimointialgoritmien ja operaatiotutkimuksen jännittävän maailman suhteen.

Löydät kaikki tähän artikkeliin liittyvät koodit GitHubissa . Jos haluat keskustella lisää, jaa kommenttisi alla!