Lineáris optimalizálás

A Wikipédiából, a szabad enciklopédiából

A lineáris optimalizálás a lineáris algebra egy ága, 1940 után fejlődött ki az elektronikus számítástechnikával együtt. A közgazdászok és a matematikusok számára egyaránt fontos. Az elmélet megalkotói George Dantzig és Neumann János.

A lineáris optimalizálási probléma azt jelenti, hogy több keresett mennyiség lineáris függvényének szélsőértékét kell meghatározni, ha mellékfeltételként lineáris egyenlőtlenségek lépnek fel, és a keresett mennyiségeknek csak nem negatív értékei jönnek számításba.

Az iparban, a gazdaságban, a haditudományban sok olyan probléma van, amely optimalizálási feladatként fejezhető ki, vagy így közelíthető meg. Ismerünk például ellátási problémákat, keverési problémákat. Bizonyos játékok optimalizálási feladatokra vezethetők vissza.

A szállítási problémák – ide tartoznak a hozzárendelési problémák is – különösen egyszerű optimalizálási feladatok. A szállítási feladatok megoldására különleges módszerek vannak.

Amennyiben valamilyen lineáris optimalizációs feladat csak két ismeretlen mennyiséget tartalmaz, akkor grafikusan is megoldható. A számolással való megoldásra különböző eljárások léteznek, ezek elektronikus számítóberendezésekkel való megoldásokra is alkalmasak. A legismertebb a szimplex módszer, amelyet George Dantzig fejlesztett ki.

A lineáris optimalizációtól különböző, más optimalizációs módszerek is vannak, például a nemlineáris vagy dinamikus optimalizálás.

Általános optimalizációs feladatok[szerkesztés]

Az általános optimalizációs feladat tipikus példájaként egy ellátási problémát tárgyalunk.

A feladat kitűzése[szerkesztés]

Egy mezőgazdasági üzemben a sertéseket burgonyával és répával hizlalják. A burgonya 3% fehérjét és 15% szénhidrátot, a répa 1% fehérjét és 10% szénhidrátot, és mind a kettő 2% ásványi sót tartalmaz. A sertéseknek naponta legalább 0,3 t fehérjét és 2,25 t szénhidrátot kell fogyasztani, de a táplálékban nem szabad 0,5 t-nál több ásványi sónak lennie. 1 t burgonya 100 márkába kerül, 1 t répa 50 márkába. Milyen burgonya-és répamennyiség használható fel, hogy a hizlalás a legolcsóbb legyen?

Megoldás[szerkesztés]

Először is felírjuk az adatokat egyenletek, illetve egyenlőtlenségek formájában. A hizlalás napi összköltsége K, és függvénye. -t célfüggvénynek nevezzük:
.
-nak lehetőleg kicsinek kell lennie. Emellett azonban be kell tartani a mellékfeltételeket: a táplálékban legalább 0,3 t fehérjének és 2,25 t szénhidrátnak kell lennie, és nem szabad túl sok sót tartalmaznia. A százalékos adatokból tehát adódnak a mellékfeltételek:



Az és változók nemnegatívak,
(-negatív érték esetén a változó főegyütthatójának a negáltját kell venni-)
tehát érvényes a nemnegativitási feltétel: , .

Mivel a feladat csak két ismeretlen mennyiséget: -et és -t tartalmaz, grafikusan is megoldható. Ehhez -et és -t egy pont derékszögű koordinátáinak tekintjük, és az síkban azt a tartományt keressük, amelynek pontjai kielégítik a mellékfeltételeket és a nemnegativitási feltételt. Ez a megengedhető tartomány, mert a megoldáshoz csak olyan pontok jönnek számításba, amelyek a határán vagy a belsejében vannak.

meghatározását például a következőképpen végezhetjük: felrajzoljuk a , illetve egyenletű egyenest úgy, hogy két pontját, például a (0; 30) és a (10; 0) pontokat berajzoljuk és összekötjük egymással. Most megnézzük, hogy a (0; 0) pont kielégíti-e az eredeti egyenlőtlenséget. Itt az egyenlőtlenséget annak a félsíknak a pontjai elégítik ki, amely nem tartalmazza (0; 0) pontot. így egymás után végigmegyünk az összes feltételen, és az a tartomány, amelynek belsejében vagy határán egyidejűleg minden feltétel kielégül.

Végül még egy, egyenest rajzolunk be, ahol tetszés szerinti szám (például ). Majd meghatározzuk legkisebb értékét úgy, hogy ezt az egyenest addig toljuk el önmagával párhuzamosan, amíg -t érinti. A mennyiség a legkisebb értékét tehát vagy a egyik csúcspontjában veszi fel, vagy a egy határoló egyenesén. Az alábbi táblázatban, ahol mindegyik csúcspontjának koordinátái, és a célfüggvény ezekhez tartozó értékei vannak feltüntetve, megtalálható a megoldás: , ha , .

Naponta tehát 5 t burgonyát és 15 t répát kell a sertéseknek adni; ez adja a minimális 1250 márka költséget.

csúcspontjai
15 0 1500
25 0 2500
2,5 22,5 1375
5 15 1250

Egy probléma általános megfogalmazása[szerkesztés]

Az előbb kifejtett ellátási probléma általánosítható, ha a három táplálékféleségen kívül még tekintetbe kell venni például zsírt, vitaminokat. Ha ezenkívül még egyéb táplálékot is bevonunk, akkor általános lineáris optimalizációs problémát kapunk.

A lineáris optimalizáció minden feladata a következő normálalakba írható: adva van a sorvektor, az A mátrix és az a oszlopvektor:
, .
Keressük az
oszlopvektort a következő feltételek mellett:

minimum, és .

A fenti példában ez így alakul:
c=(100,50), , , .

Szállítási problémák[szerkesztés]

A feladat kitűzése[szerkesztés]

Az első szállítási terv[szerkesztés]

Optimalizációs kritérium[szerkesztés]

Egy szállítási terv javítása[szerkesztés]

Hozzárendelési probléma[szerkesztés]