04.pdf

(142 KB) Pobierz
Badania operacyjne
dr inż. W. Zalewski
Badania operacyjne
dr inż. W. Zalewski
Zagadnienie optymalnego przydziału
OPTYMALIZACJA DYSKRETNA
Na wydziale produkcyjnym jest n maszyn i n obsługujących je
pracowników. Znana jest wydajność w ij każdego pracownika na każdej
maszynie (tablica 1).
Zagadnienie decyzyjne, w którym chociaż jedna zmienna decyzyjna
przyjmuje wartości dyskretne, nazywamy dyskretnym zagadnieniem
decyzyjnym.
w ij
R 1
R 2
R j
R n
śród zadań
dyskretnego programowania liniowego można
M 1
w 11
w 12
w 1j
w 1n
wyróżnić trzy grupy:
É zadania programowania liniowego całkowitoliczbowego – wszystkie
zmienne są liczbami całkowitymi;
É zadania programowania liniowego binarnego – wszystkie zmienne są
liczbami binarnymi {0, 1};
É zadania programowania liniowego mieszanego – część zmiennych
jest ciągła, część zmiennych to liczby całkowite lub binarne.
M 2
w 21
w 22
w 2j
w 2n
M i
w i1
w i2
w ij
w in
M n
w n1
w n2
w nj
w nn
Należy ustalić taki przydział robotników do poszczególnych maszyn,
aby łączna wydajność całego zespołu była maksymalna.
Model matematyczny
Zmienne decyzyjne:
x 2
1
jeżeli j-ty pracownik został przydzielony do i-tej maszyny,
w przypadku przeciwnym
x ij
0
Funkcja celu:
x 0
n
n
∑ ∑ =
w
x
max
ij
ij
i
1
j
1
f(x)→max
Warunki:
n
∑ =
x
1
(i = 1, 2, ..., n)
ij
j
1
n
∑ =
x
1
(j = 1, 2, ..., n)
ij
x 1
i
1
1
x ij
(i = 1, 2, ..., n; j = 1, 2, ..., n)
0
31
32
HACKED BY VIPER :)
960340087.040.png 960340087.041.png 960340087.042.png 960340087.043.png 960340087.001.png 960340087.002.png 960340087.003.png 960340087.004.png 960340087.005.png 960340087.006.png 960340087.007.png 960340087.008.png 960340087.009.png 960340087.010.png 960340087.011.png 960340087.012.png 960340087.013.png 960340087.014.png 960340087.015.png 960340087.016.png 960340087.017.png 960340087.018.png 960340087.019.png 960340087.020.png 960340087.021.png 960340087.022.png 960340087.023.png 960340087.024.png 960340087.025.png 960340087.026.png
Badania operacyjne
dr inż. W. Zalewski
Badania operacyjne
dr inż. W. Zalewski
Metoda podziału i ograniczeń
Podzbiory, które uległy podziałowi, nazywamy podzbiorami biernymi.
Podzbiory, które nie zostały jeszcze podzielone, nazywamy
podzbiorami aktywnymi . Dzielimy je na:
É podzbiory otwarte, które mogą ulec podziałowi,
É podzbiory zamknięte, które nie ulegają podziałowi.
Zadanie:
Należy znaleźć takie rozwiązanie x*, aby:
*
D,
f(x*) = max {f(x)
x
D}
lub
Funkcja ograniczająca
Funkcję w określoną na rodzinie 2 D podzbiorów zbioru D nazywamy
funkcją ograniczającą , jeżeli spełnia ona następujące warunki:
*
D,
f(x*) = min {f(x)
x
D}
Jeżeli zbiór rozwiązań dopuszczalnych jest niewielki, to najprościej
jest zastosować przegląd zupełny tego zbioru, czyli:
É wygenerować wszystkie jego elementy (rozwiązania),
É ustalić wartość funkcji celu f(x) dla każdego rozwiązania,
É wybrać rozwiązanie optymalne.
dla zadania na max
dla zadania na min
É x
D 1
D
f(x)
w (D 1 ),
f(x)
w (D 1 ),
É D 2
D 1
D
w (D 2 )
w (D 1 ),
w (D 2 )
w (D 1 ),
É D 1 = {x}
D
w (D 1 ) = f(x),
w (D 1 ) = f(x),
Wartości, jakie przyjmuje funkcja ograniczająca w dla poszczególnych
podzbiorów zbioru D, nazywamy ich kresami górnymi (dolnymi).
Podział zbioru D
Zbiór D dzielimy na mniejsze podzbiory, dla których liczymy:
É kres górny w zadaniu na maksimum (oszacowanie z góry wartości
funkcji celu dla rozwiązań należących do danego podzbioru);
É kres dolny w zadaniu na minimum (oszacowanie z dołu wartości
funkcji celu dla rozwiązań należących do danego podzbioru);
Warunek pierwszy oznacza, że kres górny zbioru D 1 nie może być
mniejszy od maksymalnej wartości funkcji celu dla rozwiązań należących
do tego podzbioru.
Warunek drugi określa kres górny zbioru D 2 , będącego podzbiorem
zbioru D 1 , który nie może być większy od kresu górnego zbioru D 1 .
Warunek trzeci oznacza, że jeżeli zbiór D 1 jest zbiorem
jednoelementowym, to kres górny tego zbioru musi być równy wartości
funkcji celu dla tego elementu.
Następnie wybieramy podzbiór perspektywiczny o maksymalnym
(minimalnym) kresie górnym (dolnym) oraz dokonujemy jego podziału,
jeżeli jest to możliwe i celowe.
33
34
HACKED BY VIPER :)
960340087.027.png 960340087.028.png
Badania operacyjne
dr inż. W. Zalewski
Badania operacyjne
dr inż. W. Zalewski
Wybór podzbioru perspektywicznego
Niech G r będzie zbiorem wszystkich podzbiorów aktywnych w r -tym
kroku obliczeń. Zbiorem perspektywicznym w r -tym kroku jest taki zbiór
D p , dla którego:
Zadanie programowania liniowego całkowitoliczbowego (PLC)
cx
max
Ax
b
x – wektor całkowitoliczbowy
Rozwiązujemy to zadanie pomijając warunek całkowitoliczbowości.
Jeżeli nie istnieje rozwiązanie optymalne to nie ma go również PLC. Jeżeli
rozwiązanie optymalne nie jest całkowitoliczbowe, to stosujemy metodę
podziału i ograniczeń.
Oznaczmy przez:
w(D p ) = max {w(D l )
D l
G r } dla zadań na maksimum,
w(D p ) = min {w(D l )
D l
G r } dla zadań na minimum.
Jeżeli znajdziemy taki podzbiór D k i związane z nim rozwiązanie x k , że
w(D k ) = f(x k ),
to zbiór D k zamykamy, gdyż nie zawiera on lepszego rozwiązania od x k ,
a element x k nazywamy rozwiązaniem lokalnie najlepszym.
Proces podziału zbioru D kontynuujemy do momentu,
gdy znajdziemy podzbiór perspektywiczny zamknięty . Wynika to
z następującego twierdzenia:
k
D k
PL –
zbiór rozwiązań dopuszczalnych zadania PL,
D
–
zbiór rozwiązań dopuszczalnych zadania PLC,
0 – wartość funkcji celu dla rozwiązania optymalnego zadania PL,
N(x 0 ) –
największą liczbę całkowitą nie większą od x 0 ,
D PL = { x
Ax
b , x
0 },
D = { x
x
D PL , x – wektor całkowitoliczbowy}
Twierdzenie
Jeżeli podzbiorem perspektywicznym jest podzbiór zamknięty D p
z elementem najlepszym x*, to x* jest optymalnym rozwiązaniem zadania.
Optymalność rozwiązania x* dla zadania (na maksimum) wynika
z następujących zależności:
D
D PL ,
max { cx
x
D}
x 0 = max { cx
x
D PL }.
Dla każdego podzbioru D l kres górny ustalamy zgodnie ze wzorem:
l
0
jeżeli wektor wag c nie jest całkowitoliczbowy
x
w
D
l
N
x
l
0
jeżeli wektor wag c jest całkowitoliczbowy
f(x*) = w(D p ) = max{w(D l )
D 1
G r }
Zbiór D l zamykamy, jeżeli:
É rozwiązanie optymalne zadania PL l jest całkowitoliczbowe – wtedy
w(D l ) = cx l ,
É zbiór rozwiązań dopuszczalnych D PL zadania PL l jest pusty – wtedy
ponadto:
f(x*)
max{f(x)
x
D l },
tym samym:
D},
czyli x* jest rozwiązaniem optymalnym.
f(x*)
max{f(x)
x
umownie przyjmujemy, że w(D l ) = -
35
36
HACKED BY VIPER :)
960340087.029.png 960340087.030.png
Badania operacyjne
dr inż. W. Zalewski
Badania operacyjne
dr inż. W. Zalewski
Zadanie nieliniowe o postaci standardowej
OPTYMALIZACJA NIELINIOWA
Wszystkie ograniczenia w postaci równości.
Zagadnienie decyzyjne, w którym chociaż jeden z warunków
ograniczających lub funkcja celu jest funkcją nieliniową, nazywamy
nieliniowym zagadnieniem decyzyjnym.
Metoda mnożników Lagrange’a.
Należy sprawdzić, czy funkcja celu f( x ) ma ekstremum
bezwarunkowe i czy spełnia ono warunki ograniczające. Warunkiem
wystarczającym na istnienie minimum funkcji f( x ) w punkcie x = (x 1 , x 2 ,
..., x n ) jest to, aby wyznacznik macierzy utworzonej z pochodnych
cząstkowych drugiego rzędu funkcji f w tym punkcie był dodatni, oraz aby
wartości wszystkich minorów głównych tej macierzy (w punktach
stacjonarnych) były dodatnie.
Ogół metod optymalizacji nieliniowej można podzielić na
następujące grupy:
É metody linearyzacji (sprowadzenia do postaci liniowej) zadań
programowania nieliniowego,
É liniowe metody aproksymacyjne,
É metody kierunków dopuszczalnych,
É metody aproksymacji kwadratowej,
É bezpośrednie metody poszukujące,
É metody przekształcenia zadań nieliniowych w ciąg zadań bez
ograniczeń lub z nielicznymi ograniczeniami.
2
f
2
f
2
f
3
x
2
1
x
x
x
x
2
1
n
1
2
f
2
f
2
f
3
det
B
det
0
2
2
x
x
x
x
x
1
2
n
2
4
4
6
4
2
f
2
f
2
f
3
x
x
x
x
2
n
x
1
n
2
n
Jeżeli ekstremum bezwarunkowe spełnia warunki ograniczające jest to
rozwiązanie optymalne.
Postać zadania programowania nieliniowego:
f( x )
ax
f( x )
min
Jeżeli ekstremum bezwarunkowe nie spełnia ograniczeń, funkcję celu
przekształcamy w funkcję Lagrange’a:
i ( x )
0 (i = 1, 2, ..., m)
g i ( x )
0 (i = 1, 2, ..., m)
i ( x ) = 0 (i = m+1, ..., r)
g i ( x ) = 0 (i = m+1, ..., r)
r
∑ =
( )
( )
L
x
,
f
x
i g
x
1 , x 2 , ..., x n
0
i
i
1
gdzie
i są nieoznaczonymi mnożnikami Lagrange’a.
Następnie szukamy ekstremum bezwarunkowego zmienionej funkcji celu,
które jest rozwiązaniem optymalnym.
37
38
HACKED BY VIPER :)
960340087.031.png 960340087.032.png
Badania operacyjne
dr inż. W. Zalewski
Badania operacyjne
dr inż. W. Zalewski
Zadanie nieliniowe o postaci kanonicznej
Dokonując podstawień:
Wszystkie ograniczenia w postaci nierówności.
( )
( )
g
x
f
x
r
∑ =
i
v
i
j
Twierdzenie Kuhna – Tuckera.
x
x
i
1
j
j
Dla zadania w formie:
oraz
g i ( x ) = w i
f(x 1 , x 2 , ..., x n )
min
i (x 1 , x 2 , ..., x n )
0 (i = 1, 2, ..., r)
otrzymamy:
1 , x 2 , ..., x n
0
( )
( )
L
f
x
r
g
x
∑ =
i
v
0
(j = 1, 2, ..., n)
r
i
j
x
x
x
∑ =
( )
( )
L
f
x
i g
x
gdy
i
1
j
j
j
i
i
1
( )
( )
n
L
n
f
x
r
g
x
n
i
x
x
v
x
0
j
i
j
j
j
x
x
x
j
1
j
1
i
1
j
1
j
j
j
warunki Kuhna – Tuckera mają postać:
( )
i ( x ) + w i = 0
(i = 1, 2, ..., r)
( )
x
L
f
x
r
g
∑ =
i
0
(j = 1, 2, ..., n)
i
x
x
x
i
1
j
j
j
r
∑ =
w
0
i
i
( )
( )
n
L
n
f
x
r
g
x
i
1
x
i
x
0
j
i
j
x
x
x
j
1
j
1
i
1
j
j
j
j
0
(j = 1, 2, ..., n)
i ( x )
0
(i = 1, 2, ..., r)
i
0
(i = 1, 2, ..., r)
r
∑ =
( )
g
x
0
i
i
i
1
j
0
(j = 1, 2, ..., n)
i
0
(i = 1, 2, ..., r)
W zadaniach postaci f( x )
max,
i ( x )
0
w warunkach i należy zmienić kierunki nierówności.
39
40
HACKED BY VIPER :)
960340087.033.png 960340087.034.png 960340087.035.png 960340087.036.png 960340087.037.png 960340087.038.png 960340087.039.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin