Badania operacyjne to nazwa dyscypliny, która zajmuje się metodyką rozwiązywania problemów decyzyjnych. Badania operacyjne są pomocne przy podejmowaniu decyzji gospodarczych. Jest to zbiór metod postępowania wspomagające podjęcie decyzji.

Podejmowanie decyzji polega na wyborze wariantu działania, który spełnia wszystkie warunki wyznaczane przez środowisko problemu i jednocześnie dąży do najlepszego osiągnięcia celu.

Etapy rozwiązywania problemów decyzyjnych:

1. Sformułowanie i identyfikacja problemu - opisujemy model.

2. Budowa matematycznego modelu - przełożenie etapu 1. na model matematyczny, utworzenie pewnej konstrukcji matematycznej.

3. Rozwiązanie modelu - w zależności od typu modelu wybieramy metodę rozwiązywania.

4. Ocena poprawności i realności uzyskanych rozwiązań oraz ewentualna weryfikacja modelu decyzji - wybieramy czynniki, które mają największy wpływ na rozwiązanie modelu. Jeżeli rozwiązanie nie jest optymalne to poprawiamy i rozwiązujemy od nowa.

1.BUDOWA MODELU DECYZYJNEGO

• Muszą być określone pewne parametry

• Muszą być wyodrębnione czynniki istotne

• Metoda rozwiązywania

K=f(D,Z)

F(D,Z)≥0

D=[x₁,x₂,...,x_k] - wektor zmiennych decyzyjnych

Z - zbiór wszystkich parametrów opisujących stany warunków zewnętrznych

K - funkcja korzyści, celu, kryterium

F - układ relacji, które stanowią układ warunków, które musza być spełnione, aby zapewnić realność podjętych decyzji, układ ograniczeń

Zagadnienie wyboru decyzji za pomocą modelu decyzyjnego polega na określeniu wartości zmiennych decyzyjnych, ze zbioru dopuszczalnych sposobów działania, opisanych warunkami ograniczającymi, tak, aby uzyskać najkorzystniejszą wartość funkcji celu (optimum funkcji celu).

Klasyfikacja modeli decyzyjnych:

• wg postaci analitycznej

• modele liniowe

• modele nieliniowe

• wg postaci zmiennych decyzyjnych

• ciągłe

• dyskretne

• mieszane

• wg charakteru parametrów

• deterministyczne

• stochastyczne

• wg występowania czynnika czasu

• statystyczne

• dynamiczne

MODELE LINIOWE

max

L(X)=c₁x₁+c₂x₂+...+c_kx_k (1)

min

a₁₁x₁+a₁₂x₂+...+a_1kx_k ≤ albo ≥ b₁ (2)

a₂₁x₁+a₂₂x₂+...+a_2kx_k ≤ albo ≥ b₂

: : :

a_n1x₁+a_n2x₂+...+a_nkx_k ≤ albo ≥ b₂

x₁≥0 x₂ ≥0 ... x_k≥0 (3)

1. funkcja celu

2. warunki uboczne, zgodności, ograniczające

3. warunki brzegowe

x_j (j=1,...,k) zmienne decyzyjne, niewiadome modelu

c_j (j=1,...,k) parametry funkcji celu np. zyski jednostkowe

a_ij (i=1,...,m) (j=1,...,k) parametry warunków ograniczających np. jednostkowe zużycie

b_i (i=1,...,m) np. ilości wartości posiadanych środków

wnioski i twierdzenia

Zbiór rozwiązań dopuszczalnych modelu PL jest zbiorem wypukłym.

Zbiór rozwiązań dopuszcz. Może być zbiorem:

-ograniczonym

-nieograniczonym

-pustym

-jednoelementowym

2.funkcja celu modelu program. Liniowego osiąga wielkość optymalną na wierzchołku wielościennego zbioru rozwiązań dopuszczalnych.

Gdy zbiór rozw. jest nieograniczony a funkcja celu jest maksymalizowana to nie ma rozwiązania optymalnego. Jeśli istnieje rozwiązanie optymalne to może być jedno lub nieskończenie wiele.

3.Jeżeli w modelu progr. Liniowego istnieją, co najmniej dwa rozw.optymalne o różnych wartościach wektorów zmiennych decyzyjnych to każda wypukła kombinacja liniowa tych rozwiązań jest również rozwiązaniem tego modelu.

2.MODELE PL W POSTACI STANDARDOWEJ I KANONICZNEJ

Jeżeli w modelu programowania warunki ograniczające mają charakter nierówności to model ma postać standardową.

Jeżeli warunki ograniczające w modelu PL mają charakter równań to model ma postać kanoniczną.

Każdą postać standardową można sprowadzić do postaci kanonicznej. W tym celu wprowadza się do modelu dodatkowe zmienne, które nazywa się zmiennymi swobodnymi lub bilansującymi.

n - liczba zmiennych w modelu postaci kanonicznej

m - liczba równań

n=m - jedno rozwiązanie

Gdy rząd macierzy głównej (parametrów stojących przy wszystkich zmiennych) jest większy od rzędu macierzy uzupełnionej to mamy nieskończenie wiele rozwiązań - układ rozwiązań nieoznaczony, wtedy stosuje się tzw. metodę eliminacji Gaussa - Jordana. Poszukujemy układu wektorów liniowo niezależnych, wektory bazowe, a każda jednoznaczna kombinacja tych wektorów daje rozwiązanie układu równań.

Twierdzenie:

Jeżeli zadanie modelu PL ma rozwiązanie optymalne to ma także rozwiązanie optymalne bazowe.

Wniosek: Rozwiązanie optymalne wystarczy szukać wśród rozwiązań bazowych, których liczba jest skończona. Rozwiązanie bazowe układu równań jest to dowolne rozwiązanie uzyskane przez przyjęcie za n-m zmiennych zero. Oraz rozwiązanie warunków ograniczających ze względu na pozostałe m zmiennych.

Maksymalna liczba rozwiązań bazowych jest równa liczbie kombinacji

C_n^n-m=n!/(n-m)!(n-n+m)!

Bazowe rozwiązanie dopuszczalne nazywa się rozwiązaniem podstawowym.

Rozwiązań podstawowych (bazowych dopuszczalnych) jest tyle ile jest wierzchołków wieloboku wypukłego

3.METODA SIMPLEX

Podstawy teoretyczne

L(X)=C^TX

AX=B

X≥0

X - wektor zmiennych decyzyjnych wymiaru n×1

C - wektor parametrów funkcji celu wymiaru n×1

A - macierz parametrów warunków ograniczających m×n

B - wektor wyrazów wolnych m×1

Postać wektorowa

A₁x₁+A₂x₂+A₃x₃+...+A_nx_n=B

A_i - wektor parametrów stojących przy zmiennych i

Macierz A jest rzędu n

n-m

X_P^T=[x₁,x₂,...,x_m,0,0,0]

n

i numer zmiennej bazowej

i=1, 2, ..., m

j=n+1, n+2,...,n - zmienne niebazowej

_i=1^mΣ A_iX_i=B (*)

L(X)= _i=1^mΣc_ix_i

X^T(θ) =[X₁(θ);X₂(θ); ...;X_m(θ);0;...;Xj(θ);...;0]

X_j(θ)=θ θ>0

_i=1^mΣ A_iX_i(θ)+A_jX_j(θ)=B

wektor A_j można przedstawić jako kombinację liniową wektorów A_i;

Ajθ= _i=1^mΣ A_iz_ijθ

A_jθ=θ _i=1^mΣ A_iz_ij

_i=1^mΣ A_ix_i+A_jθ=B+θ _i=1^mΣ A_iz_ij

_i=1^mΣ A_ix_i-θ _i=1^mΣ A_iz_ij+A_jθ=B

_i=1^mΣ A_i(x_i-θz_ij)+A_jθ=B

x_i-θz_ij=x_i(θ)

Zmienne bazowe przekształca się na zmienne bazowe nowego równania

_i=1^mΣ A_iX_i(θ)+A_jθ=B

x_j(θ)=θ

-X_P^T=[x₁,x₂,...,x_m,0,0,...,0]

_i=1^mΣ A_ix_i=B funkcja celu L(X)= _i=1^mΣ c_ix_i

-X₍₁₎^T=[x₁(θ);x₂(θ);...;x_m(θ);0;...;x_j(θ);0;...;0]

_i=1^mΣ A_ix_i(θ)+A_jx_j(θ)=B

Funkcja celu L[X(θ)]=_i=1^mΣ c_ix_i(θ)+c_jxj(θ)

x_j(θ)=θ θ>0

x_i(θ)= x_i-θz_j

A_j= _i=1^mΣ A_iz_ij

L[x(θ)=_i=1^mΣ c_i(x_i-θz_ij)+c_jθ= _i=1^mΣ c_ix_i- _i=1^mΣ c_iz_ijθ+c_jθ=L[X(θ)]-θ[_i=1^mΣ c_iz_ij-c_j]

L[X(θ]=L(X)-θΔ_j

Δ_j⁼ _i=1^mΣ c_iz_ij-c_j=z_j-c_j

i = 1,2,...,m

j=1,2,...,n

Może nastąpić jeden z następujących przypadków

1. Δ_j≥0 (dla max0
   Δ_j≤0 (dla min)
   to wartość funkcji celu nie można polepszyć i dane rozwiązanie jest rozwiązaniem optymalnym

2. Δ_j<0 (dla max)
   Δ_j>) (dla min)
   dla pewnego j i wszystkie odpowiadające temu indeksowi współczynniki kombinacji liniowej z_ij≤0 to zadanie nie posiada rozwiązania

3. Δ_j<0 (dla max)
   Δ_j>0 (dla min)
   i dla każdego j co najmniej jedna z liczb z_ij>0 to rozwiązanie można ulepszyć. Wówczas wyznaczamy θ, które jest minimalną wartością spośród θ=min{x_i/z_ij}

Schemat postępowania przy zastosowaniu algorytmu SIMPLEX można podzielić na kilka etapów:

1. dokonujemy wyboru wyjściowego rozwiązania bazowego oraz oceniamy jego optymalność. W tym etapie wykonujemy następujące czynności

1. wyznaczenie początkowego bazowego rozwiązania dopuszczalnego

2. budowa tablicy simpleksowej dla przyjętego rozwiązania bazowego. Jeśli zgodnie z przyjętym kryterium optymalności rozwiązanie bazowe jest optymalne postępowanie zostaje zakończone. Jeśli nie to przechodzimy do następnego etapu.

2. Etap ten polega na wyznaczeniu kolejnego poprawnego rozwiązania bazowego

1. Ustalenie zmiennej, którą wprowadzimy do poprawionego rozwiązania bazowego

2. Ustalenia zmiennej, którą należy usunąć z poprzedniego rozwiązania

3. Wyznaczenie wartości zmiennych poprawionego rozwiązania bazowego oraz odpowiadającej nowemu rozwiązaniu tablicy simpleksowej i wracamy do etapu 2a. Postępujemy tak dalej aż otrzymamy rozwiązanie optymalne

Wyznaczenie początkowego dopuszczalnego rozwiązania bazowego
Aby rozwiązać zadanie PL metodą SIMPLEX należy sprowadzić do postaci bazowej z nieujemnymym wektorem wyrazów wolnych b.

1. Przypadek
   Warunki ograniczające są postaci:
   AX≤B
   X≥0
   B≥0
   Sprowadzamy do postaci kanonicznej
   AX+X^d=B
   X^d≥0
   Początkowym rozwiązaniem jest:
   X^d=B
   X=0

2. Przypadek
   AX=B
   X≥0
   B≥0
   Jeżeli w macierzy A możemy wyodrębnić macierz jednostkową stopnia m A=[A_N;I_m] A_NX_N+I_mX_B=B to początkowym dopuszczalnym rozwiązaniem jest X_N=O X_B=B

3. Przypadek
   AX=B(*)
   X≥0
   B≥0
   W macierzy A nie można wyodrębnić podmacierzy jednostkowej stopnia m. w tym przypadku posługujemy się tzw. metodą sztucznej bazy. Polega ona na tym, że standardową postać warunków ograniczających przekształcamy w sposób sztuczny do następującej postaci:
   AX+S=B(**)
   S^T= [s₁, s₂,...,s_m] - wektor zmiennych sztucznych
   Zmienne sztuczne zostały tu wprowadzone tylko po to, aby otrzymać postać bazową układu warunków ograniczających, z których łatwo można wyznaczyć rozwiązanie bazowe. Początkowe rozwiązanie jest równe:
   X=0
   S=B
   

Układ (*) nie jest równoważny układowi (**). Jednak w wyniku odpowiednich przekształceń można uzyskać rozwiązanie bazowe dopuszczalne układu(*).
Wprowadzenie zmiennych sztucznych do warunków ograniczających musi również oznaczać wprowadzenie tych zmiennych do funkcji celu.
L(X)→max
L(X)=_i=1ⁿ Σc_ix_i-M_s1-M_s2-...-M_sm
M→∞ M jest to bardzo duża dodatnia liczba
L(X)→min
L(X)= ₌₁ⁿ Σc_ix_i+M_s1+M_s2+...+M_sm

Twierdzenie:

Jeżeli w rozwiązaniu optymalnym zadania rozszerzonego o sztuczne zmienne wektor S=0 ( wszystkie zmienne są równe zero) to rozwiązanie to jest rozwiązaniem optymalnym rozwiązania wyjściowego AX=B(*).Jeżeli w rozwiązaniu opt. zadania rozszerzonego (**) S>0 to zadanie wyjściowe jest sprzeczne.

4.DUALIZM W PROGRAMOWANIU LINIOWYM
Model prymalny

L(X)=C^TX→max

AX≤B
X≥0

Model dualny

L(Y)=B^TY→min

A^TY≥C

Y≥0

Zasady tworzenia symetrycznego (dualnego) modelu:

1. zmiennych dualnych y_i jest tyle ile jest warunków ograniczających w modelu prymalnym, czyli m.

2. współczynniki funkcji celu w modelu dualnym są równe prawym stronom warunków ograniczających w modelu prymalnym

3. maksymalizacja funkcji celu modelu prymalnego zmienia się na minimalizację f. celu w modelu dualnym i odwrotnie

4. prawe strony ograniczeń w modelu dualnym zastępuje się współczynnikami f. celu z modelu prymalnego

5. w modelu dualnym dokonuje się transpozycji macierzy układu warunków ograniczających modelu prymalnego

6. nierówności zadania dualnego zmienia się na nierówności przeciwne do zadania prymalnego

7. zadanie dualne ma tyle warunków ograniczających ile jest zmiennych w modelu prymalnym, czyli n.

Interpretacja

Zmienne dualne mają często odpowiednie interpretacje ekonomiczne. Ich interpretacja zależy od interpretacji modelu prymalnego. Załóżmy max przychód osiągamy z produkcji k wyrobów. Zużycie środków produkcji nie może przekroczyć środków b_i.

c_j oznacza cenę j-tego wyrobu. Współczynniki a_ij w modelu oznaczają wielkość zużycia i-tego środka na j-ty wyrób.
y_i - ozn. cenę i-tego środka produkcji

Tylko interpretujemy rozwiązanie opt.

Optymalna wartość zmiennej y_i określa o ile wzrośnie (zmniejszy się) przychód, jeżeli zwiększymy (zmniejszymy)zasób i-tego środka produkcji o jednostkę. Ta int. jest prawdziwa, jeśli zmiany mieszczą się w dopuszczalnych granicach i dotyczą jednego środka. Zmienną dualną, yi określa się zgodnie z neoklasyczną krańcową produktywnością jednostki i-tego środka

Twierdzenia dotyczące dualności

1. Zadanie prymalne jest zadaniem dualnym do swego zadania dualnego.(symetryczne, sprężone)

2. Jeżeli zadanie pierwotne i zadanie dualne mają rozwiązania dopuszczalne to obydwa mają rozwiązanie optymalne. Jeśli natomiast chociaż jedno z nich nie ma rozwiązania dopuszczalnego, to obydwa nie mają rozwiązania optymalnego.

3. Jeżeli x₁,x₂,...,x_n jest rozwiązaniem dopuszczalnym rozwiązania prymalnego, a y_1,y₂,...,y_n jest rozwiązaniem dopuszczalnym zadania dualnego to między wartościami f. celu zachodzi nierówność L(X) ≤ L(Y)

4. Jeżeli istnieją dwa takie dopuszczalne rozwiązania x₁,x₂,...,x_n modelu prymalnego i y₁,y₂,...,y_n modelu dualnego, że wartości funkcji celu są sobie równe L(X) = L(Y) to obydwa rozwiązania są rozwiązaniami optymalnymi

5. 
   Jeżeli x₁,x₂,...,x_njest rozwiązaniem dopuszczalnym zadania prymalnego oraz y₁,y₂,...,y_n jest rozwiązaniem dopuszczalnym zadania dualnego to aby te rozwiązania były rozwiązaniami optymalnymi wystarcza, że spełnione są następujące warunki:

1. _i=1 ⁿΣa_ijx_j<b_i y_i=0
   

2. 
   _j=1^mΣa_ijy_i>c_j xj=0

3. 
   
   y_i>0 _i=1ⁿΣ aijxj=b_i
   

4. xj>0 _i=1^mΣa_ijy_i=c_j

Twierdzenie o równowadze wykorzystujemy do sprawozdania optymalności znanego rozwiązania dopuszczalnego.

5.SYTUACJE DECYZYJNE

Optymalny model wyboru asortymentu produkcji

Zakład może produkować n - wyrobów do ich produkcji wykorzystywane są różne środki produkcji, z których część m jest dostępna w ograniczonych ilościach. Dane są normy zużycia środków produkcji oraz ceny lub zyski jednostkowe ze sprzedaży tych wyrobów.

Mogą być także podane dodatkowe informacje o popycie na produkowane wyroby. Minimalna ilość jaką trzeba wyprodukować lub max. ilość jaką można sprzedaż. A zatem parametrami w tym modelu ekonomicznym tego zadania są:

a_ij - zużycie i-tego środka produkcji na wytworzenie jednostki j-tego wyrobu

(i=1,2,...,m), (j=1,2,...,n)

b_i - posiadany zasób i-tego środka produkcji

c_j - cena lub zysk jednostkowy ze sprzedaży jednoski j-tego wyrobu

d_j- min. Ilość j-tego wyrobu jaką trzeba wyprodukować

g_j - max ilość j-tego wyrobu jaką można sprzedać

Należy określić, które wyroby i w jakich ilościach produkować aby nie przekroczyć posiadanych zasobów środków produkcji i ograniczeń popytowych, aby z maksymalizować przychód lub zysk z ich sprzedaży.

Zmiennymi decyzyjnymi w tym zadaniu x_j są wielkości produkcji j-tego wyrobu, a ogólny model jest następujący

L(X)=_j=1ⁿΣc_jx_j→max

_j=1 ⁿΣa_ij≤b_i (i=1,2,...,m)

d_j≤x_j≤g_j (dla niektórych j)

x_j≥0 (j=1,2,...,n)

Problem mieszanek

W zagadnieniu optymalnego nakładu mieszanki podejmujący decyzje pragnie określić jakie ilości podstawowych surowców należy zakupić i zmieszać, aby otrzymać produkt o pożądanym składzie chemicznym przy możliwie najniższych kosztach zakupu surowców. Szczególnym przypadkiem jest zagadnienie diety.

Aby zaspokoić potrzeby organizmu trzeba mu dostarczyć różnych składników odżywczych w różnych ilościach. Składniki te zawarte są w różnych produktach żywnościowych.

Załóżmy, że mamy do dyspozycji n-produktów żywnościowych, w których powinno być zawartych m składników odżywczych.

Parametrami w tym zagadnieniu są:

a_ij - zawartość i-tego składnika odżywczego w jednostce j-tego produktu

b_i - norma żywienia, czyli min. a czasami max. ilość i-tego składnika jaki należy dostarczyć organizmowi

c_j - cena j-tego produktu żywnościowego

d_j - min. ilość j-tego produktu jaką powinno się spożywać

g_j - max ilość j-tego produktu jaką organizm powinien otrzymać

Należy określić taką wielkość zakupu poszczególnych produktów, które zapewnią organizmowi niezbędne składniki odżywcze. Zmiennymi decyzyjnymi są zatem ilości produktów jakie należy zakupić.

x_j - ilość j-tego produktu żywnościowego

K=_j=1ⁿΣc_jx_j→min

_j=1ⁿΣa_ijx_j≥b_i (i=1,2,...,m)

d_j≤x_j≤g_j

x_j≥0 (j=1,2,...,n)

Wybór procesu technologicznego

Zakład ma produkować n - wyrobów w ilościach b₁,b₂,...,b_n. Do wytworzenia tych wyrobów można stosować m procesów technologicznych. Stosując i-ty proces tech. z jednostkową intensywnością uzyskuje się poszczególne produkty w ilościach a_ij ponosząc koszty c_j. Należy dobrać tak procesy tech., aby przy najmniejszych kosztach wytworzyć potrzebne ilości wyrobów. Zmienne decyzyjne x_j ozn. intensywność z jaką powinny być stosowane poszczególne procesy tech. Zadanie to sprowadza się do rozwiązania następującego modelu:

K=_j=1ⁿΣc_jx_j→min

_j=1ⁿΣa_ijx_j≥b_i

x_j≥0

6. PROBRAMOWANIE LINIOWE NA LICZBACH CAŁKOWITYCH

Zadanie programowania liniowego, w którym do warunków dołączono dodatkowe warunki dotyczące całkowito liczbowości wszystkich zmiennych decyzyjnych.

Def.1 Część całkowitą liczby wymiernej [a] nazywamy największą liczbą całkowitą ≤ a .Natomiast częścią ułamkową liczby a to f(a)=a-[a].Części ułamkowe liczb całkowitych są równe zero.

Def.2Dwie liczby wymierne a i b nazywamy kongruentnymi tzn. przystającymi, jeśli ich różnica jest liczbą całkowitą a-bεC

Własności wynikające z definicji:

1. a≡b→f(a)=f(b)

2. f(a+b)≡f(a)+f(b)

3. nєC →na ≡f(na)≡ nf(a)

Algorytm Gomorjego

1Etap; rozwiązujemy zadanie z algorytmem simplex, jeżeli rozwiązanie optymalne tego zadania spełnia warunki całkowitoliczbowości to postępowanie zostaje zakończone. Jeżeli nie przechodzimy do etapu 2.

2Etap: Konstruujemy dodatkowe ograniczenie tzn. płaszczyznę tnącą odcinającą ułamkową część jednego z rozwiązań zad. Programowania liniowe. Rozważamy dowolną zmienną x_k przyjmującą w i-tym wierszu optymalnej tablicy simplex, wartość niecałkowitą.

Korzystając z założenia o całkowitoliczbowości zmiennych oraz z własności kongruencji mamy:

Σf(a_ij)x _j ≡f(b_i)

Σf(a_ij)x_j≥f(b_i)

Powyzsza nierówność jest właśnie płaszczyzną tnącą, którą jako dodatkowy warunek ograniczający do tab. simplex i dalej rozwiązujemy algorytmem simpex.

7.ZAGDNIENIE TRANSPORTOWE

Problem transportowy jest określony jako problem optymalny dystrybucji towarów. Rozwiązanie problemu transportowego daje odp. Na pytanie jak przy najmniejszych kosztach można zorganizować przewóz od dostawców do odbiorców. Ekonomiczne zagadnienie transp. można przedstawić nast.:

Danych jest m-odbiorców pewnego jednorodnego produktu, zasoby produktu i-tego dostawcy wynoszą odpowiednio: a₁,a₂,...,a_nProdukt jest przeznaczony do m-odbiorców, którzy złaszaja zapotrzebowanie b₁,b₂,...,b_m. Koszt transportu jednostki produktu od i-tego dostawcy do j-tego odbiorcy wynosi c_ij.. Należy okreslić plan przewozów pomiędzy dostawcami a odbiorcami tak, aby uwzględnić dostępne zasoby dostawców i zapotrzebowanie zgłaszane przez odbiorców przy najniższych kosztach transportu.

X_ij-zm.decyzyjna,ilość towarów przewożona od i-tego dostawcy do j-tego odbiorcy. Przed przystąpieniem do budowy modeli należy sprawdzić , czy zagadnienie jest zbilansowane (zamknięte), czy niezbilansowne(otwarte).

Def. Zagadnienie transportowe nazywamy zbilansowanym jeżeli:

Σa_i=Σb_j Jeżeli równosc ta nie jest spełnione-zagadnienie niezbilansowane.

Matematyczny model zamkniętego zagadnienia transportowego:

K=ΣΣc_ijx_ij→min

Σx_ij=a_i (i=1,2,...,m) warunki bilansujące od strony dostawców

Σx_ij=b_j (j=1,2,...,n) warunki bilansujące od strony odbiorców

∑a_i>∑b_j dostawcy nie dostarczą wszystkiego, co mają ∑x_ij≤a_i (i=1,2,...,m)

Nadwyżka popytu nad podażą: ∑a_i<∑bj ∑x_ij≤b_j (j=1,2,...,n)

Każde zagadnienie niezbilansowane można sprowadzić do zagadnienia zbilansowanego(można wprowadzić fikcyjnego odbiorcę lub dostawcę):

1. jeżeli występuje nadwyżka podaży nad popytem, wprowadzamy tzw. fikcyjnego odbiorcę o popycie a_n+1=Σb_i-Σaj

2. jeżeli mamy nadwyżkę popytu nad podażą to wprowadzamy fikcyjnego dostawcę o podaży b_m+1=Σa_j-Σb_i

Własności zadania transportowego

Twierdzenie1: W każdym zbilansowanym zadaniu transportowym zbiór rozwiązań dopuszczalnych jest niepusty i ograniczony. a więc każde zbilansowane zadanie transp. posiada skończone rozwiązanie optymalne. Liniowe zadanie decyzyjne zagadnienia trans. W postaci kanonicznej można zapisać: K=C^TX_(mnx1)→min ; AX=B; X≥0 gdzie:

X_(mnx1)-wymiarowy wektor zm. decyzyjnych

C_(mnx1)-wektor kosztów jednostkowych

B_(n+mx1)- wektor wartości brzegowych warunków ograniczających

A_(m+n)x(mn)-wektor współczynników występujących w warunkach ograniczających

Twierdzenie 2

Rząd macierzy A warunków ograniczających zadania transportowego jest równy m+n-1, wniosek: rozwiązanie bazowe zadania transportowego składa się dokładnie z m+n-1 zmiennych bazowych

Twierdzenie 3

Jeżeli wszystkie a_i i b_j w zadaniu transportowym są liczbami całokowitymi, to każde rozwiązanie bazowe, w tym również optymalne, jest utworzone z liczb całkowitych.

8. ROZWIAZYWANIE ZAMKNIĘTYCH ZADAŃ TRANSPORTOWYCH

Rozwiązywanie zamkniętych zadań transportowych jest metodą iteracyjną i składa się z następujących etapów:

1. wyznaczenie wstępnego, dopuszczalnego rozwiązania bazowego

2. ocena optymalności optymalnego rozwiązania

3. przejście do nowego rozwiązania bazowego, lepszego od poprzedniego z punktu widzenia przyjętego kryterium

Sposoby wyznaczenia wstępnego rozwiązania bazowego:

1. metodą konta północno-zachodniego (lewego górnego rogu)

2. m. min. elementu macierzy kosztów jednostkowych

3. m. min. Elementu w wierszu macierzy kosztów jedn.

4. m. min. Elementu w kolumnie macierzy kosztów jedn.

Sposoby sprawdzalności optymalności i poprawienia rozwiązania zad. transportowego:

1. metoda potencjałów

2. m. przydziałów

3. m. rent różnicowych

4. m. Forda i Fulkersona

Metoda potencjałów:jej teoretyczne zasady oparte są na zasadzie dualności dla zadania programowania liniowego. Metoda ta polega na przyporządkowaniu każdej zmiennej niebazowej oceny jednostkowego kosztu związanego z wypełnieniem tej klatki jedną jednostkową. Wszystkie oceny można przedstawić w macierzy V, gdzie v_ij jest oceną klatki ij. Dane rozwiązanie bazowe V=[v_ij] jest optymalne, jeżeli macierz ocen nie zawiera elementów ujemnych. Poszczególne elementy macierzy V wyznaczone są zgodnie ze wzorem: v_ij=c_ij-(u_i+v_j), gdzie u_i i v_j to potencjały. Dla zmiennych bazowych suma; u_i+v_j=c_ij, czyli v_ij=0

9. ZAGADNIENIE TRANSPORTOWE Z KRYTERIUM CZASU

a_i-dostawcy (i=1,2,...,m), b_j-odbiorcy (j=1,2,...,n) przy założeniu: ∑a_i=∑b_j T={t_ij}- macierz o elementach t_ij- czasy dowozu towaru od i-tego dostawcy do j-tego odbiorcy. Należy wyznaczyć taki układ {x} o nieujemnych wartościach, przy warunkach ∑x_ij=a_i (i=1,2,...,m) i ∑x_ij=b_j (j=1,2,...,n) oraz x≥0, w jak najkrótszym czasie. Należy wyznaczyć takie tєmax{t_ij}czyli określić taki plan przewozów dla których odpowiednie t będzie najmniejsze. Najkrótszym czasem rozdysponowania towaru będzie najdłuższy z najkrócej trwających czasów przemieszczania ładunków od każdego dostawcy oraz do każdego z odbiorców.

!0. ZAGADNIENIE TRANSPORTOWO-PRODUKCYJNE (MAGAZYNOWE)

Danych jest n-producentów pewnego jednorodnego produktu P₁,P₂,...,P_n Każdy z nich ma określone zdolności produkcyjne: a₁,a₂...,a_n

m- odbiorców zgłasza odpowiednio zapotrzebowanie: ∑a_i≥∑b_j (łączne zdolności produkcyjne przekraczają łączne zapotrzebowanie)

Znane są jednostkowe koszty produkcji, określone dla poszczególnych producentów p₁,p₂,...,p_n oraz tablica jedn. kosztów transportu c_ij

Należy wyznaczyć taki plan transportu i produkcji aby łączny koszt transportu i produkcji był minimalny.

11. MINIMALIZACJA PUSTYCH PRZEBIEGÓW

Przyjmujemy, że mamy n-miast, między którymi odbywa się wymiana towarowa. Między nimi znane są odległości d_ij. To n-miast tworzy układ zamknięty tzn. każde z nich może być zarówno dostawcą jak i odbiorcą. Wlk. przesyłek między miastami określona jest liczbą całkowitą samochodów, niezbędnych do ich realizowania i wynosi a_ij. Można wyliczyć dla każdego miasta liczbę samochodów niezbędnych do wywiezienia przesyłek(wywóz z i-tego miasta) w_i=∑a_ij (i=1,2,...,n) oraz liczbę samochodów niezbędnych do przywiezienia towarów(przywóz do miasta), p_i=∑a_ji. Miasta dla których w_i>p_i są odbiorcami pustych środków transportu, ich zapotrzebowanie na puste środki transportu to b_i=w_i-p_i (b_i>0).Miasta gdzie w_i<p_i to dostawcy pustych środków transportu; nadwyżka pustych srodków transportu w tych miastach to a_i=p_i-w_i. Miasta dla których w_i=p_i eliminuje się z dalszych rozważań, nie są ani odbiorcami ani dostawcami. Należy ułożyć zamknięte zagadnienie transp. którego rozwiązanie optymalne wskarze z jakiego miasta i dokąd wysłać określoną liczbę pustych samochodów.

12. ZAGADNIENIE LOKALIZACJI PRODUKCJI

Danych jest N -punktów zapotrzebowania na pewien towar oraz R- punktów, w których możliwa jest lokalizacja zakładów produkcyjinych, produkujących ten towar. Zapotrzebowanie w j -tym punkcie wynosi B_j gdzie j=1,2,..N.a potencjalne zdolności produkcyjne w i-tym punkcie wynosi A_i gdzie i=1,2,...,R. Oszacowane koszty jednostkowe produkcji w i-tym punkcie wynoszą h_i a oszacowane jedn. koszty transportu towaru z punktu i - tego do j -tego punktu wynoszą c_ij , a zatem k_ij=h_i+c_ij są oszacowanymi jedn. kosztami produkcji i transportu.Załozenia:

1. nadwyżka potencjalnej produkcji nad zapotrzebowaniem ∑A_i>∑B_j przyjmuje sią tak dlatego, że w przypadku zbilansowania potencjalnych zdolności produkcyjnych zakładów z zapotrzebowaniem odbiorców nie ma problemu z lokalizacja produkcji

2. wyklucza się możliwość zaspokojenia zapotrzebowania przez budowę zakładu produkcyjnego tylko w jednym punkcie A_i<∑Bj

Zakłada się także że cała produkcja wytworzona w dowolnym punkcie będzie rozesłana do odbiorców a_i=∑x_ij. Należy ustalić w których punktach trzeba zlokalizować zakłady, ile w każdym zakładzie produkować i jak przewozić towar, aby zaspokoić zapotrzebowanie odbiorców, przy minimalnych, łącznych kosztach transportu i produkcji .Zm. decyzyjne x_ij to wielkości produkcji w i - tym punkcie dostarczone j- emu odbiorcy.

13. ROZDZIAŁ ZADAŃ PRODUKCYJNYCH MIĘDZY MIEJSAMI PRODUKCJI

N - wyrobów (albo czynności) można wykonać w P - miejscach produkcji (zakładach, na stanowiskach pracy, maszynach). Należy rozdzielić produkcję wyrobów(wykonywanie czynności) pomiędzy miejsca produkcji. Dane są a_ij - wydajność i- tego miejsca pracy (i=1,2,...,N) przy wykonywaniu j -tego wyrobu (j=1,2,...,N), Cj - założona wielkość produkcji j - tego wyrobu (j=1,2,...,N),Bi - dopuszczalny czas pracy i - tego miejsca (i=1,2,...,P)

Należy przydzielić produkcję wyrobów do poszczególnych miejsc pracy tak aby:

1. zminimalizować czas (koszt) produkcji

2. zmaksymalizowć efekty(wielkość)produkcji

Jeżeli znane są wydajności w jednostce czasu , to przydział będzie polegał na określeniu czasu pracy i -tego miejsca przy wykonywaniu j - tego wyrobu czyli x_ij

K=∑∑x_ij→min gdzie K to łączny czas pracy wszystkich miejsc pracy przy produkcji wyrobów, Ograniczenia:

1. ∑x_ij≤B_i (i=1,2,...,P) czyli nie może przekroczyć dopuszczalnych czasów pracy poszczególnych miejsc

2. ∑a _ijx _ij ≥Cj należy wytworzyć planowane ilości wyrobów

3. x _ij ≥0

Gdy mamy dany a_ij czas pracy i - tego miejsca pracy przy wykonaniu i - tego wyrobu

Cj - założona wielkość produkcji j - tego wyrobu, Bi- dopuszczalny czas pracy i- tego miejsca, x_ij -ilość j - tego wyrobu jaką należy wytworzyć w i - tym miejscu

1. ∑a _ijx _ij ≤Bi

2. ∑x _ij ≥Cj

3. x_ij ≥0

F(x)=∑a _ijx _ij →min

14. PROBLEM OPTYMALNEJ STRUKTURY ZASIEWU W GOSPODARSTWIE ROLNYM

Chodzi o takie przydzielenie pól o róznej wydajności i powierzchni pod różne uprawy aby osiągnąć max. dochód(zysk).Dane musi być:

a_i - powierzchnia w hektarach i - tego pola o danej urodzajności (i=1,2,..., m)

b_j- min. zbiory j -tej uprawy (j=1,2,..n)

a_ij - wielkość zbioru z i- tego pola j-tej uprawy

c_j - dochód ze sprzedaży jednego kwintala j - tego plonu

x_ij (zm. decyzyjna,)powierzchnia przeznaczona na j - tą uprawę na i -tym polu

Zadanie polega na rozwiązaniu modelu:

D=ΣΣc_j a_ij x_ij →max

Ograniczenia:

∑x_ij =a_i (i=1,2,...,m)

∑a_ij x_ij≥ b_j (j=1,2,...,n)

x _ij ≥0

15. PROGRAMOWANIE NIELINIOWE

Zadanie decyzyjne nazywamy nieliniowym, jeżeli f.celu lub chociaż jeden z warunków ograniczających jest f.nieliniową. f(x)→ max ; g_i(x)≥0; x_ij≥0; f(x)→min;g_i(x)≤0;

Zagadnienie Programowania Nieliniowego wypukłego nazywamy takie zad. P.N., w którym: minimalizujemy wypukłą lub maks. Wklęsłą f.celu; zbiór rozwiązań dopuszczalnych jest zbiorem wypukłym.

Zadaniem programowania wklęsłego nazywamy zad. P.N. niewypukłego, w którym: min. Wklęsłą bądź maks. Wypukłą f.celu; zbiór rozw. Dopuszczalnych jest zbiorem wypukłym;

16. ZADANIA PROGRAMOWANIA ILORAZOWEGO

Z=C^T X+C_O\d^TX+d_O →max; AX=b, x>0; c,d - parametry

Założenia: Metoda rozwiązywania to metoda Charresa-Coopera:

1. Zbiór rozwiązań dopuszczalnych jest ograniczony

d^Tx+d₀>0 Podstawa d^Tx+d₀=V

Wówczas: Z=C^Tx/v+c₀1/v→max

A*x/v - b*1/v=0

d^T*x/v+d₀*1/v=1

za: x/v=y; 1/v=y₀

Wówczas: Z=C^Ty +c₀y₀→max

Ay - by₀=0

D^Ty₀ + d₀y₀=1

y≥0 , y₀≥0

Tw: Przy przyjętych zał., prawdziwe jest nast. tw.: Jeżeli w rozw. Optymalnym zadania (y_opt , y_{0 opt} ), y_{0 opt}>0, to wektor X=y_opt /y_{0 opt} jest rozw. opt. zadania wyjściowego.

17. PODSTAWY TEORETYCZNE PROGRAMOWANIA WYPUKŁEGO

Model wypukły: f(x)→min; y_i(x)≤0.

Funkcją Lagrange'a przyporządkowaną problemowi 1 nazywamy funkcję: L(x,λ)=f(x) + ∑λ_ig_i(x).

Rozwiązanie modeli programowenia często związane jest z postacią modelu.

Jeżeli jest to postać kanoniczna to stosujemy tzw. Metodę mnożników Lagrange'a. Mamy 2 etapy:

1. Sprawdzamu czy f.celu ma ekstremum bezwarunkowe. Jeżeli tak, to czy spełnia ono warunki ograniczające, a więc czy jest jednocześnie ekstremum warunkowym. Jeżeli ekstremum bezwarunkowe spelnia warunki ograniczające to zadanie jest rozwiązane.

2. Jeżeli eks. Bezwarunkowe nie spelnia ogrniczeń, f.celu przekształcamy w f. Lagarange'a. W ten sposób zastępujemy szukanie ekst. Warunkowego funkcji f(x) szukaniem ekstremum bezwarunkowego f. Lagrange'a.

Jeżeli model wypukły ma postać standardową tomożna go rozwiązac metodą Kuhna - Tuckera.

Tw: Jeżeli wektor X jest rozw. optym. Zadania, to będą spełnione następujące warunki:

1. ∂L/∂x_j≥0

2. ∑∂L/∂x_j*x_j=0

3. g_i(x)≤0

4. ∑g_i(x)λ_i=0

5. x_j≥0

6. λ_i≥0

18. PROGRAMOWANIE DYNAMICZNE

Jest jedną z technik matematycznych, którą można wykorzystywać do zarządzania procesami etapowymi. Jest to ogólna procedura postępowania, której konkretyzacja może być przeprowadzona dla ustalonej postaci zadania. Formalnie rzecz biorąc, metody programowania dynamicznego polegają na zamianie zadań optymalizacyjnych z n-zmiennymi decyzyjnymi w n-zadań z 1 zmienną decyzyjną przy czym zadania te są powiązane ze sobą zależnością rekurencyjną. W dowolnym etapie procesu podzielonego na n-etapów wyróżniamy elementy:

1. stan wejściowy procesu do danego etapu

2. decyzję podejmowaną na danym etapie

3. stan wyjściowy

Stan procesu można opisać za pomocą jednego lub kilku parametrów zwanych zmiennymi stanu. Zmienną stanu oznaczmy jako S_k, gdzie k to k-aty etap. Decyzję p[odejmowane na tych etapach opisujemy za p[omocą zmiennych decyzyjnych X_k. Formalnie wieloetapowy proces decyzyjny może być wyrażony nast. zależnościami rekurencyjnymi: S_k=h_k (S_k-1 , X_k). Stan procesu S_k na k-tym etapie zależy od stanu wejściowego S_k-1 dla k-tego etapu i decyzji X_k podjetej na tym etapie. Problem który należy rozwiązać w każdym wieloetapowym procesie decyzyjnym polega na określeniu ciągu decyzji X₁*, X₂*,...,X_n*, przy których ustalana f.celu dla całości procesu przebiegającego w n-etapach osiąga optimum. Ciąg decyzji optymalnych dla kolejnych etapów X₁*, ...,X_n* nazywamy polityką optymalną wieloetapowego procesu decyzyjnego. F.celu w rozpatrywanym procesie wyraża na ogół koszt lub efekt przebiegu całego procesu.

Zasada optymalności Bellmana'a: polityka optymalna ma tę własność, że niezależnie od początkowego stanu S₀ i pierwszej decyzji X₁, pozostałe decyzje muszą stanowić politykę optymalną ze względu na stan wynikający z pierwszej decyzji. Oznacza to, że jeżeli X₁*, X₂*,...,X_n* jest polityką optym dla procesu n-etapowego, to również pol. opt. jest X₂*,...,X_n* dla procesu (n-1) etapowego, przy stanie początkowym: S₁=h₁(S₀ , X₁*)

19. TEORIA GIER I DECYZJI

Teoria gier zajmuje się rozwiązywaniem problemów decyzyjnych, w których mamy do czynienia z ryzykiem lub niepewnością.

Gry dwuosobowe o sumie 0 i ich własności

Gra strategiczna jest matematycznym modelem sytuacji konfliktowej, w której występują strony , dążące do przeciwstawnych celów. Strony te nazywamy graczami, a wynik gry - wygraną jednej ze stron. Wynik gry zależy od świadomego postępowania uczestników gry, czyli od stosowanych przez graczy strategii. W każdej grze może uczestniczyć dwóch lub więcej graczy. W grze strategicznej, jedyną informacją, jaką dysponuje każdy z graczy jest znajomość strategii wszystkich graczy oraz tzw. Funkcji wypłat.

Strategia jest regułą określającą wybór poszczególnych ruchów w grze przez gracza.

Funkcja wypłat jest f. przyporządkowującą danemu graczowi wynik gry, w zależności od zastosowanych przez graczy strategii.

Grę dwuosobową, w której wygrana jednego z graczy jest jednocześnie przegraną drugiego gracza nosi nazwę gry dwuosobowej o sumie 0.

Grę dwuosobową o sumie 0, nazywamy pewną trójkę G=<T,S,W>, w której T i S - zbiory strategii czystych gracza odpowiednio P₁ , P₂, przy czym W(t,s) jest f.wypłat przyjmującą skończone wartości liczbowe, określoną na iloczynie kartezjańskim TxS.

f.wypłat W (t,s) w grze dwuosobowej o sumie 0, określa wygraną gracza P1 w przypadku, gdy wybrał strategię t∈T, a gracz P2 - strategię s∈S. Wygrana gracza P1 jest jednocześnie przegraną gracza P2. Jeżeli s i t są skończone, to mamy do czynienia z grą dwuosobową skończoną, a f.wypłat można przedstawić jako A=a_ij, macierz A→ macierz wypłat.

Dolną wartością gry nazywamy liczbę V₁ = max min W(st). Strategia odpowiadająca dolnej wartości gry V₁, nosi nazwę strategii maksymalnej gracza P1. Strategię maksyminimalna jest najostrożniejszą strategią gracza P1, gwarantującą mu wygraną na poziomie V₁.

Górną wartością gry nazywamy liczbę: V₂= min max W(s,t). Strategię odpowiadającą górnej wartości gry V₂

to strategia minimaksowa gracza P2. Minimaksowa strategia gracza P2 jest najostrożniejszą strategią gwarantującą graczowi drugiemu, że nie przegra więcej niż V₂.

Jeżeli V₁=V₂ gra posiada tzw. Punkt siodłowy i rozwiązaniem są tzw. strategie czyste. Jeżeli gra nie posiada punktu siodłowego to rozwiązaniem gry są strategie mieszane.

Z dowolną strategią mieszaną graczy związana jest wartość funkcji wypłat. Funkcja wypłat dla gracza P1 określona jest w następujący sposób: E(P,Q) = PAQ^T = ∑∑p_ia_ij , q_j

Rozwiązaniem gry dwuosobowej o sumie zero jest płaca strategii mieszanych:

P = [p₁, p₂ , ..., p_m]

Q = [q₁,q₂,...,q_n]

Oraz taka liczba V, że zachodzą poniższe związki:

E ( P,Q⁰)≥V dla każdej strategii czystej Q⁰

E (P⁰,Q)≤V dla każdej strategii czystej P⁰

Strategie P i Q spełniające warunki są strategiami optymalnymi, a liczba V nazywa się wartością albo wynikiem gry. Rozwiązywanie gry dwuosobowej o sumie zero można sprowadzić do zagadnienia programowania liniowego.

20. GRA Z NATURĄ

Jest grą dwuosobową o sumie zero, której graczem P1 jest organ, podejmujący decyzję, a graczem P2 - natura. Natura jest graczem nie myślącym i nie zależy mu na wygranej. Strategie decydenta w grze noszą nazwę decyzji, natomiast strategie natury - stany natury. Wynikiem gry z naturą może być zarówno przegrana za pomocą funkcji straty albo za pomocą funkcji efektywności decyzji: m - decyzji, n- stanów.

4 kryteria wyboru decyzji w grze z naturą:

1. Kryterium Walda (pesymistyczne)

Decydent, który jest nastawiony pesymistycznie do przyszłego stanu natury postępuje tak, aby osiągnąć najlepszy rezultat przy najmniej sprzyjających okolicznościach. Kryterium, jakim posługuje się polega na maksymalizacji najmniejszych możliwych korzyści. Jest to kryterium tzw. maksyminowe.

2. Kryterium Savage'a ( min żalu)

Stosując to kryterium minimalnego żalu oceniamy skutki nietrafnej decyzji. Jeżeli stan natury okaże się najbardziej sprzyjający. W tym celu tworzy się macierz tzw straconych szans (macierz żalu), w której elementy są potencjalnymi stratami. Dla określonego stanu7 natury zawsze istnieje przynajmniej jedna decyzja przynosząca największą korzyść. Jeśli dla tego stanu natury wybrana została decyzja dająca mniejszą korzyść, to różnica między tą wartością otrzymaną, a wartością największą jest miara żalu, żal jest tą wielkością, którą moglibyśmy dodatkowo uzyskać, podejmując trafną decyzję. A więc decyzja optymalna wg kryterium Savage'a to taka która minimalizuje największą wartość żalu.

3. Kryterium Szurnicza

Dla każdej decyzji wyznacza się średnią ważoną najgorszego i najlepszego rezultatu

Sz_i = αz_j^max(1) - (1 - α)z_ij ^min(i)

α- współczynnik optymizmu α∈<0;1>

jeśli α = 1 to jest to pełny optymista, α = 0 wskazuje pełny pesymizm co do wystąpienia stanu natury.

4. Kryterium Laplace'a (braku dostatecznej racji)

Jest to szczególny przypadek kryterium Bayesa. Kryterium Bayesa opiera się na tym że znane są prawdopodobieństwa wystąpienia poszczególnych stanów natury. Jeśli są one równe p₁, p₂ , ... , p_m to dla każdej decyzji wyznacza się średnią. E(d_i) = ∑ z_ij p_ij i wybiera się decyzję , dla której suma ta jest największą. W kryterium Laplce'a zakłada się, że:

p₁ = p₂=, ... ,= p_m=1/n d_i = ∑ z_ij / n

21 MODELE DECYZYJNE GOSPODARKI ZASOBAMI

Pod pojecim zapasu te cześć wszelkiego rodzaju zasobów która przekracz potrzeby dzialalnosci produkcyjnej wynikajace z ustalonego w okreslony sposób harmonogramu przebiegu procesu produkcyjnego, wyznaczonego dla zdeterminowanych wrunkow dzialania.

PRZYCZYNY

1 ograniczona mobilnosc zasobow z przyczyn tech-organizacyjnych lub nieoplacalnosc ekonomicznej.

2 zaklucewnia produkcyjne, powodujace losowe wahania w zapotrzebowaniu na zasoby

RODZAJE KOSZTOW W SYS.GOSP.ZAPASAMI

1 koszt magazynowania

-koszty zamrożenia środków obrotowych

-amortyzacja magazynu oraz urządzeń transportowych

-koszty operacyjne(robocizna personelu obsługującego magazyn, koszty prowadzenia rejestrów i przeglądów zapasów lub koszty usług informatycznych)

2 koszty realizacji zakupu

-koszty zamówienia

-koszty transportu do magazynu

3 koszt braku lub niedoboru zapasu

-dodatkowe koszty zakupu w pośpiechu lub koszty strat z tytułu opóźnień lub utraconych możliwości produkcyjnych

podstawowym kryterium dla modeli decyzyjnych planowania zapasu jest minimalizacja łącznych kosztów dla całego rozpatrywanego systemu gosp. zasobami

*deterministyczne modele planowania zapasow

w omawianych tu modelach zakłada się zdeterminowane warunki działania, w których występują zakłócenia produkcyjne, a to oznacza, ze jedynym czynnikiem z powodu którego tworzymy zapas jest ograniczona mobilność zasobu. konsekwencja założenia o deterministycznych warunkach działania jest sprowadzenie całości problemu do wyznaczania optym. wielkości partii zamówienia dostawczego.

Q - wielkość zapotrzebowania na rozpatrywany zasób w ustalonym okresie czasu<0:T>

S-wielkosc pojedynczego zakupu zamowienia

n-liczba zakupu zamowien w ciagu okresu

k-koszt realizacji zakupu 1 partii

c1-jednostkowy koszt magazynowania w okresie<0;T>

c2-jednostkowy koszt niedoboru zapasu w okresie<0:T>

22. MODEL KLASYCZNY

1. zapotrzebowanie na rozpatrywany zasob przypadajace na okres<0;T>jest znanne i wynosi Q

2. zuzycie zasobu jest rownomierne w czasie , co oznacza ze jego iloscV(t) w kazdym momencie t <0:T> jest malejaca f.liniowa w przypadku jednej partii zakupu na ten okres lub przedzilami malejaca

3. zakupy zasobu w okresie <0:T> dokonywane sa n-razy w jednakowych odstepach czasu t gdzie:t=T \ n S=Q \ n

4. zamowienia skladane sa wyprzedzajaco tak aby dostawa kolejnej partii materialu nastapila w momencie zuzycia poprzedniej

5. zapotrzebowanie w kazdym momencie okresu <0:T> musi być zaspokojone

6. w okresie <0:T> cena jednostkowa zasobu nie ulega zmianie

7. koszt magazynowania jest proporcjonalny do wielkosci zapasu

8. koszt realizacji zakupu nie zalezy od wielkosci partii i dla pjedynczej partii wynosi

Przy powyzszych zalozeniach jedyna zm.decyzyjna w planowaniu zapasow jest wielkosc zamowienia partii S.Wielkosc te należy tak okreslic aby laczne koszty realizacji wszystkich zakupów oraz magazynowania były minimalne.D1-koszt magazynowania w okresie <0:T> D1=c1 * Z

Z - średnia wielkość zapasu w przedziale <0:T>

Problem polega na wyznaczeniu S, dla którego D jest minimalny.(D-łączny koszt) wzór Wilsona So=pod pierwiastkiem 2KQ\C1

23. MODEL II

Zmieniamy założenia g i h.

g) koszt magazynowania jest liniowa funkcja wielkości zapasu D1=Co+C1Z

Co-pewien stały koszt związany z magazynowaniem niezależny od wielkości zapasu

C1-jednostkowy koszt magazynowania

h) koszt realizacji zakupu jednej partii surowca składa się z kosztu stałego K niezależnego od wielkości partii oraz pewnego kosztu zależnego nieliniowo od wielkości partii. Łączne koszty wynoszą :Dz=[K+(Qo-as)S]Q\S

So=pod pierwiastkiem2KQ\C1-2Aq

24. MODEL III

Ograniczona pojemność magazynu, do założeń modelu klasycznego od a-h dokładamy

i) pojemność magazynu jest ograniczona, nie może przekroczyć znanej wielkości B S<=B

wzór na optymalna wielkość partii So=pod pierwiastkiem 2KQ \ C1+2λ

λ -mnożnik Lagrange'a z interpretacji tego mnożnika wynika ze gdy S<B to λ=0 w przypadku gdy pojemność magazynu zostaje w pełni wykorzystana to λ>=0 wartość ta można wyznaczyć z przyrównania pochodnej funkcji Lagrange'a względem λ do 0

25. MODEL IV

W którym dopuszczamy niedobór zapasów. Przyjmujemy założenia z modelu 1 poza e)

e) dopuszczalny jest niedobór zapasu przy czym jednostkowy koszt tego niedoboru jest wprost proporcjonalny do wielkości tego niedoboru

Z rysunku wynika ze rzeczywista wielkość partii wynosi S' W każdym cyklu o długości to występuje niedobór w czasie t' i to , albo w czasie to-t'.celem jest wyznaczenie S i S' w taki sposób aby łączne koszty magazynowania realizacji zakupów oraz niedoboru zapasu w okresie od <0:T> były minimalne

So=pod pierwiastkiem 2KQ \ C1 * C1+C2 \ C2

So'=pod pierwiastkiem 2KQ \ C * C2 \ C1+C2

Przy okazji tego modelu można zdefiniować pewien parametr zwany współczynnikiem obsługi który jest istotny w praktyce B=t' \ to optymalny poziom wspol. Obsługi jest równy Bo=C2 \ C1+C2 z którego wynika ze wspol. obsługi wzrasta gdy maleje jednostkowy koszt magazynowania

26. STOCHASTYCZNE MODELE PROGRAMOWANIA ZAPASOW

W modelach stochastycznych dopuszcza się występowanie zakłóceń produkcyjnych które powodują losowe wahania w zapotrzebowaniu na zasoby. Wymaga to tworzenia systemu rezerw pełniących role kompresorów zakłóceń.

Y-zm.losowa określająca zapotrzebowanie na rozpatrywany zasób w przedziale od <0:T>

Zal.

a) zapotrzebowanie Y jest zm.losowa o wartości oczekiwanej równej Q E(Y)=Q

b) zakupy zasobu w okresie <0:T> są dokonywane n-razy w jednakowych odstępach czasu to i w partiach o jednakowej wielkości S=Q \ n

c) rozkład zapotrzebowania w odstępach czasu pomiędzy kolejnymi dostawami jest znany i nie ulega zmianie

d) nie zależnie od kolejnych zakupów zasobu tworzona jest rezerwa zasobu w wysokości R w celu zaspokojenie zwiększonego zobowiązania. Zadanie polega na określeniu wielkości rezerwy R i wielkości partii S. W celu określenia R wprowadzimy wspol.ryzyka jest to prawdopodobieństwo ze rezerwa okaże się nie wystarczająca na pokrycie zwiększonego w danym momencie zapotrzebowania. p-wspol.ryzyka

jednym z możliwych wariantów sposobu wyznaczenia wielkości rezerwy R jest takie jej ustalenie aby wspol.ryzyka miał z góry założona dość bliska zeru wartość.

Rp-odpowiadajaca ustalonemu wspol.ryzyka p wielkosc rezerwy.musza być spelnione warunki:

P{X>=S+Rp}=<p P{X=<S+Rp}>=1-p X-zm.losowa,okreslajaca zapotrzebowanie miedzy dwoma kolejnymi zakupami.S+Rp-kwantyl rzedu 1-p zm.losowej x. Jeśli x ma rozklad ciagly to warunki powyzsze sprowadzaja się do znalezienia takiego Rp aby:F(S+Rp)=1-p

F-dystrybuanta zm.losowej x

Mając konkretna postać rozkładu zm.x z tego równania w wielu przypadkach można otrzymać wzór wyrażający wielkość Rp. Naszym zadaniem jest ustalenie optymalnej wielkości S przy której łączne koszty magazynowania i realizacji zakupu sa minimalne. Postępowanie jest analogiczne jak w 1 modelu deterministycznym z którego przejmujemy dodatkowo założenia f, g, h. Minimalizujemy następujące koszty: D=C1(1\2 S+Rp) + KQ\S --MIN

1\2 S + Rp - średnia wielkość zapasu ∂D\∂S= - KQ\S² + C1\2 + C1 * ∂Rp\∂S =0

n.p jeżeli zm.losowa x ma rozkład normalny o parametrach N[S,σ] to można udowodnić ze: ∂Rp\∂S =0

Wielkość rezerwy wyznaczona na poziomie wynikającym z ustalonego arbitralnie współczynnika ryzyka, zapewnia z odpowiednio dużym prawdopodobieństwem ze nie wystąpi niedobór zapasów. Postępowanie takie ma niejednokrotnie zastosowanie w praktyce a mianowicie wtedy gdy niedobór zapasów powoduje straty lub koszty trudne do zmierzenia. W przypadku , gdy koszt niedoboru zapasu może być oszacowany to wielkość rezerwy można ustalić na poziomie optymalnym z punktu widzenia łącznych kosztów magazynowania i niedoboru.

27. PROGRAMOWANIE SIECIOWE

W działalności podmiotów gospodarczych można wyodrębnić wiele sytuacji, które polegają na projektowaniu przedsięwzięć, złożonych z czynności powiązanych między sobą w charakterystyczny sposób.

Niektóre czynności mogą być realizowane jednocześnie natomiast inne muszą być wykonywane w ustalonej kolejności, a powiązania między nimi można przedstawić graficznie za pomocą sieci przedsięwzięcia.

Wiele zagadnień inwestycyjnych, transportowych, przedsięwzięć związanych z modernizacją lub rekonstrukcją aparatu wytwórczego itp. rozwiązywanych jest efektywnie za pomocą technik nazywanych metodami sieciowymi.

Podstawowym elementem metod sieciowych jest model sieciowy, który składa się z 2 części:

1. model graficzny, zw. siecią zależności

2. część opisowo - analityczna

Rozważane są pewne przedsięwzięcia, złożone ze skończonej ilości czynności. Każdej czynności przyporządkowane są pewne parametry, np. czas trwania czynności, czas wykonywania czynności.

Punkty w czasie, odpowiadające momentom zakończenia pewnych czynności i rozpoczęcia wykonywania innych bezpośrednio po nich następujących, nazywane są zdarzeniami. Każda czynność przedsięwzięcia łączy ze sobą 2 zdarzenia:

• jedno umożliwiające jej rozpoczęcie

• pozwalające rozpoczęcie czynności, bezpośrednio po niej występujące

Pomiędzy dwoma zdarzeniami nie powinna występować więcej, niż jedna czynność. Jeżeli w rzeczywistości tych czynności jest więcej, wówczas można wprowadzić, tzw. czynności pozorne z zerowymi czasami ich trwania, bądź zerowym kosztem ich wykonywania.

Dowolny zbiór czynności przedsięwzięcia z zadanymi dociążeniami, można przedstawić za pomocą grafu. Wierzchołkami są zdarzenia, łukami (strzałkami) - czynności: czynność pozorna to jest łuk przerywany, zdarzeniom przyporządkowuje się zwykle kolejne numery 1,2,3,4,...

Graf przedsięwzięcia jest tak konstruowany, aby był siecią. Początkiem sieci jest zdarzenie, polegające na możliwości rozpoczęcia pierwszych czynności, natomiast końcem sieci - moment zakończenia wykonywania wszystkich czynności, składających się na całe przedsięwzięcie.

Zasady prawidłowej sieci przedsięwzięcia:

1. Dowolna czynność może rozpocząć się wówczas, kiedy wszystkie czynności poprzedzające ją zostaną zakończone.

2. Łuki sieci mają tylko znaczenie logicznych powiązań, gdzie ich długość i kształt nie mają żadnego znaczenia.

3. Żadne dwa wierzchołki sieci nie mogą być połączone więcej niż jedną strzałką.

4. Wskazane jest, aby numeracja wierzchołków sieci zaczynała kolejność zdarzeń.

28. METODA CPM

Metoda CPM - ścieżki krytycznej

Zakłada się, że czasy trwania poszczególnych czynności są dane.

Celem metody CPM jest wyznaczenie najkrótszego czasu zakończenia przedsięwzięcia oraz ustalenie harmonogramu wykonania poszczególnych czynności. Spośród wszystkich czynności przedsięwzięcia szczególnego znaczenia nabierają czynności tworzące pewną ścieżkę tzw. krytyczną, która łączy początek sieci z jej wierzchołkiem końcowym. Suma czasów wykonania wszystkich czynności tworzących ścieżkę krytyczną nazywana jest czasem przejścia ścieżki. Najkrótszy możliwy czas zakończenia przedsięwzięcia równy jest czasowi krytycznemu. W celu wyznaczenia czasu krytycznego należy obliczyć pewne granice czasowe dla każdej czynności tj. najwcześniejszy i najpóźniejszy moment wejścia zdarzenia, z którego czynność wychodzi oraz zdarzenia, w którym czynność się kończy oraz tzw. zapas czasu (luz czasowy). Najważniejsze momenty zaistnienia zdarzeń obliczone są kolejno od pierwszego do ostatniego zdarzenia. Natomiast najpóźniejsze momenty oblicza się w kolejności odwrotnej (od ostatniego do pierwszego).

tij - czas realizacji czynności <ij>

T_i^w - najwcześniejszy możliwy termin wystąpienia zdarzenia i

T_i^p - najpóźniejszy dopuszczalny termin zaistnienia zdarzenia i

Dla zdarzenia początkowego T₁^w = 0

T_j^w - max czas T_j^w = max {T_i^w + tij} j = 2,3,4,...

W celu obliczania terminów najpóżniejszych przyjmujemy że dla zdarzenia końcowego sieci:

T^p_n =T^w_n

T^p_i = min{ T^p_j −t_ij }

Luzem zdarzenia nazywamy liczbę:

L_i =T^p_i −T^w_i

Jeżeli luz zdarzenia jest równy zeru to nazywamy go krytycznym.

Zapas całkowity czasu czynności ij to wielkość:

Z_ij =L_i − t_ij

_Zij = T^p_i − T^w_i −t_ij

W praktyce ważną role odgrywają czynności krytyczne. Rozpoczęcie czynności krytycznej później niż w najwcześniejszym momencie zaistnienia zdarzenia i-tego powoduje spóźnienia terminu zakończenia przedsięwzięcia. Czynności nie należące do ścieżki krytycznej mają dodatnie luzy czasowe co znaczy, że opóźnienie momentów ich rozpoczęcia w granicach tych luzów nie powoduje zmiany czasu przedsięwzięcia. Zapasy czasu czynności mówią nam o tym o ile można opóźnić rozpoczęcie danej czynności nie zmieniając czasu realizacji całego przedsięwzięcia.

29. METODA PERT

W metodzie PERT czasy trwania wszystkich czynności nie są dokładnie znane i mają charakter losowy. W sytuacji kiedy możliwa jest probabilistyczna ocena czasów trwania poszczególnych czynności stosowana jest metoda PERT.W metodzie PERT wymagane jest określenie trzech szacunkowych czasów dla każdej czynności

T_o-czas optymistyczny, czyli najkrótszy możliwy czas wykonania czynności w najbardziej sprzyjających okolicznościach.

T_m- czas modalny najbardziej prawdopodobny czas wykonania czynności w warunkach normalnych.

T_p- czas pesymistyczny,najdłuższy czas potrzebny do wykonania czynności w warunkach najmniej korzystnych.

Powyższe wielkości służą do wyznaczenia oczekiwanego czasu trwania w następujący sposób:

T_e = (t_o +4t_m+t_p) / 6

Wzór ten oparty jest na estymacji rozkładu β.Ten szczególny rozkład został wprowadzony przez twórców metody PERT, ponieważ jest to rozkład jednomodalny,ma skończoną i nieujemną górną granicę przedziału zmienności niekoniecznie jest rozkładem symetrycznym.

Po wyznaczeniu czasu oczekiwanego każdej czynności należy określić również spodziewaną wielkość odchylenia od tego czasu.W tym celu dla każdej czynności obliczana jest wariancja czasu trwania czynności w następujący sposób:

δ² =(t_p − t₀ /6)²

W celu określenia ścieżki krytycznej oczekiwanego czasu oraz zakończonego przedsięwzięcia postępuje się zgodnie z procedurą CPM, przy czym obciążeniami sieci będą czasy oczekiwane te.

Oczekiwany czas zakończenia przedsięwzięcia jest czasem przejścia ścieżki krytycznej.

W analizie PERT rozpatruje się również p-stwa zakończenia przeds-cia w dowolnie innym czasie niż w czasie oczekiwanym. W tym celu korzysta się z tezy centralnego twierdzenia granicznego i przyjmuje się, że rozkład p-stwa czasu trwania przeds-cia jest roz. normalnym.

---