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.
Document Outline
