Linearno programiranje, tehnika matematičnega modeliranja, pri kateri se linearna funkcija poveča ali zmanjša na najmanjšo možno mero, če je izpostavljena različnim omejitvam. Ta tehnika je bila uporabna za usmerjanje kvantitativnih odločitev pri poslovnem načrtovanju, industrijskem inženiringu in - v manjši meri - v družbenih in fizikalnih vedah.
optimizacija: Linearno programiranje
Čeprav se zdaj široko uporablja za reševanje vsakodnevnih težav z odločitvami, je bilo linearno programiranje pred letom 1947 razmeroma neznano
Rešitev problema linearnega programiranja se zmanjša na iskanje optimalne vrednosti (največje ali najmanjše, odvisno od problema) linearnega izraza (imenovane ciljna funkcija)
ob upoštevanju omejitev, izraženih kot neenakosti:
A, b in c so konstante, ki jih določajo zmogljivosti, potrebe, stroški, dobiček ter druge zahteve in omejitve problema. Osnovna predpostavka pri uporabi te metode je, da so različna razmerja med povpraševanjem in razpoložljivostjo linearna; to pomeni, da noben od x i ni dvignjen na moč, ki ni enaka 1. Za rešitev tega problema je treba najti rešitev sistema linearnih neenakosti (torej nabora n vrednosti n spremenljivke x i, ki hkrati izpolnjujejo vse neenakosti). Ciljna funkcija se nato ovrednoti z nadomestitvijo vrednosti x i v enačbi, ki določa f.
Uporaba metode linearnega programiranja sta v poznih tridesetih letih prejšnjega stoletja prvič resno poskušala sovjetski matematik Leonid Kantorovič in ameriški ekonomist Wassily Leontief na področjih proizvodnih načrtov oziroma ekonomije, vendar njuno delo desetletja ni bilo upoštevano. Med drugo svetovno vojno se je linearno programiranje široko uporabljalo za prevoze, načrtovanje in dodeljevanje virov, za katere veljajo določene omejitve, kot so stroški in razpoložljivost. Te aplikacije so veliko pripomogle k sprejemljivosti te metode, ki je leta 1947 dobila nov zagon z uvedbo simpleksne metode ameriškega matematika Georga Dantziga, ki je močno poenostavila reševanje problemov linearnega programiranja.
Ker pa so se poskusili čedalje bolj zapleteni problemi z več spremenljivkami, se je število potrebnih operacij eksponentno povečalo in preseglo računsko zmogljivost tudi najmočnejših računalnikov. Nato je leta 1979 ruski matematik Leonid Khačijan odkril algoritem polinomskega časa - v katerem število računskih korakov narašča kot moč števila spremenljivk in ne eksponentno - in tako omogoči rešitev doslej nedostopnih problemov. Vendar je bil Khachiyanov algoritem (imenovan elipsoidna metoda) počasnejši od metode simpleksa, ko smo ga praktično uporabili. Leta 1984 je indijski matematik Narendra Karmarkar odkril še en polinomni časovni algoritem, metodo notranje točke, ki se je izkazala za konkurenčno s simpleks metodo.
