Lineaarinen ohjelmointi, matemaattinen mallinnustekniikka, jossa lineaarinen funktio maksimoidaan tai minimoidaan, kun siihen kohdistuu erilaisia rajoituksia. Tämä tekniikka on ollut hyödyllinen ohjaamaan kvantitatiivisia päätöksiä liiketoiminnan suunnittelussa, teollisuustekniikassa ja - vähemmässä määrin - yhteiskuntatieteissä ja fysiikassa.
optimointi: Lineaarinen ohjelmointi
Vaikka lineaarista ohjelmointia käytettiin laajalti nykypäivän päätöksentekoon liittyvien ongelmien ratkaisemiseksi, se oli suhteellisen tuntematon ennen vuotta 1947. Ei työtä, jolla olisi merkitystä
Lineaarisen ohjelmoinnin ongelman ratkaisu pienenee lineaarisen lausekkeen (nimeltään objektiivifunktio) optimaalisen arvon (suurin tai pienin ongelmasta riippuen) löytämiseksi
jolle asetetaan joukko rajoitteita, jotka ilmaistaan eriarvoisuutena:
A-, b- ja c-arvot ovat vakioita, jotka määräytyvät ongelman kapasiteetin, tarpeiden, kustannusten, voittojen ja muiden vaatimusten ja rajoitusten perusteella. Perusoletus tämän menetelmän soveltamisessa on, että kysynnän ja saatavuuden väliset suhteet ovat lineaariset; toisin sanoen, yhtäkään x i: stä ei nosteta muuhun tehoon kuin 1. Jotta ratkaisu tähän ongelmaan saadaan, on löydettävä ratkaisu lineaaristen epätasa-arvoisten järjestelmien (ts. n arvojen joukko muuttujat x i, jotka samanaikaisesti tyydyttävät kaikki epätasa-arvot). Tavoitefunktio arvioidaan sitten korvaamalla x i: n arvot yhtälössä, joka määrittelee f: n.
Neuvostoliiton matemaatikko Leonid Kantorovich ja amerikkalainen taloustieteilijä Wassily Leontief yrittivät vakavasti lineaarisen ohjelmointimenetelmän soveltamista 1930-luvun lopulla valmistusaikataulujen ja taloustieteen aloilla, mutta heidän työnsä jätettiin huomiotta vuosikymmenien ajan. Toisen maailmansodan aikana lineaarista ohjelmointia käytettiin laajasti käsittelemään resurssien kuljetusta, ajoittamista ja jakamista tietyin rajoituksin, kuten kustannukset ja saatavuus. Nämä sovellukset auttoivat paljon määrittämään tämän menetelmän hyväksyttävyys, joka sai lisää vauhtia vuonna 1947 ottamalla käyttöön amerikkalaisen matemaatikon George Dantzigin yksinkerrallinen menetelmä, joka yksinkertaisti huomattavasti lineaarisen ohjelmoinnin ongelmien ratkaisua.
Koska yritettiin kuitenkin tehdä yhä monimutkaisempia, enemmän muuttujia sisältäviä ongelmia, tarvittavien toimintojen määrä kasvoi eksponentiaalisesti ja ylitti jopa tehokkaimpien tietokoneiden laskentakapasiteetin. Sitten, vuonna 1979, venäläinen matemaatikko Leonid Khachiyan löysi polynomi-aika-algoritmin - jossa laskennallisten vaiheiden lukumäärä kasvaa muuttujien lukumäärän voimana eikä eksponentiaalisesti - mahdollistaen siten ratkaisun tähän mennessä saavuttamattomiin ongelmiin. Khachiyanin algoritmi (nimeltään ellipsoid-menetelmä) oli kuitenkin käytännössä hitaampi kuin simplex-menetelmä. Intialainen matemaatikko Narendra Karmarkar löysi vuonna 1984 toisen polynomi-aika-algoritmin, sisustuspistemenetelmän, joka osoittautui kilpailukykyiseksi simplex-menetelmällä.
