Linearno programiranje, tehnika matematičkog modeliranja u kojoj se linearna funkcija maksimizira ili minimizira kada je izložena raznim ograničenjima. Ova je tehnika bila korisna za usmjeravanje kvantitativnih odluka u poslovnom planiranju, industrijskom inženjerstvu i, u manjoj mjeri, u društvenim i fizičkim znanostima.
optimizacija: Linearno programiranje
Iako se sada široko koristi za rješavanje problema svakodnevnog odlučivanja, linearno programiranje bilo je razmjerno nepoznato prije 1947. Nijedan rad nije bio važan
Rješavanje problema linearnog programiranja svodi se na pronalaženje optimalne vrijednosti (najveće ili najmanje, ovisno o problemu) linearnog izraza (zvane ciljna funkcija)
podložno skupu ograničenja izraženih kao nejednakosti:
A, b i c su konstante određene kapacitetima, potrebama, troškovima, dobiti i drugim zahtjevima i ograničenjima problema. Osnovna pretpostavka u primjeni ove metode je da su različiti odnosi između potražnje i dostupnosti linearni; to jest, nijedan od x i nije odgođen na snagu koja nije 1. Da bi se dobilo rješenje ovog problema, potrebno je pronaći rješenje sustava linearnih nejednakosti (tj. skupa n vrijednosti od varijable x i koje istovremeno zadovoljavaju sve nejednakosti). Objektivna funkcija tada se vrednuje zamjenom vrijednosti x i u jednadžbi koja definira f.
Primjene metode linearnog programiranja prvi su ozbiljno pokušali sovjetski matematičar Leonid Kantorovich i američki ekonomist Wassily Leontief prvi put ozbiljno pokušati na područjima proizvodnih planova i ekonomije, ali njihov je rad desetljećima bio zanemaren. Tijekom Drugog svjetskog rata linearno se programiranje intenzivno koristilo za prijevoz, planiranje i raspoređivanje resursa pod određenim ograničenjima kao što su troškovi i raspoloživost. Te su aplikacije učinile mnogo da se utvrdi prihvatljivost ove metode, koja je daljnji zamah dobila 1947. uvođenjem američke matematičara Georgea Dantzig-ove simpleks metode, koja je znatno pojednostavila rješenje linearnih problema programiranja.
Međutim, kako su pokušavani sve složeniji problemi koji uključuju više varijabli, broj potrebnih operacija eksponencijalno se proširio i premašio računske kapacitete čak i najmoćnijih računala. Potom je 1979. godine ruski matematičar Leonid Khachiyan otkrio algoritam polinomnog vremena - u kojem broj računajućih koraka raste kao snaga broja varijabli, a ne eksponencijalno - omogućujući tako rješenje dosad nepristupačnih problema. Međutim, Khachiyan-ov algoritam (koji se naziva elipsoidna metoda) bio je sporiji od simpleks metode kad se praktički primijenio. Indijski matematičar Narendra Karmarkar 1984. godine otkrio je još jedan polinomski vremenski algoritam, metodu unutarnje točke, koji se pokazao konkurentnim simpleks metodi.
