Operatsiooniuuringuid, teadust arvutite kasutamisest optimaalsete otsuste langetamiseks, on kasutatud ja rakendatud paljudes tarkvara valdkondades. Mõne näite toomiseks kasutavad logistikaettevõtted selle määramiseks optimaalset marsruuti punktist A punkti B jõudmiseks, elektriettevõtted kasutavad seda energiatootmise graafikute määramiseks ja tootmisettevõtted kasutavad seda teie tehaste optimaalsete personalimustrite leidmiseks.

küberturvalisuse probleemid ja lahendused

Täna uurime hüpoteetilisest probleemist lähtuvalt operatsiooniuuringute jõudu. Täpsemalt, kasutame täisarvude segaprogrammimist ( MIP ) hüpoteetilise tehase optimaalse personali skeemi määramiseks.

Operatsiooniuuringute algoritmid

Enne kui uurime oma näideprobleemist, on kasulik minna üle operatsiooniuuringute põhitõdedest ja mõista mõnda tööriista, mida täna kasutame.

Lineaarsed programmeerimisalgoritmid

Lineaarne programmeerimine on operatsioonide uurimise tehnika, mida kasutatakse matemaatilise mudeli parima tulemuse väljaselgitamiseks, kus eesmärk ja piirangud on väljendatud lineaarvõrrandite süsteemina. Lineaarse programmeerimismudeli näide võib välja näha järgmine:

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

Meie lihtsas näites näeme, et optimaalne tulemus on 5, kusjuures a = 2 ja b = 3. Kuigi see on üsna tühine näide, võite tõenäoliselt ette kujutada lineaarset programmeerimismudelit, mis kasutab tuhandeid muutujaid ja sadu piiranguid. .

Hea näide võib olla investeerimisportfelli probleem, mille puhul võite pseudokoodiga kokku puutuda järgmisega:

Maximize Subject to: Etc. ...

Mis oleks üsna keeruline ja käsitsi või katse-eksituse meetodil keeruline lahendada. Operatsioonide uurimise tarkvara kasutab nende probleemide kiireks lahendamiseks erinevaid algoritme. Kui olete huvitatud aluseks olevatest algoritmidest, soovitan teil tutvuda simplex-meetodiga siin ja sisepunkti meetod siin .

Täisarvude programmeerimise algoritmid

Täisarvuga programmeerimine on nagu lineaarne programmeerimine, mille mõnede või kõigi muutujate lisatolerants on täisarv. Kuigi see ei tundu esialgu kuigi suur edasiminek, võimaldab see meil lahendada paljusid probleeme, mis oleks võinud jääda lahendamata ainult lineaarse programmeerimise abil.

Üks nendest probleemidest on seljakotiprobleem, mille käigus antakse meile määratud esemete komplekt koos määratud väärtuste ja kaaluga ning palutakse leida meie seljakotti kõige sobivam esemete kombinatsioon. Lineaarne programmeerimismudel seda lahendada ei suuda, sest pole mingit võimalust väljendada ideed, et võite panna eseme seljakotti või mitte, kuid te ei saa osa esemest seljakotti panna - iga muutuja on muutuja ! jätkake!

Seljakotiprobleemi näitel võivad olla järgmised parameetrid:

Objekt	Väärtus (10 dollari ühikud)	Suurus (üldised üksused)
Kaamera	5	2
Saladuslik kujuke	7	4
Tohutu pudel õunasiidrit	2	7
metsasarv	10	10

Ja mudel MIP see näeb välja selline:

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

Optimaalne lahendus on antud juhul a = 0, b = 1, c = 0, d = 1, kusjuures kogu üksuse väärtus on 17.

Probleem, mille täna lahendame, nõuab ka tervet ajakava, kuna vabriku töötaja võib olla planeeritud ühte vahetusse või mitte - lihtsuse huvides ei saa te selles tehases töötajat 2/3 vahetuseks planeerida.

Täisarvude programmeerimise võimaldamiseks kasutatakse erinevaid matemaatilisi algoritme. Kui olete huvitatud aluseks olevatest algoritmidest, soovitan teil uurida lõiketasandi algoritmi ning hargnemis- ja sidumisalgoritmi siin .

Näidisprobleem: programmeerimine

Probleemi kirjeldus

Täna uurime tehase töötajate arvu probleemi. Tehase juhtkonnana tahame minimeerida tööjõukulusid, kuid tahame tagada iga vahetuse piisava katvuse, et rahuldada tootmise nõudlust.

Oletame, et meil on viis vahetust järgmiste personali nõudmistega:

Vahetus 1	Vahetus 2	Vahetus 3	Vahetus 4	Vahetus 5
1 inimene	4 inimest	3 inimest	5 inimest	2 inimest

Oletame, et meil on järgmised töötajad:

Nimi	Saadavus	Hind vahetuse kohta ($)
Melisandre	1, 2, 5	kakskümmend
Kliid	2. 3. 4. 5	viisteist
Cersei	3. 4	35
Daenerys	Neli, viis	35
Theon	2, 4, 5	10
Jon	1, 3, 5	25
Tyrion	2, 4, 5	30
James	2, 3, 5	kakskümmend
Arya	1, 2, 4	kakskümmend

Probleemi lihtsuse huvides oletame praegu, et murettekitav on ainult kättesaadavus ja hind.

Meie tööriistad

Tänase probleemi jaoks kasutame avatud lähtekoodiga lõigatud ja hargnevat tarkvara nimega CBC. Selle tarkvaraga suhtleme PuLP abil, mis on Pythoni populaarne operatsiooniuuringute modelleerimise teek. Selle kohta leiate teavet siin .

PuLP võimaldab meil mudeleid ehitada MIP väga Pythoni viisil ja integreerub väga hästi olemasoleva Pythoni koodiga. See on väga kasulik, kuna mõned populaarseimad andmetöötlus- ja analüüsivahendid on kirjutatud Pythonis ning enamik äritegevuse uurimissüsteeme nõuab enne ja pärast optimeerimist ulatuslikku andmetöötlust.

PuLP lihtsuse ja elegantsi näitamiseks on siin varasem seljakoti probleem, mis on PuLP-s lahendatud:

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

Käivitage see ja peaksite saama väljundi:

Optimal a 0.0 b 1.0 c 0.0 d 1.0

Nüüd meie programmeerimisprobleemi juurde!

Meie lahenduse kodeerimine

Meie lahenduse kodeerimine on üsna lihtne. Kõigepealt määratleme oma andmed:

kuidas alustada angularjs projekti

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

Järgmisena peame määratlema mudeli:

# 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 nüüd palume teil tulemused lahendada ja printida!

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

Kui olete koodi käivitanud, peaksite nägema järgmisi väljundeid:

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

Suurendage raskusi veidi: täiendavad piirangud

Kuigi ülaltoodud mudel oli huvitav ja kasulik, ei näita see täisarvude segaprogrammeerimise jõudu täielikult. Saaksime hõlpsalt ka silmuse kirjutada for töötajate leidmiseks x odavaim iga vahetuse jaoks, kus x on vahetuse jaoks vajalike töötajate arv. Et näidata, kuidas MIP saab kasutada probleemi lahendamiseks, mida oleks hädavajalik lahendada, uurime, mis juhtuks, kui lisame mõned täiendavad piirangud.

Täiendavad piirangud

Oletame, et uute tööeeskirjade tõttu ei saa töötajaid määrata rohkem kui kahele vahetusele. Suurenenud töö arvestamiseks oleme palunud abi Dothraki personalirühmast, mis pakub iga vahetuse jaoks kuni 10 Dothraki töötajat 40 dollariga vahetuse kohta.

Oletame ka, et väljaspool meie tehast kestvate inimestevaheliste konfliktide tõttu ei saa Cersei ja Jaime vahetustega töötada kas Daenerysega ega Joniga. Samuti ei saa Jaime ja Cersei üheski vahetuses töötada. Lõpuks, Arya, kellel on eriti keerulised inimestevahelised suhted, ei saa teha sama vahetust Jaime, Cersei või Melisandre'iga.

Nende kahe uue piirangu ja ressursside lisamine ei muuda mingil moel probleemi võimatuks imperatiivsete vahendite abil lahendamist, vaid muudab lahenduse palju keerulisemaks, kuna tuleb arvestada konkreetse vahetuse puhul töötaja tööle määramise alternatiivkuludega.

Lahendus

Segatud täisarvude programmeerimisega on see aga palju lihtsam. Peame lihtsalt oma koodeksi muutma järgmiselt:

Määrake keelude ja mõnede piirangute loend:

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

Keelustamise ja muutmise piirangute rakendamiseks sisestage mõned muutujad:

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

Lisage Dothraki muutujad:

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

Muudatuste ja keelustamisnõuete arvutamiseks vajame ka veidi muudetud tsüklit:

mis on kapitalieelarve koostamise teine ​​samm

# 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 lõpuks, tulemuste printimiseks:

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 me peaksime valmis olema. Käivitage kood ja tulemust peaksite nägema järgmiselt:

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, tulemus, mis austab keelatud töötajate nimekirja, järgib tööeeskirju ja kasutab mõistlikult Dothraki töötajaid.

järeldus

Täna uurime parema otsuse tegemiseks segatud täisarvude programmeerimise kasutamist. Arutame operatsioonide uurimisel kasutatavate aluseks olevate algoritmide ja tehnikate üle, samuti vaatleme näidisprobleemi, mis esindab seda, kuidas segatud täisarvuga programmeerimist reaalses maailmas kasutatakse.

Loodan, et see artikkel inspireerib teid operatsiooniuuringute kohta lisateavet ja paneb mõtisklema selle üle, kuidas seda tehnoloogiat teie projektides rakendada. Jäämäe tippu oleme tõesti näinud ainult optimeerimisalgoritmide ja operatsiooniuuringute põneva maailma osas.

Leiate kogu selle artikliga seotud koodi saidil GitHub . Kui soovite rohkem arutada, jagage oma kommentaare allpool!