A lineáris programozás racionális elemzési és problémamegoldási technikák összessége, amelynek célja, hogy segítse a döntéshozókat számos változót érintő kérdésekben.
A lineáris programozás neve nem a számítógépes programok létrehozásából származik, hanem egy katonai kifejezésből, a programozásból, ami azt jelenti, hogy „terveket vagy időjavaslatokat kell készíteni a harci egységek kiképzésére, logisztikájára vagy bevetésére”.
Bár úgy tűnik, hogy a lineáris programozást G. Monge használta 1776-ban, L. V. Kantorovichot annak egyik alkotójának tekintik. Matematikai módszerek a szervezéshez és a gyártáshoz (1939) című könyvében mutatta be, és a tömegek átadásáról (1942) című munkájában fejlesztette ki. Kantorovich 1975-ben megkapta a közgazdasági Nobel-díjat az emberi erőforrások optimális elosztásának problémájához való hozzájárulásáért.
Az operációkutatás általában és különösen a lineáris programozás nagy lendületet kapott a számítógépeknek köszönhetően. Az egyik legfontosabb mozzanat a szimplex módszer megjelenése volt. Ez a módszer, amelyet G. B. Dantzig fejlesztett ki 1947-ben, egy algoritmus használatából áll a célfüggvény értékének optimalizálására, figyelembe véve a korlátozásokat. A megvalósítható régió egyik csúcsából indulva, például az A csúcsból, és alkalmazva a tulajdonságot: ha a célfüggvény nem éri el maximális értékét az A csúcsnál, akkor létezik egy él, amely az A csúcsból indul, és amely mentén a az objektív funkció növekszik. elér egy újabb csúcsot.
Az eljárás iteratív, mivel az egyes szakaszokban javítja a célfüggvény eredményeit, amíg el nem éri a kívánt megoldást. Ez egy olyan csúcson van, amelytől nem kezdődik olyan él, amely mentén az objektív függvény növekedne.
Bár ebben az egységben csak kétdimenziós lineáris programozási problémák vannak megoldva, ezt a típusú elemzést alkalmazzák azokban az esetekben, amikor több száz vagy akár több ezer változóról van szó.
Ennek az oktatási egységnek a tartalma Creative Commons licenc alatt áll, hacsak másként nem jelezzük.