Lineáris programozási matematika

Lineáris programozás, matematikai modellezési technika, amelyben a lineáris függvényt maximalizálják vagy minimalizálják, amikor különféle korlátozásoknak vannak kitéve. Ez a technika hasznos volt a mennyiségi döntések irányításához az üzleti tervezésben, az ipari mérnöki munkában, és - kisebb mértékben - a társadalom- és a fizikatudományokban.

optimalizálás: Lineáris programozás

Annak ellenére, hogy széles körben használják a mindennapi döntési problémák megoldására, a lineáris programozás viszonylag ismeretlen volt 1947 előtt. Nincs jelentős jelentőségű munka

A lineáris programozási feladat megoldása a (vagyis objektív függvénynek nevezett) lineáris kifejezés optimális értékének a megállapításához (a problémától függően a legnagyobb vagy a legkisebb)

egy sor egyenlőtlenségben kifejezett korlátozás alatt:

Az a, b és c konstansok, amelyeket a probléma kapacitása, igényei, költségei, nyeresége és más követelmények és korlátozások határoznak meg. A módszer alkalmazásának alapfeltételezése az, hogy a kereslet és a rendelkezésre állás közötti különbségek lineárisak; vagyis az x _{i egyikét} sem növeli 1-nél nagyobb energiára. A probléma megoldásának megkereséséhez meg kell találni a lineáris egyenlőtlenségek rendszerének megoldását (vagyis az n x _i változók, amelyek egyszerre kielégítik az egyenlőtlenségeket). Ezután a célfüggvényt kiértékeljük az x _i értékeinek kicserélésével az egyenletet, amely meghatározza az f-et.

A lineáris programozás módszerének alkalmazását először az 1930-as évek végén a szovjet matematikus, Leonid Kantorovich és az amerikai közgazdász, Wassily Leontief próbálta meg a gyártási ütemterv és a közgazdaságtan területén, de munkájukat évtizedek óta figyelmen kívül hagyták. A második világháború alatt a lineáris programozást széles körben alkalmazták az erőforrások szállításával, ütemezésével és elosztásával, bizonyos korlátozásokkal, például a költségekkel és a rendelkezésre állással szemben. Ezek az alkalmazások nagyban hozzájárultak ennek a módszernek az elfogadhatóságához, amely 1947-ben további lendületet kapott az amerikai matematikus George Dantzig simplex módszerének bevezetésével, amely jelentősen egyszerűsítette a lineáris programozási problémák megoldását.

Mivel azonban egyre összetettebb, több változót érintő problémákat próbáltak megpróbálni, a szükséges műveletek száma exponenciálisan megnőtt és még a legerősebb számítógépek számítási képességét is meghaladta. Aztán, 1979-ben, Leonid Khachiyan orosz matematikus felfedezte a polinomiális idő algoritmust - amelyben a számítási lépések száma a változók számának hatalmaként növekszik, nem pedig exponenciálisan -, ezáltal lehetővé téve az eddig elérhetetlen problémák megoldását. Khachiyan algoritmusa (az úgynevezett ellipszoid módszer) lassabb volt, mint a simplex módszer, amikor azt gyakorlatilag alkalmazták. 1984-ben Narendra Karmarkar indiai matematikus felfedezte egy másik polinomiális idő algoritmust, a belső pont módszerét, amely versenyképesnek bizonyult a simplex módszerrel.