Funkcja wypukła
Funkcja wypukła to funkcja określona na wypukłym zbiorze A, która dla każdych dwóch punktów
spełnia nierówność:
W przypadku występowania ostrej nierówności funkcja jest ściśle wypukła. Jeśli nierówność jest
przeciwna (i ponadto
) mówimy o funkcji wklęsłej (i odpowiednio ściśle wklęsłej).
Jeśli
jest wypukła to – jest wklęsła i odwrotnie.
Funkcja liniowa jest jednocześnie wypukła i wklęsła.
Twierdzenie 1.4
Funkcja postaci
!"#
$ % &
jest wypukła, gdy
!
jest wypukła dla ' ( oraz istnieje takie ' )*
+ .
Twierdzenie 1.5
Funkcja postaci
!"#
$ % &
jest ściśle wypukła gdy co najmniej jedna
!
jest ściśle wypukła, a pozostałe wypukłe.
Twierdzenie 1.6
Funkcja określona na otwartym zbiorze wypukłym A jest wypukła wtedy i tylko wtedy, gdy dla każdej
pary
, - , .
/
wypukła jest funkcja
01 1,.
Twierdzenie 1.7
Niech f będzie funkcją klasy
2
#
określoną na otwartym i wypukłym zbiorze
- 3 .
/
. Następujące
warunki są równoważne:
1. Funkcja f jest wypukła
2. Dla każdej pary punktów
4 - zachodzi: 4 $ 564
3. Dla każdej pary
, - , .
/
funkcja
71 5 1,6, jest funkcją niemalejącą
ze względu na parametr
1.
Twierdzenie 1.10
Jeżeli funkcja wypukła f określona na wypukłym zbiorze
osiąga w nim w punkcie
8
minimum
lokalne, to przyjmuje w nim też minimum globalne.
Hiperpłaszczyzna
Hiperpłaszczyzną
9
:
w przestrzeni
.
/
nazywamy zbiór postaci:
9
:
; .
/
< =6 >? =@.
/
> A
Hiperpłaszczyzna dzieli przestrzeń na dwie półprzestrzenie domknięte:
9
:
B
; .
/
< =6 >? =@.
/
> A
9
:
C
; .
/
< =6 $ >? =@.
/
> A
Hiperpłaszczyzna podpierająca
Hiperpłaszczyznę nazywamy podpierającą zbiór
-, gdy
:
9
:
DE=F- 3 9
:
B
GHI- 3 9
:
C
Podział zbioru
Podziałem P zbioru S nazywamy zbiór podzbiorów
J
K
L M zbioru S takich że:
J N J
K
J
K
O J
P
QRG=L S T
Stożek
Stożek
J w przestrzeni .
/
to taki zbiór punktów
że dla każdego U $ punkt U V, czyli UV 3 V.
Stożek wypukły
Jeżeli stożek jest zbiorem wypukłym to nazywamy go stożkiem wypukłym.
Wielościan
Zbiór wielościenny ograniczony.
Zadanie optymalizacji
Mówimy, że zadanie optymalizacji jest sformułowane, gdy dane są
W X oraz wymaganie
wyznaczenia zbioru
W
8
lub jego niektórych elementów, gdzie:
•
W - zbiór rozwiązań dopuszczalnych
•
Y - zbiór ocen odpowiadających rozwiązaniom dopuszczalnym
•
- funkcja celu określona jako < Z [ \, gdzie:
o
Z – przestrzeń rozwiązań (decyzji) o właściwościach zależnych od rodzaju zadania
o
\ – przestrzeń ocen rozwiązań (decyzji) o właściwościach zależnych od rodzaju
zadania
•
X - relacja dominowania, pozwalająca na określenie preferencji w zbiorze \, tzn.
stwierdzenie który element z tego zbioru jest lepszy od innego elementu tego zbioru
•
W
8
- zbiór rozwiązań najlepszych
•
Y
8
- zbiór ocen odpowiadających rozwiązaniom najlepszym
•
.
/
- przestrzeń euklidesowa
Zadanie jest jednokryterialne jeśli:
< .
/
[ A
Zadanie jest wielokryterialne jeśli:
< .
/
[ .
Zadanie wypukłe
Twierdzenie 1.8
Jeżeli g jest ciągłą i wypukłą funkcją określoną na wypukłym i domkniętym zbiorze A, to dla każdej
liczby rzeczywistej
>FI']E-
^
;@-< 7 >? jest wypukły i domknięty.
Twierdzenie 1.9
Jeżeli g jest ciągłą i wklęsłą funkcją określoną na wypukłym i domkniętym zbiorze A, to dla każdej
liczby rzeczywistej
>FI']E-
^
;@-< 7 $ >? jest wypukły i domknięty.
Zbiór ograniczony
Jeśli istnieje
= .
/
)*
!
$ = ' M _DFI']E- nazywamy ograniczonym od dołu (analogicznie
dla ograniczenia górnego).
Zbiór ograniczony to zbiór ograniczony od góry i od dołu.
Zbiór wielościenny
Zbiorem wielościennym nazywamy zbiór
- postaci:
- `; .
/
< =
!
6 R
!
?
!"#
Przy czym istnieje takie
' )*R
!
S
Zbiór wypukły
Zbiór
- 3 .
/
nazywamy zbiorem wypukłym jeśli
a 4 - bc .
Przykładami zbiorów wypukłych są: odcinek, półprosta, prosta, koło, cała przestrzeń.
Nie są zbiorami wypukłymi: okrąg, koło bez środka.
Wierzchołek zbioru wypukłego
Wierzchołkiem zbioru wypukłego nazywamy taki punkt x, dla którego nie istnieją dwa takie punkty y,
z, że:
4 S Fd 4 F -)* 4 bc
Twierdzenie (1.1)
Iloczyn zbioru wypukłego przez liczbę rzeczywistą jest zbiorem wypukłym:
a e 8 ;< ?
Twierdzenie (1.2)
Iloczyn rodziny zbiorów wypukłych jest zbiorem wypukłym:
- ` -
!
!"#
Uwaga: suma mnogościowa zbiorów wypukłych nie musi być zbiorem wypukłym.
Twierdzenie 1.3
Zbiór wypukły i ograniczony od dołu bądź od góry ma co najmniej jeden wierzchołek. Każda
hiperpłaszczyzna podpierająca taki zbiór zawiera przynajmniej jeden jego wierzchołek.
Zadania PL
Zadanie prymalne
f6
8
&%g
hi
j
k6 7RF'*A
K
; .
/
< - $ R $ ?
Zadanie liniowe jest zadaniem wypukłym, gdyż funkcja celu (c|x) jest wypukła i zbiór rozwiązań
dopuszczalnych R również jest wypukły.
Zadanie dualne
R64
8
&
lm
j
b6 7RF'*n
K
;4 .
< -
o
4 f 4 $ ?
Zadanie standardowe
f6
8
&%g
hi
p
k6 7RF'*A
:
; .
/
< - R $ ?
Dualne do niego ma postać
R64
8
&
lm
p
b6 7RF'*n
:
;4 .
< -
o
4 f?
Twierdzenie 2.1
Istnieją dwa wykluczające się przypadki:
1. Zadanie prymalne i dualne mają jednocześnie rozwiązania odpowiednio
8
4
8
i zachodzi
f6
8
R64
8
2. Zadanie prymalne i dualne nie mają jednocześnie rozwiązania.
Twierdzenie 2.2
Dla każdych x, y zachodzi:
f6 $ R64
Twierdzenie 2.3
Jeśli
8
A
K
4
8
n
K
DE=Ff6
8
R64
8
to
8
4
8
są rozwiązaniami optymalnymi odpowiednio
zadania prymalnego i dualnego.
Twierdzenie 2.4
Jeżeli istnieje rozwiązanie prymalnego zadania PL to istnieje wierzchołek
A
K
, że:
k6 k6
8
&%g
hi
j
k6
Algebraiczny opis wierzchołków zbioru rozwiązań dopuszczalnych
Niech
bd
q
rhs
d bd g $ &
B – podmacierz macierzy A utworzona z m liniowo niezależnych kolumn macierzy A.
Rozwiązanie bazowe
Rozwiązaniem bazowym układu równań
b, odpowiadającym bazie B nazywamy rozwiązanie x
tego układu:
tu
v
R
w
x
Gdzie:
• B – podmacierz macierzy A będąca bazą
•
v
- wektor składowych wektora x odpowiadający bazie B
•
w
- wektor pozostałych składowych wektora x
Twierdzenie 2.6
Punkt x jest wierzchołkiem zbioru
A
K
wtedy i tylko wtedy, gdy jest nieujemnym rozwiązaniem
bazowym układu:
=
!
6 R
!
' y
#
3 y ;z { (?
K
L |6|
K
| ;z { M?
Algorytm prymalny Simplex
1. Zadanie sprowadzamy do postaci standardowej (tzn. z równościami).
a. Jeśli istnieje taki indeks i, że nie istnieje ograniczenie
!
$ , to wówczas
!
!
}
~, przy czym obie te zmienne są większe-równe od 0
2. Znajdujemy rozwiązanie bazowe odpowiadające bazie B
u
v
R ,_R
v
u
B#
R |'*f0u +
v
R
3. Warunek wejścia: szukamy wektora, odpowiadającego największej dodatniej delcie
4. Warunek wyjścia: szukamy wektora, dla którego iloraz współrzędnej z rozwiązania bazowego
przez odpowiadającą mu współrzędną wektora wchodzącego jest najmniejszy
5. Na przecięciu obu wektorów mamy punkt centralny
6. Liczymy nowe rozwiązanie bazowe
7. Warunek stopu: Jeśli wszystkie delty są ujemne, to znaleźliśmy rozwiązanie bazowe
8. Uwaga! Jeśli istnieje delta dodatnia, dla której w odpowiadającym wektorze istnieją
ujemne współczynniki to rozwiązanie optymalne nie istnieje!
9. Pamiętamy o przekształceniach:
(= &%g DE=F &%g &
10. Tabela simplexowa ma następującą postać:
Współczynniki
w
funkcji
Celu
Indeksy
wektorów bazy
Współczynniki z
funkcji celu przy
wektorach bazy
Aktualne
rozwiązanie
bazowe
3
-1
4
Macierz
4
2
6
Współczynników
Twierdzenie 3.1
Jeżeli dla każdego
L Md
K
to punkt x (rozwiązanie bazowe odpowiadające bazie B) jest
rozwiązaniem optymalnym.
Twierdzenie 3.2
Jeśli istnieje taki numer
|, że:
+ DE=F
B#
To nie istnieje skończone rozwiązanie zadania (co oznacza, że jeśli delta jest dodatnia to współrzędne
wektora, który jej odpowiada też są dodatnie).
W przeciwnym przypadku (tzn. drugi warunek jest nieprawdziwy) można skonstruować nowe
rozwiązanie bazowe odpowiadające bazie B, w oparciu o już istniejące rozwiązanie bazowe:
1
P
, takie że f6
f6. Przy czym:
•
!
!
1
P
u
B#
=
P
!
RG=' |
v
;'?
•
!
1
P
RG=' T
•
!
RG=' |
v
N ;'?;T?
M-Metoda
Jeśli w macierzy ograniczeń nie istnieje podmacierz jednostkowa możemy rozszerzyć zadanie w taki
sposób, żeby rozszerzone zadanie taką podmacierz zawierało.
M-Metoda powoduje zmianę funkcji celu z postaci:
f6M=f6 y H
!
Zakładamy, że M jest liczbą dowolnie dużą.
Twierdzenie 3.4
Jeżeli istnieje rozwiązanie zadania podstawowego to istnieje taka liczba
y
:
, że dla każdego
y $ y
:
w dowolnym rozwiązaniu optymalnym
8
8
zadania z M-Metody punkt
8
jest rozwiązaniem
optymalnym zadania podstawowego.
Twierdzenie 3.5
Jeśli dla dowolnie dużego M w rozwiązaniu optymalnym
8
8
zadania z M-Metodą mamy (=H
!
8
+
, to zadanie podstawowe nie ma rozwiązania optymalnego.
Algorytm dualny Simplex
1. Warunek wyjścia: wektor, któremu odpowiada najmniejsza współrzędna z rozwiązania
bazowego
2. Warunek wejścia: wektor, dla którego iloraz delty i współrzędnej odpowiadającej wektorowi
wychodzącemu jest najmniejszy (ale dodatni)
3. Warunek stopu: ujemne rozwiązanie bazowe
4. Rozwiązanie dualne możemy policzyć z zależności:
4
8
8 u
B#
Rozwiązanie dualnie dopuszczalne
Rozwiązanie odpowiadające sytuacji:
K
4=
K
f
K
t
RG=L |
v
fF4G'RG=*T_DE]I=FD4f0
K
RG=L |
w
RG=DFD,_=4f0*T_DE]
x
Nazywamy dualnie dopuszczalnym.
Rozwiązanie prymalnie dopuszczalne
Jeśli rozwiązanie jest dualnie dopuszczalne i dodatkowo:
v
$
w
To jest ono prymalnie dopuszczalne.
Twierdzenie 3.7
Jeżeli istnieją
, |
v
L |
w
takie że:
DE=FF
K
$ dla każdego L |
w
to nie istnieje rozwiązanie optymalne.
Zadania PLB
Zadaniem PLB nazywamy takie zadanie optymalizacji, że:
Wyznaczyć
8
J 3
/
takie że:
f6
8
&
h
k6
Gdzie:
J
/
< =
!K
K
R
!
' (
K
; ? L M
Dodatkowo zakładamy, że wektor c jest niedodatni. Jeśli byłoby inaczej należy dokonać
podstawienia:
K
K
.
Ponadto przyjmujemy oznaczenia:
•
X
P
– droga z wierzchołka
J
:
do wierzchołka
J
P
•
P
- zbiór indeksów zmiennych o ustalonych wartościach na drodze
X
P
•
|
P
C
L
P
<
K
•
|
P
B
L
P
<
K
•
P
;L |< L
P
?
•
n
P
- zbiór tych ograniczeń, w których
E (czyli prawa strona ujemna)
•
A
P
- zbiór numerów zmiennych x, przy których występują ujemne współczynniki w wierszach
należących do zbioru Q
• Uwaga: jeśli
n
P
S Q, to
:
T J
P
Rozwiązanie częściowe
Rozwiązaniem częściowym w wierzchołku
J
P
nazywamy wektor zmiennych o ustalonych na drodze
X
P
wartościach
K
,
T
K
d L
P
.
Dopełnienie rozwiązania częściowego
Wektor
T
K
d L
P
d
K
; ? nazywamy dopełnieniem rozwiązania częściowego w
wierzchołku
J
P
.
Dopełnienie dopuszczalne
Dopełnienie
T nazywamy dopuszczalnym, jeśli łącznie z rozwiązaniem częściowym
T tworzy
wektor
J. W przeciwnym przypadku dopełnienie nazywamy niedopuszczalnym.
Przykład
(=
#
¡
Przy ograniczeniach:
J
:
¢
#
£
¡
z
z
#
¤
z
z
¡
z
¡
!
; ?
x
W pierwszym kroku oszacowanie górne i dolne są w nieskończoności.
:
Qd
:
;z£?d |
P
C
Qd |
P
B
Qd n
:
;?
Osłabiamy zadanie i mamy:
(=
#
¡
Przy ograniczeniach:
J
:
3 ¥
:
;
K
; ? L
:
Rozwiązanie optymalne znajdujemy na zasadzie „zauważamy, że”, w tym przypadku
:
; ?
Ograniczenie górne:
F
:
d
:
J
:
Ponadto wyznaczamy
_
K
jako wartość minimalną każdego ograniczenia, stąd:
•
_
#
E
#
z
•
_
¦ E
•
_
z E
Jako, że zbiór
n
:
jest pusty oraz ograniczenie górne jest większe od dolnego, przechodzimy do
punktu kolejnego, czyli podziału zbioru na dwa podzbiory.
A
:
;£?
Wyznaczamy
:
('M
:
L &%g;
:
:
:
£?
:
+
Gdzie,
P
L & ; E
!
=
!K
?, gdzie a to współczynniki. Innymi słowy ze wszystkich ograniczeń
sumujemy współczynniki przy zmiennej z indeksem j i odejmujemy od nich prawą stronę
ograniczenia. Następnie bierzemy maksimum wyniku i 0.
Obliczone p jest indeksem zmiennej, dla której ustalamy wartość (będą dwie gałęzie – jak w PCL – z
wartościami 0 i 1 przy czym znak będzie „=”).
Itd.
Zadania PCL
Zadanie PCL ma postać:
Wyznaczyć
8
J 3 .
/
takie że:
8
&%g
&%g
§
f6
Gdzie:
J ; .
/
< - R $ f=TD'_*?
Gdzie wszystkie zmienne decyzyjne są całkowitoliczbowe. Jeśli tylko niektóre zmienne są
całkowitoliczbowe to zadanie takie nazywamy zadaniem mieszanym.
Relaksacja
Relaksacją (osłabieniem) zadania PCL nazywamy:
Wyznaczyć
:
¥ 3 .
/
takie że:
7
:
&%g 7
Gdzie:
•
J 3 ¥
•
7
Ponadto zachodzi
('M7 ('M
Restrykcja
Restrykcją (wzmocnieniem) zadania PCL nazywamy:
Wyznaczyć
3 .
/
takie że:
0 &%g 0
Gdzie:
•
3 J
•
0 $
Ponadto zachodzi
('M0 $ ('M
W przypadku zadania maksymalizacji min zostaje zmienione na max, nazwy funkcji mają duże litery
(G(x) i H(x)) a nierówności mają przeciwne zwroty.
Algorytm
Zadania PCL polegają na wprowadzeniu relaksacji (osłabienia) i restrykcji (wzmocnienia) aktualnych
ograniczeń zadania.
1. Zaczynamy od zadania całkowitoliczbowego i jednego wierzchołka (oszacowanie od góry i od
dołu są w nieskończoności)
2. Rozwiązujemy zadanie dla wierzchołka (np. algorytmem Simplex).
3. Jeśli rozwiązanie optymalne zadania z punktu 2. ma same współrzędne całkowite to liczymy
oszacowanie od dołu (wartość funkcji celu w tym punkcie) i wierzchołek zamykamy. Ogólnie
zamknięcie wierzchołka może mieć miejsce tylko gdy zachodzi co najmniej jeden z
warunków:
a. Oszacowanie od góry i od dołu w danym wierzchołku są sobie równe
b. Oszacowanie od góry w danym wierzchołku jest mniejsze-równe od globalnego
oszacowania od dołu
4. Jeśli jest inaczej, to wybieramy niecałkowitą współrzędną z rozwiązania optymalnego i
dokonujemy podziału. Jeśli np. współrzędna
¡
¨
¡
to dzielimy na następujące zbiory:
J
#
.
/
<
¡
©
¨
¡
ª 'J
; .
/
<
¡
$ ©
¨
¡
ª z?
5. Przy tych restrykcjach rozwiązujemy zadanie dla kolejnych wierzchołków.
6. Algorytm kończy się, gdy wszystkie wierzchołki zostaną zamknięte.
Zadania nieliniowe bez ograniczeń
Twierdzenie 6.1
Niech
< .
/
[ A funkcja różniczkowalna w punkcie x. Jeżeli istnieje , .
/
, takie że:
56,
To istnieje takie
> + , że dla wszystkich _ > zachodzi:
_,
Twierdzenie 6.2
Jeżeli prawdziwe są następujące założenia:
1. Funkcja f ma ciągłe pochodne cząstkowe
2. Zbiór
- ; .
/
<
8
? jest zwarty, to ciąg
P
generowany przez procedurę
największego spadku jest zbieżny do pewnego punktu należącego do zbioru:
Z
; .
/
< 5 ?
Twierdzenie 6.3
Jeżeli:
1. Funkcja f ma ciągłe pochodne cząstkowe
2. Zbiór
- ; .
/
<
8
? jest zwarty, to ciąg T
8
generowany przez procedurę
Gaussa-Seidela jest zbieżny do pewnego punktu należącego do zbioru:
Z ;
.
/
< 5 ?
Analogiczne twierdzenie istnieje dla metody Powella.
Metoda Największego Spadku (NS)
1. W punkcie początkowym
P
T liczymy wartość funkcji oraz jej gradientu (pochodne po
każdej ze zmiennych – zakładamy, że istnieją).
2. Jeśli norma (czyli długość wektora w przestrzeni
.
/
) z gradientu jest mniejsza od pewnego
epsilon (np. 0,01) to koniec.
3. Wyznaczamy kierunek minimalizacji jako
,
P
5
P
4. Minimalizujemy funkcję w punkcie
PC#
P
_ 8 ,
P
5. Bierzemy kolejny punkt.
Metoda Newtona
Analogicznie jak w metodzie NS, tyle że podczas liczenia kierunku gradient wymnażamy przez
odwrócony Hesjan (macierz drugich pochodnych) funkcji
.
Metoda Gaussa-Seidela (GS)
Kolejno dokonujemy minimalizacji we wszystkich kierunkach należących do podanej bazy.
Zadania unimodularne
Wśród zadań dyskretnych ważną rolę odgrywa zadanie PCL postaci:
&%g
h
k6
Gdzie:
J ; .
/
< - R $ f=TD'_*?
Osłabieniem tego zadania może być zadanie PL w postaci standardowej, tj.:
A
:
; .
/
< - R $ ?
Zatem widać, że
J 3 A
:
.
Macierz unimodularna
Macierz B kwadratowa, nieosobliwa o elementach całkowitych jest macierzą unimodularną gdy:
X 6R*_u6
Macierz całkowicie unimodularna
Macierz całkowitoliczbową
- =
!K
/
nazywamy całkowicie unimodularną, gdy każda jej
podmacierz kwadratowa nieosobliwa jest unimodularna.
Wniosek 5.1
Jeśli macierz B jest całkowicie unimodularna to
u
B#
jest całkowitoliczbowa.
Wniosek 5.2
Jeśli macierz A jest całkowicie unimodularna to przy całkowitoliczbowym wektorze d każde
rozwiązanie bazowa układu:
- R
Jest całkowitoliczbowe.
Wniosek 5.3
Jeśli macierz A oraz wektor d są całkowitoliczbowe oraz macierz A jest całkowicie unimodularna, to
rozwiązanie optymalne jest całkowitoliczbowe.
Wniosek 5.4
Jeżeli w zadaniu macierz A oraz wektor d są całkowitoliczbowe, macierz A jest całkowicie
unimodularna to rozwiązanie optymalne, bazowe zadania osłabionego jest rozwiązaniem
optymalnym zadania wyjściowego PCL.
Uwaga: całkowita unimodularność jest warunkiem dostatecznym ale nie koniecznym
całkowitoliczbowości rozwiązania bazowego układu
- R przy całkowitoliczbowym d.
Twierdzenie 5.1
Macierz A, której elementy
=
!K
przyjmują wartości -1, 0, 1 jest całkowicie unimodularna, gdy:
• Każda kolumna zawiera nie więcej niż 2 elementy niezerowe
• Wiersze macierzy A można podzielić na 2 podzbiory, takie że:
o Jeżeli kolumna zawiera 2 elementy niezerowe o takich samych znakach, to wiersze
odpowiadające tym elementom należą do różnych podzbiorów.
o Jeżeli kolumna zawiera 2 elementy niezerowe o różnych znakach, to wiersze
odpowiadające tym elementom należą do tego samego podzbioru.
Zadania nieliniowe bez ograniczeń i warunki różniczkowe Kuhna-
Tuckera
Zadanie 7.1
Zadanie postaci:
Wyznaczyć
8
A 3 .
/
, takie że:
8
&%g
w
Gdzie:
A .
/
< « 7
#
7
{ 7
o
.
/
< 7
!
' (
Punkt siodłowy
Parę
8
4
8
nazywamy punktem siodłowym funkcji 4 w zbiorze AxB, jeżeli dla każdego
- 4 u zachodzi:
8
4
8
4
8
4
8
Funkcja Lagrange’a dla zadania 7.1
Funkcja Lagrange’a dla zadania 7.1 jest dana jako:
¬ 4 4« 4
!
7
!
/
!"#
7RF'*« D7E=M'fF*M'=_=T'* )*7
!
Warunki wystarczy zapisać w postaci układu równań i rozwiązać.
Twierdzenie 7.1 (ważne)
Jeżeli
8
4
8
jest punktem siodłowym funkcji Lagrange’a w zbiorze AxB, to x jest punktem
optymalnym zadania 7.1 oraz zachodzi
4
8
«
8
.
Twierdzenie 7.2
Jeżeli punkt
8
4
8
jest punktem siodłowym funkcji Lagrange’a zadania 7.1 oraz funkcje '7
!
są
klasy
2
#
(pierwsze pochodne istnieją i są ciągłe) w
.
/
, to prawdziwe są następujące warunki, znane
jako warunki różniczkowe Kuhna-Tuckera:
5
¬
8
4
8
5
¬
8
4
8
5
¬
8
4
8
4
8
4
8
$
Twierdzenie 7.3
Jeżeli funkcje
'7
!
są wypukłymi funkcjami klasy
2
#
(pierwsze pochodne istnieją i są ciągłe) w
.
/
, to
każda para
8
4
8
spełniająca warunki Kuhna-Tuckera jest punktem siodłowym funkcji Lagrange’a a
8
jest rozwiązaniem optymalnym tego zadania.
Metody funkcji kary
Idea metod funkcji kary polega na zastąpieniu zadania 7.1 ciągiem zadań optymalizacji bez
ograniczeń poprzez skonstruowanie zastępczej funkcji celu uwzględniającej karę za niespełnienie
przez punkt x tych ograniczeń. Tworzymy ciąg zadań optymalizacji bez ograniczeń:
®
P
P
8
&%g
w
®
P
&%g
¯
°
P
RG=T z { _=T')*<
P
8 P[C±
²³³³´
8
Zewnętrzne funkcje kary
Niech zbiór
A zadania 7.1 będzie domknięty, funkcje kary będą funkcjami ciągłymi. Wówczas
mówimy, że ciąg
P
µ
jest ciągiem zewnętrznych funkcji kar, jeśli:
•
P
µ
dla każdego A T z {
•
P
µ
+ dla każdego A T z {
•
PC#
µ
+
P
µ
dla każdego A T z {
•
P
µ
P[C±
²³³³´ ¶ dla każdego A T z {
Przykład funkcji:
P
µ
T 8 & ; 7
!
?
/
!"#
Wewnętrzne funkcje kary
Niech zbiór
A zadania 7.1 będzie domknięty, funkcja kary określona na wnętrzu A
·
tego zbioru. Ciąg
funkcji
P
jest ciągiem wewnętrznych funkcji kar, jeśli:
•
P
+
PC#
+ , dla każdego A
·
T z {
•
P
P[C±
²³³³´ , dla każdego A
·
•
P
¸
K[C±
²³³³´ ¶, dla każdego ciągu
¸ A
·
, takiego że
K[C±
²³³³´ ¹, gdzie ¹ ºA, ºA -
brzeg zbioru
A dla T z {
Przykład funkcji:
P
E
P
7
!
!"#
RG= A
·
Indeks
D
Dopełnienie dopuszczalne, 8, 18
Dopełnienie rozwiązania częściowego, 8, 18
F
funkcja celu, 2, 5
Funkcja Lagrange’a, 13, 19
funkcja ściśle wklęsła, 1
funkcja ściśle wypukła, 1
funkcja wklęsła, 1
Funkcja wypukła, 1, 17
H
Hiperpłaszczyzna, 1, 2, 17
M
Macierz całkowicie unimodularna, 12, 19
Macierz unimodularna, 12, 18
Metoda Gaussa-Seidela, 12, 18
Metoda Największego Spadku, 12, 18
Metoda Newtona, 12, 18
Metody funkcji kary, 14, 19
M-Metoda, 7, 18
P
Podział zbioru, 2, 17
przestrzeń euklidesowa, 2
Punkt siodłowy, 13, 19
R
relacja dominowania, 2
Relaksacja, 10, 18
Restrykcja, 10, 18
Rozwiązanie bazowe, 5, 18
Rozwiązanie częściowe, 8, 18
Rozwiązanie dualnie dopuszczalne, 7, 18
Rozwiązanie prymalnie dopuszczalne, 7, 18
S
Simplex, 6, 7, 11, 18
Stożek
Stożek wypukły, 2, 17
Stożek wypukły, 2
W
warunki Kuhna-Tuckera, 13, 14, 19
Wewnętrzne funkcje kary, 15, 19
Wielościan, 2
Z
Zadania nieliniowe bez ograniczeń, 11, 13, 18, 19
Zadania PCL, 9, 10, 18
Zadania PL, 5, 17
Zadania PLB, 8, 18
Zadania unimodularne, 12, 18
Zadanie dualne, 5, 18
Zadanie optymalizacji, 2, 17
Zadanie prymalne, 5, 18
Zadanie standardowe, 5, 18
Zadanie wypukłe, 3, 17
zbiór ocen odpowiadających rozwiązaniom
dopuszczalnym, 2
Zbiór ograniczony, 3, 17
zbiór rozwiązań dopuszczalnych, 2, 5
zbiór rozwiązań najlepszych, 2
Zbiór wielościenny, 2, 3, 17
Zbiór wypukły, 3, 4, 17
Zewnętrzne funkcje kary, 14, 19
Zawartość
LGEBRAICZNY OPIS WIERZCHOŁKÓW ZBIORU ROZWIĄZAŃ DOPUSZCZALNYCH
OZWIĄZANIE DUALNIE DOPUSZCZALNE
OZWIĄZANIE PRYMALNIE DOPUSZCZALNE
OPEŁNIENIE ROZWIĄZANIA CZĘŚCIOWEGO
ACIERZ CAŁKOWICIE UNIMODULARNA
ZADANIA NIELINIOWE BEZ OGRANICZEŃ I WARUNKI RÓŻNICZKOWE KUHNA-TUCKERA