Ugrás a tartalomhoz

Operációkutatás II.

Dr. Bajalinov Erik, Bekéné Rácz Anett (2010)

Kempelen Farkas Hallgatói Információs Központ

Kritikus út meghatározása

Kritikus út meghatározása

A gazdasági gyakorlatban egyre fontosabbá válik, hogy összetett, egymással bonyolult logikai és időrendi kapcsolatban álló gazdasági műveleteket, tevékenységeket a lehető leggyorsabban, minél jobban és magasabb hatékonysággal lehessen elvégezni. Beruházások megvalósítása, nagy rendszerek üzembe állítása, új termékek megtervezése és létrehozása, építkezések lebonyolítása - mind olyan feladatok, ahol egymással párhuzamosan haladó, vagy egymást követő tevékenységek folynak és ezeket a tevékenységeket úgy kell megszervezni, hogy a teljes projekt a legrövidebb idő alatt lebonyolódjon. Az ilyen fajta feladatok matematikai eszközei közé tartozik a CPM (Critical Path Method) vagy "kritikus út módszer".

A módszer első lépésében a projekt keretében végrehajtandó feladatokat és azok közötti logikai és időrendi kapcsolatokat ábrázoljuk egy olyan irányított gráfban, amely a következő tulajdonságokkal rendelkezik:

  1. Az élek jelentik a tevékenységeket, a csúcspontok pedig az eseményeket: egy-egy esemény azt jelenti, hogy az ebbe a csúcspontba vezető tevékenységek már befejeződtek. Az eseménynek nincs időbeli kiterjedése.

  2. A csúcspontból kivezető éleken definiált tevékenységek csak a csúcspontba bevezető tevékenységek befejezése után kezdődhetnek el. A tevékenységeket kapacitásukkal (időtartamukkal) együtt adjuk meg.

  3. A projektet megjelenítő hálózat a tevékenységek megelőzési viszonyát mutatja. A projektnek egyetlen kezdőponttal kell rendelkeznie (általában ez lesz az 1-es csúcspont). Ugyancsak egyetlen befejező csúcspont létezhet a hálózatban.

  4. Egy tevékenységet csak egyetlen él reprezentálhat. Két csúcspont között legfeljebb egy élt húzhatunk.

  5. A hálózat csúcspontjait (az eseményeket) úgy számozzuk, hogy bármely tevékenység végét jelentő csúcs sorszáma mindig nagyobb legyen, mint a tevékenység kezdetét jelentő csúcs sorszáma. (Ennek a feltételnek nem feltétlenül egyetlen számozás felel meg.)

  6. A tevékenységi háló a logikai feltételek betartása céljából tartalmazhat fiktív éleket (fiktív tevékenységeket) is, amelyek kizárólag azt a célt szolgálják, hogy a fenti szabályok betartása mellett létezzen lehetséges hálózati reprezentáció. A fiktív élek kapacitása (időtartama) mindig 0 egység.

Másképpen, a Tij-vel jelölt tevékenységnek van Ei kezdő eseménye és Ej végpont eseménye, jelölése ezek jeleiből alakul ki az időbeli sorrendnek megfelelően (5.4. ábra).

5.4. ábra. Két egymást követő esemény és azokat összekötő (ij) tevékenység.

Egy eseményből egy vagy több tevékenység indulhat ki, ezeket párhuzamos tevékenységeknek nevezzük. A párhuzamos tevékenységek típusai:

  • Ugyanabban az eseményben végződnek (5.5. ábra).

    5.5. ábra. Az i-edik eseményből két tevékenység indul és mindkettő l-be vezet.

    Itt Ej és Ek események két párhuzamos Tij és Tik tevékenységet igényelnek. Viszont El eseményt időben megelőzi a Tkl valódi tevékenység és Tjk fiktív tevékenység, ami azt jelenti, hogy a Tkl munka megkezdésének előfeltétele nem csak Tik tevékenység befejeződése, de a Tjk munka befejeződése is.

  • Különböző eseményekben végződnek, de szinkronban kell lefolyniuk (5.6. ábra).

    5.6. ábra. Az l eseménynek két előfeltétele van - Tij és Tik munkák befejeződése.

    Tehát a két munka Tij és Tik befejeződése előfeltétele a Tjl munka megkezdésének, és Tks csak akkor indulhat, ha Tik befejeződött.

  • Különböző eseményekben végződnek, tehát befejeződésük különböző munkák kezdetét befolyásolja (5.7. ábra).

    5.7. ábra. A Tks csak akkor indulhat, ha Tij és Tik munkák befejeződnek.

    Itt a Tks csak akkor kezdődhet el, ha Tik és Tij is befejeződött; a Tst pedig Tks és Til befejeződése után kezdődhet. A Tij, Tik és Til egyszerre kezdhető tevékenységek.

  • Párhuzamos eseménysorok (5.8. ábra).

    5.8. ábra. A T78 csak akkor indulhat, ha befejeződött T67 és T47.

    Itt T15 és T12 egyidejűsége megengedett, T12, T23, T34 és T47 időben egymásután következik, hasonlóan T15, T56, T67 is, de szinkron csak a 7 eseménynél kell hogy bekövetkezzen. Viszont ha a 3 és 5 szinkronját előírjuk 5-re (5.9. ábra), az események számozása megváltozik.

    5.9. ábra. A T45 csak akkor kezdődhet, ha befejeződött T14 és T23.

Mindezek tudatában tekintsünk egy példát!

5.1. példa -

Tegyük fel, hogy egy megvalósítandó projekthez tartozó munkák összefüggését leírja a következő táblázat:

TevékenységElőzményIdőtartam (nap)
A-7
B-20
C-2
DA, B, C25
EA5
FA, C3
GA, B, C15
HG10
IH2
JH15
KD, E, F, I10
LJ, K30

Láthatjuk, hogy A, B és C tevékenység elindítható párhuzamosan az 1. csúcspontból. A D művelet csak az A, B és C munkák befejeződése után kezdődik és 25 napig tart, stb. Mivel a projekt párhuzamos tevékenységeket tartalmaz, a logikai feltételek betartása céljából fiktív élekre is szükség lesz. Ennek a táblázatnak megfelelően állítsuk elő a projekthálót (5.10.).

5.10. ábra. A tevékenységi háló.

Mielőtt elkezdjük az összeállított háló kiértékelését, vezessük be a szükséges definíciókat!


  1. Definíció. Az i-edik esemény legkorábbi időpontja az az időpont, amikor az esemény be fog következni, ha az őt megelőző események a lehető legkorábban kezdődtek el.

Ha az i-edik esemény legkorábbi időpontját ET(i)-vel jelöljük, és az eseményhez közvetlenül bevezető tevékenységek (élek) időtartama tij, akkor az ET(i) értékek kiszámolása a következőképpen történik:

  1. Soroljuk fel egy négy oszlopos táblázatban a projekthez tartozó összes eseményt.

  2. ET(1) = 0.

  3. Keressük meg az i-edik csúcsba vezető élek kezdőpontjait. Ezek a csúcspontok lesznek a vizsgált i-edik esemény közvetlen előzményei.

  4. Az i-edik esemény közvetlen előzményeinek ET értékéhez adjuk hozzá az onnan az i-edik csúcspontba vezető él (tevékenység) tji időtartamát.

  5. Vegyük ezen értékek maximumát. Ez a szám lesz az ET(i) értéke.

A fenti példánkban a legkorábbi időpontok kiszámítását az alábbi táblázat mutatja:

Esemény

Közvetlenül megelőző

esemény

Legkorábbi időpont

+ tji

Maximum

ET(i)

1--0
210 + 7 = 77
3

1

2

0 + 2 = 2

7 + 0 = 7

7
4

1

3

0 + 20 = 20

7 + 0 = 7

20
5420 + 15 = 3535
6535 + 10 = 4545
7

2

3

4

6

7 + 5 = 12

7 + 3 = 10

20 + 25 = 45

45 + 2 = 47

47

8

6

7

45 + 15 = 60

47 + 10 = 57

60

9860 + 30 = 9090

A fenti táblázat alsó jobboldali cellájában szereplő érték (90 nap) a projekt legkorábbi befejezésének időtartamát mutatja. A mi esetünkben ez 90 nap.

  1. Definíció. Az i-edik esemény legkésőbbi időpontja az az időpont, amikor az esemény még bekövetkezhet anélkül, hogy a projekt egészének tervezett befejezését annak legkorábbi időpontján túl késleltetné.

Ha az i-edik esemény legkésőbbi időpontját LT(i)-vel jelöljük, és az eseményből közvetlenül kivezető tevékenységek (élek) időtartama tij, akkor LT(i) kiszámolása a következőképpen történik:

  1. Soroljuk fel egy négy oszlopos táblázatban az összes n eseményt a projekt befejezését jelző n-edik eseménytől elkezdve visszafelé az 1-ig.

  2. LT(n) = ET(n).

  3. Keressük meg azokat a csúcspontokat, ahová az i-edik csúcsból vezet él. Ezek a csúcspontok lesznek a vizsgált i-edik esemény közvetlen követői.

  4. Az i-edik esemény közvetlen követőinek LT értékéből levonjuk az i-edik csúcspontból a következőhöz vezető él (tevékenység) tij időtartamát.

  5. Vegyük ezen értékek minimumát. Ez a szám lesz az LT(i) értéke.

Példánkban ez a következőképpen történik:

Esemény

Közvetlen követő

esemény

Legkésőbbi időpont - tij

Minimum

LT(i)

9--90
8990 - 30 = 6060
7860 - 10 = 5050
6

7

8

50 - 2 = 48

60 - 15 = 45

45
5645 - 10 = 3535
4

5

7

35 - 15 = 20

50 - 25 = 25

20
3

4

7

20 - 0 = 20

50 - 3 = 47

20
2

3

7

20 - 0 = 20

50 - 5 = 45

20
1

2

3

4

20 - 7 = 13

20 - 2 = 18

20 - 20 = 0

0

  1. Definíció. Egy esemény tűrése a legkésőbbi és legkorábbi kezdése közötti különbség:

Az esemény tűrése azt mutatja meg, hogy egy esemény bekövetkezésében mekkora késés engedhető meg, amely még nem hátráltatja a projekt legkorábbi befejezését. Ha egy esemény tűrése 0, akkor legalább egy tevékenységet azonnal indítanunk kell, hogy ne késleltessük a befejezést. Ha T(i) > 0, akkor bármely rákövetkező esemény legalább ennyi ideig várakozhat, ez a befejezést nem késlelteti.

Esemény LT(i) ET(i) T(i)
1000
220713
320713
420200
535350
645450
747503
860600
990900

Példánkban az 5-ös, a 6-os vagy a 8-as eseményekből kifutó tevékenységek közül legalább egyet azonnal kell indítanunk. Ezeket az azonnal indítandó tevékenységeket fogjuk kritikus tevékenységeknek nevezni. Az 5-ös és a 8-as csúcspontból egy-egy tevékenység vezet ki, tehát azokat azonnal indítani kell. A 6-os csúcspontban a J műveletet azonnal indítani kell, ha nem akarjuk a befejezést hátráltatni. A 7-es számú esemény tűrése azt mondja, hogy az innen kiinduló tevékenységet (mivel csak egy van) 3 napig késleltethetjük.

Egyszerűbb lenne azonban azonnal a tevékenységekre vonatkozó értékekkel dolgozni. Az ET(i) és LT(i) értékek segítségével ki tudjuk számolni az egyes tevékenységek tűréshatárát is.

  1. Definíció. Egy tevékenység tűréshatára, amit TH(i,j)-vel jelölünk, a következő módon számolható ki:

Egy tevékenység tűréshatára az a szám, amennyivel az adott tevékenység elkezdése eltolódhat anélkül, hogy a projekt egészének befejezése késedelmet szenvedne. Ha a tevékenység tűréshatára egyenlő 0-val, akkor nincs lehetőség a késleltetésre. Ha viszont TH(i,j) > 0, akkor van ilyen lehetőség. Számoljuk ki a példánkban a tevékenységek tűréshatárait!

Tevékenység TH(i,j)
A(1,2) 20 - 0 - 7 = 13
B(1,4) 20 - 0 - 20 = 0
C(1,3) 20 - 0 - 2 = 18
Fiktív(2,3) 20 - 7 - 0 = 13
Fiktív(3,4) 20 - 7 - 0 = 13
D(4,7) 50 - 20 - 25 = 5
E(2,7) 50 - 7 - 5 = 38
F(3,7) 50 - 7 - 3 = 40
G(4,5) 35 - 20 - 15 = 0
H(5,6) 45 - 35 - 10 = 0
I(6,7) 50 - 45 - 22 = 3
J(6,8) 60 - 45 - 15 = 0
K(7,8) 60 - 47 - 10 = 3
L(8,9) 90 - 60 = 30

  1. Definíció. Azokat a tevékenységeket, amelyek tűréshatára 0, kritikus tevékenységeknek nevezzük. A kritikus út a kezdő csúcspontból a befejezés csúcspontba vezető olyan út, amely kizárólag kritikus tevékenységekből áll.

Példánkban a kritikus út a

tevékenységekből áll (és mint láttuk, a hossza 90 nap). Ezeket a tevékenységeket tehát haladéktalanul el kell kezdeni. A különböző gazdasági alkalmazásokban gyakran olyan tevékenységek vannak, amelyeknek kezdésével "játszani" lehet: akár késhetünk is 13 napot az A művelet elindításával, vagy a D művelet kezdődhet 5 nappal később.

  1. Definíció. Egy tevékenység mozgáshatára, amit MH(i,j)-vel jelölünk, az a maximális időtartam, amennyivel a tevékenység elkezdését várakoztathatjuk, ha a befutó eseményből azonnal tovább akarunk indulni, amint lehet:

Számoljuk ki a példában a tevékenységek mozgáshatárait.

TevékenységMozgáshatár MH(i,j)
A(1,2) 7 - 0 - 7 = 0
B(1,4) 20 - 0 - 20 = 0
C(1,3) 7 - 0 - 2 = 5
Fiktív(2,3) 7 - 7 - 0 = 0
Fiktív(3,4) 7 - 7 - 0 = 7
D(4,7) 50 - 20 - 25 = 5
E(2,7) 47 - 7 - 5 = 35
F(3,7) 47 - 7 - 3 = 37
G(4,5) 35 - 20 - 15 = 0
H(5,6) 45 - 35 - 10 = 0
I(6,7) 47 - 45 - 2 = 0
J(6,8) 60 - 45 - 15 = 0
K(7,8) 60 - 47 - 10 = 3
L(8,9) 90 - 60 = 30

A kritikus utat megkereshetjük lineáris programozási apparátus használatával is. Írjuk fel a mintafeladatunkhoz tartozó LP-modellt.

Legyen xj a j-edik csúcsponthoz tartozó esemény bekövetkezésének időpontja. Mivel minden (ij) tevékenységre igaz az, hogy a j-edik esemény bekövetkezte előtt az i-edik eseménynek be kell következnie és az (ij) tevékenységnek is be kell fejeződnie (lásd a hálózat megkonstruálására vonatkozó szabályokat), ezért a hálózat mindegyik élére vonatkozóan igaz, hogy

A mi példánk esetében

5.4. egyenlet -


5.5. egyenlet -


5.6. egyenlet -


A fenti LP feladat optimális megoldása:

Gyakorlatban előfordulhat, hogy a kritikus út feladatban több optimális megoldás van, azaz több kritikus út található.