Lineær programmering, matematisk modelleringsteknik, hvor en lineær funktion maksimeres eller minimeres, når den udsættes for forskellige begrænsninger. Denne teknik har været nyttig til at vejlede kvantitative beslutninger inden for forretningsplanlægning, i industrielt ingeniørarbejde og - i mindre grad - inden for samfunds- og fysisk videnskab.
optimering: Lineær programmering
Selvom den nu er almindeligt anvendt til at løse daglige beslutningsproblemer, var lineær programmering relativt ukendt før 1947. Intet arbejde af nogen betydning
Løsningen af et lineært programmeringsproblem reducerer til at finde den optimale værdi (største eller mindste, afhængigt af problemet) af det lineære udtryk (kaldet objektivfunktionen)
underlagt et sæt begrænsninger, der udtrykkes som uligheder:
A'erne, b'erne og c'erne er konstanter bestemt af kapaciteter, behov, omkostninger, overskud og andre krav og begrænsninger i problemet. Den grundlæggende antagelse i anvendelsen af denne metode er, at de forskellige forhold mellem efterspørgsel og tilgængelighed er lineære; der er ingen af x i hæves til en anden end 1. For at opnå en løsning på dette problem magt, er det nødvendigt at finde løsningen af systemet af lineære uligheder (dvs. sæt af n værdier af variablerne x i, der samtidig tilfredsstiller alle uligheder). Den objektive funktion evalueres derefter ved at substituere værdierne af xi i ligningen, der definerer f.
Anvendelser af metoden til lineær programmering blev først alvorligt forsøgt i slutningen af 1930'erne af den sovjetiske matematiker Leonid Kantorovich og af den amerikanske økonom Wassily Leontief inden for henholdsvis produktionsplaner og økonomi, men deres arbejde blev ignoreret i årtier. Under 2. verdenskrig blev lineær programmering brugt i vid udstrækning til at håndtere transport, planlægning og fordeling af ressourcer underlagt visse begrænsninger, såsom omkostninger og tilgængelighed. Disse applikationer gjorde meget for at fastlægge acceptabiliteten af denne metode, der fik yderligere drivkraft i 1947 med introduktionen af den amerikanske matematiker George Dantzigs simplexmetode, der i høj grad forenklede løsningen af lineære programmeringsproblemer.
Da der blev forsøgt stadig mere komplekse problemer, der involverede flere variabler, blev antallet af nødvendige operationer udvidet eksponentielt og overskredet beregningskapaciteten på selv de mest kraftfulde computere. Derefter, i 1979, opdagede den russiske matematiker Leonid Khachiyan en polynomisk tidsalgoritme - hvor antallet af beregningstrin vokser som en magt i antallet af variabler snarere end eksponentielt - og derved muliggør løsning af hidtil utilgængelige problemer. Khachiyans algoritme (kaldet ellipsoidmetoden) var imidlertid langsommere end simplex-metoden, når den blev anvendt praktisk. I 1984 opdagede den indiske matematiker Narendra Karmarkar en anden algoritme med polynomisk tid, den indre punktmetode, der viste sig at være konkurrencedygtig med simplex-metoden.
