Programowanie sieciowe

background image

Plan zajęć

Wstęp teoretyczny
Optymalizacja struktury produkcji

Wstęp teoretyczny

Zagadnienia mieszanek
Wybór procesu technologicznego
Simpleks
Zagadnienie transportowe
Problemy przydziału
Kolokwium I
Programowanie sieciowe
Kolokwium II

CPM

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metody programowania sieciowego można zdefiniować jako techniki, które umożliwiają sprawne planowanie i
prowadzenie przedsięwzięć. Przedsięwzięcie jest to działanie człowieka, które zmierza do określonego celu,
jest zawarte w skończonym przedziale czasu, z wyraźnie zaznaczonym początkiem i końcem i realizowane
przy użyciu różnych zasobów (ludzkich, rzeczowych, finansowych itp.). Na przedsięwzięcie składa się szereg
czynności, które są ze sobą wzajemnie powiązane i są wykonywane w określonej kolejności. Zależność między
czynnościami i zdarzeniami określa strukturę logiczną modelu sieciowego.

Budowa modelu sieciowego składa się z następujących etapów:

+ sporządza się listę czynności, ustala relację między nimi oraz czas ich trwania (dla metod sieciowych
deterministycznych czas określony jest jednoznacznie, dla metod stochastycznych czas trwania czynności
określony jest z pewnym prawdopodobieństwem).
+ rysuje się wykres sieciowy, używając następujących graficznych symboli:

Czynność, część przedsięwzięcia cechująca się czasem trwania i zużywaniem zasobów,

Czynność pozorna, typ czynność, która nie zużywa czasu ani zasobów, a służy jedynie do
pokazania zależności między czynnościami,

Zdarzenie, określa stan zaawansowania prac. To moment rozpoczęcia lub zakończenia jednej lub
więcej czynności.

Dla zdarzeń przypisuje się kolejne numery identyfikacyjne, natomiast czynności porządkowane są parą
wskaźników i-j (i-numer zdarzenia rozpoczynającego czynność; j-numer zdarzenia kończącego czynność).

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zasady konstrukcji sieci (za chwilę kontynuacja etapów):

Wymagane jest, aby:

- istniał dokładnie jeden wierzchołek (zdarzenie) początkowy i jeden wierzchołek (zdarzenie) końcowy (zasadę
można spełnić wprowadzając czynności pozorne),

- wierzchołki i krawędzie (zdarzenia i czynności) były odpowiednio uporządkowane, poprzednik ma mniejszy
numer lub wcześniejszą literę od następnika,

- dwa zdarzenia miały połączenie tylko jedną czynnością, jeżeli kilka czynności wykonywanych równolegle jest
poprzednikami jednej, to należy wtedy wprowadzić czynności pozorne,

- strzałki, symbolizujące czynności, się nie przecinały.

Kolejne etapy:

+ wyznacza się podstawowe charakterystyki sieci dla poszczególnych czynności i zdarzeń (najwcześniejsze
możliwe i najpóźniejsze dopuszczalne momenty zaistnienia zdarzeń, zapasy czasu dla zdarzeń i czynności).,

+ wyznaczenie terminu końcowego dla przedsięwzięcia oraz ścieżki krytycznej.

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Przykładowa sieć:

Wykaz czynności

Zdarzenia: Sieć:

Przykład pochodzi z książki: „Metody ilościowe w organizacji i zarządzaniu”
Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadanie:

Narysować wykres sieciowy znając następujące zależności między czynnościami:

- czynności e i b rozpoczynają się po zakończeniu czynności a,
- czynności c,g rozpoczynają się po zakończeniu czynności b,
- czynność d rozpoczyna się po zakończeniu czynności c,
- czynność f rozpoczyna się po zakończeniu czynności g, ale nie wcześniej niż przed zakończeniem czynności
c.

Przykład pochodzi z książki: „Metody ilościowe w organizacji i zarządzaniu”

Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

Jak zmieni się wykres sieciowy, gdy uwzględnimy zależność, że czynność h rozpoczyna się po zakończeniu
czynności g?

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadanie:

Narysować wykres sieciowy znając następujące zależności między czynnościami:

- czynność f rozpoczyna się po zakończeniu czynności b,c,
- czynność e rozpoczyna się po zakończeniu czynności a,b,
- czynność d rozpoczyna się po zakończeniu czynności a.

Przykład pochodzi z książki: „Metody ilościowe w organizacji i zarządzaniu”

Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Analiza grafów sieciowych:

Analiza taka polega na:

- obliczeniu najkrótszego czasu wykonania programu pracy – określenie tzw. drogi krytycznej,
- wyznaczeniu drogi krytycznej (jej przebiegu) i czynności krytycznych (leżących na tej drodze), biegnących od
początkowego wierzchołka grafu do wierzchołka końcowego,
- określeniu czasów rozpoczęcia i ukończenia czynności – najwcześniejszych i najpóźniejszych terminów dla
czynności, będących składowymi grafu.

Analizę można przeprowadzić graficznie (na diagramie sieciowym) albo analitycznie (posługując się
algorytmami).

Co to jest droga krytyczna?

Drogą krytyczną nazywamy łańcuch czynności, które ma początek w zdarzeniu rozpoczynającym sieć, a koniec
w zdarzeniu ją kończącym, pozwalający na realizację wszystkich czynności zawartych w sieci. Jest to
najdłuższa droga przejścia przez sieć, zgodnie ze zwrotem czynności, rozpoczynając od zdarzenia
początkowego, a kończąc na końcowym. Na wykresie może być wiele dróg krytycznych, jedna droga może się
rozgałęzić na wiele dróg lub wiele dróg może się zbiegać w jedną.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda CPA – Critical Path Analysis

Drogę krytyczną możemy wyznaczyć posługując się dwiema metodami, które bazują na analizie czasowej
wykresu sieciowego.

Pierwsza metoda polega na przeanalizowaniu łącznego czasu trwania wszystkich czynności leżących na
możliwych do utworzenia ścieżkach. Ścieżki te prowadzą od początku wykresu do jego końca, a
przemieszczanie się musi być zgodne ze zwrotami linii łączących zdarzenia. Droga, która posiada najdłuższy
czas przewidziany na wykonanie wszystkich czynności w niej zawartych, stanowi drogę krytyczną.

Druga metoda bazuje na obliczeniach, do których używa się najwcześniejszych możliwych i najpóźniejszych
dopuszczalnych terminów zajścia zdarzeń. Wielkości te obliczane są początkowo i na ich podstawie wyznacza
się zapas całkowity czasu, jakim dysponuje każda czynność. Po obliczeniu zapasu czasu dla każdej czynności,
czynnościami krytycznymi będą te, które mają wartość zapasu całkowitego równą 0. Czynności krytyczne łączą
się w łańcuchy (łańcuch), które stanowią drogę krytyczną.

Opóźnienie jakiejkolwiek czynności krytycznej, powoduje opóźnienie całego przedsięwzięcia wyrażonego
wykresem sieciowym.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda CPA – Critical Path Analysis

Graficznie:

gdzie:

i-j – dowolna czynność na wykresie sieciowym
i – numer zdarzenia rozpoczynającego czynność
j – numer zdarzenia kończącego czynność
ti-j – czas trwania czynności i-j
NWi, NWj – najwcześniejsze możliwe terminy zaistnienia zdarzeń i,j
NPi, NPj – najpóźniejsze dopuszczalne terminy zaistnienia zdarzeń i,j

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda CPA – Critical Path Analysis

Obliczanie terminów:

Dla zdarzenia rozpoczynającego wykres przyjmuje się NW = 0.

Terminy następnych zdarzeń oblicza się korzystając z następującego wzoru:

NWj = max(NWi + ti-j)

Obliczenia terminów najwcześniejszych dokonuje się „w przód” wykresu sieciowego.

Gdy znany jest już termin najwcześniejszy zdarzenia ostatniego, zaczyna się obliczenia „wstecz” terminów
najpóźniejszych. Przyjmuje się jeszcze, że termin najpóźniejszy zdarzenia kończącego jest terminem
najwcześniejszym tego zdarzenia. Kolejne terminy oblicza się tak:

NPi = min(NPj - ti-j)

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda CPA – Critical Path Analysis

Zapasy - obliczanie:

Zapas całkowity – jest to czas, o który może być opóźnione rozpoczęcie danej czynności bez wpływu na termin
końcowy całego przedsięwzięcia. Wykorzystanie całego zapasu (ZC = 0) powoduje, że czynność staje się
czynnością krytyczną:

ZCi-j = NPj – NWi – ti-j ; (ZCi-j ≥0)

(zapasy dotyczące pozostałych, poza krytycznymi, czynności)

Zapas swobodny – mówi, o ile maksymalnie można opóźnić termin zakończenia czynności rozpoczętej w jej
terminie najwcześniejszym bez naruszenia najwcześniejszego możliwego terminu rozpoczęcia czynności
następnej:

ZSi-j = NWj – NWi – ti-j ; (ZSi-j ≥0)

Zapas krytyczny – wskazuje, o ile maksymalnie można opóźnić termin zakończenia czynności rozpoczętej w
terminie najpóźniejszym, bez naruszenia najpóźniejszego terminu rozpoczęcia czynności następnej:

ZKi-j = NPj – NPi – ti-j ; (ZKi-j ≥0)

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda CPA – Critical Path Analysis

Zapasy - obliczanie:

Zapas niezależny – mówi, o ile można maksymalnie opóźnić termin zakończenia czynności rozpoczętej w jej
terminie najpóźniejszym bez naruszenia najwcześniejszego terminu rozpoczęcia czynności następnej:

ZNi-j = NWj – NPi – ti-j

Zapas warunkowy – różnica zapasu całkowitego i swobodnego czasu dla czynności:

ZWi-j = ZCi-j – ZSi-j = NPj – NWj

Jest to wielkość czasu, która będąc wykorzystaną do opóźnienia danej czynności, wpłynie na opóźnienie
rozpoczęcia czynności następnej, ale bez wpływu na opóźnienie całego zadania.

Luz czasowy – określany jest dla zdarzeń niekrytycznych, wyrażony jako różnica pomiędzy terminem
najpóźniejszym i najwcześniejszym danej czynności:

Li = NPi – NWi

Lj = NPj– NWj

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Przykład

Narysować wykres sieciowy znając zależności między czynnościami:

- czynności c,d rozpoczynają się po czynności b,
- czynność e rozpoczyna się po zakończeniu czynności a,
- czynności f,g rozpoczynają się po zakończeniu czynności e,c,
- czynność h rozpoczyna się po zakończeniu czynności f,d,

Wykres sieciowy ma jedno zdarzenie rozpoczynające i jedno kończące.

Określić terminy najwcześniejsze, najpóźniejsze zaistnienia zdarzeń, obliczyć zapasy czasu dla każdej
czynności przy następujących czasach ich trwania:

ta = 3, tb = 2, tc = 3, td = 4, te = 4, tf = 5, tg = 3, th = 3

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie:

Wykres:

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie:

Metoda pierwsza wyznaczania ścieżki krytycznej:

Określa się wszystkie możliwe drogi przejścia pomiędzy zdarzeniem 1-6, wraz z ich łącznymi czasami.

1) 1 – 2 – 4 – 6 t

1

= 10

2) 1 – 2 – 4 – 5 – 6 t

2

= 15 – droga krytyczna

3) 1 – 3 – 4 – 6 t

3

= 8

4) 1 – 3 – 4 – 5 – 6 t

4

=13

5) 1 – 3 – 5 – 6 t

5

= 9

Metoda druga:

Określa się najwcześniejsze i najpóźniejsze terminy (są już na wcześniejszym wykresie).
Określa się zapas całkowity czasu dla wszystkich czynności:

ZC1-2 = NP2 – NW1 - t1-2 = 3 – 0 -3 = 0
ZC1-3 = NP3 – NW1 - t1-3 = 4 – 0 -2 = 2
ZC2-4 = NP4 – NW2 - t2-4 = 7 – 3 -4 = 0
ZC3-4 = NP4 – NW3 - t3-4 = 7 – 2 -3 = 2
ZC3-5 = NP5 – NW3 - t3-5 = 12 – 2 -4 = 6
ZC4-5 = NP5 – NW4 - t4-5 = 12 – 7 -5 = 0
ZC4-6 = NP6 – NW4 - t4-6 = 15 – 7 -3 = 5
ZC5-6 = NP6 – NW5 - t5-6 = 15 – 12 -3 = 0

W przypadku, gdy wynik wynosi 0, mamy do czynienia z czynnością krytyczną.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie:

Zapasy czasu:

ZS1-2 = NW2 – NW1 - t1-2 = 0
ZS1-3 = NW3 – NW1 - t1-3 = 0
ZS2-4 = NW4 – NW2 - t2-4 = 0
ZS3-4 = NW4 – NW3 - t3-4 = 2
ZS3-5 = NW5 – NW3 - t3-5 = 6
ZS4-5 = NW5 – NW4 - t4-5 = 0
ZS4-6 = NW6 – NW4 - t4-6 = 5
ZS5-6 = NW6 – NW5 - t5-6 = 0

ZK1-2 = NP2 – NP1 - t1-2 = 0
ZK1-3 = NP3 – NP1 - t1-3 = 2
ZK2-4 = NP4 – NP2 - t2-4 = 0
ZK3-4 = NP4 – NP3 - t3-4 = 0
ZK3-5 = NP5 – NP3 - t3-5 = 0
ZK4-5 = NP5 – NP4 - t4-5 = 0
ZK4-6 = NP6 – NP4 - t4-6 = 5
ZK5-6 = NP6 – NP5 - t5-6 = 0

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

ZN1-2 = NW2 – NP1 - t1-2 = 0
ZN1-3 = NW3 – NP1 - t1-3 = 0
ZN2-4 = NW4 – NP2 - t2-4 = 0
ZN3-4 = NW4 – NP3 - t3-4 = 0
ZN3-5 = NW5 – NP3 - t3-5 = 4
ZN4-5 = NW5 – NP4 - t4-5 = 0
ZN4-6 = NW6 – NP4 - t4-6 = 5
ZN5-6 = NW6 – NP5 - t5-6 = 0

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadania

Na poniższych wykresach wskaż drogę krytyczną, określ terminy najpóźniejsze i najwcześniejsze zdarzeń.

Zagadnienia teoretyczne pochodzą z książki: „Metody ilościowe w organizacji

i zarządzaniu” Pani Prof. L.Zawadzkiej

background image

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Metoda PERT:

W metodzie PERT czasy trwania poszczególnych czynności są zmiennymi losowymi. Rozkład
prawdopodobieństwa występowania różnych czasów trwania odpowiada znanemu w probabilistyce rozkładowi
beta, którego szczególnym przypadkiem jest rozkład normalny.

Dla każdej czynności znane są trzy oceny czasu jej trwania:

a – czas optymistyczny (tyle może trwać czynność w najbardziej sprzyjających warunkach)
b – czas pesymistyczny (czas trwania czynność w niesprzyjających warunkach)
m – czas modalny – najbardziej prawdopodobny, czas najczęściej występujący przy wielokrotnym powtarzaniu
czynności

Między ocenami zachodzi relacja: a ≤ m ≤ b.

Oczekiwany czas trwania czynności oblicza się ze wzoru:

natomiast odchylenie (wariancję) rzeczywistego czasu trwania czynności od wyznaczonego czasu
oczekiwanego:

t

e

=

a +4m+b

6

σ

ij

2

=

(

ba

6

)

2

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Zadanie:

Mając dane czynności składające się na przedsięwzięcie P, ich następstwo oraz czasy trwania określ:

a) czas oczekiwany t

e

b) najkrótszy czas trwania przedsięwzięcia
c) prawdopodobieństwo dotrzymania założonego terminu t

d

= 30 dni

Narysuj wykres sieciowy i wyznacz drogę krytyczną.

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

Czasy oczekiwane t

e

:

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

Wykres sieciowy:

:

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

Wykres sieciowy:

Najwcześniejszy oczekiwany termin zakończenia przedsięwzięcia wynosi 32 dni.

Droga krytyczna prowadzi przez czynności: 1-4-5-6-7-8

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

W naszej sytuacji termin zakończenia przedsięwzięcia jest wielkością losową, może się różnić od terminu
rzeczywistego. Dlatego też potrzebujemy znać odchylenie od tego terminu. W tym celu posłużymy się wariancją
terminu wykonania (σ

2

Tw

), która jest sumą wariancji czynności krytycznych.

Obliczamy wariancje dla czynności krytycznych:

Sumujemy poszczególne wariancje:

σ

14

2

=

(

7−1

6

)

2

=

1

σ

45

2

=

(

15−5

6

)

2

=

25

9

σ

56

2

=

(

14−2

6

)

2

=

4

σ

67

2

=

(

6−6

6

)

2

=

0

σ

78

2

=

(

4−4

6

)

2

=

0

σ

Tw

2

=

1+

25

9

+

4+0+0=

70

9

zatem σ=2,78

background image

Programowanie sieciowe

Optymalizacja

struktury produkcj

i

Zagadnienia

mieszanek

Wybór procesu

technologicznego

Simpleks

Wstęp teoretyczny

Problem przydziału

Kolokwium I

Programowanie

sieciowe

Kolokwium II

Zagadnienie
transportowe

Rozwiązanie zadania:

Obliczmy prawdopodobieństwo, że przedsięwzięcie będzie zakończone w pewnym narzucanym z góry terminie
t

d

(30 dni z treści zadania).

Skorzystamy ze wzoru:

td – narzucony z góry termin,

tw – oczekiwany termin wykonania przedsięwzięcia – najwcześniejszy możliwy termin zakończenia zdarzenia
końcowego (z naszej sieci 32 dni)

σ

2

Tw

wariancja terminu wykonania

Dla obliczonego współczynnika x = -0,71 z tablic dystrybuanty standaryzowanego rozkładu normalnego
odczytujemy prawdopodobieństwo dotrzymania narzuconego z góry terminu:

W praktyce przyjmuje się, że gdy wartość F(x) (dla naszego zadania F(-0,71) = 0,23885) jest w przedziale
(0,25;0,6), to termin dyrektywny nie jest zagrożony. Gdy jest ≤0,25 termin dyrektywny jest zagrożony, natomiast
gdy ≥0,6, to w przedsięwzięciu występuje duży zapas czasu.


:

x=

(

t

d

t

w

)

σ

TW

2

P

{

t

d

t

w

}

=

F ( x)

background image


Document Outline


Wyszukiwarka

Podobne podstrony:
Projekt badania operacyjne- programowanie sieciowe, Badania operacyjne
konspekt cw 4 programowanie sieciowe
Programowanie sieciowe przy użyciu gniazdek w?lphi 3 MPLMRFGCOQC4VOMKHU5DAT5YKUDWUHLWUTINXRI
Java Programowanie Sieciowe Podstawy Javy id 226331
Programowanie sieciowe 1
Programowanie sieciowe-1
PROGRAMOWANIE SIECIOWE MDR zadania
Programowanie sieciowe, Edukacja, Metody i Systemy Sterowania Produkcją
PROGRAMOWANIE SIECIOWE - MDR, zadania
08 Integracja Javy z innymi językami, programowanie sieciowe
programowanie sieciowe dzienne l2 podstawy javy Z5XS7QYSX4ALQFQWTRTRQREAPJWW7C4FBO7EGPI
programowanie sieciowe i dynamiczne, BADOP
Programowanie sieciowe - teoria, WZR UG, IV semestr, Ekonomika przedsiębiorstw - dr Mariusz Chmielew
08 Integracja Javy z innymi językami, programowanie sieciowe
2009 10 Programowanie przy użyciu gniazd sieciowych [Programowanie]
Programowanie usług sieciowych

więcej podobnych podstron