Operointitutkimusta, tieteitä tietokoneiden käytöstä optimaalisten päätösten tekemiseksi, on käytetty ja sovellettu monilla ohjelmistoalueilla. Muutaman esimerkin antamiseksi logistiikkayritykset käyttävät sitä määrittääkseen optimaalisen reitin päästä pisteestä A pisteeseen B, energiayhtiöt käyttävät sitä määrittämään sähköntuotantoaikataulut ja valmistusyritykset etsivät tehtailleen optimaalista henkilöstömallia.

Tänään tutkimme operaatiotutkimuksen voimaa käymällä läpi hypoteettisen ongelman. Tarkemmin sanottuna käytämme sekoitetun kokonaisluvun ohjelmointia (MIP) määrittääksesi optimaalisen henkilöstömallin hypoteettiselle tehtaalle.

Operaatiotutkimusalgoritmit

Ennen kuin sukellamme esimerkkiongelmaamme, on hyödyllistä käydä läpi joitakin operatiivisen tutkimuksen peruskäsitteitä ja ymmärtää hieman 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 (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Hyvin 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 alla olevaan, pseudokoodina:

Maximize Subject to: Etc. ...

Mikä olisi melko monimutkaista ja vaikea ratkaista käsin tai kokeilemalla. Operaatiotutkimusohjelmisto käyttää useita 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ävaraus joillekin tai kaikille muuttujille on kokonaislukuarvoja. Vaikka tämä ei ehkä vaikuta aluksi suurelta parannukselta, se antaa meille mahdollisuuden ratkaista monia ongelmia, jotka olisivat voineet jäädä ratkaisematta pelkästään lineaarisen ohjelmoinnin avulla.

Yksi tällainen ongelma on reppuongelma, jossa meille annetaan joukko esineitä, joille on määritetty arvot ja painot, ja meitä pyydetään etsimään korkein esineiden arvoyhdistelmä, joka mahtuu reppuimme. 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 tuotteesta reppuusi - jokainen muuttuja on jatkuva vaihteleva!

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 MIP-malli 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 kokonaisluvun ohjelmoinnin, koska tehtaan työntekijä voidaan joko ajoittaa vuoroon tai ei - yksinkertaisuuden vuoksi et voi suunnitella työntekijälle 2/3 vuorosta tässä tehtaassa.

Jotta kokonaislukuohjelmointi olisi mahdollista, käytetään useita matemaattisia algoritmeja. Jos olet kiinnostunut taustalla olevista algoritmeista, suosittelen tutkimaan leikkaustasojen algoritmia ja haara- ja sidottuja algoritmeja tässä .

Esimerkki ongelma: Aikataulu

Ongelman kuvaus

Tänään tutkimme tehtaan henkilöstöongelmaa. Tehtaan johdona haluamme minimoida työvoimakustannukset, mutta haluamme varmistaa riittävän kattavuuden jokaiselle työvuorolle 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 toistaiseksi, että saatavuus ja kustannukset ovat ainoat huolenaiheet, jotta ongelma olisi yksinkertainen.

Työkalumme

Tämän päivän ongelmaan käytämme pala avoimen lähdekoodin haarautuneita ja leikattuja ohjelmistoja nimeltä CBC. Liitymme tämän ohjelmiston kanssa käyttämällä PuLP: tä, joka on suosittu toiminnan tutkimuksen mallintamiskirjasto Pythonille. Löydät tietoa siitä tässä .

PuLP antaa meille mahdollisuuden rakentaa MIP-malleja hyvin Python-tyyliin ja integroituu hienosti olemassa olevaan Python-koodiin. Tämä on erittäin hyödyllistä, koska jotkut suosituimmista datan käsittely- ja analysointityökaluista on kirjoitettu Pythonissa, ja useimmat kaupallisen toiminnan tutkimusjärjestelmät vaativat laajaa tietojenkäsittelyä ennen optimointia ja sen jälkeen.

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

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

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

Optimal a 0.0 b 1.0 c 0.0 d 1.0

Nyt aikatauluongelmamme!

Ratkaisumme koodaus

Ratkaisumme koodaus on melko yksinkertaista. Ensinnäkin haluamme määritellä 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 haluamme määritellä mallin:

# 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

Ja nyt pyydämme sitä vain 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

Pyöritä vaikeuksia hieman: Lisärajoitukset

Vaikka edellinen malli oli mielenkiintoinen ja hyödyllinen, se ei osoita täysin kokonaislukuohjelmoinnin voimaa. Voisimme myös helposti kirjoittaa for silmukka löytää halvin x työntekijöitä jokaisesta vuorosta, missä x on vuorossa tarvittavien työntekijöiden määrä. Osoittaaksemme, kuinka MIP: tä voidaan käyttää sellaisen ongelman ratkaisemiseen, jonka ratkaiseminen olisi haastavaa välttämättömällä tavalla, tutkitaan, mitä tapahtuisi, jos lisätään muutama ylimääräinen rajoitus.

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 ottaneet palvelukseen Dothraki Staffing Groupin, joka toimittaa jopa 10 Dothrakin työntekijää kutakin vuoroa kohti 40 dollaria vuoroa kohden.

Oletetaan lisäksi, että johtuen joistakin ihmissuhteiden konflikteista tehtaamme ulkopuolella, Cersei ja Jaime eivät kykene työskentelemään työvuorossa joko Daenerysin tai Jonin rinnalla. Jaime ja Cersei eivät myöskään pysty työskentelemään yhdessä työvuorossa. Lopuksi, Arya, jolla on erityisen monimutkaiset ihmissuhteet, ei pysty työskentelemään samassa vuorossa Jaimen, Cersein tai Melisandren kanssa.

Näiden kahden uuden rajoitteen ja resurssien lisääminen ei missään tapauksessa tee ongelmaa ratkaisemattomaksi välttämättömillä keinoilla, mutta se tekee ratkaisusta paljon vaikeampaa, koska on otettava huomioon vaihtoehtoiset kustannukset, jotka aiheutuvat työntekijän aikataulutuksesta tiettyyn vuoroon.

Ratkaisu

Sekalukuisten ohjelmointien avulla se on kuitenkin paljon helpompaa. Meidän on yksinkertaisesti muutettava koodiamme näin:

Määritä kieltoluettelo ja joitain rajoituksia:

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ä muuttujat kielto- ja enimmäissiirtorajoitusten toteuttamiseksi:

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

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 hiukan muokatun silmukan laskenta- ja kieltovaatimuksia varten:

# 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

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 hyviä mennä. Suorita koodi ja sinun pitäisi nähdä lähtö seuraavasti:

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

Ja meillä on se, 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 tutkimme sekalukujen ohjelmointia parempien päätösten tekemiseksi. Keskustelimme operaatiotutkimuksessa käytetyistä algoritmeista ja tekniikoista ja tarkastelimme esimerkkiongelmaa, joka edustaa sekalukuisten ohjelmointien käyttöä todellisessa maailmassa.

Toivon, että tämä artikkeli innoitti sinua oppimaan lisää operaatiotutkimuksesta ja sai sinut miettimään, miten tätä tekniikkaa voidaan soveltaa projekteihisi. Olemme vain nähneet jäävuoren kärjen, kun on kyse optimointialgoritmien ja operaatiotutkimuksen jännittävästä maailmasta.

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

Perustietojen ymmärtäminen

Mikä on lineaarinen ohjelmointi?

Lineaarinen ohjelmointi on operaatiotutkimustekniikka, jolla määritetään paras tulos matemaattisessa mallissa, jossa tavoite ja rajoitukset ilmaistaan ​​lineaaristen yhtälöiden järjestelmänä.

Mikä on kokonaislukuohjelmointi?

Kokonaislukuohjelmointi on kuin lineaarinen ohjelmointi, jossa lisävaraus joillekin tai kaikille muuttujille on kokonaislukuarvoja.