1. Operáció kutatás Az operáció kutatás 1940 ó ta ismeretes. Bár a technikai fejlő dés, a termelési folyamatok szervezése már korábban is igényelte a matematikai eszkö zö k felhasználását, - amelyekben fellelhető k az operáció kutatás sajátosságai - tudatos alkalmazására a II világháború folyamán került sor. Első sorban katonai célokra használták. A második világháború után előszö r a hadseregben, majd a gazdasági életben is teljes polgárjogot nyert. Tö bb meghatározás ismert a fogalmára. Az operáció kutatás nem külö n tudományág, hanem tudományos magatartás a szervezési, gazdasági, mű szaki jelenségekkel szemben. A műszaki, gazdasági és szervezési folyamatok, jelenségek vizsgálatát jelentő sen megkö nnyíthetjük, ha a rendelkezésünkre álló - sokszor igen nagyszámú - alapadatokat az ismert matematikai eszkö zö k felhasználásával rendszerbe foglaljuk és kezelhető vé tesszük. Az operáció kutatásra első sorban az jellemző , hogy tudományos eszkö zö ket, mó dszereket, valamint korszerű technikát alkalmaz. Első ként a matematikát kell megemlíteni, amely az operáció kutatás leghatékonyabb tudományos eszkö ze. Fontos szerepet játszik még a matematikai statisztika és számítástechnika. Az adott folyamat, jelenség szempontjábó l alapvető cél a lehető legjobb megoldás kiválasztása, tehát valamilyen optimum elérése. Az ipari, gazdasági szervezetek szö vevényes volta miatt ezt a célt csak tudományos alapokon fekvő módszerekkel lehet biztosítani. Az operáció kutatás jellegzetessége, hogy mindig egy jól körülhatárolható teljes rendszerre vonatkozik. Ilyen alapon,, a legkülönbözőbb ipari, közeledési, igazgatási stb. rendszerekre alkalmazható . Az operációkutatás definíciója : Az operáció kutatás tudományos eszkö zö kkel, technikával, mó dszerekkel vizsgálja valamely rendszer műkö désével kapcsolatos problémákat abbó l a célból, hogy az optimális megoldást meghatározza. Tehát a dö ntések meghozatalához ad igen nagy segítséget az operáció kutatás során kidolgozott elképzelés. Innen származik az a megfogalmazás, hogy az operáció kutatás a döntések előkészítésének tudománya.
2. Gráfelméleti alapfogalmak Gráf: Egy hálózatot (gráfot) a csúcsok N halmaza és az élek E halmaza definiál G
( N , E) .
Digráf: irányított hálózat (x,y) x=kezdőpont y=végpont ( y, x) E , él=csúcspontok rendezett párja, amely megadja a két csúcspont közötti mozgás lehetséges irányát; Lánc: élek olyan sorozata, amelyben az egymást követő bármely két élnek egyetlen közös csúcsa van. Út: olyan lánc, amelyben az utolsó él kivételével mindegyik él végpontja azonos a sorozatban következő él kezdőpontjával. Legyen [N,E] digráf és legyen s,t N Legyen x0 , x1 ,...., xk 1 , xk ...xm pontsorozat melyre x0 Ekkor Ps
azt s
t
s , xm
mondjuk,
x1 , x2 .....x p
t és xk 1, xk
hogy
t
( x1 , x2 )( x2 , x3 )....( x p 1 , x p )
x0 , x1....xm
Legyen lij
N olyan
A minden i=1..m esetén. egy
s-ből
t-be
vezető
út
( xi , x j ) szakasz hossza az s pontból a p 1
t pontba menő út hossza l ( Ps t ) l ( x1 , x2 ) l ( x2 , x3 ) ... l ( x p 1 , x p )
l ( xi , xi 1 ) i 1
Kör: olyan út amelynek kezdő és végpontja azonos Vágás: legyen [N,E] digráf és osszuk az N ponthalmazt az S,T diszjukt (két halmaz metszete zérus) két nem üres halmazra Jelöljék (S,T)-vel azon élek összességét amelyek S-ből indulnak és T-be érkeznek Az (S,T) élhalmazt az [N,E] digráf (S,T) vágásának nevezzük S T N S T 0 Elválasztó vágás: ha s, t N pontok olyanok, hogy s S és t T akkot azt mondjuk, hogy (S,T) vágás az s,t pontokat elválasztja S T N S T 0
3. Hálózat és ezen megfogalmazott feladatok A hálózati folyamok témakörben olyan optimalizálási feladatokkal foglalkozunk, amelyek gráfok ill. hálózatok segítségével is megfogalmazhatók, ebből következőleg gráfelméleti eszközökkel is kezelhetők. Bevezetésképpen tekintsük az alábbi egyszerű szállítási feladatot. Három termelőtől (T) akarunk elszállítani bizonyos árut négy fogyasztóhoz (F). Valamilyen oknál fogva a , , viszonylatokban nem lehet szállítani. A termelőktől a fogyasztókhoz rendre 30, 50, 40 teherautónyi elszállítandó mennyiségű árut kell elszállítani. A fogyasztók igénye rendre 40, 20, 50, 30 teherautónyi mennyiségű áru. A fenti adatokat a termelők kínálatának ill. a fogyasztók keresletének szoktuk nevezni. Az alábbi táblázat mutatja, hogy a termelők telephelye és a megrendelőhelyek között egy teherautónyi mennyiségű árut mekkora költséggel szállíthatunk el. A tiltott viszonylatokat a táblázatban „-” jellel jelöltük.
Feladatunk a következő: Adjuk meg azt a szállítási tervet, amelynél az áruk a termelőktől a fogyasztókhoz történő elszállítása a legkisebb költséggel valósul meg! A feladat matematikai megfogalmazását az alábbiakban adjuk meg. A matematikai megfogalmazáshoz három dolgot kell meghatároznunk, ezek a következők: döntési változó megállapítása, a döntési változók lehetséges értékeit meghatározó feltételek felírása, végül annak a függvénynek a felírása, amelynek értéke szerint döntünk a lehetséges megoldások közül (ezt a függvényt célfüggvénynek nevezzük). 1. Döntési változó megállapítása:
Legyen a döntési változó az, hogy az egyes telephelyekről az egyes megrendelőhelyekre mennyi teherautónyi árumennyiséget szállítunk. Jelöljük ezeket az kétindexes változókkal, amely a termelőtől az fogyasztóhoz szállított mennyiséget mutatja. A döntési változókat az alábbi táblázatba foglalhatjuk.
2. Feltételek meghatározása:
Természetes feltétel, hogy az összes döntési változó nemnegatív. Először a kínálati feltételeket határozzuk meg. Az egyes termelőktől elszállítandó mennyiséget az egyes sorokban lévő döntési változók összege adja, amelynek egyenlőnek kell lenni a termelők kínálatával. A keresleti feltételek meghatározásánál figyelembe kell venni, hogy a termelők összkínálata kisebb, mint a fogyasztók összkereslete ( ), így a fogyasztók nem
mindegyikének az igényét lehet teljes mértékben kielégíteni. Az egyes fogyasztókhoz szállítandó mennyiséget az egyes oszlopokban lévő döntési változók összege adja, amely kisebbnek vagy egyenlőnek kell lenni a fogyasztók keresletével. 3. Célfüggvény meghatározása:
Tegyük fel, hogy a szállítási költség lineárisan változik a szállítandó mennyiséggel. Jelölje a szállítási egységköltséget a termelőtől az fogyasztóhoz, ekkor a termelőtől az fogyasztóhoz az mennyiségű áru szállítási költsége . Itt vettük figyelembe a linearitási feltételezést. A szállítás összköltsége pedig az egyes viszonylatok szállítási költségének az összege. A probléma matematikai modellje tehát a következő:
A termelőket, a fogyasztókat egy-egy „ponttal”, az egyes termelők és fogyasztók közötti szállítási kapcsolatot pedig egy-egy nyíllal reprezentálhatjuk a síkon. Ezt mutatja az alábbi ábra.
A fenti alakzatot gráfnak, pontosabban irányított gráfnak nevezzük. Amennyiben a kapcsolatokra ráírjuk a szállítási egységköltségeket, akkor hálózatot kapunk. A fentebb felírt szállítási feladat egy lineáris programozási feladat, így a lineáris programozás ismert módszereinek bármelyikével megoldható. Viszont azt is tudjuk, hogy ez egy rendkívül speciális szerkezetű lineáris programozási feladat, mivel az együtthatómátrixa csupán 0 és 1 értékeket tartalmaz és ezeket is megfelelő szabályossággal. A szállítási feladat tehát speciális szerkezeténél fogva gráfok segítségével is reprezentálható.
4.Legrövidebb úttal kapcsolatban megfogalmazott feladatok, faépítő algoritmus A probléma megfogalmazása
A P út hosszával kapcsolatban leggyakrabban a következő feladatokat fogalmazzuk meg: a. Határozzuk meg az rögzített pontok között azt a Pst utat, amelyre (1.1) minimális.Vts∈, b. Határozzuk meg a rögzített pontból a hálózat összes (vagy röviden ) pontjába a legrövidebb Psi utakat. (Ez az ún. minimális kifeszítő fa.) Vs∈ Vai∈ Vi∈ c. Keressük meg a hálózat minden (röviden ) pontpárja között a Pij legrövidebb hosszúságú utakat, azaz határozzuk meg a multiterminális minimális hosszúságú utat az adott irányított gráfban. Vaaji∈, Vji∈, d. Határozzuk meg a fenti a–c feladatok valamelyik változatára az első k számú legrövidebb utat, amelyet arra használunk, hogy a felhasználó a saját tapasztalata alapján a beduguló legrövidebb út után a második, harmadik, stb. legrövidebb utat választja. Megjegyezzük, hogy az a. és a b. feladat csak az elérendő cél szempontjából különbözik, a két feladatot azonos eljárásokkal oldhatjuk meg. A c. feladat az a. vagy b. feladatokat megoldó algoritmusok többszöri alkalmazásával is megoldható.
A szakirodalomban a feladat fontosságának megfelelően sokszáz cikk található a problémakörrel kapcsolatban. A sokféle módszer közül itt csak az alapvető eljárásokat és a közlekedési hálózatok céljaira kifejlesztett, tárolási és futási idő szempontjából leggazdaságosabb eljárásokat ismertetem. További részletes összefoglaló olvasható még a [21, 22, 39, 41, 54, 80], szakirodalmakban.
1.2. Minimális hosszúságú út két pont között Itt az pontból a pontba menő legrövidebb út meghatározásával foglalkozunk. A különbség a minimális kifeszítő fával szemben az algoritmus befejezésében van. Itt az algoritmus befejeződik, ha a t pont végleges potenciál értéket kapott, . A másik esetben az algoritmus befejezésének feltétele . Vs∈ Vt∈ Tt∈esetén ,VaTaii∈∀∈
1.3. Faépítő módszerek A fejezetben tárgyalt módszerek mindegyike egy minimális összhosszúságú (Shortest Path – SP) fát határoz meg. Ennek csúcspontja egy előre rögzített s pont, amely tartalmazza a hálózat összes pontját (ha a hálózat összefüggő), és az s pontból bármelyik pontig a legrövidebb Psi útvonalból áll. Ezt a fát s gyökérpontú minimális hosszúságú kifeszítő fának, röviden minimális fának nevezzük. Ezek az algoritmusok a fentiekben megfogalmazott a. és b. feladat megoldását szolgáltatják. Ha minden -re végrehajtjuk az algoritmust, akkor a c. feladat megoldását is megkapjuk.Vi∈ Vi∈ Vs∈8
határozzuk meg az s-ből t pontba menő legrövidebb utat határozzuk meg s-ből az összes többi pontba vezető legrövidebb utat határozzuk meg a legrövidebb utakat az összes ponton keresztül Faépítés, Dijkstra-féle eljárás: xi P ponthoz hozzárendelünk egy potenciált, ( xi ) a kezdőpontból az xi -ig menő legrövidebb távolság, ( xi ) ebben az esetben nem határoztuk meg a távolságot, 2 halmazra osztjuk P-t S
xi
( xi )
Legrövidebb út algoritmus (L) L0
T s
s
xi T
( xi )
S
N s
( s) 0
keressük azon xi pontokat amelyekre ( xi , x j ) E , xi (x j )
( xi ) t ( xi , x j ) x*j
E , xj
T
N S T
( xi )
0
xi T ; L1
T xj ideiglenes potenciál
min ( xi ) határozzuk meg azt a j-t amely a kezdőponthoz a
legközelebb van L2 s s x*j , T T x*j , ( x*j ) x*j kiválasztott pont L3 t S ha t S kész, (t ) a legrövidebb út s-től, ellenkező esetben L1-től kell újrakezdeni Maximális hosszúságú kifeszítő fa (F): az algoritmus ugyanaz, mint az előbbinél, de L3ban eltérés van F0 L0 F1 L1 F2 L2 F3 ha T=0 készen vagyunk, egyébként F1-nél folytatjuk ,
n 2 / 2 lépés szükséges (Floyd-)Warshall algoritmus: c1 vesszük az első pontot és végrehajtjuk az L algoritmust, vesszük a 2. pontot és végrehajtjuk az algoritmust, mindaddig követjük ezt az eljárást, míg az összes pontot meg nem határoztuk c2 megnézzük, hogy az 1-es pontot bevonva i-j-be menő útba rövidebbet kapunk-e majd a 2-es pontot vonjuk be és így tovább majd végül az összes pontot bevonjuk
5.Tervütemezési feladattípusok, a terv-ütemháló definíciója A gráfelméleten alapuló ún. hálódiagramos módszerek alkalmazása elősegíti az optimális döntés előkészítést, hatékonyan támogatja bármely munkaszervezet vezetésének főbb funkcióit: a tervezés, szervezés, irányítás és ellenőrzés feladatát. Alapvető hálómodellek: CPM (Critical Parth Method =kritikus út módszer) PERT (Program Evaluation and Review Technique = program értékelési és felülvizsgálati technika). Továbbfejlesztett modellek: MPM, PEP, MOST, CPM-COST, PERT-COST. A hálós módszer lényege: a munkafolyamatot részekre, tevékenységekre bontjuk rögzítjük a fontosabb állapotokat, ezeket eseményeknek nevezzük feltárjuk a tevékenységek (események) közötti soros illetve párhuzamos kapcsolatokat, majd ábrázoljuk egy gráfnak illetve mátrixnak megfelelően a tevékenységekhez időtartamot, erőforrás adatokat rendelünk, s elvégezzük a konkrét modellre vonatkozó számításokat. A terv alapján megszervezzük a munkafolyamatot. Végrehajtás közben aktualizáljuk a hálót úgy, hogy a tervezett végrehajtási idő lehetőleg ne növekedjen. A hálós módszerek osztályozása: a. számszerűsítés szerint: logikai: csak kapcsolatot fejez ki technikai: számszerű adatokat, súlyokat is tartalmaz b. alkalmazott gráf szerint: esemény orientált: ha a gráf pontjainak az események ábráit feleltetik meg (CPM,PERT) tevékenység orientált: ha a gráf pontjainak a tevékenységek ábráit feleltetik meg (MPM) c. meghatározottság szerint: determinisztikus: ha adatfajtánkként egyetlen határozott-determinált adatot rendelnek a tevékenységhez (CPM,MPM) sztochasztikus: az adatoknál a véletlen hatását is számításba veszik (PERT). Terütemháló definíciója: az irányított gráfnak 1 db kezdő és 1 db végpontja van. Nem tartalmaz irányított kört. A kezdőpontból minden egyes esemény elérhető. Bármely közbülső ponttól a végpontig el lehet jutni. Nincs párhuzamos él.
6.Kritikus út algoritmus, időtartalékok Mennyi a min idő amikorra befejeződik a terv? Kritikus út: s kezdőpontból a t végpontba a leghosszabb út. A legkorábbi kezdés pi , a legkésőbbi befejezés q i , ha pi qi akkor kritikus esemény, az ezeket összekötő út az ún kritikus út, ahol nincs időtartalék. A kritikus úthoz tartozó tevékenységeket kritikus tevékenységeknek nevezzük. Az egyes tevékenységek legkorábbi kezdési időpontjának meghatározása: az egyes eseményekhez, a gráf pontjaihoz rendelhető minimális számérték, p jelölje az egyes eseményekhez tartozó minimális értéket, a belőle induló tevékenységek legkorábbi kezdési időpontját, txy jelölje az x és y eseményeket összekötő tevékenység időtartamát. Algoritmus:
L0
p1
0
S
1
T=V-S
L1
H ( x, y) x S , y T , nincs olyan T amelyre ( , y) E azon éleket tekintjük, ( x, y) H -ra kiszámoljuk amelyek végpontjába csak S-ből vezet út L2 py
max p y , y *
px t xy L3 p y
ahol p y maximális L4 S
S
y* T
T
y*
py* végleges L5 ha T=0 kész, egyébként L1-től folytatjuk. Legkésőbbi befejezés meghatározása: az egyes eseményekhez, a gráf pontjaihoz rendelhető maximális számérték, minden egyes tevékenységet ekkorra be kell fejezni, hogy a projekt ne boruljon. q jelölje az egyes eseményekhez tartozó maximális értéket, az odavezető tevékenységek legkésőbbi befejezési időpontját. A gráf „duálisát” vesszük, az éleket megfordítjuk ugyanazzal a számmal. Az algoritmus során visszafelé haladunk a gráfon. Algoritmus
H
qn
pn
( x, y) x S , y T , nincs olyan
kiszámoljuk q y T
L0
T
qx t xy L3 q y
S
n
T amelyre ( , y) E
min q y , y *
T=V-S L2
L1
( x, y) H -ra
ahol q y maximális L4 S
S
y*
y * q y* végleges L5 ha T=0 kész, egyébként L1-től folytatjuk.
Maximális (teljes) tartalékidő: mij=qj–pi –tij ennyivel később kezdhető meg a t ij tevékenység az i-edik esemény legkorábbi megvalósulása után, hogy a j-edik esemény legkésőbbi megvalósítási határidejét még biztosítsa. Szabad (saját) tartalékidő: sij=pj–pi –tij ennyivel később kezdhető meg a t ij tevékenység az i-edik esemény legkorábbi megvalósulása után, hogy a j-edik esemény legkorábbi megvalósulását ne késleltesse. Biztos (minimális) tartalékidő: bij=pj–qi –tij ennyivel később kezdhető meg a t ij tevékenység az i-edik esemény legkésőbbi megvalósítási határideje után, hogy a j-edik esemény legkorábbi megvalósítását biztosítsa.
Feltételes időtartalék: fij=qj–qi–tij ennyivel később kezdhető meg a t ij tevékenység az iedik esemény legkésőbbi megvalósítása után, hogy a j-edik esemény legkésőbbi megvalósítását biztosítsa.
7.Lineáris programozási feladat lin. prog. feladat az alábbi alakban a11 x1 ... a1n xn b1
.... P : primál (alakú ) feladat am1 x1 ... amn xn bm x1
0...........xn
0 változók nemnegativizása
(c1 x1 ... cn xn )
max célfg. max imalizálása
8.Dualitás problémaköre, dualitási tétel Pr imál feladat
Duál feladat
A x b
'
A:m n
A y
x 0 b Rm c' x
max c, x
y Rn
c
0 c
b' y
A:n m Rn min b, y
Rm
tétel:a duál feladat duálja maga a kiinduló primál feladat
biz.:
A x b x 0 '
c x
A' y
c
A' y
y
0
y
max b' y
min
b' y
c
A' x b x 0
max
c' x
0
A x b x 0
min c ' x
max
duál képzés azonos átalakítás duál képzés azonos átalak . Dualitás tétel: Ha egy primál-duál feladat pár egyikének létezik megengedett megoldása és véges optimuma, akkor ugyanez fennáll a másikra is, és a két feladat optimum értéke egyenlő. Általános primál-duál megfeleltetési szabály: Ha a primál feladatban egy feltétel egyenlőség alakú, akkor a megfelelő változó a duál feladatban nincs nem negativitással korlátozva, illetve ha a primál feladat egy változója nincs nem negavititással korlátozva, akkor a duál feladat megfelelő feltétele egyenlőség alakú.
9.Játékelméleti modellek, Neumann tétel
Neumann János pókerezni szeretett, és kezdettõl fogva érdekelte, hogy – ha már az osztást befolyásolni nem tudjuk – miként blöfföljünk. A probléma felírásához – mai szemmel nézve kézenfekvõ módon – a matematikát használta, fõ érdeme azonban az elméletnek a játékokon messze túlmenõ általánosítása volt. A minimax tételt bizonyító elsõ publikációjában a már a napjainkban is használt normális alakot (normal form) használja a játékok leírására (Neumann [1928]).
Kétszemélyes zéróösszegű játék: legyen az I. játékosnak m db, a II. játékosnak n db lehetséges stratégiája; az egyes stratégiapárok választása esetén a játék eredményét a kifizetési mátrix tartalmazza; az I.nek célszerű azt az i stratégiát választania amelyre a max min aik 1 i m 1 k n
maximum megvalósul; a II.nek célszerű azt a stratégiát választania, amelyre a minimum megvalósul; Ezek között mindig fennáll a egyenlőtlenség; min max aik 1 k n 1 i m
Ha a egyenlőséggel teljesül akkor (i,k) stratégiapár így történt megválasztása mindkét játékos számára elfogadható lesz; ekkor ez esetben az (i,k) stratégiapárt optimálisnak, az egymással egyenlő és számokat a játék tiszta értékének nevezzük. sorminimumok maximuma, oszlopmaximumok minimuma, , kifizetési mátrix a11 a12 ...a1n
a21 a22 ...a2 n am1 am 2 ...amn Ha egy kifizetési mátrix esetén -ban nem áll egyenlőség, más elv szerint kell a játékosoknak stratégiát választaniuk. Az új elv a stratégiák véletlenszerű választása, másképp fogalmazva a stratégiák keverése. Ezen azt értjük, hogy az I.es az 1,2,…m stratégiák közül egy az x1 , x2 .....xm valószínűségekkel leírt diszkrét valószínűség eloszlás szerint választ egyet véletlenszerűen, azaz valójában a diszkrét valószínűség eloszlások m
x x Rm ,
xi
1, xi
0, i 1...m
halmazából választ egy elemet. A II.es pedig az
i 1
1,2,…n stratégiák közül, egy az y1 , y2 ..... yn valószínűségekkel leírt diszkrét valószínűség eloszlás szerint választ egyet véletlenszerűen, azaz valójában a diszkrét eloszlások n
y y Rn ,
yk
1, yk
0, k 1...n
halmazából választ egy elemet! Ez feloldja ezt az
k 1
anomáliát
.
Mit állít a kétszemélyes zéróösszegű játékról Neumann János tétele? m
max min x
y
n
. i 1 k 1
m
aik xi yk
min max y
x
n
.
aik xi yk ahol
és
lásd előző kérdés. Tetszőleges
i 1 k 1
valós számokból álló kifizetési mátrix esetén az előbbi reláció mindig egyenlőséggel érvényes!
