Literatura:

1. E. Ignasiak: „Badania operacyjne”

2. S. Krawczyk „Badania operacyjne dla menedżerów”

3. K. Kukuła: „Badania operacyjne w przykładach i zadaniach”

Wprowadzenie do problematyki badań operacyjnych 02-10-2003

• Badania operacyjne należą do grupy nauk o organizacji i zarządzaniu;

• Badania operacyjne to naukowa metoda rozwiązywania problemów z zakresu podejmowania decyzji kierowniczych;

• Badania operacyjne jest to dziedzina nauki zajmująca się analizą celowych działalności, generowaniem i oceną ilościową różnych decyzji kierowniczych, taktycznych lub strategicznych.

Przedmiotem badań operacyjnych są decyzje (głównie kierownicze) o różnym zasięgu oddziaływania, mające charakter strategiczny lub taktyczny (operacyjne - nie!)

Do metod badawczych procesu decyzyjnego należą przede wszystkim metody matematyczne, metody heurystyczne i metody symulacyjne.

Cechy charakterystyczne badań operacyjnych:

1. ukierunkowanie na podejmowanie decyzji;

2. podejście systemowe;

3. interdyscyplinarny charakter;

4. podejmowanie decyzji na podstawie modeli decyzyjnych analizowanych systemów;

5. konieczność stosowania metody nauk ścisłych;

6. konieczność stosowania techniki biurowej.

Podstawy analizy procesów decyzyjnych 30-10-2003

Problem - postrzegane odchylenie między tym, co w rzeczywistości jest lub może się stać przy naszej bierności a tym, co w danej sytuacji uznaje się za pożądane, przy czym w okresie postrzegania nie wiadomo jak zlikwidować to odchylenie lub je uniknąć.

Rodzaje problemów:

1. problemy innowacyjne - ujmują coś, czego nie ma a być powinno;

2. problemy modyfikacyjne - ujmują zjawiska, które występują, ale powinny przebiegać inaczej;

3. problemy likwidacyjne - ujmują zjawiska, które występują a występować nie powinny;

Problem ma charakter decyzyjny, jeżeli efektem jego analizy są co najmniej 2 propozycje, które mogą być uznane za rozwiązania i niezbędne jest rozstrzygnięcie, które z nich stanie się związaniem.

Cechą charakterystyczną problemu decyzyjnego jest to, że z samej jego treści nie wynika zasada rozstrzygania, którą z propozycji należy uznać za rozwiązanie. W celu dokonania wyboru trzeba określić reguły pomocnicze.

Analiza procesu decyzyjnego

Proces decyzyjny - obejmuje wszelkie działania, w wyniku których następuje podjęcie decyzji, czyli rozwiązanie jakiegoś problemu. Proces decyzyjny polega na opracowaniu i analizie pewnego zbioru wariantów oraz wyborze spośród nich najlepszego z przyjętego punktu widzenia.

Decyzja - akt wyboru jednego wariantu działania spośród wielu możliwych.

Elementy procesu decyzyjnego:

1. podmiot podejmowanych decyzji (decydent) - ten, który ustala reguły;

2. zbiór możliwych rozwiązań (wariantów decyzji);

3. funkcja decyzyjna (funkcja celu lub funkcja kryterium) - zasada wskazywania rozwiązania najlepszego spośród wielu możliwych;

4. informacje o stanach otoczenia,

5. inne elementy zależna od konkretnej sytuacji decyzyjnej.

Etapy procesu decyzyjnego:

1. Sformułowanie problemu i określenie celu decyzji.

2. Zebranie informacji niezbędnych do podjęcia decyzji.

3. Ustalenie możliwych wariantów decyzji.

4. Wybór optymalnego wariantu decyzji.

5. Sformułowanie decyzji i wprowadzenie jej w życie.

6. Kontrola wykonania decyzji (sygnalizacja różnic między planowanym a rzeczywistym stanem).

Podstawowe pojęcia

Warunki ograniczające - warunki określające, jakie decyzje mogą być podjęte (są to warunki nie zależne od decydenta).

Decyzje dopuszczalne - decyzje uwzględniające warunki ograniczające.

Pole decyzyjne - zbiór decyzji dopuszczalnych tzn. takich, co, do których nie ma podstaw do ich odrzucenia.

Funkcja decyzyjne - zasada wskazywania rozwiązania spośród alternatyw (wariantów decyzyjnych).

Decyzja optymalne - decyzja dopuszczalna realizująca postawiony cel w sposób możliwie najlepszy.

Rodzaje modeli decyzyjnych

Model decyzyjny - celowo uproszczony, matematyczny obraz rzeczywistego obiektu stworzony w celu wyboru optymalnej decyzji.

Kryteria klasyfikacji modeli decyzyjnych:

1. Czas lub liczba etapów procesu decyzyjnego:

• m. statyczne (jednoetapowe) - odzwierciedlają procesy ekonomiczne w ściśle określonej jednostce czasu,

• m. dynamiczne (wieloetapowe) - ukazują przebieg procesu gospodarczego w kolejnych jednostkach czasu w pewnym przedziale.

2. Liczba kryteriów realizujących cele pewnego obiektu gospodarczego:

• m. jednokryteriowe - występuje jedna funkcja celu,

• m. wielokryteriowe - występuje wiele funkcji celu.

3. Liczba podmiotów gospodarczych:

• m. niekonfliktowe - służą do rozwiązywania problemów, w których decyduje kierownictwo jednoosobowe,

• m. konfliktowe - powstają, gdy decyzje podejmuje kierownictwo wieloosobowe.

• Stopień określoności procesów gospodarczych:

• m. deterministyczne - nie uwzględniają odchyleń losowych,

• m. stochastyczne - uwzględniają wpływ odchyleń losowych.

• Charakter zależności zmiennych:

• m. liniowy - charakteryzuje badane zjawisko za pomocą równań lub nierówności liniowych,

• m. nieliniowe - przedstawiają zależności o charakterze krzywoliniowym.

• Postać zmiennych decyzyjnych:

• m. ciągłe - zmienna może przyjmować dowolne wartości z określonego przedziału liczbowego,

• m. dyskretne - zmienna może przyjmować wartości ze zbioru skończonego lub nieskończonego, ale przeliczalnego:

• m. dyskretne całkowitoliczbowe

• m. dyskretne binarne (zerojedynkowe)

• m. dyskretne mieszane

Do najczęściej stosowanych w praktyce modeli ekonomiczno-matematycznych należą:

• macierzowe modele bilansowe - związane z analizą przepływów międzygałęziowych; modele takie składają się z równań bilansowych, umożliwiają analizę powiązań między jednostkami gospodarczymi. Jednostki gospodarcze traktowane są jako dostawcy i odbiorcy.

• funkcje regresji (modele ekonometryczne);

• modele programowania liniowego;

• modele budowane w oparciu o matematyczną teorię gier.

Model programowania matematycznego

Matematyczny model decyzyjny to model programowania matematycznego:

• jest to zapis problemu decyzyjnego w języku matematycznym;

• pewna konstrukcja formalna opisująca pewne istotne cechy rzeczywistej sytuacji z możliwie dokładnym przybliżeniem.

Budowa matematycznego modelu decyzyjnego obejmuje:

1. Wyznaczenie zmiennych decyzyjnych.

2. Określenie parametrów.

3. Podanie funkcji celu.

4. Zapisanie warunków ograniczających.

W matematycznym modelu decyzyjnym występują dwa rodzaje wielkości ekonomicznych spełniające odmienną rolę w procesie podejmowania decyzji. Są to zmienne decyzyjne i parametry.

Zmienne decyzyjne - pewne wielkości, za pomocą których opisuje się decyzji. Wielkości te należy wyznaczyć korzystając z modelu. Zmienne decyzyjne oznaczamy: x₁, x₂,..., x_n, (niewiadome)

Parametry - wielkości niezależne od podmiotu decyzyjnego. Zakłada się, że wszystkie parametry są stałe i znane. Dlatego modele programowania liniowego są modelami deterministycznymi.

Model programowania matematycznego składa się z dwóch części:

1. Warunki ograniczające - to wartości określające, jakie decyzje mogą być podjęte.

Ogólny zapis: x₁, x₂,..., x_n є D

gdzie:

D - zbiór decyzji dopuszczalnych (może być zapisany za pomocą równań, nierówności i warunków logicznych)

W warunkach ograniczających występują wielkości dane zwane parametrami i wielkości, które należy ustalić, zwane zmiennymi decyzyjnymi.

2. Funkcja celu (funkcja kryterium) - jest to funkcja określona na zbiorze decyzji dopuszczalnych i opisująca stopień realizacji postawionego celu.

Ogólny zapis: f(x₁, x₂,..., x_n)

Wybór optymalnej decyzji polega na ustaleniu takiej decyzji dopuszczalnej, przy której funkcja celu osiąga wartość najkorzystniejszą tzn. w zależności od badanej sytuacji wartość minimalną lub maksymalną.

Zadanie decyzyjne można zapisać ogólnie:

f(x) → max, x є D f(x) → min, x є D

gdzie:

f - funkcja celu,

x - dowolna decyzja,

D - zbiór decyzji dopuszczalnych

Ze względu na postać analityczną funkcji celu oraz warunków ograniczających wyróżniamy:

1. modele liniowe

2. modele nieliniowe

Liniowy model programowania matematycznego lub liniowe zadanie decyzyjne (ZD) to zadanie decyzyjne, w którym wszystkie związki zachodzące między zmiennymi decyzyjnymi zarówno w funkcji celu jak i w warunkach ograniczających są funkcjami liniowymi.

Jeżeli wszystkie zmienne są ciągłe to jest to zadanie programowania liniowego (PL).

Zadanie programowania liniowego o postaci standardowej - jest to zadanie, w którym wszystkie ograniczenia są:

• nierównościami typu ≤ dla zadań na maksimum lub

• nierównościami typu ≥ dla zadań na minimum

oraz wszystkie zmienne muszą być nieujemne i ciągłe.

Zadanie programowania liniowego o postaci standardowej

Zadania na maksimum:




Zadania na minimum:




Parametry:

c_j - j-ta waga funkcji celu,

b_i - i-ty wyraz wolny,

a_ij - współczynnik macierzy ograniczeń stojący w i-tym wierszu i j-tej kolumnie.

Nierówność typu ≤ dla zadania na maksimum oraz nierówność typu ≥ dla zadania na minimum nazywamy nierównościami typowymi.

Wybrane zagadnienia programowania liniowego 06-11-2003

Wybór struktury asortymentowej produkcji

Należy wyznaczyć strukturę asortymentową produkcji czyli wielkość produkcji poszczególnych wyrobów tak, by przychody ze sprzedaży lub zysk ze sprzedaży były maksymalne.

Założenia podstawowe (muszą być spełnione):

1. Przedsiębiorstwo może produkować n wyrobów.

2. Do produkcji tych wyrobów potrzeba m rodzajów środków produkcji. Przedsiębiorstwo dysponuje ograniczonym zasobem każdego środka produkcji.

3. Znana jest norma zużycia każdego środka produkcji.

4. Znane są ceny sprzedaży lub zyski ze sprzedaży jednostki każdego wyrobu.

Założenie dodatkowe (mogą ale nie muszą występować):

1. Przedsiębiorstwo ma rozeznanie w zakresie możliwości zbytu swoich wyrobów. Wie, że może sprzedać najwyżej g_j jednostek i-tego wyrobu i musi sprzedać (ze względu na zawarte umowy) d_j jednostek j-tego wyrobu.

2. Określenie proporcje w jakich powinny być produkowane poszczególne wyroby:

Zmiennymi decyzyjnymi są w tym przypadku wielkości produkcji poszczególnych wyrobów:

(x₁, x₂,..., x_n), gdzie x_j - wielkość produkcji j-tego wyrobu.

Dane są parametry:

1. A - macierz o wymiarach m×n, której elementy a_ij oznaczają normy zużycia i-tego środka produkcji na jednostkę j-tego wyrobu.

A = [a_ij] _(m×n) i = 1,...,m (numer środka produkcja),

j = 1,...,n (numer wyrobu)

2. B - wektor, którego elementy b_i oznaczają dysponowaną wielkość i-tego środka produkcji.

B = [b_i] _(m×1) (wektor kolumnowy)

i = 1,...,m (numer środka produkcja)

3. C - wektor, którego współrzędne c_i oznaczają cenę jednostkową (lub zysk jednostkowy) j-tego wyrobu.

C = [c_i] _(1×n) j = 1,...,n (numer wyrobu)

Jeżeli występują dodatkowe założenia to:

4. d_j - dolna granica wielkości produkcji j-tego wyrobu;

g_j - górna granica wielkości produkcji j-tego wyrobu

5. p_j/p_k - proporcja w jakich powinny być produkowane wyroby j-ty i k-ty.

Najprostszy schemat wyboru struktury asortymentowej produkcji (bez uwzględniania dodatkowych założeń):




Schemat ten może być rozszerzony przy występowaniu dodatkowych założeń o następujące warunki:




Przykład:

Przedsiębiorstwo produkuje dwa wyroby A i B. Limit I-go środka produkcji wynosi 1000 jednostek a II-go - 840 jednostek. Normy zużycia środka przedstawia tabela. Zdolności produkcyjne jednego z wydziałów, stanowiącego wąskie gardło procesu produkcyjnego nie pozwalają produkować więcej niż 1000 sztuk wyrobu A i 1500 sztuk wyrobu B.

Wyrobu B należy wytwarzać dwa razy więcej niż wyrobu A (wyroby te stanowią komplet: 1 sztuka wyrobu A + 2 sztuki wyrobu B). Zysk osiągany na jednostce produkcji wynosi odpowiednio 2zł. i 3 zł.

Środki produkcji	Normy zużycia		Limit środków produkcji
		A		B
I	15	34	1000
II	15	20	840
zysk	2	3	X

Zaplanować strukturę asortymentową produkcji tak, aby przy przyjętych ograniczeniach zysk ze sprzedaży był największy.

Zbuduj model matematyczny opisujący przedstawioną sytuację:

1. Zmienne decyzyjne:

x₁ - wielkość produkcji wyrobu A

x₂ - wielkość produkcji wyrobu B

2. Parametry




A - normy zużycia

B - ograniczenia

C - ceny lub zyski




g₁=1000 - górna granica wyrobu A

g₂=1500 - górna granica wyrobu B

3. Funkcja celu:

2x₁+3x₂→max

4. Warunki ograniczające:

15x₁ + 34x₂ ≤ 1000

15x₁ + 20x₂ ≤ 840

0 ≤ x₁ ≤ 1000

0 ≤ x₂ ≤ 840




Zagadnienie diety lub dobór składu mieszanki

Należy ustalić taki plan żywienia, aby koszt diety był minimalny. Należy określić jakie ilości produktów żywnościowych należy kupić, aby przy pełnym zaspokojeniu potrzeb organizmu obniżyć do minimum koszty wyżywienia.

Podobne z formalnego punktu widzenia do zagadnienia diety jest ustalenie optymalnych zestawów różnych mieszanek. Chodzi o takie dobranie składników, aby otrzymana mieszanka posiadała pożądane własności, przy minimalnym koszcie.

Założenia:

1. W dyspozycji decydenta pozostaje n różnych produktów (żywnościowych).

2. Należy z tych produktów sporządzić dietę tak, by zawierała ona m składników odżywczych.

3. Znana jest zawartość każdego składnika w jednostce wagowej danego produktu.

4. Dane są niezbędne minimalne zawartości każdego składnika w diecie. W przypadku produktów żywnościowych (zagadnienia diety) te minimalne ilości składników nazywane są normami żywienia.

5. Znane są ceny każdego z n produktów.

Założenia dodatkowe:

1. Dla niektórych produktów ustalane są maksymalne ich ilości w diecie g_j. Mogą być również ustalone minimalne ilości spożycia produktów dj.

2. Określono proporcje w jakich produkty powinny występować w diecie.




3. W odniesieniu do niektórych składników, których nadmierne spożycie może być szkodliwe określono górne granice ich spożycia h_i (maksymalna ich ilość).

Zmiennymi decyzyjnymi są w tym przypadku ilości poszczególnych produktów w diecie (x₁, x₂,..., x_n).

x_j - ilość j-tego produktu w diecie

Dane są parametry

1. A - macierz o wymiarach m×n, której elementy a_ij oznaczają zawartość i-tego składnika w jednostce wagowej j-tego produktu.

A = [a_ij] _(m×n) i = 1,...,m (numer składnika),

j = 1,...,n (numer produktu)

2. B - wektor, którego elementy b_i oznaczają niezbędną minimalną zawartość i-tego składnika w diecie.

B = [b_i] _(m×1) (wektor kolumnowy)

i = 1,...,m (numer składnika)

3. C - wektor, którego współrzędne c_i oznaczają cenę jednostkową (lub zysk jednostkowy) j-tego produktu.

C = [c_i] _(1×n) j = 1,...,n (numer produktu)

Jeżeli występują dodatkowe założenia to:

4. d_j - minimalna ilość j-tego produktu;

g_j - maksymalna ilość j-tego produktu.

5. p_j/p_k - proporcja w jakich produkt j-ty i k-ty powinny występować w diecie.

6. h_i - maksymalna ilość i-tego składnika.

Najprostszy schemat wyboru struktury asortymentowej produkcji (bez uwzględniania dodatkowych założeń):




Schemat ten może być rozszerzony przy występowaniu dodatkowych założeń o następujące warunki:




Modyfikacji mogą ulec również warunki ograniczające występujące w schematach podstawowych.




Przykład:

Do karmienia zwierząt stosuje się dwa rodzaje pasz. Cena 1 kg paszy I-go rodzaju wynosi 4 zł., a paszy ii-go rodzaju 5 zł. Zawartości odżywcze pasz i dzienne normy zapotrzebowania przedstawia tabela:

Zawartość w 1 kg paszy	Rodzaj pasz		Dzienne normy zapotrzebowania
		I		II
Białko	6	2	20
Wapń	6	8	34
Witaminy	0	8	10
Cena	4	5	X

Ponadto paszy I-go rodzaju należy dostarczyć co najmniej 10 kg, natomiast witamin zwierzęta nie powinny otrzymywać więcej niż 50 jednostek dziennie.

Jaką ilość paszy każdego rodzaju należy stosować dziennie, aby koszty karmienia zwierząt były najniższe. Zbuduj model matematyczny opisujący przedstawioną sytuację.

1. Zmienne decyzyjne:

x₁ - ilość paszy I-go rodzaju

x₂ - ilość paszy II-go rodzaju

2. Parametry




d_I =10

h₃ =50

3. Funkcja celu:

4x₁+5x₂→min

4. Warunki ograniczające:

6x₁ + 2x₂ ≥ 20

6x₁ + 8x₂ ≥ 34

50 ≥ x₂ ≥ 10

x₁ ≥10

5. Warunki brzegowe:

x₁ ≥0

x₂ ≥ 0

Wybór procesu technologicznego - problem rozkroju

Należy określić skalę zastosowania możliwych sposobów rozkroju pozwalających na wykrojenie zamówionej liczby detali przy najmniejszych kosztach. Należy zatem zminimalizować odpady.

Założenia:

1. Z arkuszy materiału o znormalizowanych wymiarach (wszystkie arkusze mają te same wymiary) należy wykroić m różnych detali.

2. Istnieje możliwość wykrawania tych m detali z jednego arkusza materiału n różnymi sposobami.

3. Należy wykroić b_i detali i-tego rodzaju (i = 1,2,...,n)

4. Przy cięciu arkusza materiału j-tym sposobem (j = 1,2,...,m) otrzymujemy a_ij detali i-tego rodzaju (i = 1,2,...,n) i odpad materiału w ilości c_j jednostek (j = 1,2,...,m).

Zmiennymi decyzyjnymi są ilości arkuszy materiału cięte poszczególnymi sposobami (x₁, x₂,..., x_n).

x_j - liczba arkuszy materiału ciętych j-tym sposobem

Dane są parametry

1. A - macierz o wymiarach m×n, której elementy a_ij oznaczają liczbę detali i-tego typu otrzymywanych z jednego arkusza materiału przy cięciu go j-tym sposobem.

A = [a_ij] _(m×n) i = 1,...,m (numer typu detalu),

j = 1,...,n (numer sposobu cięcia materiału)

2. B - wektor, którego elementy b_i oznaczają liczbę zamówionych detali i-tego typu.

B = [b_i] _(m×1) (wektor kolumnowy)

i = 1,...,m (numer typu detalu)

3. C - wektor, którego współrzędne c_i oznaczają ilość odpadów otrzymywanych przy cięciu arkusza materiału j-tym sposobem.

C = [c_i] _(1×n) j = 1,...,n (numer sposobu cięcia metalu)

Schemat problemu rozkroju:




Trudność w rozwiązywaniu zadania rozkroju polega na tym, że macierz A określająca sposoby cięcia materiału i odpady należy obliczyć na podstawie informacji o wymiarach arkusza materiału i zamówionych detali.

Przykład:

Huta otrzymała zamówienie na dostarczenie 300 prętów metalowych długości 0,5 m i 200 prętów długości 2,1 m. Huta dysponuje odpowiednim materiałem ale o długości 4,3 m.

W jaki sposób huta powinna zrealizować zamówienie, aby zminimalizować odpady? Należy sformułować model matematyczny opisujący przedstawioną sytuację decyzyjną.

Rodzaj detalu (długość)	Sposób rozkroju			Wielkość zamówienia
		I	II		III
0,5	0	4	8	300
2,1	2	1	0	200
Odpady	0,1	0,2	0,3	X

Odpad to taka część materiału, z której nie da się wyciąć najmniejszego detalu.

Zmienne decyzyjne:

x₁ - liczba prętów (o długości 4,3 m) ciętych sposobem I

x₂ - liczba prętów (o długości 4,3 m) ciętych sposobem II

x₃ - liczba prętów (o długości 4,3 m) ciętych sposobem III

Parametry:




Funkcja celu:

0,1x₁ + 0,2x₂ + 0,3x₃ →min

Warunki ograniczające:

4x₂ + 8x₃ →min

2x₁ + x₂→min

x₁ ≥ 0

x₂ ≥ 0

x₃ ≥ 0

x₁, x₂, x₃ ∈C

Metoda Simplex 13-11-2003

Jest to uniwersalna metoda stosowana do rozwiązywania zadań programowania liniowego.

Algorytm metody simplex ma charakter iteracyjny czyli etapowy, a wyniki poszczególnych iteracji przedstawia się w tablicach zwanych tablicami simplexowymi.

Etapy metody simplex:

Etap wstępny

• Budowa modelu matematycznego zadania programowania liniowego.

• Sprowadzenie zadania programowania liniowego do postaci kanonicznej.

Etap I

• Wybór wyjściowego rozwiązania bazowego i ocena jego optymalności:

Krok 1

Przyjęcie wyjściowego bazowego rozwiązania dopuszczalnego.

Krok 2

Budowa tablicy simplexowej.

Krok 3

Sprawdzanie optymalności przyjętego rozwiązania bazowego:

• jeżeli rozwiązanie jest optymalne to postępowania zostaje zakończone,

• jeżeli rozwiązanie nie jest optymalne to przechodzimy do etapu II.

Etap II

• Wyznaczenie kolejnego poprawionego rozwiązania bazowego.

Krok 1

Ustalenie zmiennej, którą wprowadzamy do rozwiązania.

Krok 2

Ustalenie zmiennej, którą należy usunąć z rozwiązania.

Krok 3

Wyznaczenie wartości zmiennych poprawionego rozwiązania bazowego oraz odpowiadającej mu tablicy simplexowej.

Etap III

• Dla rozwiązania w etapie II powtarzamy postępowanie od kroku 3 etapu I, czyli sprawdzamy optymalność przyjętego równania bazowego.

Postać kanoniczna zadania programowania liniowego

Postać tę otrzymujemy z postaci standardowej modelu poprzez sprowadzenie nierówności z warunków ograniczających do równości.

Dla zadania na maksimum, gdy warunki ograniczające mają postać <= (mniejsze, równe) dokonuje się tego wprowadzając tzw. zmienną swobodną do każdej nierówności. Zmienna swobodna równoważy lewą stronę każdego warunku ograniczającego z jego prawą stronę.

Zmienne swobodne wchodzą do funkcji celu z tzw. wagami zerowymi.

Przykład 1 20-11-2003

Postać standardowa

Funkcja celu: Warunki ograniczające: Warunki brzegowe:

3x₁ + 2x₂ → max x₁ + x₂ <= 6 x₁, x₂ >= 0

3x₁ <= 12

Postać kanoniczna

Funkcja celu: Warunki ograniczające: Warunki brzegowe:

3x₁ + 2x₂ + 0x₃ + 0x₄ → max x₁ + x₂ + x₃ = 6 x₁, x₂, x₃, x₄ >= 0

3x₁ + x₄ = 12

x₃, x₄ - zmienne swobodne

TABLICA SIMPLEX

	CJ	3			2			0	0
Ci	xB	x1			x2			x3	x4	bi	bi/ti k
0 0	x3 x4		1 3		1 0			1 0	0 1	6 12	6/1 = 6 12/3 = 4
	Zj Cj - Zj	0 131			0 2			0 0	0 0	Fc = 0
0 3	x3 x1	0 1				1 0		1 0	-1/3 1/3	2 4	2/1 = 2 -
	Zj Cj - Zj	3 0			0 121			0 0	1 -1	Fc = 12
2 3	x2 x1	0 1			1 0			1 0	-1/3 1/3	2 4
	Zj Cj - Zj	3 0			2 0			2 -2	1/3 -1/3	Fc = 16

k-ta kolumna - kolumna wyróżniona

r-ty wiersz - wiersz nowej zmiennej bazowej

C_j - Z_j - kryterium simplexowe (wskaźnik optymalności)

b_i/t_{i k} - nie dzielimy gdy t_{i k} <= 0

I tablica simplex - do nowej bazy ma wejść zmienna x₁ zamiast x₄.

Jeżeli macierz zmiennych bazowych (w odpowiedniej kolejności) jest macierzą zero-jedynkową to tablica simplexowa jest poprawna.

Dla zadania na minimium, gdy warunki ograniczające mają postać >= (większe, równe) stosuje się zmodyfikowaną postać metody simplex z tzw. sztuczną bazą.

Od lewej strony warunku ograniczającego odejmujemy tzw. zmienną swobodną i dodajemy zmienną sztuczną ze współczynnikami równymi 1. Nierówności zastępujemy równościami.

Do funkcji celu zmienne swobodne wchodzą ze współczynnikami równymi 0 a zmienne z tzw. współczynnikami M, gdzie M jest bardzo dużą liczbą dodatnią.

Przykład 2: 27-11-2003

Postać standardowa

Funkcja celu: Warunki ograniczające: Warunki brzegowe:

2x₁ + 4x₂ → min x₁ + 3x₂ >= 9 x₁, x₂ >= 0

x₁ >= 3

Postać kanoniczna

Funkcja celu: Warunki ograniczające: Warunki brzegowe:

3x₁ + 2x₂ + 0x₃ + 0x₄ + MS₁+ MS₂ → max x₁ + 3x₂ - x₃ + S₁ = 6 x₁, x₂, x₃, x₄ >= 0

x₁ - x₄ + S₂ = 12

x₃, x₄ - zmienne swobodne

S₁, S₂ - zmienne sztuczne

CJ

2

4

0

0

M

M

Ci

xB

x1

x2

x3

x4

S1

S2

bi

bi/ti k

0 0

S1 S2

1 1

131 0

-1 0

0 -1

1 0

0 1

9 3

9/3 = 3 -

Zj Cj - Zj

2M 2-2M

3M 4 -3M

-M M

-M M

M 0

M 0

Fc = 12M

0 3

x2 S2

1/3 111

1 0

-1/3 0

0 -1

1/3 0

0 1

3 3

9 3

Zj Cj - Zj

4/3 + M 2/3 - M

4 0

-4/3 4/3

-M M

4/3 M-4/3

M 0

Fc = 12 + 3M

2 3

x2 x1

0 1

1 0

-1/3 0

1/3 -1

1/3 0

-1/3 1

2 3

Zj Cj - Zj

2 0

4 0

-4/3 4/3

-2/3 2/3

4/3 M-4/3

2/3 M-2/3

Fc = 14

Jest to jedyne rozwiązanie bazowe:

x₂ = 2

x₁ = 3

Fc = 14

x₃, x₄, S₁, S₂ = 0

Rozwiązanie modelu jest zdegenerowane jeżeli przynajmniej jedna zmienna bazowa jest równa 0. Mogą wówczas wystąpić ciągi stale powtarzających się rozwiązań tzw. cykle. W kolejnych tablicach powtarzają się rozwiązania (wartości funkcji celu).

Analiza wrażliwości

Po rozwiązaniu zadania PL należy przeprowadzić analizę wrażliwości. Umożliwia ona ocenę stopnia wrażliwości uzyskanego rozwiązania optymalnego na zmianę wybranych parametrów modelu:

1. współczynników funkcji celu,

2. wyrazów wolnych w warunkach ograniczających.

Analiza wrażliwości rozwiązania optymalnego na zmiany współczynników funkcji celu.

Umożliwia ustalenie w jakich granicach mogą się zmienić wagi funkcji celu aby dotychczasowe rozwiązanie pozostało optymalne (nie zmieniają się optymalne wartości zmiennych decyzyjnych, zmieni się jednak - wzrośnie lub zmaleje - wartość funkcji celu).

Należy określić dopuszczalny wzrost lub spadek wagi funkcji celu tzn. taki, przy którym nie zmieni się rozwiązanie optymalne.

Dopuszczalny wzrost i dopuszczalny spadek funkcji celu określają tzw. zakresy stabilności decyzji optymalnej.

Zakładamy, że waga funkcji celu stojąca przy zmiennej x₁, (cena jednostkowa sprzedaży wyrobu I) zmieni się w następujący sposób:

c₁' = c₁ + δ₁

Przykład 1 - ostatnia tablica simplexowa (zmodyfikowana).

	CJ	3 + δ1	2	0	0
Ci	xB	x1	x2	x3	x4	bi	bi/ti k
2 3	x2 x1	0 1	1 0	1 0	-1/3 1/3	2 4
	Zj Cj - Zj	3 0	2 0	2 -2	1/3 + 1/3δ1 -1/3 - 1/3δ1	Fc = 16 + 4δ1

W zadaniu na maksimum wszystkie kryteria simplexowe dla rozwiązania optymalnego powinny być niedodatnie stąd:

-1/3 - 1/3δ₁ <= 0

a zatem:

δ₁ >= -1

δ₁ ∈ < -1; +∞)

a c₁ ∈ < 3 -1; 3 +∞)

tj.: c₁ ∈ <2; +∞)

Oznacza to, że rozwiązanie optymalne nie ulegnie zmianie jeżeli cena wyrobu pierwszego będzie przyjmowała wartość z przedziału <2; +∞).

Nie zmienią się tylko optymalne wartości x₁ i x₂, natomiast zmieni się (zmniejszy lub zwiększy) wartość funkcji celu o x₁δ₁.

W przypadku wzrostu ceny c₁ o np. 10 jednostek (w granicach dopuszczalnego wzrostu - w tym przypadku jest on nieograniczony ) wartość funkcji celu wzrośnie o:

x₁δ₁ = 10*4 = 40 i wyniesie 16 + 40 = 56 przy założeniu, że cena wyrobu drugiego nie ulegnie zmianie.

W przypadku spadku ceny c1 o 1 (w granicach dopuszczalnego spadku) wartość funkcji zmieni się o :

x₁δ₁ = -1*4 = -4 i wyniesie 16 - 4 = 12 przy założeniu, że cena wyrobu drugiego nie ulegnie zmianie.

Jeżeli warunki rynkowe umożliwiają zmianę zarówno ceny c1 jak i c2 wartość funkcji celu zmieni się o:

x₁δ₁ + x₂δ₂

Dla problemu rozkroju analiza wrażliwości rozwiązania optymalnego na zmiany współczynników funkcji celu nie ma sensu, ponieważ wagi funkcji celu oznaczają ilości odpadów jakie pozostają po zastosowaniu określonych sposobów cięcia, a zatem nie można mówić o dopuszczalnym wzroście lub spadku poszczególnych odpadów. Odpad dla danego sposobu rozkroju jest dokładnie taki jak ustalono i nie może ulec zmianie.

Analiza wrażliwości rozwiązania optymalnego na zmiany wyrazów wolnych warunków ograniczających.

Analiza wrażliwości umożliwia również określenie w jakich granicach mogą zmieniać się wyrazy wolne warunków ograniczających, aby w rozwiązaniu optymalnym pozostały te same zmienne bazowe.

Jeżeli wyrazy wolne będą się zmieniać w dopuszczalnych granicach to:

• zmienne bazowe nie ulegną zmianie,

• natomiast mogą się zmieniać optymalne wartości zmiennych decyzyjnych (aby je obliczyć należy ponownie obliczyć ZPL, zmieniając wartości wyrazów wolnych),

• zmieni się wartość funkcji celu - nową wartość funkcji celu można wyznaczyć wykorzystując do jej ustalenia interpretację zmiennych dualnych (jeżeli zmienne dualne będą równe 0 wartość funkcji celu nie zmieni się).

Badanie wrażliwości rozwiązania optymalnego na zmiany wyrazów wolnych warunków ograniczających polega na ustaleniu ich dolnej i górnej granicy zmian. Zmianę wyrazu wolnego i-tego warunku ograniczającego można zapisać jako:

b_i' = b_i + ε_i

gdzie:

ε_i - jest dopuszczalną zmianą i-tego wyrazu wolnego nie powodującą zmiany bazy optymalnej.

Wartość ε_i wyznaczana jest osobno dla każdego warunku ograniczającego.

Wartość ε_i wyznacza się przy uwzględnieniu warunku nieujemności zmiennych bazowych, a zatem:

x_b = B^-1b >= 0

Po zastąpieniu b₁ wyrażeniem b₁ + ε₁ nowy wektor wyrazów wolnych analizowanego zadania (b_i') będzie miał postać:




Macierz B (macierz współczynników ograniczeń dla zmiennych bazowych z ostatniej tablicy simplexowej) i macierz odwrotną do niej przedstawiono poniżej:




a zatem ε_i >= -2

czyli ε_i ∈ <-2; +∞)

stąd b₁∈ <6-2; 6+∞) tj: b₁∈ <4; +∞)

Jeżeli wyraz wolny pierwszego warunku ograniczającego b₁ będzie przyjmował wartość z przedziału <4; +∞) to w rozwiązaniu optymalnym pozostaną zmienne bazowe x₁, x₂, natomiast przy założeniu, że wyraz wolny b₁ wzrośnie o ε₁ = 3, optymalne wartości zmiennych decyzyjnych wyniosą:

x₁ = 4 oraz x₂ = 2 + 3 = 5

a funkcja celu będzie równa Fc = 3*4 +2*5 = 22

W analizie wrażliwości wykorzystuje się interpretację zmiennych dualnych, które często określa się jako ceny dualne.

Wartość zmiennej dualnej pozwala określić czy, z punktu widzenia przyjętej funkcji celu, powiększenie lub zmniejszenie wyrazów wolnych warunków ograniczających jest opłacalne czy nie i w jakim stopniu.

Wartość zmiennej dualnej określa o ile zmieni się wartość funkcji celu zadania pierwotnego, jeżeli o jednostkę wzrośnie wyraz wolny warunku zadania pierwotnego związanego z tą zmienną dualną.

Etapy podejmowania decyzji na podstawie matematycznego modelu decyzyjnego:

1. Powstanie sytuacji decyzyjnej i konieczność wykorzystania do podjęcia decyzji optymalnej metod optymalnych.

2. Budowa matematycznego modelu decyzyjnego.

3. Wyznaczenie rozwiązania matematycznego modelu decyzyjnego. jest to wskazanie decyzji optymalnej.

Procedura rozwiązywania liniowych modeli decyzyjnych obejmuje2 etapy:

1. Wyznaczanie zbioru rozwiązań dopuszczalnych.

2. Znalezienie rozwiązania optymalnego.

Definicja 1

Rozwiązaniem dopuszczalnym programu liniowego nazywamy każdy punkt X = [x₁, x₂,..., x_n] spełniający warunki ograniczające. Zbiór wszystkich punktów spełniających ograniczenia tworzy zbiór rozwiązań dopuszczalnych (ZRD).

Definicja 2

Rozwiązaniem optymalnym programu liniowego nazywamy taki punk ze zbioru rozwiązań dopuszczalnych, w którym funkcja celu osiąga wartość ekstremalną tj. maksymalną lub minimalną w zależności od rozpatrywanej sytuacji decyzyjnej.

Twierdzenie 1

Zbiór rozwiązań dopuszczalnych programu liniowego jest zbiorem wypukłym. Jeżeli występują dwie zmienne decyzyjne to jest to wielobok wypukły.

Twierdzenie 2

Jeżeli rozwiązanie optymalne istnieje to znajduje się ono w wierzchołku zbioru rozwiązań dopuszczalnych.

Twierdzenie 3

Jeżeli rozwiązaniem optymalnym programu liniowego są dwa wierzchołki wieloboku rozwiązań dopuszczalnych to również punkty znajdujące się na odcinku łączącym te wierzchołki stanowią zbiór rozwiązań optymalnych.

Można wyodrębnić trzy typy rozwiązań:

1. Istnieje tylko jedno rozwiązanie optymalne. Wówczas optymalna wartość funkcji celu jest liczbą skończoną i odpowiada tylko jednemu zestawowi wartości zmiennych decyzyjnych.

2. Istnieje wiele rozwiązań dopuszczalnych . Wówczas optymalna wartość odpowiada wielu zestawom wartości zmiennych decyzyjnych.

3. Rozwiązanie optymalne nie istnieje. Ma to miejsce wówczas gdy zbiór rozwiązań dopuszczalnych jest zbiorem pustym co oznacza, że układ warunków ograniczających jest sprzeczny lub rozwiązań dopuszczalnych jest zbiorem nieograniczonym w kierunku wzrostu wartości funkcji celu dla zadania na maksimum bądź spadku funkcji celu dla zadania na minimum.

Metoda geometryczna

Może być stosowana przede wszystkim dla modelu z dwiema zmiennymi decyzyjnymi. W przypadku większej liczby zmiennych przy dwóch warunkach ograniczających zadanie PL można rozwiązać metodą geometryczną po uprzednim przejściu do tzw. problemu dualnego.

Etapy metody geometrycznej:

• wyznaczenie półpłaszczyzn odpowiadających poszczególnym warunkom ograniczającym,

• znalezienie części wspólnej dla wszystkich półpłaszczyzn (jest to zbiór rozwiązań dopuszczalnych)

• wyszukanie w ZRD rozwiązania najlepszego dla przyjętej funkcji celu.

Wartość ekstremalną funkcji celu można wyznaczyć dwoma sposobami:

• Wyznaczając wartość tej funkcji w punktach wierzchołkowych ZRD,

• Konstruując tzw. linię stałej wartości funkcji celu zwaną izokwantą lub linia warstwicową funkcji celu. Należy narysować izokwantę przyjmując dowolną wartość funkcji celu. Wszystkie izokwanty są równoległe. Im izokwanta jest bardziej oddalona od początku układu współrzędnych, tym większym wartościom funkcji celu odpowiada. Należy przesuwać izokwantę równolegle tak aby nie stracić punktu styczności z obszarem rozwiązań dopuszczalnych.

Badania operacyjne - wykłady

16

element

centralny

kolumna

wyróżniona

---