1 Metody programowania sieciowego w zarządzaniu przedsięwzięciami Programowanie sieciowe stanowi specyficzną grupę zagadnień programowania matematycznego. Programowanie sieciowe bazuje na teorii grafów. Teoria grafów w zagadnieniach sieciowych jest zastosowana do opisu zależności występujących między czynnościami składającymi się na realizację określonego przedsięwzięcia. Metody programowania sieciowego stosuje się do kierowania przedsięwzięciami, które są zbiorem powiązanych ze sobą czynności, dla których określono cele ich realizacji oraz czasy rozpoczęcia i zakończenia danej czynności. Do najbardziej rozpowszechnionych metod zarządzania przedsięwzięciami należą metody programowania sieciowego CPM i PERT.
2 CPM - Critical Path Method Metoda Ścieżki Krytycznej – deterministyczna metoda stosowana wówczas, gdy dysponujemy wystarczającą ilością danych do ścisłego określenia czasu trwania czynności (tj. każdej czynności przypisuje się dokładnie jeden ściśle określony czas trwania). PERT - Program Evaluation and Review Technique Stochastyczna metoda planowania i kontroli projektu, stosowana w zarządzaniu projektami. Dla każdej czynności określa się trzy czasy: 1) Optymistyczny 2) Pesymistyczny 3) Najbardziej prawdopodobny Początkowo wykorzystywana głównie przy dużych, wieloletnich programach wojskowych USA, z czasem znalazła również zastosowanie w projektach cywilnych.
3 Wspólnym elementem obydwu metod jest sieć zależności pomiędzy czynnościami i zdarzeniami – często nazywana siecią czynności. Każde przedsięwzięcie stanowiące zbiór czynności można przedstawić w postaci sieci zależności pomiędzy tymi czynnościami. Sieć (graf liniowy) składa się ze zbioru węzłów (punktów, wierzchołków) oraz ze zbioru łuków (połączeń) łączących różne pary tych węzłów. Najczęściej przyjmuje się, że: wierzchołki oznaczają zdarzenia, łuki – czynności. Czynność – to wyodrębniona część składowa przedsięwzięcia, której realizacja związana jest z upływem czasu i zużyciem zasobów. Zdarzenie - to moment rozpoczęcia lub ukończenia jednej lub kilku czynności.
4 Przykład CPM I Przedsiębiorstwo rozważa przeprowadzenie akcji reklamowej. Plan przedsięwzięcia obejmuje następujące czynności: (1 - 2) przygotowanie wzoru ulotki reklamowej (czas trwania t 12 = 1) (2 – 4) określenie miejsc, w których ulotki będę rozdawane mieszkańcom miasta (t 24 = 2) (2 – 3) wysłanie wzoru do firmy powielającej ulotki (t 23 = 1) (3 – 4) odebranie ulotek od firmy powielającej (t 34 = 3) (4 – 6) paczkowanie ulotek (t 46 = 1) (2 – 5) rekrutacja osób rozdających ulotki (t 25 = 6) (5 – 6) szkolenie osób rozdających ulotki (t 56 = 1) (6 – 7) wręczenie ulotek osobom rozdającym ulotki i przypisanie każdej osoby do obszaru działania (t 67 = 1)
5 Jak widać ścieżka krytyczna obejmuje czynności (1 – 2), (2 – 5), (5 – 6) oraz (6 – 7). Luzy na zdarzeniach tworzących ścieżkę krytyczną są równe zero. Podobnie zapasy na czynnościach ścieżki krytycznej mają wartość zero. Zatem najkrótszy czas realizacji całego przedsięwzięcia reklamowego to 9 jednostek czasu (np.dni).
6 Przedsiębiorstwo stoi przed problemem wprowadzenia nowego produktu na rynek. Realizacja tego przedsięwzięcia wiąże się z wykonaniem następujących czynności: Czynności (i,j) Czas trwania t ij Zakup surowców na prototypy (1,2) 5 Wyprodukowanie prototypu i jego ocena (2,3) 20 Badanie rynku (1,3) 35 Wybór opakowania (3,7) 2 Analiza kosztów produkcji (3,4) 10 Zakup surowców do produkcji (4,6) 15 Produkcja (6,8) 30 Zakup opakowań (7,8) 10 Wybór strategii reklamowej (4,5) 1 Reklama i zbieranie zamówień (5,9) 20 Pakowanie (8,9) 5 Wysyłka do sklepów (9,10) 10 Przykład CPM II
7 Przedsiębiorstwo stoi przed problemem wprowadzenia nowego produktu na rynek. Realizacja tego przedsięwzięcia wiąże się z wykonaniem następujących czynności: Czynności (i,j) Czasy trwania t ij a m b Zakup surowców na prototypy (1,2) 4 5 6 Wyprodukowanie prototypu i jego ocena (2,3) 18 20 22 Badanie rynku (1,3) 30 35 40 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Wybór opakowania (3,7) 1 2 3 Analiza kosztów produkcji (3,4) 8 10 12 Zakup surowców do produkcji (4,6) 10 15 20 Produkcja (6,8) 28 30 32 Zakup opakowań (7,8) 9 10 11 Wybór strategii reklamowej (4,5) 1 / 2 1 2 --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Reklama i zbieranie zamówień (5,9) 16 20 22 Pakowanie (8,9) 2 5 6 Wysyłka do sklepów (9,10) 7 10 13 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Przykład PERT
8 Na podstawie czasów trwania czynności a, m, b obliczamy T e, czyli średni oczekiwany czas trwania każdej czynności: T e = (a + 4m + b) / 6 oraz wariancję czasu trwania każdej czynności: W = [ (b – a) / 6 ] 2
9 Dla ustalenia prawdopodobieństwa zakończenia przedsięwzięcia w czasie krótszym lub równym t korzystamy ze wzorów : Gdzie x to zmienna standaryzowana: t us – termin ustalony zdarzenia końcowego t ws – najwcześniejszy termin zdarzenia kończącego przedsięwzięcie W tws – suma wariancji czynności leżących na ścieżce krytycznej - dystrybuanta rozkładu normalnego
10 Dystrybuanta rozkładu Normalnego dla x < 0 z00,010,020,030,040,050,060,070,080,09 0,000,50,49600,49200,48800,48410,48010,47610,47210,46810,4641 -0,100,46020,45620,45220,44830,44430,44040,43640,43250,42860,4247 -0,200,42070,41680,41290,40910,40520,40130,39740,39360,38970,3859 -0,300,38210,37830,37450,37070,36690,36320,35940,35570,35200,3483 -0,400,34460,34090,33720,33360,33000,32640,32280,31920,31560,3121 -0,500,30850,30500,30150,29810,29460,29120,28770,28430,28100,2776 -0,600,27430,27090,26760,26440,26110,25790,25460,25140,24830,2451 -0,700,24200,23890,23580,23270,22970,22660,22360,22070,21770,2148 -0,800,21190,20900,20610,20330,20050,19770,19490,19220,18940,1867 -0,900,18410,18140,17880,17620,17360,17110,16850,16600,16350,1611 -1,000,15870,15630,15390,15150,14920,14690,14460,14230,14010,1379 -1,100,13570,13350,13140,12920,12710,12510,12300,12100,11900,1170 -1,200,11510,11310,11120,10940,10750,10570,10380,10200,10030,0985 -1,300,09680,09510,09340,09180,09010,08850,08690,08530,08380,0823 -1,400,08080,07930,07780,07640,07490,07350,07220,07080,06940,0681 -1,500,06680,06550,06430,06300,06180,06060,05940,05820,05710,0559 -1,600,05480,05370,05260,05160,05050,04950,04850,04750,04650,0455 -1,700,04460,04360,04270,04180,04090,04010,03920,03840,03750,0367 -1,800,03590,03520,03440,03360,03290,03220,03140,03070,03010,0294 -1,900,02870,02810,02740,02680,02620,02560,02500,02440,02390,0233
11 Dystrybuanta rozkładu Normalnego dla x > 0 z00,010,020,030,040,050,060,070,080,09 00,50,50400,50800,51200,51600,51990,52390,52790,53190,5359 0,10,53980,54380,54780,55170,55570,55960,56360,56750,57140,5754 0,20,57930,58320,58710,59100,59480,59870,60260,60640,61030,6141 0,30,61790,62170,62550,62930,63310,63680,64060,64430,64800,6517 0,40,65540,65910,66280,66640,67000,67360,67720,68080,68440,6879 0,50,69150,69500,69850,70190,70540,70880,71230,71570,71900,7224 0,60,72580,72910,73240,73570,73890,74220,74540,74860,75180,7549 0,70,75800,76120,76420,76730,77040,77340,77640,77940,78230,7852 0,80,78810,79100,79390,79670,79960,80230,80510,80790,81060,8133 0,90,81590,81860,82120,82380,82640,82890,83150,83400,83650,8389 10,84130,84380,84610,84850,85080,85310,85540,85770,85990,8621 1,10,86430,86650,86860,87080,87290,87490,87700,87900,88100,8830 1,20,88490,88690,88880,89070,89250,89440,89620,89800,89970,9015 1,30,90320,90490,90660,90820,90990,91150,91310,91470,91620,9177 1,40,91920,92070,92220,92360,92510,92650,92790,92920,93060,9319 1,50,93320,93450,93570,93700,93820,93940,94060,94180,94300,9441 1,60,94520,94630,94740,94850,94950,95050,95150,95250,95350,9545 1,70,95540,95640,95730,95820,95910,95990,96080,96160,96250,9633 1,80,96410,96490,96560,96640,96710,96780,96860,96930,97000,9706 1,90,97130,97190,97260,97320,97380,97440,97500,97560,97620,9767
12 Programowanie dynamiczne Programowanie dynamiczne jest jedną z technik matematycznych, którą można zastosować do rozwiązywania takich problemów jak: 1. Optymalizacja trasy, 2. Zagadnienie finansowania inwestycji, 3. Optymalizacja zapasów, alokacja zasobów, 4. Wymiana majątku trwałego itd.
13 Zasada optymalności Bellmana Przedmiotem programowania dynamicznego jest optymalizacja wieloetapowych problemów decyzyjnych. „Polityka optymalna ma tę własność, że niezależnie od początkowego stanu i początkowej decyzji pozostałe decyzje muszą stanowić politykę optymalną ze względu na stan wynikający z pierwszej decyzji.” Zamiana zadania optymalizacyjnego z n zmiennymi decyzyjnymi na n zadań optymalizacyjnych z jedną zmienną decyzyjną * zadania te są powiązane zależnością liniową !!!
14 Optymalne rozwiązanie dla k-tego etapu jest równocześnie rozwiązaniem optymalnym dla etapów k+1, k+2, … N. Tak więc optymalne rozwiązanie dla etapu pierwszego stanowi optymalne rozwiązanie dla całego problemu. Problem rozwiązuje się rozpoczynając od poszukiwania rozwiązania dla ostatniego etapu N, a następnie cofając się poszukujemy rozwiązania dla etapu N-1. Uzyskane w ten sposób rozwiązanie dla etapów N-1 oraz N jest optymalne bez względu na to, w jaki sposób osiągnięto etap N-1. Powtarzając w powyższy sposób etap po etapie dochodzimy do rozwiązania optymalnego dla pierwszego etapu, a więc i dla całego problemu.
15 Przykład: Leopold jedzie samochodem nad morze. Cała trasa została podzielona na kilka etapów. Odległości między poszczególnymi miastami, przez które można przejechać jadąc od miejsca zamieszkania 1 do miejsca pobytu nad morzem 7 są przedstawione poniżej. Znaleźć najkrótszą trasę przejazdu z miejsca 1 do 7.
16 Krok I: Załóżmy, że Leopold jest na początku III etapu podróży. W tej sytuacji odległość od celu wynosi: od miasta 5: d 5,7 = 70 km od miasta 6: d 6,7 = 50 km
17 Krok II: Cofamy się o jeden etap. Na początku II etapu podróży odległość poszczególnych miast (tj. 2, 3 i 4) od celu wynosi: od miasta 2: d 2,5 + d 5,7 = d 2,5,7 120 + 70 = 190 km d 2,6 + d 6,7 = d 2,6,7 120 + 50 = 170 km od miasta 3: d 3,5 + d 5,7 = d 3,5,7 100 + 70 = 170 km d 3,6 + d 6,7 = d 3,6,7 90 + 50 = 140 km
18 od miasta 4: d 4,5 + d 5,7 = d 4,5,7 70 + 70 = 140 km d 4,6 + d 6,7 = d 4,6,7 130 + 50 = 180 km Tak więc: z miasta 2 do 7 należy wybrać drogę d 2,6,7 = 170 km, z miasta 3 do 7 drogę d 3,6,7 = 140 km, z miasta 4 do 7 drogę d 4,5,7 = 140 km.
19 Krok III: Cofamy się o jeden etap. Na początku I etapu podróży odległość od celu wynosi: od miasta 1: d 1,2 + d 2,6,7 = d 1,2,6,7 50 + 170 = 220 km d 1,3 + d 3,6,7 = d 1,3,6,7 40 + 140 = 180 km d 1,4 + d 4,5,7 = d 1,4,5,7 30 + 140 = 170 km Z miasta 1 do 7 należy wybrać drogę d 1,4,5,7 = 170 km.
20
21 Załóżmy, że pomyliśmy drogi i wyruszając z miasta 1 zamiast do 4 pojechaliśmy do 3. Jak należy zaplanować dalszą trasę? od miasta 3: d 3,5 + d 5,7 = d 3,5,7 100 + 70 = 170 km d 3,6 + d 6,7 = d 3,6,7 90 + 50 = 140 km Wybieramy drogę d 3,6,7 liczącą 140 km.
22 Problem Wyboru najkrótszej trasy...
23
24 Problem alokacji zasobów Przedsiębiorstwo dysponuje środkami w wysokości 500 tys. PLN, które może przeznaczyć na inwestycje związane ze zwiększeniem zdolności produkcyjnych. Przewiduje się, że każda z inwestycji przyniesie określony zysk w zależności od ilości zainwestowanych środków pieniężnych. W jaki sposób zainwestować posiadane środki, aby osiągnąć maksymalny zysk? Spodziewany zysk od zainwestowanej kwoty w tys. PLN 100200300400500 Inwestycja I 25.65496120152.5 Inwestycja II 21.86490.4123.6135 Inwestycja III 395693116141
25 Na początku wyznaczamy optymalne decyzje w oparciu o Inwestycje I i II: Inw. II – kwota zainwestowana w II inwestycje S I, II – Suma zainwestowana w I i II inwestycje łącznie.
26 Następnie do analizy włączamy Inwestycję III, to znaczy badamy wszystkie trzy inwestycje łącznie: Inw. III – kwota zainwestowana w III Inwestycje S I, II, III – Suma zainwestowana w I, II i III inwestycje łącznie. Maksymalny zysk równy 162.6 tys. PLN uzyskamy inwestując 100 tys. PLN w Inwestycję III oraz 400 tys. PLN w Inwestycje II. Natomiast w Inwestycję I nie inwestujemy wcale.