Metody programowania sieciowego w zarządzaniu

Metody programowania sieciowego w zarządzaniu

przedsięwzięciami

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

.

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)

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

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

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.

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ą !!!

Oznacza to, iż optymalne rozwiązanie zagadnienia

z zakresu programowania dynamicznego, ma tę
własność, że:

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.

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.

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

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

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

.

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,5,7

=

d

1,3,5,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

.

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.