Lineáris optimalizálás

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 nem lineáris vagy dinamikus optimalizálá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.

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?

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,03x+0,01y\geq 0,3$
$0,15x+0,10y\geq 2,25$
$0,02x+0,02y\leq 0,5$
Az $x$ és $y$ 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: $x\geq 0$, $y\geq 0$.

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 a megoldá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 például a következőképpen végezhetjük: felrajzoljuk a $0,03x+0,01y=0,3$, illetve $3x+y=30$ 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 $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 (például $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$
$P_{1}$	15	0	1500
$P_{2}$	25	0	2500
$P_{3}$	2,5	22,5	1375
$P_{4}$	5	15	1250

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 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 $'''c'''=(c_{1},c_{2},...,c_{n})$ 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(x_{1},x_{2},...,x_{n})=cx$ $\rightarrow$ minimum, $Ax\leq a$ és $x\geq 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}}$.