Badania operacyjne Wykład 1. 18.02.2014

Badania operacyjne – są zbiorem modeli i metod poszukiwań optymalnych rozwiązań. W badaniach operacyjnych wykorzystywane są metody matematyczno – statystyczne do wyznaczania optymalnych rozwiązań problemów decyzyjnych.

Decydent – osoba, która podejmuje decyzje o realizacji danego przedsięwzięcia i która ponosi odpowiedzialność za jego realizację.

Kryterium decyzyjne (kryterium optymalności) miara za pomocą, której można dokonać klasyfikacji poszczególnych decyzji na lepsze i gorsze. Często wykorzystywanym kryterium decyzyjnym jest zysk. Optymalizacja polega na maksymalizacji zysku lub minimalizacji kosztów.

Rodzaje decyzji (Z. Łęcki 2008)

Wyróżnić można następujące rodzaje decyzji:

- dopuszczalne – nadające się do realizacji

- niedopuszczalne – niemożliwe do realizacji ze względu na brak możliwości np. ze względu na brak środków finansowych

- optymalne – uzyskanie założonego efektu przy najniższym możliwym zużyciu środków

- nieoptymalne – uzyskanie gorszego efektu lub większe zużycie środków

Modelem decyzyjnym (modelem optymalizacyjnym) nazywamy narzędzia wykorzystywane do wyznaczania optymalnej decyzji.

Rodzaje modeli decyzyjnych:

1. Model programowania nieliniowego

2. Model programowania liniowego

3. Model programowania dynamicznego

4. Modele sieciowe

5. Drzewa decyzyjne

6. Modele symulacyjne

Etapy rozwiązania programowania:

1. Sformułowanie problemu decyzyjnego

2. Wybór zmiennych decyzyjnych – wielkości, które należy ustalić

3. Określenie funkcji celu – funkcja celu zapisana w postaci funkcji matematycznej. Celem jest uzyskanie jak największych korzyści lub jak najmniejszych strat.

Zadanie decyzyjne

f(x) → max f(x) → min

Zysk koszt (strata)

dla x є D

1. Określenie warunków ograniczający

Ograniczenia są to nierówności lub równania wyrażające w sposób formalny warunki, w jakich działa decydent.

1. Nieujemność zmiennych decyzyjnych

Modelem matematyczny –nazywamy zapis problemu decyzyjnego w języku matematycznym.

Parametry – dane wielkości występujące w równaniu

Zmienne decyzyjne – wielkości, które należy ustalić (niewiadome w funkcji celu)

W modelach optymalizacyjnych występują trzy elementy:

1. Funkcja celu

2. Warunki ograniczające

3. Warunki nieujemności zmiennych decyzyjnych

Jeżeli w zadaniu decyzyjnym funkcja celu jest funkcją liniową oraz warunki ograniczające są liniowe, to określamy ją nazwą programowania liniowego.

Metoda programowania liniowego

Standardowa postać programowania liniowego

f(x) → max oraz wszystkie ograniczenie są nierównościami typu ≤ oraz wszystkie zmienne są nieujemne

f(x) → min oraz wszystkie ograniczenie są nierównościami typu ≥ oraz wszystkie zmienne są nieujemne

Rozwiązaniem dopuszczalnym zagadnienia programowania liniowego nazywamy wektor zmiennych decyzyjnych

x = [ x₁, x₂, …, x_n ], który spełnia warunki ograniczające.

Rozwiązaniem optymalnym nazywamy takie rozwiązanie dopuszczalne, dla którego funkcja celu osiąga wartość ekstremalną.

Postać kanoniczna zadania programowania liniowego

Warunki ograniczające dane są równaniami oraz wszystkie zmienne są nieujemne.

Przykład: Przedsiębiorstwo wytwarza dwa rodzaje produktów P₁ i P₂, które są obrabiane na dwóch maszynach M1 i M2. W tablicy podano czas pracy maszyn przypadający na obróbkę jednostki danych wyrobów.

Wyroby	Czas przypadający na jednostkę wyrobu (w h)
	M1
P1	2
P2	6

Wiadomo, że zysk jednostkowy (w zł) dla danych produktów wynosi odpowiednio dla P₁ 4 zł, a dla P₂ – 5 zł. Maszyna M1 może pracować miesięcznie nie więcej niż 100 godzin, natomiast maszyna M2 nie więcej niż 120 godzin. Zbudować model matematyczny tego zadania.

x₁ – planowana wielkość produkcji wyrobu P₁

x₂ – planowana wielkość produkcji wyrobu P₂

Model zagadnienia

Funkcja celu: f(x₁, x₂) = 4 x₁ + 5 x₂ → max

Warunki ograniczające:

2 x₁ + 6 x₂ ≤ 100

4 x₁ + 3 x_2­ ≤ 120

Warunki brzegowe: x₁, x₂ ≥ 0

Gradient: v = [4, 5]

Gradient – wektor prostopadły, dzięki któremu przesuwać będziemy w górę lub w dół funkcję celu.

Zbiory rozwiązań dopuszczalnych

Metoda graficzna rozwiązywania zadań programowania liniowego

Przy wyznaczaniu metodą graficzną zbioru rozwiązań dopuszczalnych mogą wystąpić:

1. Wielokąt wypukły

x₂

Rozwiązanie optymalne zawsze w jednym z

wierzchołków.

x₁

1. Zbiór rozwiązań dopuszczalnych stanowi zbiór nieograniczony

x₂

Funkcja celu nie osiągnie wartości maksymalnej.

x₁

1. Zbiór rozwiązań dopuszczanych jest zbiorem pustym

x₂

Nie ma rozwiązania optymalnego

x₁

1. Zbiór rozwiązań dopuszczalnych stanowi odcinek

x₂

x₁

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

x₂

x₁

Wykorzystanie metody graficznej w celu rozwiązania zadania programowania liniowego polega na wyznaczeniu punktów, w których funkcja celu osiąga swą wartość największą ( najmniejszą) w zbiorze rozwiązań dopuszczalnych.

Rozwiązanie zadania z wykorzystaniem programu EXCEL:

Zmienne decyzyjne:

x_i – wielkość produkcji wyrobu W_i

Model:

Funkcja celu: f(x₁, x₂) = 10 x₁ + 15 x₂ → max

Warunki ograniczające:

4 x₁ + 2 x₂ ≤ 500

2 x₁ + 4 x_2­ ≤ 600

Warunki brzegowe: x₁, x₂ ≥ 0

Komórka celu u nas = 40

Komórki zmienne 1,2

Warunki ograniczające: 8 ≤ 500; 10 ≤ 600

Luz – oznacza, np. że czas pracy maszyny został wykorzystany całkowicie

Solver → opcje → przyjmij nieujemne → rozwiąż

Wykład 2. 04.03.2014

Metoda Simpleks

Istota algorytmu simpleks polega na badaniu kolejnych rozwiązań bazowych programu liniowego w postaci kanonicznej:

1. Wyznaczamy rozwiązania bazowe

2. Sprawdzamy, czy jest ono rozwiązaniem optymalnym

3. Jeżeli rozwiązanie w punkcie 2 nie jest rozwiązaniem optymalnym wyznacza się lepsze rozwiązanie.

ANALIZA WRAŻLIWOŚCI

Określenie zakresu zmian parametrów funkcji celu, wektora warunków ograniczających oraz macierzy współczynników warunków ograniczających, które nie wpłyną na zmiany wyznaczonego wcześniej rozwiązania optymalnego.

Raport wyników

Komórka celu:

Komórka	Wartość początkowa	Wartość końcowa
$E$4	120	189

← max / min

Komórki decyzyjne

Komórka	Nazwa	Wartość początkowa	Wartość końcowa
	x1	0	3
	x2	5	0
	x3	1,138796E - 11	3

Warunki ograniczające:

Komórka	Nazwa	Wartość komórki	Formuła	Status	Luz
$E$8	Lewa strona	15	$E$8 ≤ $F$8	Wiążące	0
$E$9	Lewa strona	15	$E$9 ≤ $F$9	Wiążące	0
$E$10	Lewa strona	9	$E$10 ≤ $F$10	Niewiążące

Wartość lewych stron warunków ograniczających dla rozwiązania optymalnego

Wartość końcowa – wartość zmiennych decyzyjnych, rozwiązanie.

Raport wrażliwości

	Dopuszczalny wzrost	Dopuszczalny spadek
x1	1E + 30	2,999
x2	1,79999	1E + 30
x3	12	5,142857141

Dopuszczalny wzrost i dopuszczalny spadek wartości współczynników funkcji celu, gdy wartości innych współczynników pozostaną bez zmian (zakres stabilności decyzji optymalnej względem zmian wartości współczynników funkcji celu).

c₁ c₂ c₃ ↓ rozwiązanie optymalne

f(x₁, x₂, x₃) = 15 x₁ + 24 x₂ + 48x₃ (3,0,3) (189)

c₁ є < 15 – 2,99; 15 + ∞ > c₁ є < 12,01; ∞ > c₁, c₂, c₃ – współczynniki funkcji celu. Jeżeli c₁, będzie należało do przedziału < 12,01; ∞ > i c₂, c₃ nie zmienią się to nie wpłynie to na zmianę rozwiązania optymalnego.

c₂ є < 24 - ∞; 24 + 1,8 > c₂ є < 0; 25,8 >

Jeżeli c₁, c₃ nie zmienią się to nie spowoduje to zmiany rozwiązania optymalnego.

Wartość końcowa – wartość lewych stron warunków ograniczających dla rozwiązania optymalnego

15

15

9

Dopuszczalny wzrost i spadek dotyczą zmian wartości wyrazów wolnych dla prawej strony warunków ograniczających.

Cena dualna – występuje, gdy luz wynosi 0, gdy maksymalnie jest wykorzystany zasób, wtedy występują ceny dualne.

Każdemu zagadnieniu programowania liniowego odpowiada zagadnienie optymalizacji zwane zagadnieniem dualnym.

Wykorzystanie zadania dualnego:

1. Pozwala na uproszczenie obliczeń

2. Pozwala na obliczanie wrażliwości rozwiązania programowania liniowego na dane ograniczenia.

Zadanie pierwotne a zadanie dualne

Między zadaniem pierwotnym a zadaniem dualnym zachodzi dokładnie jeden z następujących związków:

1. Oba zadania maja skończone rozwiązanie optymalne

2. Jedno z zadań jest niedopuszczalne, a drugie nieograniczone

3. Oba zadania są niedopuszczalne

Jeżeli: x – dowolne rozwiązanie dopuszczalne problemu pierwotnego

v – dowolne rozwiązanie dopuszczalne problemu dualnego to:

c^T x ≤ b^T v

Zadanie pierwotne Zadanie dualne

3 x₁ + 4 x₂ + x₃ → max 7 y₁ + 16 y₂ → min

x₁ + x₂ + 2x₃ ≤ 7 macierz y₁ + 2 y₂ ≥ 3

2 x₁ + 4 x₂ + x₃ ≤ 16 y₁ + 4 y₂ ≥ 4

x₁, x₂, x₃ ≥ 0 2 y₁ + y₂ ≥ 1

y₁, y₂ ≥ 0

Przykład:

12 y₁ + 14 y₂ → max

12 y₁ + 4 y₂ ≥ 12 optymalne (1,3) (54)

	12	14
	x1	x2
	1	3	54
	L	P
1	12	4	24
2	4	8	28

4 y₁ + 8 y₂ ≥ 14

y₁, y₂ ≥ 0

Cena dualna

0,5

1,5

Zadanie pierwotne to do tej pory na ćwiczeniach było.

Rozwiązaniem zadania dualnego są ceny dualne!

Interpretacja:

0,5 – wzrost zasobu surowca S1 o jednostkę spowoduje wzrost optymalnej wartości funkcji celu o 0,5 jednostki (względem wartości 54)

1,5 – wzrost zasobu surowca s2 o jednostkę przyczyni się do wzrostu zysku przedsiębiorstwa o 1,5 jednostek względem wartości 54.

Jeżeli luz = 0 to cena dualna > 0, luz ≠ 0 to cena dualna = 0!

Programowanie liniowe całkowitoliczbowe

Jeżeli składowe rozwiązania optymalnego są liczbami całkowitymi, nazywamy je rozwiązaniem całkowitoliczbowym.

Zaznaczamy tolerancję zerową!

1. Czyste zadanie programowania całkowitoliczbowego – wszystkie zmienne przyjmują wartości całkowite

2. Mieszane zadanie programowania całkowitoliczbowego – warunki dotyczące wartości całkowitych dotyczą niektórych zmiennych.

Zagadnienie mieszanek (diety)

Dotyczy ustalenia składu mieszanki (ile surowców należy zmieszać), żeby przy najniższych kosztach otrzymać produkt o założonym składzie chemicznym.

Jakie dane potrzebne są do zagadnienia rozwiązania modelu optymalizacji mieszanki ??

1. Zawartość poszczególnych i - tych składników odżywczych w jednostce j –tego produktu (wykorzystywanych do sporządzania mieszanki np. zawartości białka, witamin).

2. Normy żywieniowe ( minimalne lub maksymalna ilość składnika jaki trzeba dostarczyć)

3. Cena produktów wykorzystywanych do sporządzenia mieszanki

a₁₁ x₁ + a₁₂ x₂ + … + a_1n x_n ≥ b₁

a₂₁ x₁ + a₂₂ x₂ + … + a_2n x_n ≥ b₂

… może być też ≤

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n ≥ b_m

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0

Z (x) = c₁ x₁ + c₂ x₂ + … + c_n x_n → min

c₁, c₂, … - cena j – tego produktu

b₁, b₂, … - norma żywieniowa

a_m1, a₂₂, a_1n, … - zawartość i – tego składnika w jednostce j –tego produktu

Wybór procesu technologicznego

Należy tak dobrać proces technologiczny, żeby wyprodukować dane ilości wyrobów przy jak najmniejszych kosztach.

Przykład: Jak należy pociąć otrzymane bele papieru, żeby odpad powstały przy cieciu był jak najmniejszy? …

Wykład 3. 18.03.2014

ZAGADNIENIA TRANSPORTOWE

Celem zadania transportowego jest wyznaczenie przy danej sytuacji popytowo - podażowej oraz danych środkach transportu takich przepływów od poszczególnych dostawców do poszczególnych odbiorców żeby przyjęte kryterium osiągnęło wartość minimalna.

Funkcja celu zawsze dąży do minimalizacji.

Role mierników kryterium najczęściej spełniają:

1. W krótkim okresie odległości ekonomiczno-taryfowe

2. W długim okresie oprócz odległości ekonomiczno-czasowych koszty inwestycji, czas realizacji inwestycji.

Każdy klasyczny model transportowy posiada, co najmniej jedno rozwiązanie optymalne.

Rodzaje zagadnień transportowych:

1. Klasyczne zagadnienie transportowe- szukamy, jak najtanszego rozwiezienia towarów od dostawców do odbiorców

2. Wieloetapowe zagadnienia transportowe – oprócz odbiorców i dostawców występują jeszcze inne punkty pośrednie

Klasyczne zagadnienia transportowe dzielimy na:

1. Otwarte

2. Zamknięte

W wieloetapowych zagadnieniach transportowych dodajemy ograniczenia dotyczące punktów pośrednich (suma towarów wpływająca do punktu pośredniego i wypływająca z tego punktu jest równa zero).

Problem zagadnienia:

R – liczba dostawców pewnego towaru, z których każdy dysponuje A_i jednostkami tego towaru

N – liczba odbiorców

B_i zapotrzebowanie każdego z odbiorców

C_ji – jednostkowy koszt transportu od i-tego dostawcy do j-tego odbiorcy

Celem jest opracowanie planu przewozu towaru pomiędzy dostawcami i odbiorcami, żeby łączne koszty tego przewozu były najniższe. Czasami dolicz się także koszty magazynowania.

Zamknięte zagadnienie transportowe

Warunki ograniczające:

1. i-ty dostawca ma dostarczyć wszystkim odbiorcom tyle towaru ile posiada (warunków jest tyle ilu dostawców)

_N

∑ x_ij = A_{i (i=1,2…R)}

^j=1

1. j-ty odbiorca ma otrzymać od wszystkich dostawców tyle towaru ile potrzebuje (warunków tych jest N)

_R

∑ x_ij = B_{j (j=1,2…N)}

ⁱ⁼¹

x_ij>=0

_{R N}

∑ ∑ c_ij x_ij = min

^{i=1 j=1}

PRZYKŁAD

	Odbiorca1	Odbiorca2
Dostawca1	2	3
Dostawca2	4	8

50 200

X_ij – ilość towaru, jaka powinna być dostarczona od i-tego dostawcy do j-tego odbiorcy

fc= 2x₁₁ +3x₁₂ +4x₂₁ +8x₂₂ ­ min

warunki ograniczające dla dostawców:

x₁₁ +x₁₂ =100

x₂₁ +x₂₂ =150

warunki ograniczające dla odbiorców:

x₁₁ +x₂₁=50

x₁₂ +x₂₂=200

x_ij>=0

Exel

Odbiorca1 Odbiorca2

2	3
4	8

Dostawca1

Dostawca2

L

P

A

B

fc = suma iloczynów (A;B)

do warunków ograniczających zapisujemy L=P

Otwarte zagadnienia transportowe

Zagadnienie otwarte można sprowadzić do zagadnienia zamkniętego przez wprowadzenie fikcyjnego odbiorcy, którego zapotrzebowanie jest równe nadwyżce podaży nad popytem.

Fikcyjnym odbiorca jest najczęściej magazyn.

PRZYKŁAD

Odbiorca1 Odbiorca2 Magazyn

2	3	1
4	8	2

Odbiorca1 Odbiorca2 Magazyn

0	0	0
0	0
0	0	0
50	200	50

ZAGADNIENIE TRANSPORTOWO-PRODUKCYJNE

Dane dotyczące zagadnienia:

R- liczba producentów pewnego produktu gdzie i-ty producent ma zdolność produkcyjna, Ai

N- liczba odbiorców, którzy są zaopatrywani przez danych producentów

Założenie: zdolności produkcyjne przekraczają zapotrzebowanie odbiorców

C_ij –jednostkowy koszt transportu od i-tego dostawcy do j-tego odbiorcy

P_i – jednostkowe koszty produkcji w i-tym zakładzie

Do kosztu transportu dodaje się jednostkowe koszty produkcji.

ZAGADNIENIA PRZYDZIALU

W zagadnieniu przydziału dokonuje się optymalnej alokacji danych zasobów.

Celem jest zaprogramowanie przydziału zadań produkcyjnych do poszczególnych miejsc pracy z punktu widzenia nastepujacych kryteriów:

1. minimalizacji czasu lub kosztów wykonywania żądań planowych

2. maksymalizacji efektów pracy (np. ilości wyprodukowanych wyrobów)

MODEL 1

Dane są informacje dotyczące:

1. wydajności i-tego miejsca przy wykonywaniu j-tego wyrobu – a_ij

2. założonej wielkości produkcji j-tego wyrobu

C_{j (j=1,2,…N)}

1. dopuszczalnego czasu pracy i-tego miejsca

B_{i (i=1,2…P)}

Przydzielamy produkcje do poszczególnych miejsc tak żeby zminimalizować czas lub koszty produkcji lub zmaksymalizować wielkość produkcji.

W modelu 1 mogą występować dane dotyczące wydajności miejsc pracy w jednostkach czasu. Przydział polega na ustaleniu czasu pracy i-tego miejsca przy wykonywaniu j-tego wyrobu, czyli wartości x_ij.

MODEL 2

Dane są informacje dotyczące:

1. czasu pracy i-tego miejsca przy wykonywaniu j-tego wyrobu – a_ij

2. założonej wielkości produkcji j-tego wyrobu

C_{j (j=1,2,…N)}

1. dopuszczalnego czasu pracy i-tego miejsca

B_{i (i=1,2…P)}

Należy przydzielić produkcje do miejsc pracy żeby zminimalizować czas produkcji lub zmaksymalizować wielkość produkcji.

W modelu 2 mogą występować dane dotyczące jednostkowych czasów pracy. Przydział polega na ustaleniu ilości j-tego wyrobu, jaka należy wytworzyć na i-tym miejscu x_ij.

Zadaniem przydziału (rozmieszczenia) nazywamy zbilansowane zadanie transportowe, w którym wielkość podaży i popytu są równe jedności.

Badania operacyjne Wykład 4. 1.04.2014

Programowanie sieciowe

W celu planowania przedsięwzięć zapewniających sprawny przebieg ich wykonania wykorzystać można metody programowania sieciowego.

Przedsięwzięcie – zorganizowane działanie człowieka, które zmierza do osiągnięcia zamierzonego celu, które:
- ma wyróżniony początek i koniec,
- realizowane jest w skończonym przedziale czasu,
- realizowane jest z wykorzystaniem danej ilości materiałów, środków finansowych, środków technicznych i energii.

Na przedsięwzięcie składa się ciąg czynności, które :
- są ze sobą powiązane,
- wykonywane są w określonej kolejności,
- mogą wystąpić czynności, które są wykonywane równocześnie.

Optymalizacja przedsięwzięcia polega na:
1. Ocenie parametrów zdarzeń i czynności,
2. Wyodrębnieniu wchodzących w jego skład czynności,
3. Wyznaczeniu charakterystyk sieci dotyczących zdarzeń, czynności i całego projektu,
4. Wyznaczeniu ścieżki krytycznej.

Ścieżką w sieci – nazywamy ciąg czynności i zdarzeń umożliwiających przejście od początku do końca sieci (od zdarzenia początkowego do zdarzenia końcowego).

Ścieżka krytyczną – nazywamy drogę, której czas przejścia jest najdłuższy (wszystkie czynności muszą być zakończone).

Modele sieciowe mogą być wykorzystywane do rozwiązania następujących problemów:
1. Najdłuższej i najkrótszej drogi.
2. Maksymalnego przepływu w sieciach.
3. Przepływu o minimalnym koszcie.

Metody analizy sieciowej:
Modele sieciowe deterministyczne – określone jednoznacznie są czasy trwania danych czynności, np. metoda CPM (metoda ścieżki krytycznej CPM).
Modele sieciowe stochastyczne – z pewnym prawdopodobieństwem można określić czasy trwania danych czynności, np. metoda PERT.

Czynność – część przedsięwzięcia z określonym czasem trwania oraz zużyciem środków.

Strzałki wskazują kierunek przebiegu czynności w czasie.

Czynność pozorna – nie zużywa czasu oraz środków. Jest wykorzystywana do przedstawienia zależności pomiędzy czynnościami.

- - - - - - - - - - >

Zdarzenie – moment rozpoczęcia lub zakończenia wielu lub jednej czynności. Zaistnienie zdarzenia nie pochłania kosztów.

Każde zdarzenie w ciągu czynności jest zdarzeniem początkowymi końcowym tylko dla jednej czynności.

Oznaczenia:

i – numer zdarzenia, w którym czynność się rozpoczyna.
j – numer zdarzenia, w którym czynność się kończy.

Reguły konstrukcji sieci (Kukuła 2004)
1. Istnieje dokładnie jeden wierzchołek początkowy zdarzenia i jeden wierzchołek końcowy zdarzenia.
2. Wierzchołki i luki są odpowiednio uporządkowane (i < j).
3. Dwa zdarzenia są połączone tylko jedną czynnością (wprowadzamy czynności pozorne, jeżeli kilka czynności wykonywanych równolegle poprzedza jedną czynność).
4. Strzałki obrazujące czynności nie przecinają się.

W przypadku zdarzenia w sieci wyznacza się:
1. Najwcześniejszy możliwy moment zaistnienia zdarzenia (t).
2. Najpóźniejszy możliwy moment zaistnienia zdarzenia (T).
3. Zapas czasu (L). L = T_i − t_i .

Zapas czasu informuje o ile można wydłużyć czas trwania danej czynności, żeby czas realizacji przedsięwzięcia nie uległ zmianie.
czynności leżące na ścieżce krytycznej mają zapas czasu równy zero.

Metoda CPM
1. Jeżeli do zdarzenia dochodzi więcej niż jedna czynność, to najwcześniejszy możliwy moment zaistnienia tego zdarzenia jest równy maksymalnej wartości z obliczonych najwcześniejszych momentów zaistnienia zdarzenia.
2. Jeżeli do zdarzenia dochodzi więcej niż jedna czynność, to obliczając najpóźniejszy możliwy moment zaistnienia zdarzenia wybieramy wielkość mniejszą.

Sieć czynności danego przedsięwzięcia.

Czynność	Czas trwania czynności
1-2 1-3 2-4 3-4 4-5 4-6 5-7 6-7 6-8 7-9 8-9	3 1 2 3 2 4 1 3 2 3 2

Ścieżka krytyczna 1-2-4-6-7-9.

Dane są trzy czasy trwania czynności:
1. Czas optymistyczny (a) – czas trwania czynności w najbardziej optymistycznych warunkach.
2. Czas pesymistyczny (b)
3. Czas modalny (m) – czas, który najczęściej występuje przy wielokrotnym powtarzaniu czynności (czas najbardziej prawdopodobny).

Czas optymistyczny <= czas modalny <= czas pesymistyczny.

Czas oczekiwany czynności obliczamy według następującego wzoru $\mathbf{t}\mathbf{=}\frac{\mathbf{(}\mathbf{a}\mathbf{+}\mathbf{4}\mathbf{m}\mathbf{+}\mathbf{b}\mathbf{)}}{\mathbf{6}}$ .

Wariancja czasów trwania czynności $\mathbf{\sigma}_{\mathbf{\text{ij}}}^{\mathbf{2}}\mathbf{=}\left( \frac{\mathbf{b}\mathbf{-}\mathbf{a}}{\mathbf{6}} \right)^{\mathbf{2}}$.

Wariancja terminu wykonania przedsięwzięcia jest równa sumie wariancji dla czynności krytycznych. Wariancja jest miarą rozbieżności pomiędzy czasem pesymistycznym i optymistycznym. Prawdopodobieństwo jest większe, że czynność zostanie zrealizowana w czasie przeciętnym, jeżeli wariancja jest bliższa zeru.

Wariancja terminu wykonania przedsięwzięcia (σ_Tw²).

Odchylenie standardowe terminu wykonania określa spodziewana wielkość odchylenia rzeczywistego terminu wykonania przedsięwzięcia od wyznaczonego w sieci terminu oczekiwanego.

W celu obliczenia prawdopodobieństwa, że przedsięwzięcie będzie zakończone w pewnym terminie wykorzystywana jest statystyka $\mathbf{X}\mathbf{=}\frac{\mathbf{t}_{\mathbf{d}}{\mathbf{-}\mathbf{t}}_{\mathbf{w}}}{\sqrt{\mathbf{\sigma}_{\mathbf{\text{Tw}}}^{\mathbf{2}}}}$

t_d - narzucony termin

t_w – oczekiwany termin .

F(x) ∈  ⟨0,25 ;0,6⟩ otrzymanie terminu jest realne.

F(x) ≤ 0, 25 małe szanse dotrzymania terminu realizacji przedsięwzięcia.

Jeżeli występuje więcej niż jedna ścieżka krytyczna to wyznaczamy odchylenie standardowe oraz obliczamy prawdopodobieństwo.

Wykład 5 15.04.2014

Analiza czasowo-kosztowa CPM-COST

Możemy rozpatrywać możliwości skrócenia termonu realizacji przedsięwzięcia tak, żeby koszty związane z jego realizacją były jak najmniejsze.

Konstruując program przyspieszenia realizacji przedsięwzięcia bierzemy pod uwagę czynności krytyczne, ponieważ ich koszty przyspieszenia są najmniejsze.

Średni gradient kosztu określa przyrost kosztów wykonania czynności ze względu na skrócenie czasu jej wykonania o jednostkę.

$$\mathbf{S}\mathbf{=}\frac{\mathbf{K}_{\mathbf{\text{gr}}}{\mathbf{-}\mathbf{K}}_{\mathbf{n}}}{\mathbf{t}_{\mathbf{n}}{\mathbf{-}\mathbf{t}}_{\mathbf{\text{gr}}}}$$

1. Wyznaczamy termin realizacji przedsięwzięcia oraz ścieżkę krytyczna biorąc pod uwagę czasy normalne trwania czynności.

2. Dla czynności krytycznych obliczamy gradienty kosztów.

3. Usuwamy te zestawienia dla których t_n=t_gr.

4. Skracanie rozpoczynamy od czynności krytycznej o najmniejszym gradiencie.

5. W przypadku wystąpienia więcej niż jednej ścieżki krytycznej czas skracamy na wszystkich ścieżkach krytycznych o ta samą wartość.

6. Najkrótszy czas realizacji przedsięwzięcia wystąpi wtedy, gdy wszystkie czynności leżące na ścieżce krytycznej osiągną czasy graniczne.

Dane dotyczące przedsięwzięcia przedstawiono w tabeli:

i - j	tn	tgr	Kn	Kgr	S
1-2	10	8	300	400	50
1-4	12	7	100	150	10
2-3	8	6	280	350	35
3-6	12	10	250	300	25
4-5	17	17	200	200	-
5-6	15	10	200	220	4

Ścieżka krytyczna 1-4-5-6.
Czas wykonania 44 dni.

Rozpoczynamy skracanie od czynności 5-6, ponieważ gradient jest najmniejszy równy 4.
Wzrost kosztów wynikających ze skróceń wynosi K₁ = 4 * (15−10) = 20 jednostek pienieznych.
Czas realizacji przedsięwzięcia będzie wynosił 39 dni.

Skracamy czynność 1-4 o 5 jednostek czasowych. Wzrost kosztów wynikający ze skrócenia czynności wynosi K₂ = 10 * (12−7) = 50 jednostek pienieznych. Czas realizacji będzie wynosił 34 dni.

Koszty przyspieszenia przedsięwzięcia wynoszą K = K₁ + K₂ = 20 + 50 = 70 jedn.pienieznych.

Optymalizacja wielokryterialna

Polega na znalezieniu optymalnego rozwiązania, które jest akceptowane z punktu widzenia każdego kryterium.

1. Zadania jednokryterialne – maksymalizacja lub minimalizacja jednego celu.

2. Zadania wielokryterialne – optymalizacja więcej niż jednego kryterium:

• Więcej niż jedna funkcja celu,

• Warunki ograniczające skonstruowane tak jak w przypadku zadań jednokryterialnych.

Przy wyznaczaniu rozwiązania optymalnego można wyróżnić dwie grupy rozwiązań:

1. Rozwiązania zdominowane.

2. Rozwiązania niezdominowane.

Nie zawsze jesteśmy w stanie polepszyć rozwiązanie ze względu na rozważane kryteria, bez pogorszenia wartości pozostałych kryteriów.
Rozwiązanie dominujące czyli takie, które jest lepsze od wszystkich możliwych nie zdarza się często. Decydent podejmuje decyzję w ten sposób, żeby w maksymalnym stopniu zrealizować założone cele.

Przy wyznaczaniu rozwiązań „najlepszych” zadania wielokryterialnego mogą pojawić się następujące przypadki (np. przy maksymalizacji)

f₁ → max ∖ nf₂ → max ∖ nwarunki ograniczajace x_i ≥ 1

f₁ → max f₂ → max
war. ogr. war. ogr.

(2,3) (2,3)

ale jeśli inne np.

(2,4) (4,1)

(2,4)

Wektor y¹ dominuje wektor y² , jeżeli y¹ nie jest gorszy od y² oraz przynajmniej jedna składowa wektora y¹ jest większa od odpowiadającej składowej y².

f_i(y¹) ≥ f_i(y²) dla wszystkich i = 1, 2, …k.

Jeżeli w modelu wielokryterialnym istnieje rozwiązanie najlepsze spośród wszystkich rozwiązań nazywamy je rozwiązaniem optymalnym wektorowo.

Rozwiązania niezdominowane – nie istnieją dla nich rozwiązania lepsze, poprawa wartości jednego kryterium obniża wartość innego kryterium. Są to rozwiązania optymalne wektorowo w przestrzeni kryterialnej, a odpowiadające im rozwiązania w przestrzeni decyzyjnej nazywamy rozwiązaniami sprawnymi (Trzaskalik 2008).

kryterium 2

kryterium 1

Aby łatwiej wyznaczyć warunki ograniczające obie funkcje celu robimy na maksimum gdy mamy max i min. Aby z min zrobić max przemnażamy funkcję celu minimalizującą przez (-1) i otrzymujemy funkcje maksymalizującą.

Wykład 6. 6.05.2014

Zadanie wielokryterialne z hierarchią kryteriów

Hierarchia celów polega na ustawieniu celów w kolejności od kryterium najważniejszego do kryterium najmniej ważnego dla decydenta.

Etapy rozwiązania

1. Rozwiązujemy zadanie jednokryterialne względem kryterium „najważniejszego”.

2. Rozwiązujemy zadanie wielokryterialne względem pozostałych kryteriów. Uwzględniamy dodatkowy warunek ograniczający – poprzedni cel jest osiągnięty na wyznaczonym poziomie. Na każdym etapie liczba warunków ograniczających zwiększa się o jeden warunek.

Rozwiązywanie problemu wielokryterialnego metoda sumy ważonej

Programowanie dynamiczne

Programowanie dynamiczne jest techniką optymalizacyjną, która może być wykorzystywana do rozwiązania problemów decyzyjnych równolegle z innymi metodami optymalizacji. Wykorzystując programowanie dynamiczne do optymalizacji rozważamy sposób podejścia do danego problemu, nie pojedynczą procedurę. Polega ona na podziale problemu optymalizacyjnego na mniejsze problemy, które są rozwiązane po kolei oddzielnie.

Wzajemna zależność pomiędzy danymi etapami określa zasada optymalności Bellmana.

Pierwszym kroku dla każdego etapu tworzymy równania optymalności, w kolejnym łączymy ze sobą rozwiązania zadań cząstkowych i podejmujemy optymalną decyzję realizacji całego procesu.

W programowaniu dynamicznym wykorzystuje się zasadę optymalności Bellmana, w myśl której optymalne rozwiązanie zagadnień z zakresu programowania dynamicznego ma tę własność, że optymalne rozwiązanie dla k – tego etapu jest jednocześnie rozwiązaniem optymalnym dla etapów k+1, k+2, …, N.

Tak więc optymalne rozwiązanie dla etapu pierwszego stanowi optymalne rozwiązanie dla całego problemu. Zakres programowania dynamicznego rozwiązuje się zaczynając od znalezienia rozwiązania dla ostatniego etapu (etapu N) i cofając się w celu poszukiwania rozwiązania dla etapu wcześniejszego, czyli (N – 1).

Zastosowanie zadań programowania dynamicznego

1. Zagadnienia dyliżansu – problem najkrótszej drogi

2. Zagadnienia finansowania inwestycji – jak zainwestować kapitał, żeby przyniósł jak największy zysk.

Przyjmuje się następujące założenia:

- efekt zastosowania każdego z programów inwestycyjnych nie zależy od tego czy zostały zastosowane równocześnie inne programy inwestycyjne

- zwrot nakładów inwestycyjnych jest mierzony w tych samych jednostkach.

1. Sterowanie zapasami – polega na minimalizacji kosztów produkcji i kosztów magazynowania w rachunku optymalizacyjnym należy uwzględnić koszty produkcji, wielkość produkcji, możliwości magazynowania oraz koszty magazynowania.

2. Zagadnienie plecaka – jak naładować plecak przedmiotami o najwyższej wartości uwzględniając jednocześnie jego pojemność.

3. Zagadnienie wymiany majątku trwałego – określenie optymalnego momentu wymiany maszyn i pojazdów uwzględniając eksploatację, koszty utrzymania w celu ustalenia momentu wymiany urządzenia wykorzystuje się dane dotyczące: wartości urządzenia, spadek wartości rynkowej urządzenia (upływ czasu), wzrost kosztu remontów.

Modele zapasów

Zapasy w przedsiębiorstwie

Minimalizacja łącznych kosztów gospodarowania zapasami.

Powody utrzymania zapasów:

1. Zmiany produkcji związane ze zmianami popytu wynikającymi z sezonowości.

2. Utrzymanie plynności procesu produkcji

3. Wyeliminowanie wahan losowych wynikających np. ze zwiększenia popytu.

Modele deterministyczne

Jaką ilość surowca wykorzystanego do produkcji należy kupić i w jakich terminach.

Koszty wynikające z zakupu surowca:

- cena surowca

- koszty wynikające z dokonania zamówienia

- koszty magazynowania

Celem jest ustalenie optymalnej wielkości dostawy surowca ze względu na minimalne koszty zakupu, zamówienia i magazynowania.

Modele probabilistyczne

Wyznaczamy optymalną wielkość zapasu surowca, który należy zgromadzić na początku danego okresu jeżeli zapotrzebowanie na ten surowiec podlega wahaniom losowym.

Założenie: Nie można w badanym okresie uzupełniać zakupionego na początku tego okresu surowca.

Model deterministyczny opisany wzorem Willsona

Założenie: Równomierne zużycie towaru.

$$K_{C} = K*\ \frac{D}{Q} + \ p*D + \ \frac{h*Q}{2}\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$$

K_C – koszt całkowity utrzymania zapasów

Q – wielkość partii zakupu

D – popyt w danym okresie

h –

Korzystając z rachunku różniczkowego i minimalizując koszty całkowite otrzymujemy wzory umożliwiające wyznaczenie optymalnej wielkości zamówienia, optymalnej liczby dostaw np. w ciągu roku.

$$Q^{*} = \ \sqrt{\frac{2\ K*D}{h}}\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }n^{*} = \ \frac{D}{Q^{*}}\text{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$$

Przykład:

Jednostkowa cena zakupu półproduktu wynosi 20 zł. Przedsiębiorstwo zużywa rocznie 10 000 szt. tego półproduktu. Koszt obsługi zamówienia wynosi 20 zł, koszty magazynowania jednej sztuki półproduktu wynoszą 10 zł.

$$Q^{*} = \ \sqrt{\frac{2\ *\ 20\ *\ 10\ 000}{10}\ } = 200\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$

$$h^{*} = \ \frac{10\ 000}{200} = 50\ \ \ \ \ \ \ \ \ \ \ \ \ \ t^{*} = \ \frac{360}{50} = 7,2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$

Egzamin 45 min 2 tury

definicje

pytania testowe

uzupełnienie zdań

zapis funkcji celu

warunki ograniczające

interpretacja pliku wynikowego z Excela

kawałek sieci do uzupełnienia

Wykład 7. 20.05.2014

Programowanie nieliniowe z ograniczeniami

Programowaniem nieliniowym nazywamy zadanie następującej postaci, jeżeli przynajmniej funkcja f lub h jest funkcją nieliniową.

f(x) min(lub max)

h_i (x) ≤ 0 i = 1,2,…, m (lub ≥ 0)

Problem optymalizacji bezwarunkowej - w przypadku, gdy nie występują ograniczenia.

Problem optymalizacji warunkowej – w przypadku, gdy ograniczenia występują.

Problem minimalizacji bezwarunkowej polega na wyznaczeniu minimum wartości funkcji dla danego problemu.

Kwestie wyznaczenia wartości maksymalnej lub minimalnej danej funkcji rozstrzyga twierdzenie Wetestrassa.

Rozwiązanie zagadnienia programowania nieliniowego polega na wyznaczeniu minimalnej lub maksymalnej wartości funkcji f w danym zbiorze danych.

W celu rozwiązania problemu programowania nieliniowego wyznaczamy rozwiązanie optymalne problemu równoważnego, który nie zawiera warunków ograniczających.

Problem rozwiązuje się tworząc funkcję Lagrange’a.

L(x, λ) = f(x) + $\sum_{i = 1}^{m_{2}}{\lambda_{i}h_{i}\left( x \right)}$

f(x) – funkcja celu

h_i(x) – warunki ograniczające

Warunkiem wystarczającym, na istnienie ekstremum (minimum) funkcji celu f(x) w punkcie stacjonarnym P jest, żeby wyznacznik macierzy zbudowanej z pochodnych cząstkowych drugiego rzędu był dodatni oraz wartość wszystkich minorów głównych danej macierzy w punkcie stacjonarnym były dodatnie.

$\left| \begin{matrix} f_{\text{xx}}^{"} & f_{\text{xy}}^{"} \\ f_{\text{yx}}^{"} & f_{\text{yy}}^{"} \\ \end{matrix} \right|\ $> 0 – max, funkcja wypukła

$\left| \begin{matrix} f_{\text{xx}}^{"} & f_{\text{xy}}^{"} \\ f_{\text{yx}}^{"} & f_{\text{yy}}^{"} \\ \end{matrix} \right|$ < 0 – min

minor mały wyznacznik np. $\left| \begin{matrix} x_{11} & x_{12} & x_{12} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \\ \end{matrix} \right|\text{\ minor\ tej\ macierzy\ to\ np.\ }\left| \begin{matrix} x_{22} & x_{23} \\ x_{32} & x_{33} \\ \end{matrix} \right|$

Jeśli wszystkie wyznaczniki (w tym mnory) II rzędu są dodatnie funkcja jest dodatnia.

Drzewa decyzyjne – są narzędziem wykorzystywanym do podejmowania decyzji w warunkach ryzyka. Decydent nie dysponuje pełną wiedzą w związku z rezultatem podejmowanych decyzji. Decydent nie jest w stanie przewidzieć następstw swoich decyzji w zależności od zaistnienia okoliczności. Znane są wartości prawdopodobieństw zaistnienia poszczególnych zdarzeń.

Drzewo decyzyjne jest formą grafu składającego się z węzłów (decyzji) oraz gałęzi.

kwadraty: warianty pozostające pod kontrolą decydenta, który ma możliwość swobodnego wyboru

koła: węzły losowe (decydent nie ma wpływu)

W celu podejmowania decyzji można wykorzystać elementy rachunku prawdopodobieństwa. W tym celu potrzebny jest rozkład prawdopodobieństwa zaistnienia danych zdarzeń. Muszą być znane wartości prawdopodobieństwa wystąpienia wariantu danej sytuacji. Oczekiwany koszt decyzji można wyznaczyć w sposób następujący:

$$\text{EC}\left( x_{j} \right) = \ \sum_{i = 1}^{n}R_{\text{ij}}p_{j}$$

W celu podejmowania decyzji można wykorzystać wartość oczekiwaną.

EC(x_j) – wartość oczekiwana

Drzewa decyzyjne mogą być wykorzystywane na przykład w celu podjęcia decyzji dotyczącej opłacalności wprowadzenia nowego produkty na rynku.

E(A) = 0,6 + 90 + … = koszt bierzemy mniejszy

E(B) = …… jeśli zysk to wybieramy większy

Teoria gier

Definicja gry: 1. Sytuacja konfliktowa.

2. Dowolnym jej uczestnikiem jest gracz.

3. Każda strona ma pewną strategię postępowania.

4. Wynikowi gry zwykle przyporządkowuje się pewną wartość liczbową.

Podstawowym założeniem gry jest zachowanie racjonalne.

Aby dana sytuacja mogła zostać nazwana grą, musi spełniać następujące warunki:

1. Istnieje skończona liczba uczestników.

2. Każdy uczestnik posiada skończoną liczbę sposobów działania (strategii).

3. Uczestnik, który chce posłużyć się teorią gier, musi znać wszystkie dostępne pozostałym graczom strategie, lecz nie może wiedzieć, która z nich będzie obrana.

4. Wygrana każdego uczestnika zależy zarówno od działania pozostałych graczy, jaki i od jego własnego działania.

5. Wszystkie możliwe wyniki są mierzalne.

W zależności od liczby tych przeciwników, ich interesów rozróżniamy rodzaje gier:

1. Gry dwuosobowe

2. Gry wieloosobowe

3. Gry koalicyjne

Gry dwuosobowe o sumie zero:

Grami dwuosobowymi o sumie zero, są takie sytuacje, gdy w grze biorą udział tylko dwie strony, a przegrana jednej ze stron jest wygrana drugiej.

Macierz wypłat

Punkty siodłowe – wybranie strategii bezpiecznej dla gracza 1 jak i 2, wybrać taką strategię aby jak najmniej stracić.

Strategia A dominuje strategię B jeżeli wartości są większe od B.

Punkt siodłowy – jeżeli jego wartość jest mniejsza lub równa każdej wartości w jego kolumnie.

Jeżeli gra posiada punkt siodłowy, to jego wartość jest wartości gdy gracze powinni wybrać te strategie, które zawierają ten punkt.

Metoda pozwalająca na określenie punktu siodłowego

1. Wyznaczamy najmniejszą wartość z każdego wiersza a następnie wyznaczamy największą wartość spośród nich.

2. Wyznaczamy największe wartości z każdej kolumny a następnie określamy najmniejszą spośród nich.

Dylemat więźnia (gra niekooperacyjna)

„wsypać kompana” jest strategią dominującą