Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics

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.

• 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.

• 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