Lineārā programmēšana, matemātiskās modelēšanas tehnika, kurā lineārā funkcija tiek maksimizēta vai samazināta līdz minimumam, pakļaujot dažādus ierobežojumus. Šis paņēmiens ir bijis noderīgs, lai vadītu kvantitatīvos lēmumus uzņēmējdarbības plānošanā, rūpniecības inženierijā un - mazākā mērā - sociālajās un fizikālajās zinātnēs.
optimizācija: Lineārā programmēšana
Lai arī lineārā programmēšana mūsdienās tiek plaši izmantota ikdienas lēmumu problēmu risināšanai, līdz 1947. gadam tas bija salīdzinoši nezināms
Lineāras programmēšanas problēmas risinājums tiek samazināts līdz optimālās vērtības (lielākās vai mazākās atkarībā no problēmas) atrašanai (saukta par objekta funkciju)
ievērojot ierobežojumu kopumu, kas izteikts kā nevienlīdzība:
A, b un c ir konstantes, ko nosaka spējas, vajadzības, izmaksas, peļņa un citas problēmas prasības un ierobežojumi. Pamatpieņēmums, izmantojot šo metodi, ir tāds, ka dažādās attiecības starp pieprasījumu un pieejamību ir lineāras; tas ir, neviens no x i netiek paaugstināts uz citu jaudu, izņemot 1. Lai iegūtu šīs problēmas risinājumu, jāatrod lineāro nevienādību sistēmas risinājums (tas ir, n vērtību kopa n mainīgie x i, kas vienlaikus apmierina visas nevienādības). Mērķa funkcija tiek novērtēta, aizstājot x i vērtības vienādojumā, kas nosaka f.
Lineārās programmēšanas metodes pielietojumu nopietni mēģināja padomju matemātiķis Leonīds Kantorovičs un amerikāņu ekonomists Vasilijs Leontiefs 30. gadu beigās attiecīgi ražošanas grafiku un ekonomikas jomā, taču gadu desmitiem ilgi viņu darbs tika ignorēts. Otrā pasaules kara laikā lineārā programmēšana tika plaši izmantota, lai risinātu jautājumus ar resursu transportēšanu, plānošanu un piešķiršanu, ievērojot noteiktus ierobežojumus, piemēram, izmaksas un pieejamību. Šīs lietojumprogrammas daudz darīja, lai noteiktu šīs metodes pieņemamību, kas 1947. gadā ieguva turpmāku stimulu, ieviešot amerikāņu matemātiķa Džordža Dantziga simpleksa metodi, kas ievērojami vienkāršoja lineārās programmēšanas problēmu risinājumu.
Tomēr, tā kā tika mēģināts aizvien sarežģītākas problēmas, kas saistītas ar vairāk mainīgiem, nepieciešamo operāciju skaits pieauga eksponenciāli un pārsniedza pat visspēcīgāko datoru skaitļošanas iespējas. Pēc tam, 1979. gadā, krievu matemātiķis Leonīds Khachiyan atklāja polinoma laika algoritmu, kurā skaitļošanas soļu skaits pieaug kā mainīgo skaita spēks, nevis eksponenciāli, tādējādi ļaujot atrisināt līdz šim nepieejamas problēmas. Tomēr Khachiyan algoritms (saukts par elipsoīda metodi) bija lēnāks nekā simpleksa metode, kad to praktiski pielietoja. Indijas matemātiķis Narendra Karmarkars 1984. gadā atklāja citu polinoma laika laika algoritmu - interjera punktu metodi, kas izrādījās konkurētspējīgs ar simpleksa metodi.
