Linjär programmeringsmatematik

Linjär programmering, matematisk modelleringsteknik där en linjär funktion maximeras eller minimeras när den utsätts för olika begränsningar. Denna teknik har varit användbar för att vägleda kvantitativa beslut inom affärsplanering, inom industriteknik och - i mindre utsträckning - inom samhälls- och fysikvetenskap.

optimering: Linjär programmering

Även om den allmänt användes nu för att lösa vardagliga beslutsproblem var linjär programmering relativt okänd före 1947. Inget arbete av någon betydelse

Lösningen av ett linjärt programmeringsproblem minskar till att hitta det optimala värdet (största eller minsta, beroende på problemet) för det linjära uttrycket (kallas objektfunktionen)

med förbehåll för en uppsättning begränsningar uttryckta som ojämlikheter:

A, b och c är konstanter som bestäms av kapacitet, behov, kostnader, vinster och andra krav och begränsningar av problemet. Det grundläggande antagandet vid tillämpningen av denna metod är att de olika förhållandena mellan efterfrågan och tillgänglighet är linjära; det vill säga, ingen av x _i är upphöjda till en annan än 1. För att erhålla lösningen på detta problem effekt, är det nödvändigt att hitta en lösning för systemet med linjära olikheter (dvs den uppsättning av n värden av variablerna x _i som samtidigt tillfredsställer alla ojämlikheter). Målfunktionen utvärderas sedan genom att substituera värdena på x- _i i ekvationen som definierar f.

Tillämpningar av metoden för linjär programmering försökades allvarligt i slutet av 1930-talet av den sovjetiska matematikern Leonid Kantorovich och av den amerikanska ekonomen Wassily Leontief inom områdena tillverkningsscheman och ekonomi, men deras arbete ignorerades i årtionden. Under andra världskriget användes linjär programmering i stor utsträckning för att hantera transport, schemaläggning och fördelning av resurser med vissa begränsningar såsom kostnader och tillgänglighet. Dessa applikationer gjorde mycket för att fastställa acceptabiliteten för denna metod, som fick ytterligare drivkraft 1947 med introduktionen av den amerikanska matematikern George Dantzigs simplexmetod, som kraftigt förenklade lösningen av linjära programmeringsproblem.

Då emellertid allt mer komplexa problem som involverade fler variabler försökte expanderade antalet nödvändiga operationer exponentiellt och överskred beräkningskapaciteten för även de mest kraftfulla datorerna. Sedan 1979 upptäckte den ryska matematikern Leonid Khachiyan en polynom-tidsalgoritm - där antalet beräkningssteg växer som en kraft i antalet variabler snarare än exponentiellt - vilket möjliggör lösningen av hittills otillgängliga problem. Men Khachiyans algoritm (kallad ellipsoidmetoden) var långsammare än simplexmetoden när den praktiskt tillämpades. 1984 upptäckte den indiska matematikern Narendra Karmarkar en annan algoritm för polynomisk tid, den inre punktmetoden, som visade sig konkurrenskraftig med simplexmetoden.