Programare liniară, tehnică de modelare matematică în care o funcție liniară este maximizată sau minimizată atunci când este supusă diferitelor constrângeri. Această tehnică a fost utilă pentru ghidarea deciziilor cantitative în planificarea afacerilor, în inginerie industrială și - într-o măsură mai mică - în științele sociale și fizice.
optimizare: programare liniară
Deși utilizat pe scară largă acum pentru a rezolva problemele de decizie de zi cu zi, programarea liniară a fost comparativ necunoscută înainte de 1947. Nici o lucrare care nu are nicio importanță
Soluția unei probleme de programare liniară se reduce la găsirea valorii optime (cea mai mare sau cea mai mică, în funcție de problemă) a expresiei liniare (numită funcție obiectivă)
sub rezerva unui set de constrângeri exprimate ca inegalități:
A's, s și c sunt constante determinate de capacitățile, nevoile, costurile, profiturile și alte cerințe și restricții ale problemei. Presupunerea de bază în aplicarea acestei metode este că diferitele relații dintre cerere și disponibilitate sunt liniare; adică niciunul din x i nu este ridicat la o altă putere decât 1. Pentru a obține soluția la această problemă, este necesar să se găsească soluția sistemului de inegalități liniare (adică setul de n valori ale variabilele x i care satisfac simultan toate inegalitățile). Funcția obiectivă este apoi evaluată substituind valorile x i în ecuația care definește f.
Aplicarea metodei de programare liniară a fost încercată serios pentru prima dată la sfârșitul anilor '30 de matematicianul sovietic Leonid Kantorovich și de economistul american Wassily Leontief în domeniile programelor de fabricație și, respectiv, ale economiei, dar munca lor a fost ignorată de zeci de ani. În timpul celui de-al Doilea Război Mondial, programarea liniară a fost utilizată pe larg pentru a trata transportul, programarea și alocarea resurselor supuse anumitor restricții, cum ar fi costurile și disponibilitatea. Aceste aplicații au făcut mult pentru a stabili acceptabilitatea acestei metode, care a obținut un impuls suplimentar în 1947, odată cu introducerea metodei simplex a matematicianului american George Dantzig, care simplifica foarte mult soluția problemelor de programare liniară.
Cu toate acestea, pe măsură ce s-au încercat probleme din ce în ce mai complexe care implică mai multe variabile, numărul operațiilor necesare s-a extins exponențial și a depășit capacitatea de calcul a chiar și a celor mai puternice computere. Apoi, în 1979, matematicianul rus Leonid Khachiyan a descoperit un algoritm de timp polinomial - în care numărul de pași de calcul crește ca o putere a numărului de variabile, mai degrabă decât exponențial - permițând astfel soluția unor probleme până acum inaccesibile. Cu toate acestea, algoritmul lui Khachiyan (numit metoda elipsoid) a fost mai lent decât metoda simplex atunci când a fost practic aplicat. În 1984, matematicianul indian Narendra Karmarkar a descoperit un alt algoritm al timpului polinomial, metoda punctului interior, care s-a dovedit competitiv cu metoda simplex.
