Operációkutatási fogalomtár PDF Nyomtatás E-mail

A Fogalomtár abban segíthet Önnek, hogy a szokatlan vagy ismeretlen szakmai kifejezéseknek a pontos jelentését kikereshesse. Tudjuk, hogy egy ilyen gyűjtemény soha nem lehet teljes, de igyekszünk folyamatosan bővíteni, hogy segítsük az Ön munkáját.



Alapfeladat
Érzékenységvizsgálat
Globális Optimum
Hozzárendelési feladat
Konvex függvény
Konvex tartomány
Lineáris kombináció
Lokális optimum
LP


Magyar módszer
Megengedett megoldás
MILP
MINLP
NLP
Operációkutatás (Operation Research - OR)
Szállítási feladat
Utazó Ügynök Probléma


* * *

Alapfeladat

A feladatban van n db folytonos x = (x1, ... xn) és m db bináris y = (y1, ... ym) változó. Van egy célfüggvény f(x,y), és egy feltételhalmaz, amely egyenlőtlenségekkel van megadva: g(x,y)<=0. A feladat megtalálni azon (x,y) értékeket, amelyek teljesítik a feltételeket, és a célfüggvény értéke minimális rajta.




Érzékenységvizsgálat

Azt vizsgálja, hogy egy optimalizálási feladat (x,y) megoldása hogyan változik a feladat paramétereinek változásával. Főbb fajtái: árnyékár, redukált költség.

Bővebben lásd:
http://www.sce.carleton.ca/faculty/chinneck/po/Chapter6.pdf (angol nyelvű)

 



Globális optimum

Olyan (x,y) megoldása egy optimalizálási feladatnak, amely az egész térben optimális.

(x,y) globális optimuma az alapfeladatnak, ha




Hozzárendelési feladat

A kombinatorikus optimalizálás egyik típusfeladata. Van két halmazunk, melyeknek az elemeit szeretnénk összepárosítani úgy, hogy egy elem csak egy párban szerepelhet (Pl. munkákat és gépeket kell összepárosítani.). Minden párosnak van egy költsége (pl. az adott munka elvégzésének ideje az adott gépen). A feladatunk megtalálni azt a párba rendezést (párosítást), amelyben a párok összköltsége (összes munkaidő) minimális. A leghatékonyabb megoldó algoritmus a feladatra a Magyar módszer.

         



Konvex függvény

Egy függvényt konvexnek nevezünk egy konvex tartományon, ha bármely, a tartományban levő két pont függvényértékét összekötő szakasz a függvény grafikonja fölött megy.





Konvex tartomány

Egy tartományt akkor nevezünk konvexnek, ha bármely két pontját összekötő szakaszt teljes egészében tartalmazza a tartomány.





Lineáris kombináció

Az a1, a2,...,an számok lineáris kombinációi azok a számok, amiket megkaphatunk az a1, a2,...,an-ből úgy, hogy beszorozzuk őket egy-egy (nem feltétlenül azonos) konstanssal, majd ezeket a szorzatokat összeadjuk.




 

Lokális optimum

Olyan (x,y) megoldása egy optimalizálási feladatnak, amely egy kis környezetben optimális, de az egész térben nem az.

(x,y) lokális optimuma az alapfeladatnak, ha



 

LP – lineáris programozási feladat

Egy alapfeladat lineáris, ha benne a célfüggvény és a feltételtér is lineáris, továbbá nincsenek benne bináris változók. Ez az optimalizálási feladatok közül a legegyszerűbb típus, amelyre gyors és hatékony algoritmusok léteznek (pl. szimplex-tábla).




 

Magyar módszer

A hozzárendelési feladat leghatékonyabb megoldó algoritmusa, melyet Harold W. Kuhn fejlesztett ki 1955-ben. Nevét Kőnig Dénes és Egerváry Jenő tiszteletére kapta, akinek az algoritmus alapjául szolgáló javítóutas eljárás köszönhető.

Bővebben lásd:

1. http://www.cs.ust.hk/~golin/COMP572/Notes/Matching.pdf (angol nyelvű)

2. http://www.math.uwo.ca/~mdawes/courses/344/kuhn-munkres.pdf (angol nyelvű)

 



Megengedett megoldás

Azok a lehetséges megoldásai egy optimalizálási feladatnak, amelyek eleget tesznek a benne szereplő feltételeknek.

Az alapfeladat esetében azon (x,y) pontok halmaza, amelyekre


teljesül.




MILP – vegyes értékű lineáris programozási feladat

Egy alapfeladat vegyes értékű lineáris, ha benne a célfüggvény és a feltételtér is lineáris, továbbá vannak benne bináris változók. Vannak hatékony algoritmusok, de nagy méretű feladatra lassúak.





MINLP – vegyes értékű nemlineáris programozási feladat

Egy alapfeladat vegyes értékű nemlineáris, ha benne a célfüggvény és a feltételtér sem lineáris, és vannak benne bináris változók (alapfeladat). Az optimalizálási feladatok között a legnehezebbek közül való, de léteznek rá közelítő algoritmusok.





NLP

Egy alapfeladat nemlineáris, ha benne a célfüggvény és a feltételtér sem lineáris, de nincsenek benne bináris változók. Az ilyen típusú feladatok általában megoldhatóak, de minden feladatra univerzálisan alkalmazható hatékony algoritmus nincs. Speciális fajtáira vannak hatékony közelítő algoritmusok (pl. Newton-módszer, gradiens-módszer).




 

Operációkutatás (Operation Research - OR)

A matematikát több területre bonthatjuk (például algebra, analízis). Az egyik ilyen részterület az operációkutatás, ahova elsősorban a matematikai programozás tartozik, de ide sorolják a kibernetikát és a vezérléselméletet is. A matematikai programozás legfontosabb része az optimalizálási feladatok megoldhatóságának vizsgálata és hatékony megoldása.

Bővebben lásd:

http://hu.wikipedia.org/wiki/Matematika

 



Szállítási feladat

 



 


 

Utazó Ügynök Probléma

A kombinatorikus optimalizálás egyik típusfeladata. Az alapprobléma: n db várost kell bejárnia egy ügynöknek úgy, hogy a lehető legkevesebbet utazzon, és mindenhova pontosan egyszer menjen, azaz az útvonalát kell optimalizálni. Sok ipari feladat is erre vezethető vissza. (Pl. gépsoron a műveletek elrendezése úgy, hogy a műveletek közötti átállási idő összességében a lehető legkevesebb legyen.)