Tantárgy » BMEVITMDV01
Optimalizálás és alkalmazásai
Optimalization and Its Applications
A tantárgyleírás hatályossága
Hatályosság kezdete:
2026. March 21.
Hatályosság vége:
—
| Tantárgy neve (magyarul, angolul) |
Optimalizálás és alkalmazásai
Optimalization and Its Applications
|
||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Tantárgykód | BMEVITMDV01 | ||||||||||||
| Tantárgyjelleg | — | ||||||||||||
| Képzési szint | — | ||||||||||||
| Kurzustípusok és óraszámok (heti/féléves) |
|
||||||||||||
| Tanulmányi teljesítmény/értékelés típusa | vizsga | ||||||||||||
| Tantárgy kreditértéke | 5 | ||||||||||||
| Tantárgyfelelős |
DR. Rétvári Gábor Ferenc
elérhetőség:
retvari.gabor@vik.bme.hu
|
||||||||||||
| Tantárgyat gondozó oktatási szervezeti egység |
Távközlési és Mesterséges Intelligencia Tanszék
|
||||||||||||
| Kar | Villamosmérnöki és Informatikai Kar | ||||||||||||
| Tantárgy weboldala | — | ||||||||||||
| Tantárgy elsődleges mintatantervi jellege | — | ||||||||||||
| Közvetlen előkövetelmények – Erős előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Gyenge előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Párhuzamos előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Mérföldkő előkövetelmény | nincs | ||||||||||||
| Közvetlen előkövetelmények – Kizáró feltétel | nincs |
Célkitűzés
Tantárgyprogram
- Bevezetés a numerikus optimalizálásba: alapfogalmak, feltételes és feltétel nélküli feladatok, célfüggvény(ek), osztályozás (lineáris, kvadratikus, nemlineáris, ...), az algoritmusok iteratív jellege. Modellezési technikák, a modellezés lépései, hibafüggvények. Konkrét műszaki problémák megfogalmazása optimalizálási feladatként (pl. hálózati útvonalválasztás, hálózattervezés, optimális szabályozás, készletoptimalizálás)
- A lineáris programozás alapjai. A lineáris programok általános formája. Példák. Lineáris és nemlineáris optimalizálási problémák megfogalmazása lineáris program formájában. A lineáris programmal modellezhető problémák általános jellemzői, példák és alkalmazások
- Lineáris programok megoldása: bevezetés a konvex analízisbe, poliéderek, lineáris programok grafikus megoldása, a szimplex tábla, bázismegoldások, a szimplex algoritmus, optimalitás, nemkorlátos megoldások, a degeneráció fogalma és kezelése, komplexitás. Példák megoldása a szimplex tábla segítségével
- Lineáris programok duáljai és a duál szimplex: Farkas lemmája, a dualitás fogalma, a duális előállítása, a dualitás gyenge és erős tétele, a duál szimplex algoritmus. Példák megoldása a duál szimplex segítségével
- A lineáris programozás klasszikus alkalmazásai: a szállítási probléma, az ütemezési probléma, hálózati folyamproblémák, folyamok egészértékűsége, többtermékes folyamok, duálisok, lineáris programok dekompozíciójának alapjai. A klasszikus alkalmazások, mint a híradástechnikai feladatok megoldásának modell esetei.
- Lineáris programok megoldása számítógépes programcsomaggal (labor): irodai alkalmazások (OpenOffice.org, MS Excel), matematikai szoftverek (GNU Octave, MATLAB), matematikai modellező nyelvek (GNU MathProg, AMPL), explicit megoldó szoftverek (GLPK, SAS-OR).
- Bevezetés az egészértékű lineáris programozásba: nevezetes kombinatorikus optimalizálási problémák megfogalmazása egészértékű lineáris program formájában, az egészértékű lineáris programok általános formája, komplexitás
- Egészértékű lineáris programok megoldása: egészértékű lineáris programok visszavezetése lineáris programra, teljes unimodularitás, a Gomory-féle duál-frakcionális vágások módszere, korlátozás és szétválasztás (branch-and-bound), korlátozás és vágás (branch-and-cut), a Lagrange-i relaxáció, esettanulmányok
- Egészértékű lineáris programok megoldása számítógépes programcsomaggal (labor): szöveges példák megfogalmazása és megoldása folytonos és egészértékű lineáris program formájában, gyakorlati korlátok
- Bevezetés a nemlineáris programozásba: a nemlineáris programok általános alakja. Az optimalitás szükséges és elégséges feltételei. Alkalmazások
- Nemlineáris programok megoldása: kvadratikus programok megoldása, feltételmentes optimalizálás, keresési és gradiens alapú algoritmusok (egy és többváltozós), nemlineáris programok visszavezetése feltételmentes optimalizálásra (megengedett irányok módszere, SUMT módszer)
- Globális optimum keresése/közeítése: mohó módszer, helyi/szomszédossági keresés, dinamikus programozás
- Általános optimalizáló metaheurisztikák: tabu-keresés, szimulált lehűtés (SA), genetikus/evolúciós algoritmus (GA), ILP és nemlineáris feladatok megoldása SA és GA módszerekkel
- Nemlineáris programok és metaheurisztikák megoldása számítógépes programcsomaggal (labor): GAMS és LEMON bemutatása.
A numerikus optimalizálási eljárások fontos szerepet töltenek be a műszaki feladatok megoldásában. A tárgy sok példán keresztül bemutatja a műszaki természetű -- kiemelten a villamosmérnöki tervezésben előforduló -- problémák megfogalmazását optimalizálási feladat formájában, majd a megoldási módszerek ismertetése után rámutat a tipikus modellezési hibákra is. Kiemelt hangsúlyt kap a lineáris programozás és az egészértékű programozás alapjainak elsajátítása, melyek segítségével vizsgáljuk az egyes optimalizálási feladatok sajátosságait. Bemutatjuk a nemlineáris, és a heurisztikus megoldó algoritmusokat is. A hallgatók megismerik a legelterjedtebb optimalizáló és modellező programcsomagokat, hogy a tanultakat a gyakorlatban kamatoztathassák.
Tanulmányi eredmények
Ez a tantárgy a KKK rendeletben meghatározott, következő kompetenciák fejlesztését szolgálja:
Tudás
Nincsenek rögzített tanulási eredmények.
Képességek
Nincsenek rögzített tanulási eredmények.
Attitűd
Nincsenek rögzített tanulási eredmények.
Autonómia és felelősség
Nincsenek rögzített tanulási eredmények.
Oktatási módszertan
Előadás
Tanulástámogató anyagok
Online források
Mokhtar S. Bazaraa, John J. Jarvis, Hanif D. Sherali, "Linear Programming and Network Flows" (2nd ed), Wiley-Interscience, 2004. Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin, "Network Flows: Theory, Algorithms, and Applications", Prentice Hall, 1993, 846 pages. Luenberger D. G., Ye Y., "Linear and Nonlinear Programming (3nd ed.), New York: Springer 2008, 544 pages Vizvári Béla, "Egészértékű programozás", Tankönyv, Budapest: Typotex 2006, 353 oldal Laurence A. Wolsey, "Integer Programming", Wiley and Sons, 1998
A tantárgy teljesítéséhez ajánlott előzetes ismeretek
Tudás típusú kompetenciák
(azon előzetes ismeretek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Képesség típusú kompetenciák
(azon előzetes képességek és készségek összessége, amelyek megléte nem kötelező, de a tantárgy eredményes teljesítését nagyban elősegíti)
nincs
Ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák
(azon ajánlott (nem kötelező) előzetesen megszerzendő kompetenciák összessége, amelyek jelentősen hozzájárulnak a tantárgy eredményes teljesítéséhez)
nincs
Általános szabályok
Követelmények:
a. A szorgalmi időszakban: 2 zárthelyi
b. A vizsgaidőszakban: írásbeli és szóbeli vizsga
c. Elővizsga: nincs
A 2 zárthelyinek külön-külön min. elégségesnek kell lennie.
Pótlási lehetőségek:
a szorgalmi időszak utolsó két hetének valamelyikében különeljárási díj fejében a zárthelyi pótolható abból a részből (részekből), amely nem sikerült. A zárthelyit (zárthelyiket) csak a szorgalmi időszakban lehet pótolni.
Teljesítményértékelési módszerek
Szorgalmi időszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Szorgalmi időszakban végzett teljesítményértékelések részaránya
Nincs megadva részarány.
Vizsgaidőszakban végzett teljesítményértékelések részletes leírása
Nincs megadva részletes értékelés.
Vizsgarészek részaránya
Nincs megadva részarány.
Érdemjegy megállapítása
Nincs megadva érdemjegy határ.
Jelenléti és részvételi követelmények
Nincs megadva jelenléti követelmény.
Javítás, ismétlés és pótlás különös szabályai
Nincs megadva.
Rövid leírás
Nincs megadva.
Részletes leírás
Nincs megadva.
Ajánlott tantárgyak
A következő tárgyak korábbi hallgatása esetén ez a tantárgy nem vehető fel:
VITMD097 Alkalmazott optimalizálás és játékelmélet
A tantárgy elvégzéséhez szükséges tanulmányi munka
Nincs megadva munkaidő bontás.
Tantárgykövetelmények hatályossága
Tantárgykövetelmények hatályosságának kezdete:
—
Tantárgykövetelmények hatályosságának vége:
—
Tantervi elhelyezés
Nincsenek rögzített tantervi elhelyezések ehhez a tárgyverzióhoz.