4.2. 4.2. A feladat matematikai vizsgálata

A fent vázolt két feladat szoros kapcsolatát az alábbi lemma szemlélteti.

LEMMA:

Tetszőleges -ből -be vezető út és tetszőleges megengedett ütemezés esetén a célfüggvények értékei között az alábbi összefüggés áll fenn:

Bizonyítás.

A duál feladat feltételének felhasználásával és egyszerűsítéssel egyszerűen adódik, hogy

A lemmából két fontos következményt olvashatunk ki.

1. KÖVETKEZMÉNY:

Ha az -ből -be vezető út és a megengedett ütemezés olyan, hogy a lemmában egyenlőség áll fenn, akkor a úthossz maximális értékű, a ütemezés pedig minimális értékű, azaz az út és az ütemezés optimális.

Bizonyítás.

Legyen a szóbanforgó út és az ütemezés olyan, hogy .

Indirekte tegyük fel, hogy a út nem maximális, azaz létezik egy út, amelyre

Mivel a útra is igaz a lemma állítása, így

A fenti két összefüggés ellentmond egymásnak, így feltevésünk szerint nem létezik út, tehát a út maximális.

Most pedig indirekte tegyük fel, hogy az ütemezés nem minimális, azaz létezik egy ütemezés, amelyre

Mivel az ütemezésre is igaz a lemma állítása, így

Az utóbbi két összefüggés ellentmond egymásnak, tehát a feltevésünk hamis volt, azaz nem létezik ütemezésnél jobb, tehát az ütemezés optimális (minimális).

A soron következő második következményt szokás optimalitási kritériumnak vagy egyensúlyi összefüggésnek is nevezni, mivel arra ad választ, hogy milyen feltételek esetén egyezik meg a két célfüggvény, azaz mikor optimálisak a megengedett megoldások.

2. KÖVETKEZMÉNY (optimalitási kritérium):

A lemmában egyenlőség akkor és csak akkor áll fenn, ha a út minden élén

Bizonyítás.

Rendezzük át a lemma bizonyításában szereplő egyenlőtlenséget, ekkor a lemmabeli egyenlőség fennállásához azt kell megvizsgálnunk, hogy mikor lesz az alábbi összefüggés zérus

A duál feltétel szerint az összeg minden tagja nempozitív, így az összeg akkor és csak akkor lehet zérus, ha minden tagja zérus. Ez pedig azt jelenti, hogy a lemmabeli egyenlőség szükséges és elégséges feltétele, hogy minden útbeli élen .

TÉTEL:

A tervütemhálóban létezik olyan -ből -be vezető út és a feltételeket kielégítő ütemezés, hogy a lemmában egyenlőség áll fenn, azaz létezik maximális út és minimális ütemezés; a maximális úthossz (átfutási idő) és a minimális ütemezés (ütemezés értéke) egyenlő egymással, képletben:

Bizonyítás.

A bizonyítás konstruktív jellegű, az optimális megoldáspár (primál és duál) meghatározásának menetét (algoritmusát) is szolgáltatja. Két halmazt fogunk megkonstruálni.

A) Legyen egy halmaz a következőképpen megkonstruálva:

Az S halmaz az események sorszámozása miatt legyen: , azaz az első k pont. Mint tudjuk a kritikus út mentén . Jelölje az S-beli pontokhoz tartozó eseményidőket .

Ha közelebbről megvizsgáljuk az eseményidőket, akkor azt tapasztaljuk, hogy az az idő, aminél korábban nem kezdhetők el az pontból kiinduló tevékenységek. Ezt az időt legkorábbi időnek nevezzük. Ennél az időnél azért nem kezdhetjük korábban a tevékenységeket, mert az ponthoz kritikus út vezet, ez pedig azt jelenti, hogy az pontba vezető valamelyik tevékenység éppen -ben fejeződött be.

Az S halmaz megkonstruálása után két eset adódhat:

  1. S = N, ez azt jelenti, hogy a t befejező eseményhez is vezet kritikus út, tehát optimális megoldáshoz jutottunk.

  2. , ekkor tekintsük a soron következő pontot. Ahhoz, hogy is S-be tartozzon, kritikus úton kell s-ből elérni, ehhez az eseményidőt az alábbiak szerint kell meghatározni:

    Tehát a maximumképzést azon élekre kell végezni, melyek végpontja . Meg kell nézni tehát, hogy mely élek vezetnek az pontba. Mivel az pontba már kritikus út vezet, így könnyen érthető, hogy a legnagyobb időértéket kell választani, hogy az pontba is kritikus út vezessen.

B) Legyen egy halmaz a következőképpen megkonstruálva:

A T halmaz az események sorszámozása miatt legyen: , azaz az utolsó (n-m) pont. Mint tudjuk a kritikus út mentén . Jelölje a T-beli pontokhoz tartozó eseményidőket .

Ha közelebbről megvizsgáljuk az eseményidőket, akkor azt tapasztaljuk, hogy az az idő, aminél későbben nem fejezhetők be az pontba befutó tevékenységek. Ezt az időt legkésőbbi időnek nevezzük. Ennél az időnél azért nem fejezhetjük be későbben a tevékenységeket, mert az pontból kritikus út vezet t-be, ez pedig azt jelenti, hogy az pontból kiinduló tevékenységek közül valamelyik tevékenység éppen -ben kezdődik el.

A T halmaz megkonstruálása után két eset adódhat:

  1. T = N, ez azt jelenti, hogy az s kezdőeseményből is vezet kritikus út, tehát optimális megoldáshoz jutottunk.

  2. , ekkor tekintsük a soron következő pontot. Ahhoz, hogy is T-be tartozzon, kritikus úton kell tőle t-be jutni, ehhez az eseményidőt az alábbiak szerint kell meghatározni:

    Tehát a minimumképzést azon élekre kell végezni, melyek kezdőpontja . Meg kell nézni tehát, hogy mely élek indulnak ki az pontból. Mivel az pontból már kritikus út vezet t-be, így könnyen érthető, hogy a legkisebb időértéket kell választani, hogy az pontból is kritikus út vezessen.

Az legkorábbi idők meghatározásakor az kezdőértékkel, az legkésőbbi idők meghatározásakor pedig az kezdőértékekkel szokás dolgozni. Akár az S, akár a T halmazt konstruáljuk meg, mindig véges lépésben eljutunk az optimális megoldáshoz.

Ha rendelkezésünkre állnak az legkorábbi idők és az legkésőbbi idők, akkor az eseményidőkre mindig igaz, hogy

Azokat az eseményeket, amelyekre

kritikus eseményeknek nevezzük. A kritikus utat a kritikus eseményeket összekötő tevékenységek alkotják. A kritikus út tevékenységeit kritikus tevékenységeknek nevezzük.

Egy munkafolyamat kivitelezésének megtervezéséhez és irányításához a fentieken kívül ismerni kell a tevékenységek ütemezését is. Ezt az eseményidőkből egyszerűen számolhatjuk az alábbiak szerint:

  1. A tevékenység legkorábbi kezdési időpontja:

    Egy (x,y) tevékenység legkorábban az x esemény legkorábbi idejében kezdődhet az eseményidő definíciója miatt. Tehát az (x,y) tevékenység legkorábbi kezdési időpontja: .

  2. A tevékenység legkorábbi befejezési időpontja:

    Egy (x,y) tevékenység legkorábban akkor befejeződhet be, ha legkorábban lett elkezdve. Tehát a legkorábbi időhöz még hozzá kell adni a tevékenység idejét. Tehát az (x,y) tevékenység legkorábbi befejezési időpontja: .

  3. A tevékenység legkésőbbi befejezési időpontja:

    Egy (x,y) tevékenység legkésőbben az y esemény legkésőbbi idejében fejeződhet be az eseményidő definíciója miatt. Tehát az (x,y) tevékenység legkésőbbi befejezési időpontja: .

  4. A tevékenység legkésőbbi kezdési időpontja:

    Egy (x,y) tevékenység legkésőbben akkor kezdődhet, ha legkésőbb lett befejezve. Tehát a legkésőbbi időből még le kell vonni a tevékenység idejét. Tehát az (x,y) tevékenység legkésőbbi kezdési időpontja: .

Nyilvánvaló, hogy a kritikus tevékenységeknél a legkorábbi és a legkésőbbi kezdési (vagy befejezési) időpontok megegyeznek. A többi tevékenység legkorábbi és legkésőbbi kezdési (vagy befejezési) időpontjai eltérőek, tehát ezek tartalékidővel (lebegésseI) rendelkeznek. Az alábbiakban a tartalékidőket ismertetjük:

  1. Teljes (összes) tartalékidő:

    A legkedvezőbb körülmények között számított érték, azaz, ha az (x,y) tevékenység legkorábban kezdődhet és legkésőbben fejeződhet be, képletben:

  2. Szabad tartalékidő:

    Ha a tevékenység legkorábban kezdődhet és legkorábban fejeződhet be, képletben:

  3. Független tartalékidő:

    A legkedvezőtlenebb feltételek mellett számított érték, azaz ha az (x,y) tevékenység legkésőbb kezdődhet és legkorábban fejeződhet be, képletben:

    Ha a független tartalékidő pozitív, akkor ez a tartalékidő más tevékenységek lebegésétől függetlenül felhasználható. Ha negatív, akkor nincs független időtartalék, ezért zérusnak vesszük.