Lineáris optimalizálás

A Wikipédiából, a szabad lexikonbó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 G. B. 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 pl. 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 G. B. Dantzig fejlesztett ki.

A lineáris optimalizációtól különböző, más optimalizációs módszerek is vannak, pl. a nem lineáris vagy dinamikus optimalizálás.

Tartalomjegyzék

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

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

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

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 x burgonya-és y répamennyiség használható fel, hogy a hizlalás a legolcsóbb legyen?

[szerkesztés] Megoldá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, x és y függvénye. K-t célfüggvénynek nevezzük:
K = K(x;y) = 100x + 50y.
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:
0,3x+0,01y \ge0,3
0,15x+0,10y \ge2,25
0,02x+0,02y \le0,5
Világos továbbá, hogy az x és y változók negatív értékeinek nincs értelme, ezért érvényes a nemnegativitási feltétel: x \ge0, y \ge0.

Mivel a feladat csak két ismeretlen mennyiséget: x-et és y-t tartalmaz, grafikusan is megoldható. Ehhez x-et és y-t egy pont derékszögű koordinátáinak tekintjük, és az (x;y) síkban azt a G 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 amegoldáshoz csak olyan (x;y) pontok jönnek számításba, amelyek a G határán vagy a belsejében vannak.

G meghatározását pl. a következőképpen végezhetjük: felrajzoljuk a 0,3x + 0,01y = 0,3, illetve 3x + y = 30 egyenletű egyenest úgy, hogy két pontját, pl. 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 G 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, K = 100x + 50y = c egyenest rajzolunk be, ahol c tetszés szerinti szám (pl. c = 500). Majd meghatározzuk c legkisebb értékét úgy, hogy ezt az egyenest addig toljuk el önmagával párhuzamosan, amíg G-t érinti. A c mennyiség a legkisebb értékét tehát vagy a G egyik csúcspontjában veszi fel, vagy a G egy határoló egyenesén. Az alábbi táblázatban, ahol G mindegyik csúcspontjának koordinátái, és a K(xy) célfüggvény ezekhez tartozó értékei vannak feltüntetve, megtalálható a megoldás: K = 1250, ha x = 5, y = 15.

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.

G csúcspontjai x y K(x;y
P1 15 0 1500
P2 25 0 2500
P3 2,5 22,5 1375
P4 5 15 1250

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

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 pl. 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 '''c''' = (c1,c2,...,cn) sorvektor, az A mátrix és az a oszlopvektor:
A=\left( \frac{a_{11}...a_{1n}}{a_{m1}...a_{mn}} \right), a=\left( \frac{a_1}{a_m} \right).
Keressük az
x=\left( \frac{x_1}{x_n} \right) oszlopvektort a következő feltételek mellett:

K = K(x1,x2,...,xn) = cx \rightarrow minimum, Ax \le a és x \ge 0.

A fenti példában ez így alakul:
c=(100,50), A=\begin{pmatrix} -0,03 & -0,01 \\ -0,15 & -0,10 \\ 0,02 & 0,02 \end{pmatrix}, a=\begin{pmatrix} -0,3 \\ -2,25 \\ 0,5 \end{pmatrix}, x=\begin{pmatrix} x \\ y \end{pmatrix}.

[szerkesztés] 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