Tag Archives: problem dinamičkog alociranja

Matematički problem koji bi svijet mogao zaustaviti

Naš zahtjevni užurbani stil života oslanja se na dodjelu ograničenih skupova resursa neprestano mijenjajućem broju ljudi. Kako ovaj zadatak postaje sve teži, trebat će mu rješenja malo poznate matematičke zagonetke.
Nije lako precizno predvidjeti šta ljudi žele i kad će do htjeti. Mi smo zahtjevna stvorenja, očekujući da će svijet ponuditi brza rješenja za naše sve složenije i raznolike probleme modernog života.

Tokom poslednjih nekoliko decenija, istraživači su razvili efikasno matematičko rešenje koja može raspodeliti resurse u različitim industrijama i scenarijima. Ali kad je raspodjela napravila odjednom utjelovljenje na kasnije raspodjele, problem postaje dinamičan i kompleksan. Ovo zahtijeva da ova rješenja uzmu u obzir promjenu i neizvjesnu prirodu stvarnog svijeta.




Takvi problemi su poznati kao problemi s dinamičkom raspodjelom resursa. Oni se pojavljuju na svakom mjestu gdje nađete ograničen resurs koji treba dodijeliti u stvarnom vremenu.

Bez obzira na to čekate li taksi ili isporuku sljedećeg dana, lista dinamičkih problema s raspodjelom resursa i njihove svakodnevne primjene su “gotovo beskrajni”, izjavio je Warren Powell, inženjer sa Univerziteta Princeton koji istražuje ove probleme još od 1980-ih.
Ali problemi s dinamičkom raspodjelom resursa ne odnose se samo na to da ljudima date ono što žele, kad oni to žele. Oni će takođe biti od ključnog značaja za rješavanje nekih od najvažnijih i najsloženijih svjetskih pitanja, uključujući klimatske promjene, jer nam pomažu da raspodijelimo često oskudne i iscrpljene resurse naše planete na najefikasniji mogući način.

Ali pogledajmo najprije pojednostavljeni primjer da vidimo šta je problem dinamičke raspodjele resursa i šta ga čini tako teško riješiti.

Zamislite da kuvate večeru za četveročlanu porodicu. Odlučili ste se za govedinu sa svim ukrasima, sigurni u spoznaju da je čvrsti porodični favorit. Ali čim se spremate da poslužite, vaša kćerka najavljuje da je vegetarijanka, tekstovi vašeg partnera govore da kasni, a sin vam kaže da je pozvao i nekoliko prijatelja na večeru. Zatim, vaš pas odleti zajedno sa govedinom dok očajnički pokušavate shvatiti kako ćete udovoljiti potrebama svih ovih (sasvim iskreno) vrlo zahtjevnih i nesavjesnih pojedinaca.
Ovo je trivijalni primjer problema s dinamičkom raspodjelom resursa, ali pokazuje neke od osnovnih izazova s kojima se istraživači susreću prilikom rješavanja ovih problema. Za početak se parametri koji utječu na potražnju neočekivano mijenjaju i kratkoročno i dugoročno. Ni na koji način niste mogli tačno predvidjeti nove prehrambene potrebe svoje kćeri, dogovoreni dolazak partnera ili dodatne goste vašeg sina dok ste spremali ovaj obrok.

Dugoročno, potražnja za obrocima u vašoj kući također se svakodnevno mijenja. Možda ćete trebati hraniti dvije ili 20 osoba pri svakom sjedenju. Od obroka do obroka, nemate pojma koga ćete hraniti, šta će i kada će htjeti. Možete uzeti poučen pogodak na osnovu prethodnog iskustva, ali to nije robusna metoda, jer su ljudska priroda i mnogi drugi parametri koji utječu na potražnju nepredvidivi.
Postupanja pojedinaca u ovom scenariju takođe utiču na buduće stanje sistema. Svaki put kada osobi dodijelite određeni obrok, to mijenja sistem. Uklanja jednu gladnu osobu i hranu iz vaše kuhinje.



“Svi primjeri [dinamičke raspodjele resursa] trebaju se baviti promjenom ulaza i okruženja, koja su vrlo dinamična i teško ih je procijeniti i predvidjeti, jer buduće opterećenje nije statistički ovisno od trenutnog opterećenja”, kaže Eiko Yoneki, viši istraživač koji vodi grupa podataka usmjerenih na podatke na računarskoj laboratoriji Univerziteta u Cambridgeu. „Jedna promjena pokreće drugu promjenu, a ako želite kontrolirati sistem tačnim odlukama, morate uzeti u obzir budući status sistema.“

Štaviše, što više ljudi ili opcija za obrok dolaze u vašu kuhinju, stvari se dalje kompliciraju. Sada imate više načina da dodijelite niz različitih obroka različitim ljudima. Ovaj broj kombinacija raste eksponencijalno jer sistemu dodajete više ljudi ili obroka.
S ovim se, na primjer, može suočiti velika bolnica kada pokušava nahraniti sve pacijente koji uđu kroz njena vrata. Isto se odnosi i na pokušaj liječenja ovih pacijenata. Lijekovi koji su im potrebni, a koji sami imaju ograničen rok trajanja, a oprema potrebna za dijagnostiku i liječenje stalno će se mijenjati kako pristižu različiti pacijenti. Ograničeni resursi poput MRI skenera, ljekara i medicinskih sestara također moraju biti izdvojeni. Da bi se pozabavili tim problemom i kako bi se spriječilo da troškovi izviru iz kontrole, rukovodstvo bolnice može koristiti matematičke modele kako bi pomoglo koordinaciju svih ovih stvari.

Problem je što se većina postojećih metoda oslanja na povijesne podatke da bi predvidjeli. Ova metoda se ne postiže dobro za takve sisteme i ne može se nositi ni sa najmanjim promjenama. Ako dođe do promjene, vraćaju se u kvadrat i počinju iznova raditi rješenje. Takvi problemi brzo postaju neizrecivi za račune, čak i za prilično mali broj ljudi i resursa – bilo da je to obrok ili MRI skener.

Problemi s dinamičkom raspodjelom resursa također proizlaze iz niza različitih scenarija i svaki od njih ima svoje posebne probleme. Na primjer, Yoneki istražuje implikacije ovih problema kako bi pomogao da se naši računarski sistemi i aplikacije pokrenu brže i efikasnije.

„Moderni računarski sistemi su složeni i potrebno je prilagoditi mnoge konfiguracijske parametre, uključujući raspodjelu resursa poput memorije, računarskog kapaciteta, komunikacijske sposobnosti i bilo kakvog ulaza u sisteme“, kaže ona. „Računalni sistemi su dinamični i bave se stalno promenljivim okruženjima, koja zahteva metodologiju dinamičke kontrole.“

Dakle, računar o kojem čitate ovaj članak gotovo se sigurno bori sa nekim problemima dinamičke raspodjele resursa u ovom trenutku. Mrežne telefonske mreže i računalstvo u oblaku ovise i o rješavanju ovih problema.

Tvrtke za dostavu također rješavaju probleme s dinamičkom raspodjelom resursa kako bi ubrzali isporuke. Na primjer, UPS je razvio svoj integrirani sistem za optimizaciju i navigaciju na putu (Orion) kako bi optimizirao svoje rute isporuke koristeći napredne algoritme. Kompanija tvrdi da je rješenje uštedjelo 100 milijuna godišnje, ali drugi izvještaji otkrivaju borbe sistema u složenim urbanim sredinama.




Teškoće snabdijevanja su još jedan “problem koji nikada neće nestati”, kaže Powell, zbog složene prirode današnjih proizvoda. Na primjer, ako želite proizvesti standardni pametni telefon, trebate koordinirati stotine komponenti širom svijeta, a sve se to sastavi u određenom redoslijedu na tvorničkom katu. „Prekidi u lancu snabdijevanja glavni su problem kada se pokušava zadovoljiti potrebe društva“, dodaje on.

Napredak u mašinskom učenju nudi nove nade u rješavanju problema s dinamičkom raspodjelom resursa. Tehnika umjetne inteligencije nazvana učenje dubokog pojačanja omogućava algoritam da nauči što treba raditi interakcijom sa okolinom. Algoritam je dizajniran da uči bez ljudske intervencije, tako što je nagrađen za pravilno izvođenje i kažnjen za pogrešno izvođenje. Pokušavajući maksimizirati nagrade i minimizirati kazne, brzo se može doći do optimalnog stanja.

Učenje dubokog pojačanja nedavno je omogućilo program AlphaGo iz Googleovog DeepMind-a da savlada svjetskog prvaka u Go-u. Sistem je počeo da ne zna ništa o igri Go, a zatim je igrao protiv sebe kako bi trenirao i optimizirao svoje performanse. Iako su igre važan dokaz koncepta tehnika učenja dubokog pojačanja, učenje takvih igara nije krajnji cilj takvih metoda.

Izvor: BBC