PO Egzamin

background image

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:

background image

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:

< .

/

[ .

background image

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:

background image

-  ` -

!

!"#

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.

background image

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:

background image

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#



background image

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=FD4f0

‚

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:

background image



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.

background image

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ć:

background image

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.

background image

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.

background image

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

background image

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:

background image

¬ 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

!

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:

background image



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

·

background image

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

background image

Zawartość

FUNKCJA WYPUKŁA

1

T

WIERDZENIE

1.4

1

T

WIERDZENIE

1.5

1

T

WIERDZENIE

1.6

1

T

WIERDZENIE

1.7

1

T

WIERDZENIE

1.10

1

HIPERPŁASZCZYZNA

1

H

IPERPŁASZCZYZNA PODPIERAJĄCA

2

PODZIAŁ ZBIORU

2

STOŻEK

2

S

TOŻEK WYPUKŁY

2

WIELOŚCIAN

2

ZADANIE OPTYMALIZACJI

2

ZADANIE WYPUKŁE

3

T

WIERDZENIE

1.8

3

T

WIERDZENIE

1.9

3

ZBIÓR OGRANICZONY

3

ZBIÓR WIELOŚCIENNY

3

ZBIÓR WYPUKŁY

3

W

IERZCHOŁEK ZBIORU WYPUKŁEGO

3

T

WIERDZENIE

(1.1)

3

T

WIERDZENIE

(1.2)

3

T

WIERDZENIE

1.3

4

ZADANIA PL

5

background image

Z

ADANIE PRYMALNE

5

Z

ADANIE DUALNE

5

Z

ADANIE STANDARDOWE

5

T

WIERDZENIE

2.1

5

T

WIERDZENIE

2.2

5

T

WIERDZENIE

2.3

5

T

WIERDZENIE

2.4

5

A

LGEBRAICZNY OPIS WIERZCHOŁKÓW ZBIORU ROZWIĄZAŃ DOPUSZCZALNYCH

5

R

OZWIĄZANIE BAZOWE

5

T

WIERDZENIE

2.6

6

A

LGORYTM PRYMALNY

S

IMPLEX

6

T

WIERDZENIE

3.1

6

T

WIERDZENIE

3.2

6

M-M

ETODA

7

A

LGORYTM DUALNY

S

IMPLEX

7

R

OZWIĄZANIE DUALNIE DOPUSZCZALNE

7

R

OZWIĄZANIE PRYMALNIE DOPUSZCZALNE

7

T

WIERDZENIE

3.7

8

ZADANIA PLB

8

R

OZWIĄZANIE CZĘŚCIOWE

8

D

OPEŁNIENIE ROZWIĄZANIA CZĘŚCIOWEGO

8

D

OPEŁNIENIE DOPUSZCZALNE

8

P

RZYKŁAD

9

ZADANIA PCL

9

R

ELAKSACJA

10

R

ESTRYKCJA

10

A

LGORYTM

10

ZADANIA NIELINIOWE BEZ OGRANICZEŃ

11

T

WIERDZENIE

6.1

11

T

WIERDZENIE

6.2

11

T

WIERDZENIE

6.3

11

M

ETODA

N

AJWIĘKSZEGO

S

PADKU

(NS)

12

M

ETODA

N

EWTONA

12

M

ETODA

G

AUSSA

-S

EIDELA

(GS)

12

ZADANIA UNIMODULARNE

12

M

ACIERZ UNIMODULARNA

12

background image

M

ACIERZ CAŁKOWICIE UNIMODULARNA

12

ZADANIA NIELINIOWE BEZ OGRANICZEŃ I WARUNKI RÓŻNICZKOWE KUHNA-TUCKERA

13

Z

ADANIE

7.1

13

P

UNKT SIODŁOWY

13

F

UNKCJA

L

AGRANGE

A DLA ZADANIA

7.1

13

T

WIERDZENIE

7.1

(

WAŻNE

)

14

T

WIERDZENIE

7.2

14

T

WIERDZENIE

7.3

14

METODY FUNKCJI KARY

14

Z

EWNĘTRZNE FUNKCJE KARY

14

W

EWNĘTRZNE FUNKCJE KARY

15

INDEKS

16


Document Outline


Wyszukiwarka

Podobne podstrony:
PYTANIA ZAPAMIĘTANE PO EGZAMINACH
!!!Chudy, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
Spisałam sobie po egzaminie pytania-co pamietalam, FiR, Bankowośc II
Po egzaminie, p1, aw_1
Po egzaminie, p10, aw_1
Pytania zebrane zaraz po egzaminie
Definicje - egzaminwer2, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
PO, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
Definicje - egzamin, WAT, III SEM, OPTYAMALIZACJA, PO - egzamin, PO - egzamin
Po egzaminie, kraków0 (1)
Po egzaminie, kp-13, W profilaktyce zespołu zaburzeń oddychania u noworodków urodzonych przedwcześni
Po egzaminie, p3, aw_1

więcej podobnych podstron