CZTERY ETAPY W BADANIACH OPERACYJNYCH

1. Budowa modelu -określić cel działania, wyodrębnić czynniki, od których zależy osiągnięcie tego celu oraz określić zakres zmienności, konstruujemy model matematyczny (postać analityczną)

2. Rozwiązanie modelu, czyli wyznaczenie decyzji optymalnej w zależności od postaci analitycznej zbudowanego modelu stosujemy odpowiednie metody

3. Weryfikacja modelu i uzyskanego rozwiązania - analiza rozwiązania powinna być dokonana z punktu widzenia realności i stabilności rozwiązania tzn. odpowiedzi na pytania jak dalece rozwiązanie pozostaje aktualne

4. Wdrażanie modelu

MATEMATYCZNY MODEL DECYZYJNY składa się z trzech części: z funkcji celu, która dąży do max lub min z warunków ubocznych albo ograniczających i warunków brzegowych. W modelu dec. Wyróżniamy dwie grupy wielkości x1,.. są to zmienne dec. + wszystkie pozostałe to parametry.

KLASYFIKACJA MODELI DEC.

1. Ze względu na zmienne decyzyjne:

1. liniowe i nieliniowe

Jeśli wszystkie zmienne decyzyjne występują w pierwszej potędze to taki model to model liniowy. Ponadto, jeżeli te zmienne są ciągłe to określamy je jako programowanie liniowe. Jeżeli choć jedna ze zmiennych dec jest w innej potędze niż pierwsza to mamy model nieliniowy. Są to modele programowania nieliniowego..

2. Ze względu na parametry

1. deterministyczne i stochastyczne

Jeżeli wszystkie parametry są stałe i znane, to model deterministyczny. Jeśli choć 1 parametr jest niepewny albo niestały, to model stochast. Modele stochast.dzielą się na 3 typy

• probabilistyczne, jeżeli jeden parametr jest zmienną losową o rozkładzie prawdopodobieństwa

• stochastyczne - jeżeli choć 1 parametr jest zmienną losową o nieznanym rozkładzie prawd., ale za pomocą statystyki matemat.ten rozkład można oszacować

Tymi dwoma typami modeli zajmują się takie teorie jak programowanie sieciowe, teoria odnowy, teoria masowej obsługi (kolejek), programowanie dynamiczne

• strategiczne - w tego typu modelach o parametrze wiemy tylko tyle, że przyjmuje wartości z pewnego przedziału inaczej mówiąc znamy obszar zmienności parametru. Tą klasą modeli zajmuje się teoria gier

3. Ze względu na rolę czasu

1. statyczne - dotyczą jednego okresu

2. dynamiczne - więcej okresów

GEOMETRYCZNA METODA. Tą metodą można rozwiązywać modele z 2 ewentualnie 3 zmien.dec. M.G.składa się z 2 etapów.

1. Wyznaczenie obszaru dopuszczalnych rozwiązań, w gem. interpretacji obszarem dopuszczalnym będzie zbiór zawarty w I ćwiartce (wynika to z warunków brzegowych) Zostanie utworzona przez wykreślenie słabych nierówności. Obszar dopuszczalnych rozwiązań jest wielokątem wypukłym utworzonym z półpłaszczyzn.

2. Poszukujemy rozwiązania optymalnego - aby wyznaczyć rozwiązania optymalne wychodzimy z f- celu. Wyznaczamy równanie izokwanty. (linii na której wszystkie punkty mają tę samą wartość f.celu. Przy przesunięciu równoległym nie zmieniają się wspólcznynniki kierunkowe. Im dalej od początku układu współrzędnych tym większy zysk ale nie przekraczamy układu rozwiązań.

OGÓLNY MEDEL LINIOWY:

1. L(x)=Σ(j=1, n) cj*xj max (min)

2. Σ(i=1, m) aij*xj <=bi i=1,2...m

>=

=

3.xj>=0 j=1,2...n

Gzie: cj, bi, aij oznaczają parametry modelu

cj jest wagą (współczynnikiem) f.celu przy j-tej zmiennej dec.

bi jest wyrazem wolnym i-tego warunku ograniczającego

aij - współcz.przy j-tej zm.dec.przy i-tym warunku ograniczaj.

Wyrażenie I jest funkcja celu (funkcją kryterium) której wartość zależnie od przypadku jest maksymalizowana lub minimalizowana. Nierówność oraz równanie w punkcie II tworzą układ warunków ograniczających model (warunki uboczne).

Model nazywamy modelem o postaci standardowej w którym wszystkie ograniczenia są nierównościami typu mniejsze lub równe dla zadań na max lub większe lub równe dla zadań na min oraz wszystkie zmienne muszą być nieujemne. Model w którym wszystkie warunki ograniczające są równaniami nazywamy modelem o postaci kanonicznej.

PODSTAWOWE OKREŚLENIA METODY PL

Rozwiązaniem dopuszczalnym PL jest wektor X spełniający warunki uboczne i brzegowe modelu. Rozwiązaniem podstawowym modelu nazywamy takie rozwiązanie dopuszczalne, które posiada nie więcej niż m dodatnich wartości xj. Niezdegenerowanym rozw. podstawowym nazywamy takie rozw., które zawiera dokładnie m dodatnich wartości xj.

Zdegradowane rozwiązanie podstawowe posiada mniej niż m dodatnich wartości xj.

PODSTAWOWE TWIERDZENIA METODY PL

1. Jeżeli optymalne rozwiązanie PL istnieje to przynajmniej 1 rozwiązanie podstawowe jest rozwiązaniem optymalnym

2. Zbiór wszystkich rozwiązań dopuszczalnych PL jest zbiorem wypukłym. Zbiór przestrzeni N wymiarowej jest zbiorem wypukłym jeśli ma tę własność że każdy punkt będący kombinacją liniową wypukłą punktów wierzchołkowych należy do zbioru, tzn.
   

3. Jeżeli wektory dla i=1,2,3 .... N są rozwiązaniem optymalnym PL to wektor ... będący kombinacją liniową wypukłą jest rozwiązaniem optymalnym

Dotyczy to kiedy izokwanta pokrywa się z wierzchołkami.

4. Max liczba rozwiązań podstaw.= się ilości kombinacji (n m)

ETAPY METODY SIMPLEX

1. znaleźć rozwiązanie podstawowe

2. zbadać czy wyjściowe rozwiązanie podstawowe jest optymalne. Aby to stwierdzić trzeba wyliczyć pewne wielkości. W tej metodzie pojawia się kryter.optymaln.

3. jeśli nie jest optymalne musimy znaleźć lepsze rozwiązanie podstawowe. W geometrycznej interpretacji oznacza to przechodzenie z jednego wierzchołka na drugi, przy czym zawsze na lepszy.

ZAŁOŻENIA METODY SIMPLEX

1. Model postaci kanon.(mamy m war.ubocznych, m<n)

2. Wśród n wektorów Aj m wektorów jest liniowo niezależ.

3. Zakładamy że mamy gotowe rozwiązanie podstawowe postaci X=(x1,x2..,xm,0,0,......0) i -te zmienne, które wchodzą do pierwszego rozwiązania podstawowego, j-te miejsca zerowe

Jeżeli rozwiązanie z punktu III jest 1st rozwiązaniem podstawowym to musi spełniać następujące warunki uboczne

Zakładamy że to rozwiązanie podstawowe jest rozwiązaniem niezdegenerowanym.

METODA SZTUCZNEJ BAZY (tzw. Metoda M)

Przy ustalaniu stanu początkowego spotykamy się z następującymi sytuacjami:

Przypadek I (<=) stosując algorytm simplex należy postać standardową modelu zamienić na postać kanoniczną. Jeżeli wszystkie bi są >0 to rozwiąz.podstawowe jest natychmiastowe

Przypadek II jeżeli układ warunków ubocznych jest w postaci równań. W tym przypadku aby zbudować rozw.podstawowe w którym wektory bazy będą tworzyły macierz jednostkową należy do każdego równania wprowadzić tzw. zmienną sztuczną (fikcyjna) którą będziemy oznaczali przez ui dla i=1,2..m

Przepadek III jeżeli warunki uboczne są dane w postaci nierówności o znaku >= to aby zmienić te nierówności na równania należy do każdej nierówności wprowadzić zmienną swobodną ze znakiem -. Gdy wprowadzamy zmienne sztuczne nie jest spełniony warunek brzegowy, bo zmienne są ujemne nie możemy ustalić rozwiązania podstawowego. Musimy do każdego równania wprowadzić zmienną sztuczną ui.

Zmienne sztuczne nie maja interpretacji ekonomicznej. Wprowadzamy je tyko w celu rachunkowym w tych przypadkach (II i III) kiedy trzeba wprowadzić zmienne sztuczne, metoda nosi nazwę metody sztucznej bazy lub inaczej metody M.

TWIERDZENIA DOT SZTUCZNEJ BAZY

1. Jeżeli rozwiązanie wyjściowe ma chociaż jedno rozwiązanie optymalne to jest ono również rozwiązaniem zadania rozszerzonego. Zastosowanie metody simplex do zadania rozszerzonego zapewnia takie rozwiązania w którym każda ze zmiennych sztucznych równa się 0

2. Jeżeli zadanie wyjściowe nie ma rozwiązania, to rozwiązanie zadania rozszerzonego będzie miało przynajmniej jedno ui dla i=1....m dodatnie.

ALGORYTM TRANSPORTOWY. Znajduje ono zastosowanie do rozwiązywania pewnych szczególnych przypadków modeli liniowych. Na określonym terenie istnieje n-dostawców

i każdy z nich dysponuje odpowiednio ai>0 i=1,2,...,n jednostkami towaru. Jednocześnie istnieje m odbiorców j=1,2...m zgłaszających zapotrzebowanie na ten towar w ilościach bj. Przyjmijmy że są dane jednostkowe koszty transportu cij dla i=1,2,...n ; j=1,2...m. Jeżeli przez xij oznaczymy wielkość dostaw od i-tego dostawcy do j-tego odbiorcy to zagadnienie transportowe można zapisać:

I K= Σ(i=1, n) Σ(j=1, m) cij*xij --> min

II.1 Σ xij <= ai dla i=1,2...n

II.2 Σ xij = bj dla j=1,2...m

III xij >= 0 ; i=1,2...n; j=1,2...m

Jest to postać standardowa zagadnienia transport. Jeżeli warunek I jest równością to wówczas mamy do czynienia z postacią kanoniczną modelu transport., tzw. zamkniętym zagadnieniem. W zamkniętym zagad. transp. mamy MxN zmiennych oraz M+N warunków ubocznych. Powyższe zagadnienie można zapisać w następującej tablicy:

punkty punkty odbioru limity

odprawy 1 2 ..... m odprawy

1 x11 x12 ..... x1m a1

2 x21 x22 ..... x2m a2

: : : : :

n xn1 xn2 ..... xnm an

zaopatrz. b1 b2 ..... bn Σbj= Σai

ALGORYTM ROZWIĄZ.ZAMKN.ZAD.TRANSPORT.(3 ETAPY):

Etap I: ustalenie planu podstaw.(metoda LG rogu, metoda min. elementu w macierzy)

# metoda LG rogu - polega na kolejnym przyporządkowaniu zmiennym odpowiednich wartości, przy czym każdorazowo dla tych tras, kt. znajdują się w LG rogu tablicy przewozów. Poszukiwanie rozwiązania podst. rozpoczynamy od wartości xij dla trasy (1,1). Wartość tą wyznacz.wg wzoru:X11=min(a1, b1) Następnie od wartości A1 i B1 odejmujemy X11 eliminujemy z dalszych rozważań wiersz lub kolumnę, dla której różnica jest dodatnia, do dalszych obliczeń przechodzimy z wartością tej różnicy i znów rozp.powyższe oblicz.przesuw.się do PD rogu.

Aby rozwiązanie podst., było niezdegenerowane musi być spełniony warunek M+N - 1 <= liczbie wypełnionych kratek.

# Metoda minimalnego elementu macierzy - polega na poszukiwaniu w macierzy kosztów bezpośrednich, najniższego kosztu. Dla tej trasy max przewóz, jaki może być zrealizowany za wzgl. na podaż i popyt. Następnie odpowiednio aktualizujemy (zmniejszamy) podaż odpowiedniemu dostawcy i popyt odpowiedniemu odbiorcy o wyznaczony przewóz. Macierz Cij aktualizujemy usuwając z niej wiersz lub kolumnę, której odpowiada 0 podaż lub zerowy popyt. Powyższą procedurę powtarzamy aż do wyznaczenia M+N-1 tras bazowych.

Etap II : sprawdzamy czy rozw. podst. jest optymalne. W tym celu wychodzimy z jednego z planów ustalonych powyższymi metodami. W tym celu wyznaczamy tablicę kosztów pośr.cij odpowiadającą rozwiązaniu podst. Istnieją 2 sposoby wypełniania tablicy Cij: - metoda bez nazwy

-Metoda potencjałów -polega ona na przyporządkowaniu każdemu pkt.nadania liczby Ui i każdemu pkt.odbioru Vj. Powyższe oznaczenia muszą spełniać następujący układ równań: Cij* = Ui + Vj. Układ ten posiada k równań oraz k+1 niewiad., można więc nadać 1 zmien.dowolną wartość np. U1=0

Następnie obliczamy kryterium optymalności: Δ j = Cij* - Cij (różnica kosztów pośrednich i bezpośrednich). Jeżeli wszystkie elementy tablicy Δj są <=0 to kończymy obliczenia. Otrzymane rozwiązanie podst.jest optymalne. Jeżeli choć 1 kratka jest >0 to rozwiąz.nie jest optymalne, przechodzimy do modyfikacji rozwiąz

Etap III Modyfikacja rozwiązania. W tym etapie korzystamy z metody Simplex, która mówi, że do nowego rozwiąz.wprowadza się tę zmienną, dla której Δj jest największa. Wprowadzając tę zmienną do bazy musimy inną zmienną z bazy usunąć, a ponadto pociąga to za sobą zmianę wartości innych zmiennych. Reguły pozwalające na mechaniczne korygowanie wartości zmiennych, są następujące: w ostatnim planie wytyczamy graf zaczynając od kratki (Δj max),wprowadzając symbol "+" i na zmiany symbol "-" przy czym nie wolno zmieniać kierunku przez puste kratki. Ilość ładunku, jaką należy przenieść jest = max liczbie ze znakiem "-". W met.Simplex jest to wartość Q. Po ustaleniu planu 2 i obliczeniu jego kosztów należy stwierdzić, czy jest on optymalny, powtarzamy etap II, aż wszystkie Δj<=0.

OTWARTY PROBLEM TRANSPORTOWY - jeśli Σai ≠ Σbj, to

wówczas mówimy o otwartym zadaniu transportowym. Aby można było do takiego zagadnienia zastosować algorytm transportowy, należy zadanie to zbilansować. Jeżeli Σ limitów odprawy jest > niż zapotrzebowanie, to tworzymy dodatkowy punkt odbioru zgłaszający zapotrzebowanie równe różnicy pomiędzy dostawcami a zapotrzebowaniem. Koszty transportu między tymi fikcyjnymi pkt.odbioru a dostawcami zakładamy =0.

DUALIZM W PROGRAMOWANIU LINIOWYM

Dla każdego zadania decyzyjnego nazwanego zadaniem pierwotnym, istnieje pewne inne liniowe zadanie decyzyjne nazywane zadaniem dualnym. Aspekt matematyczny: Załóżmy, że mamy dany model w postaci standardowej, który będziemy nazywali modelem pierwotnym.

I L((x) = Σcj *xj --> max.

II a11 X1 + a12 X2 + .... + a1n Xn <= b1

a21 X1 + a22 X2 + ....+ a2n Xn <= b2

: : : : : : :

am1 X1 + am2 X2 +....+amn Xn <= bm

III X1, X2, .... Xn >= 0 model dualny:

I K(x) = Σbi i Yi --> min

II a11 Y1 + a21 Y2 + .... + am1 Ym >= c1

a12 Y1 + a22 Y2 + ....+ am2Ym >= c2

: : : : : : :

a1n Y1 + a2n Y2 +....+amn Ym >= cn

III Y1,Y2 ,....,Ym >= 0

WŁASNOŚCI PROGRAMU DUALNEGO:

1. jeżeli w zadaniu pierwotnym chodzi o maksymalizację wartości funkcji celu to w zadaniu dualnym wartość f. celu będzie minimalizowana , i odwrotnie.

2.liczba zmiennych w zadaniu dualnym jest równa liczbie równań w zadaniu pierwotnym.

3. wagi funkcji celu zadania pierwotnego są wyrazami wolnymi zadania dualnego

4.wyrazy wolne zad. pierwotnego są wagami f. celu zadania dualnego.

5. macierz współczynników przy zmiennych decyzyjnych w programowaniu dualnym jest macierzą transponowaną macierzy z programowania liniowego

6.kierunek nierówności w war. ubocznych programu dualnego jest przeciwny.

ZWIĄZKI MAT. MIEDZY PROGR.PIERWOTNYM A DUALNYM:

1.przy dowolnych rozwiązaniach dopuszczalnych program. pierwot. i programu dualnego zachodzi warunek :

ΣCj*Xj <= Σbi*Yi

wartość funkcji celu programowania pierwotnego nie przewyższa funkcji celu prog. dualnego.

2. oba programy (pierw. i dualny) mają rozwiązania optymalne. Są to takie i tylko takie rozwiązania, przy których wartości funkcji celu obu programów są sobie równe:

Σ Cj*Xjo = Σbi*Yio

Xjo j= 1,2...,n - optymalne rozwiązanie programu pierwotnego

Yio i= 1,2,...,m - optymalne rozwiązanie programu dualnego

3. na to, aby wektory X jo Yio były odpowiednimi optymalnymi rozwiązaniami swoich programów potrzeba i wystarczy, aby spełnione były następujące warunki(tzw. twierdz. o równowadze)

Ai1 X1o + Ai2 X2o+ ...+ Ain Xno < Bi to Yio = 0

A1j Y1o + A2j Y2o +...+ Amj Ymo > Cj to Xjo = 0

ZASTOSOWANIA METOD PL

1. wybór rozmiarów i struktury produkcji w przedsiębiorstwie (model działalności zakładu) oznaczenia: Xi dla j=1,2,...,n - ilość wyrobów produkowanych przez przeds.

Aij dla i=1,2...,m ; j=1,2,...,m - nakłady i-tego środka produkcji na jednostkę j-tego wyrobu

Bi dla i=1,2,...,m - limity i-tego środka produkcji

Cj dla j=1,2,...,n - zysk ze sprzedaży j-tego wyrobu

Uj dla j=1,2,...,n - dolna granica wlk. produkcji j-tego wyrobu

Vj dla j=1,2,...,n - górna granica produkcji j-tego wyrobu

L((x)= Σ CjXj --> max

Σ Aij Xj <= Bi , i=1,2,...,m

Uj <= Xj <= Vj , j=1,2...n

2. problem mieszanki (diety)

Aij dla i=1,2...,m ; j=1,2,...,n - zawartość i-tego składnika odżywczego w jednostce j-tego produktu

Pj dla j=1,2,...,n - jednostkowa cena j-tego produktu

bi dla i=1,2,...,m - norma żywieniowa i-tego skł.odżywczego

Xj dla j=1,2,...,n - ilość j-tego produktu wchodz.w skład diety.

Problem polega na tym, aby ułożyć najtańszą dietę, tj.sporządzić wykaż ilośc.artykułów żywn., aby koszt ich nabycia był najtańszy.

L(x) = Σ Pj Xj --> min

Σ aij Xj >= Bi i=1,2,..m

Xj >= 0 j=1,2,...n

3. Wybór procesu technologicznego. Zagadnienie wyboru pr. technologicznego ma wiele różnorodnych wariantów.

A) planowanie produkcji wg procesów technologicznych

Aij dla i=1,2,...,m ; j=1,2,...,n - wielkość produkcji wyrobów "i" na jednostkę czasu , przy j-tym procesie technologicznym

Xj - skala, w jakiej powinny być produkow.proc.technologiczne,

Bi - wielkość produkcji, jaką przedsiębiorstwo ma dostarczyć,

Cj - koszty 1 uruchomienia j-tego procesu technologicznego

Należy dobrać taki proces technologiczny, aby dostarczyć produkcję w żądanych ilościach , przy najmniejszych kosztach.

L(x) = Σ Cj Xj --> min

Σ aij Xj = Bi i=1,2,...,m

Xj >= 0 j=1,2,...,n m < n

Warunek uboczny oznacza , że należy tyle produkować, jakie jest zapotrzebowanie. Ilość wytwarzanych wyrobów nie może być większa od liczby użytych procesów technologicznych.

B) planowanie prod.budowl.(mieszkań) wg technik budowlanych

j=1,2,...,n - rodzaje technik budowlanych

Xj dla j=1,2,...,n - ilość metrów kwadratowych powierzchni mieszkalnej wybudowanych techniką "j"

Bi - limity materiałów budowlanych

Aij - nakłady i-tego materiału budowlanego na j-tą technikę

Załóżmy, że produkcją budowlaną są mieszkania. Budować je można przy pomocy rozmaitych technik. Na jednostkę produkcji budowlanej np. 1 m^2 budowli, zużywa się materiały budowlanej w różnych ilościach, w zależności od rodzaju techniki. Materiały budowlane, siła robocza są w ilościach ograniczonych..

Problem polega na tym, aby wyznaczyć ile mieszkań i jaką techniką wybudować, aby wyprodukować max mieszkań.

Z= X1 + X2 + ...+ Xn --> max

ΣAij Xj <= Bi i=1,2,...,m

Xj >= 0 j=1,2,...,n

4. Problem przydziału maszyn do wykonania pewnych czynności

i=1,2,...,m - oznacza liczbę maszyn, j=1,2,...,n - l.czynności

Ai , i=1,2,...,m - max czas pracy i-tej maszyny

Bj , j=1,2,...,n - ustalony z góry czas wykonywania czynn. j-tej

Xij - czas pracy maszyny i-tej na wykonanie czynności j-tej

Wij - wydajność i-tej maszyny przy wykorzystaniu czynności

Przy tych oznaczeniach f. celu polega na max łącznej wydajności wszystkich maszyn I Z= ΣΣ Wij Xij --> max

II Σ Xij = Bj j=1,2,...,n III Xij >= 0

Σ Xij = Ai i=1,2,...,m

Σ Ai = Σ Bj

PROGRAMOWANIE LINIOWE W LICZBACH CAŁKOWITYCH

Programowanie w liczbach całkowitych jest jedną z 3 grup zadań wchodzących w skład programowania dyskretnego. W tego typu zadaniach wszystkie zmienne są liczbami całkowitymi. Drugą grupę stanowią zadania programowania binarnego, w których wszystkie zmienne są liczbami binarnymi. Trzecia grupa to programowanie liniowe mieszane ,gdzie część zmiennych to zm. ciągłe, część to zm. całkowite , a część to zm. binarne. Do zadań, w których wielkości zmiennych oznaczają ilość jednostek wyrobów niepodzielnych, tj. zadania na najlepszy podział zadań produkcyjnych między przedsiębiorstwa, na optymalizację programów produkcji itp. Często tego typu zad.rozwiązywane są zwykłymi metodami z kolejnym zaokrąglaniem wartości zmiennych do liczb całkowitych. W przypadku, gdy pojedyncza jednostka wyrobu stanowi b. małą część całej wielkości produkcji nie powoduje to istotnych zniekształceń. W przypadku odwrotnym można mówić tylko o pewnym przybliżeniu do rzeczywiście optymalnego planu z liczbami całkowitymi. Opracowano parę metod rozwiązywania zadań PL w liczbach całkowitych, z których najbardziej znaną jest met. Gommor'ego.

ISTOTA METODY GOMMOR'EGO

Liczba "a" jest kongruentna do liczby "b" , w tym i tylko w tym przypadku, gdy różnica a-b jest liczbą całkowitą. Kongruencję oznaczamy za pomocą trzech kresek poziomych. Wszystkie liczby całk. są kongruentne między sobą oraz kongruentne do 0

Część ułamkową liczby "a" będziemy określać jako najmniejszą liczbę nieujemną kongruentną do liczby "a". Część ułamkową liczby "a" będziemy oznaczać symbolem f(a). Części ułamkowe liczb całkowitych są równe 0. Własności kongruencji liczb:

1) if a = b => f(a) = f(b)

2) f(a+b) = f(a) +f(b)

3) if "n" jest liczbą C to dla dowolnego "a": n*a = f(n*a) = n*f(a)

ETAPY METODY GOMMORY'EGO

I etap - obliczeń nie różni się od zwykłych obliczeń algorytmu Simplex. Jeżeli plan optymalny spełnia wszystkie warunki zadania łącznie z warunkiem dotyczącym liczb całkowitych , to zadanie jest rozwiązane w pierwszym etapie.

II etap - Jeżeli niektóre wartości zmiennych w planie optymalnym są ułamkami, to ustala się ograniczenia dodatkowe, jakby odcinające ułamkową część rozwiązania, lecz utrzymujące w mocy wszystkie pozostałe warunki, kt. powinien spełniać plan optymalny. Ograniczenia dodatkowe dołącza się do wyjściowych ograniczeń zadania i tak rozszerzony układ rozwiązujemy ponownie metodą Simplex. Jeśli i tym razem rozwiązania optymalne posiada liczby ułamkowe to należy dać jeszcze 1 ograniczenie dodatkowe i proces obliczeń powtórzyć od początku. Algorytm pozwala po wykonaniu skończonej ilości kroków osiągnąć optymalne rozwiąz.w liczbach C, if ono istnieje.

PRZEDMIOT TEORII TEORIA ODNOWY

historycznym punktem wyjścia TO jest demografia matematyczna, której głównym zadaniem jest ustalenie zmian zachodzących w liczebności i strukturze populacji. Teorię demografii matematycznej można uogólnić na inne zbiory, których pewne elementy przybywają a inne ubywają. Jeżeli za zbiór przyjmiemy środki trwałe, to możemy traktować go jako populację, w której istnieje „wymieralność” i „narodziny” elementów tej populacji. Wymierają el., które zostają zużyte w procesie produkcji i muszą być z tego procesu usunięte, a rodzą się elem.nowe, wprowadzone do procesu produkcji.

DEFINICJA TEORII ODNOWY

podana przez Banasińskiego: TO stanowi zespół metod matematyczno-statystycznych służących do ustalenia prawidłowości w procesie ubywania elementów tworzących zbiór pewnych obiektów trwałego użytkowania oraz do określenia liczby obiektów, które w danym okresie będą musiały być zastąpione nowymi obiektami o takich samych lub podobnych własnościach. Odnowa środków produkcji dokonuje się w samym procesie produkcji, przy czym odbywa się odmiennie w przypadku środków obrotowych i środków trwałych. Środki obrotowe zużywają się w ciągu jednego cyklu obrotowego o znanym okresie i w końcu każdego takiego okresu muszą być odnowione, aby proces produkcyjny mógł być kontynuowany. Odnowa środków obrotowych nie nasuwa większych trudności, natomiast środki trwałe nie zużywają się w ciągu 1 cyklu produkcji i pozostają w procesie produkcyjnym przez dłuższy czas zwany okresem użytkowania danego środka

ZAŁOŻENIA TO:

-rozpatrywane środki trwałe są jednorodne,

-obiekty pozostają w użytkowaniu całkowitą liczbę okresów i ubywają w końcu okresu, tzn., że czas życia środków trwałych jest zmienną losową typu skokowego,

-proces zużywania się śr.trw. jest procesem reprodukcji prostej, a więc przez cały czas badania liczba obiektów jest stała,

-istnieje górny kres trwania obiektów wynoszących (omega) lat.

2 RODZAJE PROCESÓW ODNOWY:

a)proces odnowy w pełnym toku- oznaczamy przez t jednostkę czasu, w rozpatrywanym zbiorze znajdują się obiekty wprowadzone do użytkowania przed rokiem, 2 laty,…,”omega”-laty; oznaczamy N0 (t-1), N0(t-2), …,N0(t- „omega”) liczbę obiektów wprowadzonych do użytkowania odpowiednio w roku: t-1,t-2,…t-„omega”, przez p1,p2,…,p”omega” prawdopod.ubytku spośród obiektów (współczynnik eliminacji) wprowadzonych:

• przed rokiem wychodzi z użytkowania N0(t-1)p1

Ogólna liczba ubytku w t: No(t)=No(t-1)p1+...+No(t-omega)pw

Aby wyrównać powstały ubytek w roku t należy wprowadzić tyle obiektów ile ulega wycofaniu; oznaczamy tę liczbę przez N0 (t), którą trzeba wprowadzić do użytkowania. Określa ono liczbę obiektów N0(t), które trzeba odnowić w danym roku dla wyrównania ubytku obiektów wychodzących z zużycia.

b)rozwijający się proces odnowy w przypadku rozwijającego się procesu odnowy przyjmujemy, że pierwsze obiekty zostały wprowadzone do użytkowania w roku t=0 i w liczbie N0(0). Liczba obiektów, które trzeba odnowić w kolejnych latach dla t=1,2,…,”omega”-1 wynosi: No(1)=No(0)p1

No(2)=No(1)p1+No(0)p2 ......

No(w-1)=No(w-2)p1+...+No(0)pw-1

TO ustala prawidłowości w procesie ubywania elementów tworzących zbiór pewnych obiektów trwałego użytkowania oraz określa liczbę obiektów, które w danym okresie będą musiały być zastąpione nowymi obiektami. Jednak TO nie ogranicza się do wspomnianych zagadnień, zajmuje się również wyznaczaniem optymalnego okresu użytkowania.

WYZNACZANIE OPTYMALNEJ POLITYKI ODNOWY

1.w zakresie obiektów, które psują się nagle. Należy wyróżnić 2 rodzaje kosztów wymiany:

k1-koszt wymiany urządzenia zużytego;

k2-koszt wymiany urządzenia jeszcze sprawnego.

Zakładamy, że koszt wymiany urządzenia zużytego jest wyższy niż koszt wymiany urządzenia jeszcze sprawnego, czyli k1>k2. Jeżeli powyższa nierówność zachodzi to może się okazać, że opłaca się wymienić wszystkie urządzenia, kiedy jeszcze są sprawne. Kryterium wyboru optymalnej polityki odnowy jest min sumy kosztów odnowy. Na podstawie równań odnowy obliczamy ile w poszczególnych latach przeciętnie zużyje się urządzeń. Następnie wyliczamy przeciętny wydatek na jeden okres wynikający z polityki odnowy wszystkich urządzeń, co jeden okres, co dwa, itd. Optymalna wartość odpowiadać będzie najniższemu wydatkowi przeciętnemu na jeden okres. Min. koszt wskazuje nam, po którym okresie czasu najkorzystniej jest wymienić wszystkie urządzenia.

2.obiekty, których koszty utrzymania rosną z czasem,

obiekty tej grupy w miarę upływu czasu starzeją się fizycznie i moralnie. Po pewnym czasie eksploatacja urządzenia staje się tak kosztowna, że zachodzi konieczność jego wymiany na nowe. W związku z tym powstaje problem wyznaczenia optymalnego okresu użytkowania urządzenia tzn., w jakim momencie stare urządzenie powinno być wymienione na nowe.

Funkcja kryterium w tym przypadku stanowi min przeciętne roczne koszty. Przyjmujemy, że koszty utrzymania rozpatrywanego obiektu są niemalejącą funkcją czasu, a wartość złomu jest stała. Oznaczenia:

C-koszt zakupu urządzenia, S- wartość złomu, n- liczba lat eksploatacji, T- przeciętne roczne koszty całkowite, F(t)- stopa wydatków na utrzymanie urządzenia. Zagadnienie polega na znalezieniu wartości n, która min małe T. przy tych oznaczeniach koszty całkowite występujące w ciągu okresu n lat wynoszą:

Roczny przeciętny koszt jest dany wzorem:

Chcąc obliczyć min T różniczkujemy względem n i przyrównujemy do 0

Biorąc pod uwagę, że f(0)=0 oraz, że f(n) jest funkcją niemalejącą utrzymujemy warunek min funkcji w postaci f(n)=T. a więc min T nastąpi dla takiego n, dla którego nakłady bieżące f(n) (stopa utrzymania) zrównają się z dotychczas poniesionymi przeciętnymi kosztami. Opierając się na tych wynikach możemy zadecydować, kiedy należy odnowić urządzenie pod warunkiem, że dysponujemy dokładnym wzorem określającym koszty utrzymania. Jeżeli mamy dane roczne koszty utrzymania to nie musimy korzystać z przedstawionych wyżej warunków gdyż możemy przystąpić do wymiany urządzenia wówczas, gdy przeciętne koszty osiągają min. przeciętne koszty roczne obliczamy następująco: od wartości początkowej odejmujemy wartość złomu a dodajemy bieżące koszty eksploatacji liczone od początku aż do danego roku włącznie i dzielimy przez okres użytkowania

TEORIA GIER

podstawowe pojęcia teorii gier

Nazwa gier pochodzi od pierwszej dziedziny zastosowań a mianowicie od analizy strategii dwóch walczących stron. Za prekursora nowoczesnej teorii gier uważa się francuskiego matematyka E. Borell'a. Polak Hugo Steinhaus. Za początek związku teorii gier i ekonomii uważamy 1944 rok, opublikowanie książki „Teoria gier i zachowania ekonomiczne”. Podstawowym pojęciem teorii gier jest konflikt, który wywołany jest przez rzadkość pewnych dóbr, często jest też motywowany psychologicznymi przesłankami konkurujących przedmiotów. Podmioty konkurujące będziemy nazywać graczami, a grą zbiór reguł określających możliwe zachowanie się uczestników gry.

Inna definicja mówi, że gra to sformalizowany model sytuacji konfliktowej. Klasyfikacja gier zależna jest od zespołu reguł określających daną grę, a mianowicie:

1.istotna jest liczba uczestników; powinno ich być min 2, może być znacznie więcej, przyjmujemy jednak, że liczba uczestników jest jednak skończona;

2.każdy uczestnik dysponuje skończoną liczbą możliwych sposobów działania, są to strategie gracza;

3.uczestnik, który chce się posłużyć teorię gier musi znać wszystkie dostępne pozostałym graczom sposoby działania i efekty, lecz nie może wiedzieć, który z nich zostanie obrany;

4.gdy wszyscy obrali swe działania wielkość wygranych, które każdy może uzyskać jest skończona;

5.wygrana każdego gracza zależy zarówno od działania pozostałych graczy jak i od jego działania;

6.wszytskie możliwe wyniki są mierzalne.

Ponadto zakłada się racjonalność gracza. Oznacza to, że dąży on do max wygranej lub min przegranej. Może to osiągnąć wchodząc w koalicję z innymi graczami, przez co może zwiększyć swoje wygrane. Celem gry jest wygrana, tzn. wypłata jest to wielkość wygranej jednego z graczy. Czasami może oznaczać stratę. Każdą grę charakteryzuje wartość gry, czyli uśredniona wielkość wypłaty, jaką by otrzymał gracz stosując optymalne strategie. Jeżeli ilość strategii każdego z graczy jest liczbą skończoną to taką grę nazywamy zamkniętą. Jeśli rozum gracza i reguły gry decydują o tym, że powinien stosować tylko jedną ze strategii to mówimy o strategii czystej. Jeżeli reguły decydują, że w celu optymalizacji wyniku gry należy stosować kilka strategii z różnymi częstościami to mówimy o strategiach mieszanych.

Dotyczy to gier wielokrotnie powtarzalnych.

II GRY DWUOSOBOWE O SUMIE 0

Są to najprostsze działania antagonistycznych stron. Mamy 2 graczy X i Y. Każdy z nich ma skończoną ilość strategii. Gracz X ma „m” strategii, a gracz Y „n” strategii. Wygrana jednego z graczy jest jednocześnie przegraną drugiego gracza, tzn. suma wygranych dwóch graczy =0. Oznaczamy przez:

x1, x2, …, xm- kolejne strategie pierwszego gracza.

Zakładamy, że pierwszy z nich jest graczem wygrywającym, a drugi- przegrywającym. Oznaczamy przez:

aij- liczbę, która będzie oznaczała wypłatę dla gracza pierwszego, gdy stosuje on i-tą strategię, a gracz drugi zastosował j-tą strategię.

Macierz złożoną z elementów aij dla i=1,2,…,m; j=1,2,…,n będziemy nazywali macierzą wypłat gracza X. macierz tę możemy zapisać w sposób następujący:

Gracz X będzie się starał zmaksymalizować swoją wygraną, a gracz Y zminimalizować swoją przegraną. Ujemna wygrana gracza X oznacza wygraną gracza Y. Ważną cechą charakteryzującą grę są dolne i górne wartości gry.

Jeżeli gracz X stosuje strategię i-tą to otrzyma, co najmniej minimum aij jednostek wypłaty. Ponieważ dąży on do maksymalizacji wyrażenia min aij, czyli szuka takiej strategii, która zapewni mu:

V1= max min [aij]

Stosuje, więc on strategię maxyminową. Jest to strategia gwarantująca, co najmniej wypłatę= V1. Wielkość V1 to dolna wartość gry. Natomiast gracz drugi postępuje odwrotnie. Minimalizuje wygraną, która zgodnie z przyjętymi założeniami jest najczęściej przegraną. Szuka, więc takiego :

V2= min max [aij]

Stosuje on, więc strategię, która gwarantuje, że nie przegra więcej niż V2 jednostek niezależnie od strategii gracza X. wartość V2 to górna wartość gry. Powyższe strategie gracza X i Y są to tzw. strategie MINIMAXU. Zawsze V1<= V2, co oznacza, że dolna wartość gry nie przekracza górnej wartości gry.

PRZYKŁAD

W celu sprawdzenia czy gra ma rozwiązanie w zbiorze strategii czystych wyznaczamy min wartość w każdym wierszu, tzn. przyjmujemy, że gracz Y wybiera najbardziej niekorzystną dla X strategię oraz max wartość w każdej kolumnie tzn., że gracz Y zakłada, że X wybiera najgorszą dla niego strategię. Gracz X wybierze tę strategię, dla której min wygrana będzie największa. Dla Y wybierze tę strategię, dla której max przegrana jest najmniejsza. Jeżeli max z min wygranych jest = min z max przegranych to mówimy, że istnieje rozwiązanie gry w zbiorze strategii czystych. Jest to punkt siodłowy inaczej punkt równowagi.

Istnieją gry bardziej skomplikowane i w tych przypadkach istotne jest ustalenie czy w macierzy występuje zasada dominacji.

Cechy zasady dominacji:

1.jeżeli wszystkie elementy w danej kolumnie są >= odpowiedniemu elementowi w innej kolumnie i co najmniej jeden jest większy to kolumna jest zdominowana;

2.analogicznie, jeżeli wszystkie elementy w danym wierszu są <= odpowiednim elementom w innym wierszu i co najmniej jeden jest < to wiersz ten jest zdominowany, oznacza to, że gracz X powinien odrzucić strategię i-tą, w której wszystkie aij są mniejsze lub, co najwyżej równe aij (zdominowane), podobnie gracz Y powinien odrzucić strategie , które dominują nad pozostałymi. Umożliwia to uproszczenie i redukcję macierzy gry.

GRY Z NATURĄ

Stanowią odrębną klasę gier. Zakładają one nieantagonistyczność przeciwnika, którym jest bardzo ogólnie rozumiana natura. Natura może być reprezentowana przez warunki klimatyczne, jakość surowca, zasobność łowisk. Tylko osoba podejmująca decyzje jest graczem aktywnym. Natura nie wybiera dla siebie optymalnej strategii, lecz może istnieć pewien schemat losowy, który z różnymi częstościami realizuje poszczególne stany natury. Sytuacje, które możemy modelować przy pomocy gier z naturą powstają w warunkach:

1.prognostycznych- nowe ceny, koszty, zmienne warunki handlu;

2.wprowadzenie nowych technik produkcyjnych;

3.planowanie i budowa inwestycji- nieznajomość przyszłych sytuacji;

4.zetknięciej działalności ludzkiej z rzeczywistym stanem natury- rolnictwo, leśnictwo.

Decyzje podejmowane przy pomocy gry z naturą:

a)jednorazowe- decyzja o podobnym charakterze nie była jeszcze podejmowana i dotyczy raz zaistniałej sytuacji;

b)powtarzalne- wielokrotnie stajemy przed koniecznością wyboru podobnych decyzji.

Ułatwienie w procesie wyboru decyzji w grach z naturą są to tzw. reguły decyzyjne ustalające kryteria porównywania i wyboru decyzji. Oprócz powtarzalności decyzji duży wpływ na wybór reguły decyzyjnej ma skala zysku i strat. Duże ryzyko i kosztowność strat skłaniają do ostrożności, natomiast małe ryzyko i małe koszty zachęcają do hazardu. Wprowadzimy następujące oznaczenia:

(omega)- przestrzeń stanów (strategii natury);

(eta)- jeden ze stanów natury;

1. przestrzeń decyzji (strategii ekonomisty);

aj- j=1,2, …, n j-ta decyzja ekonomisty;

Ujk- użyteczność j-tej decyzji, przy k-tym stanie natury.

Decydent stara się max użyteczność podejmowanej decyzji. Jednak nie zna częstości realizacji poszczególnych stanów natury. Sytuację taką możemy opisać przy pomocy tablicy:

Poszczególne reguły decyzyjne mówią nam, które ze strategii a1,12,…,an powinien zrealizować decydent. Mogą one wskazać jedną lub kilka decyzji optymalnych, przy czym każda z reguł może wskazać odmienne decyzje.

Reguły:

1.reguła WALDA (reguła max-min)- wbrew poprzednim założeniom o nieantagonistycznym działaniu natury zakłada ona aktywne przeciwdziałanie, czyli przyjęcie przez naturę najbardziej niekorzystnego dla decydenta stanu. Jest to właściwe przy dużej szkodliwości ewentualnych strat, wybieramy taką decyzję Dj, dla której :

Dj= max min Ujk (dop. Dług.)

Dla każdego wiersza określamy wartość min (zakładamy, że zajdą warunki najbardziej niekorzystne) a następnie z tych wartości wybieramy największą.

2.reguła HURWICZA- dla każdej decyzji bierzemy pod uwagę dwa ekstremalne stany natury tzn. najbardziej korzystny (max Ujk) i najbardziej niekorzystne (min Ujk) z odpowiednimi wagami. Wagi stanowi współczynnik optymizmu lub ostrożności alfa będące naszą subiektywną oceną prawdopodobieństwa wystąpienia najbardziej korzystnego stanu natury alfa [0,1]. Wybieramy decyzję Dj, dla której:

ponieważ współczynnik optymizmu alfa możemy ocenić tylko na podstawie danych z przeszłości, więc możliwość stosowania powyższej reguły decyzyjnej istnieje tylko dla decyzji powtarzalnych. Jeżeli alfa=1 to kryterium Hurwicza jest identyczne z kryterium Walda.

3.reguła BAYESA (LAPLACE'A)- przyporządkowuje ona poszczególnym stanom natury ……………… odpowiednie prawdopodobieństwa p1,p2,…pn. Przy czym pk>=0 suma pk=1.

Ponieważ prawdopodobieństwa są nieznane, więc reguła ta stosuje „zasadę równej racji”, czyli równość prawdopodobieństw zaistnienia poszczególnych stanów natury. Wtedy pk=1/m. wybieramy decyzję Dj taką:

Dj=

Regułę Bayesa należy stosować w przypadku decyzji powtarzalnych.

4.reguła SAVAGE'A- jest to reguła minimaxu skutków błędnej decyzji. W celu jej zastosowania musimy zbudować macierz zysków i strat alternatywnych (macierz żalu). Oznaczamy ją przez: [Ujk]

Strata jest różnicą między największą wygraną możliwą dla danego stanu natury, a wygraną odpowiadającą naszej decyzji. Elementy macierzy żalu konstruujemy wg wzoru:

Ujk= max Ujk - Ujk

Następnie w tak określonej macierzy dla każdego wiersza poszukujemy elementu max, a następnie wiersza, w którym wartość ta jest najmniejsza tzn. szukamy decyzji Dj, dla której zachodzi :

Dj= min max [Ujk]

Ideą tej reguły jest niedopuszczenie do zbyt wysokich strat wynikłych w skutek wyboru błędnej decyzji.

5.reguła PARETO- nakazuje wybrać tę decyzję, dla której :

Dj= [uik<=ujk]

Jest to, więc nic innego jak zjawisko dominacji jednej ze strategii decydenta nad innymi.

PROGRAMOWANIE SIECIOWE

1.istota i cechy charakterystyczne programowania sieciowego.

Podstawowym narzędziem konstrukcji i analizy PS jest teoria grafów. Zasadniczą cechą PS jest podział badanych przedsięwzięć na pojedyncze czynności. Przedsięwzięciem nazywamy operację składającą się z określonego zbioru czynności wzajemnie powiązanych w czasie. Oznacza to, że poszczególne przedsięwzięcia mają określone miejsce w całym przedsięwzięciu. Istnieją czynności, które muszą zachodzić w określonym porządku oraz pewne czynności, które mogą być wykonywane wspólnie gdyż są od siebie niezależne. Punktem wyjścia PS jest konstrukcja harmonogramu operacji, który należy wykonać w trakcie realizacji przedsięwzięcia. Jeżeli przykładowo przedsięwzięcie będzie realizowane w ciągu tygodnia to poszczególne czynności są znane dokładnie wraz z czasami ich realizacji. Realizację poszczególnych czynności należy projektować z uwzględnieniem warunków ograniczających. Można je podzielić na 4 grupy:

-ograniczenia strukturalne- dotyczą konieczności respektowania pewnych reguł dotyczących kolejności poszczególnych czynności. Należy znaleźć odp. na pytanie dotyczące każdej operacji, a mianowicie: jakie operacje należy wykonać przed rozpoczęciem operacji badanej? i jakie operacje należy wykonać po zakończeniu operacji badanej?

-ograniczenia lokalizujące w czasie- określają one czy rozpoczęcie i zakończenie danej operacji odbywało się w określonym z góry przedziale czasu,

-ograniczenia wynikające z niesubstytucyjności i niepodzielności zasobów- niektóre operacje nie mogą być wykonywane równolegle ze względów technicznych lub ze względu na niedostateczną ilość, np. maszyn,

-ograniczenia bilansowe- mogą dotyczyć liczby pracowników, sprzętu. W zależności od rodzaju problemu szuka się rozwiązania spełniającego następujące warunki:

*minimalny czas wykonania przy danym minimalnym koszcie,

*minimalny czas wykonania bez względu na koszt,

*minimalny koszt przy danym czasie wykonania,

*minimalny koszt w zależności od czasu wykonania.

2.elementarne pojęcia z teorii grafów

metody PS wykorzystują pojęcia i określenia z teorii grafów. W zależności od przedmiotu zastosowań poszczególne pojęcia maja następującą interpretację:

-PUNKT- w PS oznacza wierzchołek, węzeł, element;

-ŁUK- odcinek, linia, krawędź, kanał;

-PUNKT może oznaczać poszczególne elementy zbiorowości, określone zdarzenia lub poszczególne jednostki organizacyjne;

-ŁUK może oznaczać powiązania organizacyjne, czynności, które trzeba wykonać, trasy przekazania środków materiałowych, kanały łączności;

-GRAF może oznaczać połączenie punktów łukami, zbiory skierowanych krawędzi i wierzchołków, schemat strukturalny lub organizacyjny, sieć łączności lub sieć komunikacji;

-GRAF PŁASKI- graf, który można narysować na płaszczyźnie w taki sposób, aby żadne dwa wierzchołki nie pokrywały się i żadne dwa łuki nie przecinały się w punktach nie będących ich początkami ani końcami;

-PĘTLA- jest to łuk, którego początek i koniec pokrywają się;

-DROGA- to ciąg łuków grafu takich, że koniec każdego z nich pokrywa się z początkiem następnego;

-CYKL- to droga, która zaczyna się i kończy w tym samym wierzchołku;

-GRAF ZORIENTOWANY- jeżeli jego wierzchołki połączone są strzałkami wskazującymi kierunek i te zorientowane linie nazywamy łukami;

-SIEĆ- graf zorientowany bez pętli.

3.metody PS

rozwiązanie problemów ekonomicznych metodami sieciowymi wymaga zbudowania harmonogramów, czynności składających się na przedsięwzięcie. Jeśli łukom sieci przyporządkujemy odpowiednie czynności, natomiast wierzchołkom zakończenie poprzedniej i rozpoczęcie następnej czynności, to mówimy, że została określona tzw. sieć czynności. Metody PS zajmują się analizą sieci i wyznaczaniem optymalnych dróg przejścia przez sieć. Istnieje szereg metod PS, wśród których możemy wymienić 2 podstawowe:

1. PERT- powstała w 1958 roku w USA tzn. metoda planowania i kontroli w warunkach dużej niepewności;

2. CPM- metoda analizy drogi krytycznej opracowana w USA w 1956 roku.

Między tymi metodami różnice są niewielkie. Konstrukcja MS wymaga odróżnienia pojęcia czynności i zdarzenia.

Czynnością będziemy nazywać proces wykonywania określonego zadania cząstkowego będącego elementem przedsięwzięcia. Na rysunku oznaczamy strzałką.

Zdarzeniem (węzłem) nazywamy moment rozpoczęcia lub zakończenia danej czynności. Nie zużywa ono czasu i na rysunku oznaczamy kółkiem.

Zdarzenia i czynności tworzą razem sieć zależności (wykres sieciowy). Sieć zależności musi spełniać następujące warunki:

-istnieje jeden i tylko jeden węzeł, który nie jest końcem żadnej czynności,

-istnieje jeden i tylko jeden węzeł, który nie jest początkiem żadnej czynności,

-nie istnieją cykle.

Węzeł, który nie jest końcem żadnej czynności jest początkiem przedsięwzięcia. Węzeł, który nie jest początkiem żadnej czynności jest końcem przedsięwzięcia. Podstawowym problemem stosowania metod PS jest konstrukcja sieci czynności. Polega na :

-opracowanie spisu czynności, z których składa się przedsięwzięcie,

-ustalenie zdarzenia początkowego i końcowego,

-ustalenia dla każdej czynności:

*które czynności muszą być wykonywane przed rozpoczęciem danej czynności,

*które czynności muszą być wykonywane równolegle z daną czynnością,

*które czynności mogą się zaczynać po zakończeniu omawianej czynności,

-numerowanie węzłów w sieci,

-przyporządkowanie poszczególnym czynnościom czasu ich trwania.

Mając sporządzoną sieć czynności wraz z przyporządkowanymi czynnościami i czasami ich trwania przystępujemy do analizy sieci czynności. Analiza sieci czynności:

*ustalenie najwcześniejszych i najpóźniejszych momentów, w których zaczyna się i kończy dana czynność przy założeniu, że czynność pierwsza zaczyna się w momencie t=0, obliczmy je korzystając z czasów trwania czynności, których łączny czas limituje wykonanie całego przedsięwzięcia;

*wyznaczenie drogi krytycznej, czyli wskazanie tych następujących po sobie czynności, których łączny czas trwania limituje czas wykonania całego przedsięwzięcia;

*ustalenie zapasów czasu na czynności nie leżących na drodze krytycznej (dla czynności leżących na drodze krytycznej zapas czasu =0) wskazujących, jakie opóźnienia w realizacji tych czynności nie wpłyną na czas trwania całego przedsięwzięcia .

PRZYKŁAD

1.zbudować sieć czynności opisującą przedsięwzięcie

w trakcie realizacji przedsięwzięcia niektóre czynności muszą być wykonywane w określonej sekwencji jedno po drugim. Czynności takie tworzą w sieci pewien ciąg następujących po sobie łuków. Na przedsięwzięcie składają się także czynności, które mogą być wykonywane równolegle niezależnie od siebie. Jeżeli rozpoczęcie pewnej czynności wymaga ukończenia kilku czynności bezpośrednio ją poprzedzających to przedstawiamy je jako czynności schodzące się.

2.ustalenie najkrótszych możliwych czasów realizacji całego przedsięwzięcia. Wyznaczamy je przez Te i obliczamy w sposób następujący: stanowi początkowemu przyporządkowujemy chwilę równą zero. Jest to punkt wejściowy Te=0. Dalej przesuwamy się od wejścia do wyjścia z sieci. Każdemu punktowi sieci przyporządkowujemy największą z liczb równych

sumie czasów Te odpowiadającego jakiemuś punktowi łuku oraz oczekiwanego czasu „te” wykonania czynności.

3.dopuszczalne czasy najdłuższe Tl. Dla wyjścia sieci mamy Tl=Te. Następnie obliczamy Tl dla poszczególnych punktów przesuwając się od wyjścia do wejścia. Czas Tl odpowiadający jakiemuś punktowi, z którego wychodzi pewien łuk jest równy różnicy między czasem Tl odpowiadającym pewnemu punktowi i czasem potrzebnym na wykonanie pewnej czynności. Jeżeli z pewnego punktu wychodzi więcej niż jeden punkt to jako czas Tl przyjmuje się najmniejszą z różnic obliczonych w powyższy sposób. Obliczanie czasów Tl i Te dla wszystkich punktów sieci pozwala wyznaczyć ścieżkę krytyczną. Jest to ciągły układ łuków od wejścia do wyjścia siatki łączących punkty, których rezerwa czasu Rt=0.

Rt= Tl -Te

Rezerwę czasu nazywamy zapasem albo luzem.

METODA PERT

Tak jak metoda CPM korzysta z teorii grafów i posługuje się tymi samymi pojęciami. Różnice między nimi polegają na sposobie obliczenia czasów trwania czynności. Metoda CPM korzysta ze stałych czasów trwania czynności natomiast w metodzie PERT czasy trwania czynności traktowane są jako niezależne zmienne losowe, których rozkłady zbliżone są do rozkładu Beta. W metodzie pert posługujemy się dwiema granicznymi ocenami czasu optymistycznym-a i pesymistycznym-b. oprócz tych dwóch czasów korzystamy również z oceny czasów najbardziej prawdopodobnego i oznaczamy go „n”.

CZAS OPTYMISTYCZNY- jest to czas potrzebny dla realizacji czynności przy braku zakłóceń.

CZAS PESYMISTYCZNY- zakłada, że w trakcie realizacji czynności pojawiają się warunki nie sprzyjające (zakłócające) prawidłowy tok wykonania czynności. Prawdopodobieństwa wystąpienia czasu optymistycznego i pesymistycznego są bliskie 0.

CZAS NAJBARDZEIJ PRAWDOPODOBNY- jest to czas przeciętny czasów trwania wielokrotnej realizacji danej czynności.

Na podstawie tych trzech czasów wyznaczamy oczekiwaną wartość zmiennej losowej korzystając ze wzoru:

a-czas optymistyczny (najkrótszy czas trwania czynności)

b-czas pesymistyczny (najdłuższy możliwy czas trwania czynności)

m-czas modalny (najbardziej prawdopodobny).

Powyższy wzór przedstawia wartość oczekiwaną zmiennej losowej czasu trwania czynności poprzedzającej i następnej. Ponadto wyznaczamy wariancję.

1

---