mini|Slikovni prikaz jednostavnog linearnog programa s dvije varijable i šest nejednakosti. Skup mogućih rješenja prikazan je žutom bojom i formira poligon, dvodimenzionalni politop. Optimum linearne funkcije troškova je tamo gdje crvena linija siječe poligon. Crvena linija predstavlja skup nivoa funkcije troškova, a strelica označava smjer u kojem optimiziramo. Linearno programiranje je najstarija i jedna od metoda operacijskih istraživanja koja se najčešće primjenjuje u praksi.http://www.purplemath.com/modules/linprog.htm desno|mini|Zatvorena izvodljiva oblast problema sa tri varijable je konveksni poliedar. Površine koje daju fiksnu vrijednost ciljne funkcije su ravni (nisu prikazane). Problem linearnog programiranja je pronaći tačku na poliedru koja se nalazi na ravni sa najvećom mogućom vrijednošću. Linearno programiranje je model kojom se matematički može opisati lingvistički problem traženja optimalne vrijednosti (minimum ili maksimum) funkcije cilja s određenim brojem strukturnih varijabli x1, x2,...,xn međusobno povezanih linearnim vezama, tj. ograničenjima u obliku linearnih jednadžbi ili nejednadžbi. Da bi se problem linearnog programiranja mogao riješiti, potrebno je postaviti matematički model koji se sastoji od funkcije cilja ili kriterija i ograničenja u obliku jednadžbi ili nejednadžbi i uvjeta nenegativnosti.
Problem rješavanja sistema linearnih nejednakosti datira barem još od Fouriera, koji je 1827. objavio metodu za njihovo rješavanje, i po kojem je nazvana metoda Fourier-Motzkinve eliminacije. lijevo|mini|128x128piksel|Džon fon Nojman Krajem 1930-ih, sovjetski matematičar Leonid Kantorovič i američki ekonomista Vasilij Leontijev nezavisno su se bavili praktičnim primjenama linearnog programiranja. Kantorovič se fokusirao na proizvodne rasporede, dok je Leontijev istraživao ekonomske primjene. Njihov revolucionarni rad je decenijama uglavnom bio zanemaren.
Od 1946. do 1947. godine, George B. Dantzig je samostalno razvio opću formulaciju linearnog programiranja za korištenje u problemima planiranja u američkom ratnom zrakoplovstvu. Godine 1947., Dantzig je također izumio simpleks metodu koja je, po prvi put, efikasno riješila problem linearnog programiranja u većini slučajeva. Kada je Dantzig dogovorio sastanak s Johnom von Neumannom kako bi razgovarali o svojoj simpleks metodi, von Neumann je odmah pretpostavio teoriju dualnosti shvativši da je problem na kojem je radio u teoriji igara ekvivalentan. Dantzig je pružio formalni dokaz u neobjavljenom izvještaju "Teorem o linearnim nejednakostima" 5. januara 1948. Dantzigov rad je postao dostupan javnosti 1951. godine. U poslijeratnim godinama, mnoge industrije su ga primjenjivale u svom svakodnevnom planiranju. mini|163x163piksel|Leonid Kantorovič
Reference
Vanjski linkovi
https://www.sciencedirect.com/science/article/pii/S0167924408700659 https://www.researchgate.net/publication/359740818_The_Evolution_of_Linear_Programming_Utilization_in_Supply_Chain_Management_Pre-pandemic_and_Pandemic_Period_Comparison https://www.sciencedirect.com/topics/engineering/linear-programming-problem
Kategorija:Matematička optimizacija Kategorija:Operativno istraživanje
Kategorija:Geometrijski algoritmi