Istraživanje otkriva optimalan način optimizacije

Izvorna verzija od ovu priču pojavio u Časopis Quanta.

Godine 1939., nakon što je zakasnio na svoj kolegij statistike na UC Berkeley, George Dantzig — student prve godine diplomskog studija — prepisao je dva problema s ploče, misleći da su domaća zadaća. Smatrao je da mu je domaća zadaća “teža za napraviti nego inače”, ispričao je kasnije, i ispričao se profesoru što je trebalo nekoliko dana više da je dovrši. Nekoliko tjedana kasnije, njegov mu je profesor rekao da je riješio dva poznata otvorena problema iz statistike. Dantzigovo djelo pružit će osnovu za njegovu doktorsku disertaciju i, desetljećima kasnije, inspiraciju za film Dobri Will Hunting.

Dantzig je doktorirao 1946., odmah nakon Drugog svjetskog rata, i ubrzo je postao savjetnik za matematiku novoosnovanog američkog ratnog zrakoplovstva. Kao i kod svih modernih ratova, ishod Drugog svjetskog rata ovisio je o razboritoj raspodjeli ograničenih resursa. Ali za razliku od prijašnjih ratova, ovaj je sukob bio doista globalnih razmjera, a dobiven je velikim dijelom čistom industrijskom moći. SAD bi jednostavno mogao proizvesti više tenkova, nosača zrakoplova i bombardera od svojih neprijatelja. Znajući to, vojska je bila intenzivno zainteresirana za probleme optimizacije – to jest, kako strateški rasporediti ograničene resurse u situacijama koje mogu uključivati ​​stotine ili tisuće varijabli.

Zračne snage zadužile su Dantiga da pronađe nove načine za rješavanje problema optimizacije poput ovih. Kao odgovor na to, izumio je simpleks metodu, algoritam koji se oslanjao na neke od matematičkih tehnika koje je razvio dok je rješavao svoje probleme na ploči gotovo desetljeće prije.

Gotovo 80 godina kasnije, simpleks metoda je još uvijek među najčešće korištenim alatima kada je potrebno donijeti logističku odluku ili odluku u opskrbnom lancu pod složenim ograničenjima. Učinkovito je i djeluje. “Uvijek je trčao brzo i nitko nije vidio da nije brz”, rekao je Sophie Huiberts francuskog Nacionalnog centra za znanstvena istraživanja (CNRS).

U isto vrijeme, postoji zanimljivo svojstvo koje je dugo bacalo sjenu na Dantzigovu metodu. Godine 1972. matematičari su dokazali da vrijeme potrebno za dovršenje zadatka može eksponencijalno rasti s brojem ograničenja. Dakle, bez obzira na to koliko je metoda brza u praksi, teorijske analize dosljedno nude najgore scenarije koji impliciraju da bi moglo trajati eksponencijalno dulje. Za simpleks metodu, “naši tradicionalni alati za proučavanje algoritama ne rade”, rekao je Huiberts.

Ali u novom papir koji će biti predstavljen u prosincu na konferenciji Foundations of Computer Science, Huiberts and Eleon Bachdoktorandica na Tehničkom sveučilištu u Münchenu, čini se da su prevladali ovaj problem. Učinili su algoritam bržim, a također su pružili teoretske razloge zašto se eksponencijalna vremena izvođenja kojih se dugo strahovalo ne materijaliziraju u praksi. Djelo, koje se nadovezuje na a značajan rezultat od 2001. od strane Daniel Spielman i Shang-Hua Tengje “briljantan [and] prelijepo”, kaže Teng.

“To je vrlo impresivan tehnički rad, koji majstorski kombinira mnoge ideje razvijene u prethodnim pravcima istraživanja, [while adding] neke istinski lijepe nove tehničke ideje”, rekao je László Véghmatematičar sa Sveučilišta u Bonnu koji nije bio uključen u ovaj pokušaj.

Optimalna geometrija

Simpleks metoda osmišljena je za rješavanje klase problema kao što je ovaj: Pretpostavimo da tvrtka za namještaj proizvodi ormare, krevete i stolice. Slučajno, svaki ormar je tri puta isplativiji od svake stolice, dok je svaki krevet dvostruko isplativiji. Ako želimo ovo napisati kao izraz, koristeći a, bi c da bismo predstavili količinu proizvedenog namještaja, rekli bismo da je ukupna dobit proporcionalna 3a + 2b + c.

Da bi maksimizirali profit, koliko bi od svake stavke tvrtka trebala proizvoditi? Odgovor ovisi o ograničenjima s kojima se suočava. Recimo da tvrtka može proizvesti najviše 50 artikala mjesečno, dakle a + b + c manji je ili jednak 50. Ormare je teže napraviti—ne može se proizvesti više od 20—pa a manji je ili jednak 20. Za stolice je potrebno posebno drvo, a njegova je ponuda ograničena, stoga c mora biti manji od 24.

Simpleksna metoda pretvara situacije poput ove—iako često uključuje mnogo više varijabli—u geometrijski problem. Zamislite grafički prikaz naših ograničenja za a, b i c u tri dimenzije. Ako a manji ili jednak 20, možemo zamisliti ravninu na trodimenzionalnom grafikonu koja je okomita na a osi, sijekući je na a = 20. Uvjetovali bismo da naše rješenje mora ležati negdje na ili ispod te ravnine. Isto tako, možemo stvoriti granice povezane s drugim ograničenjima. U kombinaciji, ove granice mogu podijeliti prostor u složeni trodimenzionalni oblik koji se naziva poliedar.