Linearno programiranje

Linearno programiranje je najstarija i jedna od metoda operacijskih istraživanja koja se najčešće primjenjuje u praksi.^[1]

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,^[2] i po kojem je nazvana metoda Fourier-Motzkinve eliminacije.

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.^[3] 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.^[3] 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.^[3] Dantzig je pružio formalni dokaz u neobjavljenom izvještaju "Teorem o linearnim nejednakostima" 5. januara 1948.^[4] Dantzigov rad je postao dostupan javnosti 1951. godine. U poslijeratnim godinama, mnoge industrije su ga primjenjivale u svom svakodnevnom planiranju.

Commons logo

Commons ima datoteke na temu: Linearno programiranje

Reference

↑ http://www.purplemath.com/modules/linprog.htm
↑ Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (3rd izd.). CRC Press. str. 1. ISBN 978-1498710169.
1 2 3 Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. str. xxvii. ISBN 0387948333. OCLC 35318475.
↑ George B. Dantzig (april 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Arhivirano s originala (PDF), 20. 5. 2015.

Vanjski linkovi

[1] ttp://www.purplemath.com/modules/linprog.htm

[SierksmaZwols2015-2] Gerard Sierksma; Yori Zwols (2015). Linear and Integer Optimization: Theory and Practice (3rd izd.). CRC Press. str. 1. ISBN 978-1498710169.

[:0-3] 1 2 3 Dantzig, George B.; Thapa, Mukund Narain (1997). Linear programming. New York: Springer. str. xxvii. ISBN 0387948333. OCLC 35318475.

[dantzig1982-4] George B. Dantzig (april 1982). "Reminiscences about the origins of linear programming". Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Arhivirano s originala (PDF), 20. 5. 2015.

[1]

[2]

[3]

[4]