Modele optymalizacyjne
Ekonometria/Zaoczne/Wykład 3
Dr I. Świeczewska
PROBLEM DECYZYJNY
}� Z problemem decyzyjnym mamy do czynienia gdy
zachodzą następujące okoliczności:
}� 1) istnieje decydent (osoba, lub grupa osób), który musi
rozwiązać określony problem;
}� 2) jest określony pewien cel, który ma być osiągnięty w
wyniku podjęcia określonej decyzji;
}� 3) istnieją co najmniej dwa sposoby, za pomocą których
można ten cel osiągnąć (przynajmniej dwa rozwiązania
tego problemu);
}� 4) istnieje otoczenie, które wpływa na sposób rozwiązania
problemu i jego wynik.
Rozwiązanie problemu decyzyjnego
}� Proces podejmowania decyzji polega na wyborze
przez decydenta takiego sposobu działania, który
spełnia wszystkie warunki problemu wyznaczone
przez środowisko, a jednocześnie prowadzi do
określonego celu.
}� Rozwiązanie problemu decyzyjnego, które wyznacza
najlepszy sposób działania nosi nazwę
ROZWI
ZANIA OPTYMALNEGO.
Dlaczego metody matematyczno-statystyczne są
często jedynym sposobem rozwiązywania problemów
decyzyjnych?
}� 1. Złożoność problemów decyzyjnych;
}� 2. Ogromna liczba możliwych do podjęcia decyzji
wyznaczonych przez środowisko (nieskończenie
liczny zbiór wszystkich możliwych w danych
warunkach decyzji dopuszczalnych);
}� 3. Zaufanie do metod matematycznych (!)
Przykłady zastosowań metod badań operacyjnych
}� 1) Wybór optymalnego asortymentu produkcji
(ustalenie struktury asortymentowej w
przedsiębiorstwie, która przy określonych
ograniczeniach zagwarantuje osiągniecie np.
maksymalnego zysku - zagadnienie z zakresu
planowania produkcji);
}� 2) Problem optymalnej diety (mieszanka pokarmowa
spełniająca pewne wymogi, co do zawartości
ważnych w odżywianiu składników, przy
jednocześnie najniższych kosztach zakupu
produktów stosowanych w diecie);
Przykłady zastosowań metod badań operacyjnych
}� 3) Problem optymalnego rozkroju;
}� 4)Ustalenie optymalnej struktury portfela
inwestycyjnego ;
}� 5) Ustalenie optymalnego harmonogramu dostaw
produktów między dostawcami i odbiorcami;
}� 6) Zarządzanie projektami;
}� 7) & & & & Itd. (można mnożyć w
nieskończoność!!!)
Model decyzyjny
Konstrukcja formalna (matematyczna), na podstawie
której możliwy jest wybór optymalnej (najlepszej!!!)
decyzji prowadzącej do spełnienia określonego celu
ze zbioru wszystkich możliwych (w określonych
warunkach) decyzji, czyli ze zbioru decyzji
dopuszczalnych.
Etapy budowy modelu decyzyjnego
}� 1. Analiza problemu decyzyjnego  poznanie
specyfiki analizowanego problemu decyzyjnego,
powiązań między poszczególnymi wielkościami czy
kategoriami, ustalenie listy ograniczeń oraz
określenie narzędzia oceny decyzji, zgromadzenie
niezbędnych danych;
}� 2. Ustalenie zmiennych decyzyjnych ;
}� 3. Określenie funkcji celu  zdefiniowanie i formalny
zapis funkcji celu wraz z określeniem rodzaju
ekstremum (optimum), którego poszukujemy;
}� 4. Sformułowanie warunków ograniczających za
pomocą odpowiednich równań lub nierówności;
}� 4 (Określenie warunków brzegowych).
ELEMENTY MODELU DECYZYJNEGO
x1
}� Zmienne decyzyjne  niewiadome , x2,K�, xn ,
których wartości należy ustalić; są one składowymi
x =� (x1, x2,K�, xn)
decyzji
;
}� Zbiór decyzji dopuszczalnych, czyli takich, które
są możliwe do podjęcia przy danych ograniczeniach;
zbiór decyzji dopuszczalnych określony jest przez
warunki ograniczające;
}� Funkcja celu  funkcja zmiennych decyzyjnych, za
pomocą której możliwa jest ocena każdej decyzji pod
względem stopnia realizacji określonego celu; przy
funkcji celu określa się także kierunek optymalizacji
(maksymalizacja, minimalizacja).
PROBLEM DECYZYJNY W FIRMIE KRZAK 
PRZYKA
AD
Firma KRZAK wytwarza dwa produkty A i B, których ceny zbytu wynoszą
odpowiednio 3 zł/szt. oraz 4 zł/szt. Należy opracować dzienny plan produkcji zakładu tak,
aby wartość produkcji liczona w cenach zbytu była możliwie największa. Produkcja jest
limitowana głównie przez dwa czynniki: dostępny czas pracy maszyn i surowiec
podstawowy. Dzienny limit czasu pracy maszyn wynosi 500 minut. Umowy z producentem
surowca podstawowego wskazują, że każdego dnia zakład będzie miał do dyspozycji 350 kg
tego surowca (bezpieczny poziom). Zakład jest zainteresowany takim programem dziennej
produkcji, przy którym osiągał będzie zysk minimum 600 zł. Sztuka wyrobu A wymaga 1
minuty czasu pracy maszyn, natomiast sztuka wyrobu B - 2 minut. Na wyprodukowanie
sztuki wyrobu A zużywa się 1 kg surowca specjalnego. Również sztuka wyrobu B wymaga 1
kg tego surowca. Jednostkowy zysk ze sztuki wyrobu A wynosi 2 zł/szt., a ze sztuki wyrobu
B  1 zł/szt.
MODEL DECYZYJNY DL PROBLEMU
DECYZYJNEGO W FIRMIE KRZAK
zmienne decyzyjne
x1 - dzienna produkcja wyrobu A [szt.]
x2 - dzienna produkcja wyrobu B [szt.]
funkcja celu (wartość produkcji w cenach zbytu)
w(x1,x2) = w(x) = 3x1 + 4x2 �� max [zł]
ograniczenia:
(maszyny) x1 + 2x2 Ł� 500 [minuta]
(surowiec) x1 + x2 Ł� 350 [kg]
(min. zysk) 2x1 + x2 ł� 600 [zł]
warunki brzegowe
x1 ł� 0 [szt.]
x2 ł� 0 [szt.]
CZYM JEST ZAGADNIENIE PROGRAMOWANIA
LINIOWEGO?
}� ZADANIE OPTYMALIZACYJNE ��ZADANIE
PROGRAMOWANIA MATEMATYCZNEGO
}� ZADANIE PROGRAMNOWANIA LINIOWEGO
(PL) SZCZEGÓLNY PRZYPADEK ZADAC
Z
ZAKRESU PROGRAMOWANIA
MATEMATYCZNEGO
}� ZADANIE PROGRAMOWANIA LINIOWEGO:
}� Wszystkie ograniczenia zapisane są w postaci równań lub
słabych nierówności (nierówności typu  d" ,  e" ) liniowych;
}� Funkcja celu jest funkcją liniową.
OGÓLNA POSTAĆ ZADANIA PL
f(x)=c1x1+c2x2+...+cnxn��max/min funkcja celu
a11x1 +� a12x2 +� K� +� a1n xn Ł� b1
��
��
K� K� K� K� K� K� K� K� K�
��
��a x1 +� ak2x2 +� K� +� akn xn =� bk
ograniczenia
�� k1
��
K� K� K� K� K� K� K� K� K�
��
��a x1 +� am2x2 +� K� +� amn x ł� bn
m1
��
x1e"0, x2e"0, ..., xne"0 warunki brzegowe
ROZWI
ZANIE ZADANIA PL
}� ZBIÓR ROZWI
ZAN DOPUSZCZALNYCH ZADANIA
PL JEST ALBO ZBIOREM PUSTYM ALBO ZBIOREM
DOMKNI
TYM I WYPUKA
YM O SKOC
CZONEJ
LICZBIE WIERZCHOA
KÓW
}� JEŚLI ZBIÓR ROZWI
ZAC
DOPUSZCZALNYCH JEST
ZBIOREM PUSTYM, TO ZADANIE PL NIE POSIADA
ROZWI
ZANIA  JEST SPRZECZNE;
}� JEŚLI ZBIÓR ROZWI
ZAC
DOPUSZCZALNYCH JEST
ZBIOREM NIEPUSTYM, TO FUNKCJA LINIOWA
OSI
GA SWOJ
WARTOŚĆ NAJWI
KSZ

(NAJMNIEJSZ
) W WIERZCHOA
KU TEGO ZBIORU
METODY ROZWI
ZYWANIA ZADAC
PL
}� METOD A GRAFICZNA  można ją zastosować do
rozwiązywania zadań PL z dwiema zmiennymi
decyzyjnymi;
}� METODA ALGEBRAICZNA  algorytm simpleks 
metoda uniwersalna, można ją stosować do
rozwiązywania zadań PL z dowolną liczbą
zmiennych decyzyjnych
GRAFICZNE ROZWI
ZANIE PROBLEMU
DECYZYJNEGO W FIRMIE KRZAK
GRAFICZNE ROZWI
ZANIE PROBLEMU
DECYZYJNEGO W FIRMIE KRZAK
}� Zbiór rozwiązań dopuszczalnych jest zbiorem
ograniczonym (istnieje kula o skończonym
promieniu, w której zawiera się ten zbiór),
domkniętym (wszystkie punkty brzegowe należą do
zbioru) i wypukłym (dowolne dwa punkty zbioru
można połączyć odcinkiem zawartym całkowicie w
tym zbiorze).
}� Na tym zbiorze funkcja liniowa osiąga wartość
największą/najmniejszą w wierzchołku tego zbioru;
}� Wierzchołkami zbioru rozwiązań dopuszczalnych są
punkty A=(300, 0); B=(250, 100); C=(350,0);
}� Wartośc funkcji celu w tych wierzchołkach jest równa:
f(300,0)=900; f(250,100)=1150; f(350,0)=1050
MAX
GRAFICZNE ROZWI
ZANIE PROBLEMU
DECYZYJNEGO W FIRMIE KRZAK
Raport wyników - Solver
Nazwa Wartość początkowa Wartość końcowa
funkcja celu 0 1150
Nazwa Wartość początkowa Wartość końcowa
x1 0 250
x2 0 100
Nazwa Wartość komórki formuła Status Luz
450 $B$24<=$D$24 Niewiążące 50
350 $B$25<=$D$25 Wiążące 0
600 $B$26>=$D$26 Wiążące 0
x2 100 $B$19>=0 Niewiążące 100
x1 250 $B$18>=0 Niewiążące 250
MOŻLIWE RODZAJE ROZWI
ZAC
ZADANIA PL
}� ROZWI
ZANIE JEDNOZNACZNE  tylko w jednym
wierzchołku zbioru rozwiązań dopuszczalnych funkcja
celu osiąga wartość najmniejszą /największą;
}� ROZWI
ZANIE NIEJEDNOZNACZNE  w więcej niż
jednym wierzchołku zbioru rozwiązań dopuszczalnych
funkcja celu osiąga wartość najmniejszą/największą;
}� BRAK SKOC
CZONEGO ROZWI
ZANIA
OPTYMALNEGO  taka sytuacja może mieć miejsce
jedynie w przypadku, gdy zbiór rozwiązań
dopuszczalnych jest zbiorem nieograniczonym;
}� ZADANIE SPRZECZNE  zbiór rozwiązań
dopuszczalnych jest zbiorem pustym.
GRAFICZNA ILUSTRACJA RÓŻNYCH RODZAJÓW
ROZWI
ZAC
ZADANIA PL  ROZWI
ZANIE
NIEJEDNOZNACZNE
x2
G
A
B
x1
GRAFICZNA ILUSTRACJA RÓŻNYCH
RODZAJÓW ROZWI
ZAC
ZADANIA PL  BRAK
SKOC
CZONEGO ROZWI
ZANIA OPTYMALNEGO
x2
G
x1
GRAFICZNA ILUSTRACJA RÓŻNYCH RODZAJÓW
ROZWI
ZAC
ZADANIA PL  ZADANIE SPRZECZNE
x2
x1
Analiza postoptymalizacyjna
Analiza postoptymalizacyjna, przeprowadzona po
rozwiązaniu modelu obejmuje:
1. Stopień wykorzystania poszczególnych limitów
składających się na ograniczenia modelu;
2. Badanie wrażliwości (stabilności) rozwiązania
optymalnego na zmiany poszczególnych
parametrów modelu  w jakim zakresie możliwa
jest zmiana poszczególnych parametrów modelu,
aby otrzymane rozwiązanie wciąż pozostało
rozwiązaniem optymalnym.
Analiza postoptymalizacyjna
}� Zmiany poszczególnych parametrów modelu
obejmują:
}� 1. zmiany we współczynnikach funkcji celu;
}� 2. zmiany wyrazów wolnych w poszczególnych
ograniczeniach;
}� 3. zmiany w liczbie warunków ograniczających
(dodanie lub usunięcie pewnych ograniczeń);
}� 4. zmiany w liczbie zmiennych decyzyjnych;
}� 5. zmiany wartości współczynników przy zmiennych
decyzyjnych w ograniczeniach modelu.
Analiza postoptymalizacyjna  zmiany
współczynników funkcji celu
W jakich granicach może się zmieniać wartość
xk
ck
współczynnika przy zmiennej , aby otrzymane
rozwiązanie optymalne nie uległo zmianie, przy
założeniu ceteris paribus.
Komórki decyzyjne
Wartość Przyrost Współczynnik Dopuszczalny Dopuszczalny
Nazw a końcow a krańcow y funkcji celu w zrost spadek
x1 250 0 3 1 1E+30
x2 100 0 4 1E+30 1
Zatem:
c1 ��(-�Ą�, 4
c2 �� 3,+�Ą�)
Analiza postoptymalizacyjna  zmiana wartości
wyrazu wolnego w warunku ograniczającym
}� W jakich granicach można zmieniać wartości
prawych stron ograniczeń modelu tak, aby struktura
rozwiązania optymalnego nie uległa zmianie.
}� Dla przykładu:
Warunki ograniczające
Wartość Cena Prawa strona Dopuszczalny Dopuszczalny
Komórka Nazwa końcowa dualna w. o. wzrost spadek
$B$24 450 0 500 1E+30 50
$B$25 350 5 350 16,66666667 50
$B$26 600 -1 600 100 50
Z powyższego wynika, że:
b1 �� 450,+�Ą�); b2 �� 300; 366,67 ; b3 �� 550; 700
Dziękuję za uwagę!