Tiesinio programavimo matematika

Linijinis programavimas, matematinio modeliavimo technika, kurios metu linijinė funkcija yra maksimaliai padidinta arba sumažinta, kai patiriami įvairūs suvaržymai. Ši technika buvo naudinga priimant kiekybinius sprendimus planuojant verslą, pramonės inžinerijoje ir (mažesniu mastu) socialiniuose ir fiziniuose moksluose.

optimizavimas: Linijinis programavimas

Nors linijinis programavimas buvo plačiai naudojamas kasdienių sprendimų problemoms spręsti, iki 1947 m. Jis buvo palyginti nežinomas. Nėra jokio reikšmingo darbo

Linijinio programavimo uždavinio sprendimas sumažina iki optimalios (didžiausios arba mažiausios, atsižvelgiant į problemą) tiesinės išraiškos vertės (vadinamos objektyvo funkcija) radimo.

kuriems taikomi apribojimai, išreikšti kaip nelygybė:

A, b ir c yra konstantos, kurias lemia problemos pajėgumai, poreikiai, išlaidos, pelnas ir kiti reikalavimai bei apribojimai. Pagrindinė šio metodo taikymo prielaida yra ta, kad įvairūs paklausos ir prieinamumo santykiai yra tiesiniai; tai yra, nė vienas iš x _i nėra padidinamas iki kitos galios nei 1. Norint gauti šios problemos sprendimą, reikia rasti tiesinių nelygybių sistemos sprendimą (tai yra n reikšmių aibės kintamieji x _i, kurie tuo pačiu patenkina visas nelygybes). Tada objektyvo funkcija įvertinama pakeičiant x _i reikšmes lygtyje, apibrėžiančioje f.

Linijinio programavimo metodą pirmą kartą rimtai bandė pritaikyti 1930-ųjų pabaigoje sovietų matematikas Leonidas Kantorovičius ir amerikiečių ekonomistas Wassily Leontief atitinkamai gamybos grafikų ir ekonomikos srityse, tačiau jų darbai buvo ignoruojami dešimtmečius. Antrojo pasaulinio karo metu linijinis programavimas buvo plačiai naudojamas ištekliams vežti, planuoti ir paskirstyti, atsižvelgiant į tam tikrus apribojimus, tokius kaip išlaidos ir prieinamumas. Šios programos labai padėjo nustatyti šio metodo priimtinumą, kuris dar labiau paspartėjo 1947 m., Įvedus amerikiečių matematiko George'o Dantzigo simplekso metodą, kuris labai supaprastino linijinio programavimo problemų sprendimą.

Tačiau, kadangi buvo bandoma vis sudėtingesnių problemų, apimančių daugiau kintamųjų, būtinų operacijų skaičius išsiplėtė eksponentiškai ir viršijo net galingiausių kompiuterių skaičiavimo galimybes. Tuomet, 1979 m., Rusų matematikas Leonidas Khachiyanas atrado polinomo laiko algoritmą, kuriame skaičiavimo žingsnių skaičius auga kaip kintamųjų skaičiaus galia, o ne eksponentiškai, ir tai leido išspręsti iki šiol neprieinamas problemas. Tačiau Khachiyan algoritmas (vadinamas elipsoido metodu) buvo lėtesnis nei simplekso metodas, kai buvo praktiškai pritaikytas. 1984 m. Indijos matematikė Narendra Karmarkar atrado kitą polinominio laiko algoritmą - interjero taško metodą, kuris pasirodė esąs konkurencingas taikant simplekso metodą.