Optimumszámítás

Picture of matematikai alkalmazások

matematikai alkalmazások

Matematikai érdekességek, amelyek jól jöhetnek az érettségin vagy a felvételin is.

Alkalmazások
linprog

Oszd meg, ha tetszik!

Használjuk optimálisan az erőforrásokat

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.
A szimplex módszer már lényegében tetszőleges dimenzióban képes az optimális érték meghatározására, ha egyáltalán létezik. A lineáris programozás során előfordulhat, hogy nincs optimális megoldás, illetve az is lehetséges, hogy a megadott feltételek mellett több (akár végtelen sok) megoldás is van.
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ó.
A feladat bonyolultnak tűnik, pedig csak két alkatrészt, két terméket és a profitot vesszük figyelembe. Mi lehet egy autó-, vagy egy mobiltelefon gyárban? Térjünk vissza a példához és összegezzük az eddigieket egy táblázatban.
(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.
Azt könnyen beláthatjuk, hogy minél magasabban van a profit vonal, annál nagyobb összeget jelképez, ugyanis az összprofitot az \(y\) tengellyel vett metszéspontjának második koordinátája adja. Ezt a vonalat úgy szeretnénk megrajzolni, hogy a lehető legmagasabban húzzuk meg, hogy még érintse (vagy áthaladjon) a lila mezőn. Esetünkben a lila mező és a piros vonal közös pontja nem egész koordinátájú \((8,8;\,17,6)\), amely darabáru esetén csak úgy értelmezhető, hogy egy alacsonyabban lévő profit vonalat kell vizsgálnunk, amely áthalad a lila mezőn. Az egyszerűség kedvéért tekintsük most a termékeket ömlesztett árunak, például előkevert betonnak. Ebben az esetben a kapott \((8,8;\,17,6)\) csúcspont meghatározza az optimális mennyiséget, a gyártandó termékekből, hogy a profit maximális legyen, amelyet most már ki is tudunk számolni, \(P=246,4\) eFt.
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.
Előfordul, hogy a profit helyett a költségeket vizsgáljuk. Ekkor minden megfordul, nem az egyenesek alatti, hanem a feletti területeket tekintjük megvalósítható tartománynak, és a költség egyenesét a lehető legalacsonyabb helyzetbe szeretnénk mozgatni, hogy értéke minimális legyen (a lehető legalacsonyabb helyen metssze az \(y\) tengelyt).

Érdekességek

További alkalmazások

Most kedvező áron az előkészítő csomag

2023 iFeladatok I.

Interaktív feladatok felvételire és emelt szintű érettségire
4.590 Ft 2022/23 tanévre
  • 20 iFeladat automatikus javítással
  • 19 témakör
  • 121 megoldási lépés
  • Megoldássegítő felépítés
  • 2,15 átlagos nehézség (1-3 skálán)
  • A tananyag 2023. június 30-ig érhető el

2023 Emelt szintű
matematika előkészítő

Kidolgozott feladatok felvételire és emelt szintű érettségire
59.900 Ft 2022/23 tanévre
  • 25 kidolgozott témakör
  • Több mint 200 kidolgozott példa
  • 13 interaktív feladatsor
  • 21 elméleti összefoglaló
  • Felkészülés folyamatos követése, naplózása
  • 2024-től érvényes követelményekkel kiegészítve
  • 25 szóbeli tétel - teljes tételsor
  • A tananyag 2023. június 30-ig érhető el

2023 Középszintű matematika kurzusok

Tananyag középszintű matematika felkészüléshez
1.750 Ft 2022/23 tanévre, kurzusonként
  • Témakörönkénti előfizetés
  • Megértést segítő magyarázat
  • Definíciók, tételek
  • Kidolgozott típuspéldák
  • Online feladatok, azonnali javítással
  • Felkészülés folyamatos követése, naplózása
  • 2024-től érvényes követelmények alapján
  • A tananyag 2023. június 30-ig érhető el