Lineaarne programmeerimine, matemaatiline modelleerimise tehnika, milles mitmesuguste piirangute korral lineaarset funktsiooni maksimeeritakse või minimeeritakse. See tehnika on olnud kasulik kvantitatiivsete otsuste suunamiseks äriplaneerimisel, tööstustehnilises töös ja vähemal määral ka sotsiaal- ja füüsikateaduste alal.
optimeerimine: Lineaarne programmeerimine
Ehkki lineaarset programmeerimist kasutatakse laialdaselt igapäevaste otsustusprobleemide lahendamiseks, oli see enne 1947. aastat suhteliselt tundmatu. Ühtegi olulist tööd ei olnud
Lineaarse programmeerimise ülesande lahendus taandub lineaarse avalduse (mida nimetatakse objektiivfunktsiooniks) optimaalse väärtuse leidmiseks (sõltuvalt probleemist suurim või väikseim).
millele kehtivad ebavõrdsusena väljendatud piirangud:
A, b ja c on konstandid, mis on määratud probleemi mahutavuse, vajaduste, kulude, kasumi ja muude nõuete ning piirangutega. Selle meetodi rakendamisel on põhieelduseks, et nõudluse ja saadavuse erinevad seosed on lineaarsed; see tähendab, et ükski x i ei tõuse muule võimsusele kui 1. Sellele probleemile lahenduse leidmiseks on vaja leida lahendus lineaarsete ebavõrdsuste süsteemile (st n väärtuste kogumile n muutujad x i, mis rahuldavad samaaegselt kõiki ebavõrdsusi). Seejärel hinnatakse objektiivset funktsiooni, asendades x i väärtused võrrandis, mis määratleb f.
Lineaarse programmeerimise meetodi kasutamist proovisid tõsiselt 1930ndate lõpus Nõukogude matemaatik Leonid Kantorovich ja ameerika majandusteadlane Wassily Leontief vastavalt tootmisgraafikute ja majanduse alal, kuid nende tööd eirati aastakümneid. Teise maailmasõja ajal kasutati laialdaselt lineaarset programmeerimist ressursside transpordi, ajakava koostamise ja eraldamisega seotud piirangutega, näiteks kulude ja saadavuse osas. Need rakendused aitasid selle meetodi aktsepteeritavust palju paremini tõestada, mis sai 1947. aastal täiendava tõuke Ameerika matemaatiku George Dantzigi simpleksmeetodi kasutuselevõtuga, mis lihtsustas oluliselt lineaarse programmeerimise probleemide lahendamist.
Kuna aga üritati teha üha keerukamaid ja rohkem muutujaid hõlmavaid probleeme, laienes vajalike toimingute arv plahvatuslikult ja ületas isegi kõige võimsamate arvutite arvutusvõimsuse. Siis, 1979. aastal, avastas vene matemaatik Leonid Khachiyan polünoomi ajalise algoritmi - milles arvutuslike sammude arv kasvab pigem muutujate arvu võimsusena kui eksponentsiaalselt -, võimaldades seeläbi seni ligipääsmatute probleemide lahendamist. Kuid Khachiyani algoritm (mida nimetatakse ellipsoidi meetodiks) oli praktilise rakendamise korral aeglasem kui simpleksmeetod. India matemaatik Narendra Karmarkar avastas 1984. aastal teise polünoomi-aja algoritmi, sisemiste punktide meetodi, mis osutus simpleksmeetodi abil konkurentsivõimeliseks.
