Többféle méretű egységdobozokkal kell megtölteni egy kamion rakterét. A rendelkezésre álló erőforrásokkal, alapanyagokkal kell gyártanunk termékeket, hogy a költség minimális, vagy a profit maximális legyen. Banki hitelek mögé kell szétosztani (allokálni) biztosítékokat, hogy a legkisebb hitelrész legyen fedezetlen. Ez csak néhány példa mindennapokból, amikor bizonyos korlátozó feltételek, peremfeltételek mellett kell egy előre meghatározott, függvénnyel leírható célértéket maximalizálni vagy éppen minimalizálni. Ha nagyon le szeretnénk egyszerűsíteni, akkor a korlátozó tényezőket, a lehetőségeink halmazát az egyes források tekintetében elsőfokú egyenlőtlenségekkel írhatjuk le. A célfüggvény az erőforrásaink felhasználásával elkészített produktum valamilyen tulajdonságát írja le, amelyet adott esetben minimalizálni, máskor maximalizálni szeretnénk. Egyszerű esetben egy koordináta rendszerben is le tudjuk írni a feladat megoldását, és lényegében három egyenessel megoldhatjuk a problémát. Az ilyen típusú problémákkal a lineáris programozás foglalkozik, amelynek talán az egyik legismertebb eljárása a szimplex módszer.
Elgondolkodtál már azon, hogy a felvételinél, az adott egyetemeken, főiskolákon lévő férőhelyekre hogyan osztják szét a felvételizőket, saját rangsorukat is figyelembe véve? Igen, ezt is lineáris programozással oldják meg. Természetesen azt szeretnénk, ha a felsőoktatásban lévő minden férőhely betöltésre kerülne, és a lehető legtöbb diák az általa felállított rangsornak megfelelő helyre jutna be. A megoldás a felvételi pontok rendszere, amely “mérhetővé teszi” a teljesítményt, amely alapján a besorolás történik. A felvételi rendszere ebből a szempontból meglehetősen összetett, ezért nem is célunk ezt jobban részletezni. A fenti kitekintő mellett egy konkrét példát veszünk majd végig, amely segít megérteni a lineáris programozás alapját, és még a gyakorlati hasznát is könnyű ezzel a példával megvilágítani.
Egy gyárban A és B terméket gyártanak, amelyek előállításához két alkatrészt szerelnek össze, azonban az egyes termékek eltérő arányban tartalmazzák az alkatrészeket. Az elkészült árut természetesen eladják, amely nyereséget termel az üzemnek. A profit mértéke eltérő a két termék esetén. Az egyes alkatrészekből korlátos mennyiség áll rendelkezésre. A cél pedig, hogy a lehető legmagasabb profitot érje el a gyártó.
| (db) | Az egyes termékek alkatrészigénye | Alkatrészek raktárkészlete | |
|---|---|---|---|
| A termék | B termék | ||
| 1. alkatrész | 1 db/termék | 2 db/termék | 44 db van készleten |
| 2. alkatrész | 3 db/termék | 1 db/termék | 44 db van készleten |
| Maximalizálandó cél | |||
| Profit | 8 eFt/db | 10 eFt/db | – |
| eFt = ezer forint | |||
Most már fel tudjuk írni azokat az összefüggéseket, amelyek a korlátokat, peremfeltételeket jelentik, illetve a célfüggvényt is.
\[
\begin{aligned}
2B+A&\leq 44\quad (1.)\\
B+3A&\leq 44\quad (2.)\\
10B+8A&=P\quad (3.)\\
\end{aligned}\notag
\]
Nézzük meg az \((1.)\) egyenlőtlenség jelentését. \(44\) db 1-es típusú alkatrészünk van raktáron, amely felhasználását összesítjük, azaz minden \(A\) termékhez felhasználunk \(1\)-et és minden \(B\) termékhez \(2\)-t belőle. A \((2.)\) egyenlőtlenség hasonlóan értelmezhető. A \((3.)\) egyenlet pedig a profitot mutatja, azaz 8.000 forintot keres a cég az \(A\) termék, és \(10.000\) forintot a \(B\) termék eladásával. A célunk, hogy ezt maximalizáljuk. Az első két egyenletben azért van egyenlőtlenség jel, mert a feltételek alapján minden gyártási párosítás megfelelő, amely maximum 44 alkatrészt használ fel. A profitot nem ismerjük, csak azt, hogy milyen arányban járul hozzá a két termék. Átrendezzük az egyenlőtlenségeket és ábrázoljuk őket.
\[
\begin{aligned}
2B&\leq -A+44\quad \text{kék terület}\\
B&\leq -3A+44\quad \text{piros terület}\\
B&=-\frac{8}{10}A+\frac{P}{10}\quad \text{piros vonal}\\
\end{aligned}\notag
\]
A kék és piros háromszögek közös lila része mutatja azon pontok halmazát, amely mindkét peremfeltételt, a két termék gyártása során a teljes alkatrészigényt figyelembe veszi, azaz a két termékből az ilyen mennyiségű gyártás együttesen megvalósítható a raktárkészletből. A piros vonal helyzetét tekintve egy kicsit már előre szaladtunk. Jelenleg csak annyit tudunk, hogy ezzel a vonallal párhuzamos, ugyanis meredekségét meghatározza az egyes termékeken elérhető profit hányadosa.
Természetesen figyelembe vehetnénk több alapanyagot is a gyártás során, amelyek további peremfeltételeket határoznának meg, ezzel bővítve a színes területek számát. Gyakran a megvalósítható tartomány egy sokszög, amelyhez ha ábrázoljuk a profit egyenesét, akkor azt addig kell eltolni, hogy az csak érintse a sokszöget (ez jelenti a maximumot). Könnyű belátni, hogy előfordulhat olyan eset, amikor a profit egyenese nem egy csúcsra, hanem egy oldalra illeszkedik. Ilyenkor nem egyértelmű a megoldás, végtelen sok optimális hely van. Ezek között közömbös a választás a megadott feltételek és célfüggvény mellett.
Copyright © iMatek 2020-2025 – Minden jog fenntartva
