Lineær programmeringsmatematikk

Lineær programmering, matematisk modelleringsteknikk der en lineær funksjon maksimeres eller minimeres når den utsettes for forskjellige begrensninger. Denne teknikken har vært nyttig for å lede kvantitative beslutninger i forretningsplanlegging, i industriell ingeniørarbeid, og - i mindre grad - i samfunns- og fysikkvitenskap.

optimalisering: Lineær programmering

Til tross for at det nå ble brukt mye for å løse daglige beslutningsproblemer, var lineær programmering relativt ukjent før 1947. Ingen arbeider av noen betydning

Løsningen av et lineært programmeringsproblem reduserer til å finne den optimale verdien (største eller minste, avhengig av problemet) for det lineære uttrykket (kalt objektfunksjonen)

underlagt et sett med begrensninger uttrykt som ulikheter:

A-, b- og c-er er konstanter bestemt av kapasitet, behov, kostnader, fortjeneste og andre krav og begrensninger i problemet. Den grunnleggende antagelsen i anvendelsen av denne metoden er at de forskjellige sammenhengene mellom etterspørsel og tilgjengelighet er lineære; det vil si, ingen av x _i er hevet til en annen enn 1. For å oppnå den løsning på dette problemet kraft, er det nødvendig å finne den løsning av det system av lineære ulikheter (det vil si den mengde med n-verdier av variablene x _i som samtidig tilfredsstiller alle ulikhetene). Den objektive funksjonen blir deretter evaluert ved å erstatte verdiene til x _i i ligningen som definerer f.

Anvendelser av metoden for lineær programmering ble først seriøst forsøkt på slutten av 1930-tallet av den sovjetiske matematikeren Leonid Kantorovich og av den amerikanske økonomen Wassily Leontief innen henholdsvis produksjonsplaner og økonomi, men arbeidet ble ignorert i flere tiår. Under andre verdenskrig ble lineær programmering mye brukt for å håndtere transport, planlegging og fordeling av ressurser underlagt visse begrensninger som kostnader og tilgjengelighet. Disse applikasjonene gjorde mye for å fastslå akseptansen av denne metoden, som fikk ytterligere drivkraft i 1947 med introduksjonen av den amerikanske matematikeren George Dantzigs enkle metode, som i stor grad forenklet løsningen på lineære programmeringsproblemer.

Da stadig mer kompliserte problemer som involverte flere variabler ble forsøkt utvidet antallet nødvendige operasjoner eksponentielt og overskredet beregningskapasiteten til selv de kraftigste datamaskinene. I 1979 oppdaget den russiske matematikeren Leonid Khachiyan en polynomtid-algoritme - der antall beregningstrinn vokser som en kraft av antall variabler i stedet for eksponentielt - og dermed tillater løsning av hittil utilgjengelige problemer. Imidlertid var Khachiyans algoritme (kalt ellipsoid-metoden) tregere enn simplex-metoden når den praktisk ble brukt. I 1984 oppdaget den indiske matematikeren Narendra Karmarkar en annen algoritme med polynomisk tid, den indre punktmetoden, som viste seg konkurrerende med simplex-metoden.