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

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

Twierdzenie 1.10

Jeżeli funkcja wypukła f określona na wypukłym zbiorze

osiąga w nim w punkcie

minimum

lokalne, to przyjmuje w nim też minimum globalne.

Hiperpłaszczyzna

Hiperpłaszczyzną

w przestrzeni

nazywamy zbiór postaci:

; .

< =6 >? =@.

> A

Hiperpłaszczyzna dzieli przestrzeń na dwie półprzestrzenie domknięte:

; .

< =6 >? =@.

> A

; .

< =6 $ >? =@.

> A

Hiperpłaszczyzna podpierająca

Hiperpłaszczyznę nazywamy podpierającą zbiór

-, gdy

DE=F- 3 9

GHI- 3 9

Podział zbioru

Podziałem P zbioru S nazywamy zbiór podzbiorów

L M zbioru S takich że:

J N J

O J

QRG=L S T

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

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:

Z – przestrzeń rozwiązań (decyzji) o właściwościach zależnych od rodzaju zadania

\ – 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

•

- zbiór rozwiązań najlepszych

•

- 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

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:

Zadania PL

Zadanie prymalne

&%g

k6 7RF'*A

; .

< - $ 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

b6 7RF'*n

;4 .

< -

4 f 4 $ ?

Zadanie standardowe

&%g

k6 7RF'*A

; .

< - R $ ?

Dualne do niego ma postać

R64

b6 7RF'*n

;4 .

< -

4 f?

Twierdzenie 2.1

Istnieją dwa wykluczające się przypadki:

1. Zadanie prymalne i dualne mają jednocześnie rozwiązania odpowiednio

i zachodzi

R64

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

DE=Ff6

R64

są rozwiązaniami optymalnymi odpowiednio

zadania prymalnego i dualnego.

Twierdzenie 2.4

Jeżeli istnieje rozwiązanie prymalnego zadania PL to istnieje wierzchołek

, że:

k6 k6

&%g

Algebraiczny opis wierzchołków zbioru rozwiązań dopuszczalnych

Niech

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:

Gdzie:

• B – podmacierz macierzy A będąca bazą
•

- wektor składowych wektora x odpowiadający bazie B

•

- wektor pozostałych składowych wektora x

Twierdzenie 2.6

Punkt x jest wierzchołkiem zbioru

wtedy i tylko wtedy, gdy jest nieujemnym rozwiązaniem

bazowym układu:

6 R

' y

3 y ;z { (?

L |6|

| ;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

R ,_R

R |'*f0u +

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

funkcji

Celu

Indeksy

wektorów bazy

Współczynniki z

funkcji celu przy

wektorach bazy

Aktualne

rozwiązanie

bazowe

-1

Macierz

Współczynników

Twierdzenie 3.1

Jeżeli dla każdego

L Md

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

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:

, takie że f6

f6. Przy czym:

•

RG=' |

;'?

•

RG=' T

•

RG=' |

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

, że dla każdego

y $ y

w dowolnym rozwiązaniu optymalnym

zadania z M-Metody punkt

jest rozwiązaniem

optymalnym zadania podstawowego.

Twierdzenie 3.5

Jeśli dla dowolnie dużego M w rozwiązaniu optymalnym

zadania z M-Metodą mamy (=H

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

8 u

Rozwiązanie dualnie dopuszczalne

Rozwiązanie odpowiadające sytuacji:

RG=L |

fF4G'RG=*T_DE]I=FD4f0

RG=L |

RG=DFD,_=4f0*T_DE]

Nazywamy dualnie dopuszczalnym.

Rozwiązanie prymalnie dopuszczalne

Jeśli rozwiązanie jest dualnie dopuszczalne i dodatkowo:

To jest ono prymalnie dopuszczalne.

Twierdzenie 3.7

Jeżeli istnieją

, |

L |

takie że:

DE=FF

$ dla każdego L |

to nie istnieje rozwiązanie optymalne.

Zadania PLB

Zadaniem PLB nazywamy takie zadanie optymalizacji, że:

Wyznaczyć

J 3

takie że:

Gdzie:

< =

' (

; ? L M

Dodatkowo zakładamy, że wektor c jest niedodatni. Jeśli byłoby inaczej należy dokonać

podstawienia:

Ponadto przyjmujemy oznaczenia:

•

– droga z wierzchołka

do wierzchołka

•

- zbiór indeksów zmiennych o ustalonych wartościach na drodze

•

;L |< L

•

- zbiór tych ograniczeń, w których

E (czyli prawa strona ujemna)

•

- zbiór numerów zmiennych x, przy których występują ujemne współczynniki w wierszach

należących do zbioru Q

• Uwaga: jeśli

S Q, to

T J

Rozwiązanie częściowe

Rozwiązaniem częściowym w wierzchołku

nazywamy wektor zmiennych o ustalonych na drodze

wartościach

d L

Dopełnienie rozwiązania częściowego

Wektor

d L

; ? nazywamy dopełnieniem rozwiązania częściowego w

wierzchołku

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:

; ?

W pierwszym kroku oszacowanie górne i dolne są w nieskończoności.

;z£?d |

Qd |

Qd n

Osłabiamy zadanie i mamy:

Przy ograniczeniach:

3 ¥

;

; ? L

Rozwiązanie optymalne znajdujemy na zasadzie „zauważamy, że”, w tym przypadku

; ?

Ograniczenie górne:

Ponadto wyznaczamy

jako wartość minimalną każdego ograniczenia, stąd:

•

¦ E

•

z E

Jako, że zbiór

jest pusty oraz ograniczenie górne jest większe od dolnego, przechodzimy do

punktu kolejnego, czyli podziału zbioru na dwa podzbiory.

;£?

Wyznaczamy

('M

L &%g;

£?

Gdzie,

L & ; E

?, 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ć

J 3 .

takie że:

&%g

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:

&%g 7

Gdzie:

•

J 3 ¥

•

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

; .

$ ©

¨
¡

ª 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

- ; .

? jest zwarty, to ciąg

generowany przez procedurę

największego spadku jest zbieżny do pewnego punktu należącego do zbioru:

; .

< 5 ?

Twierdzenie 6.3

Jeżeli:

1. Funkcja f ma ciągłe pochodne cząstkowe
2. Zbiór

- ; .

? jest zwarty, to ciąg T

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

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

4. Minimalizujemy funkcję w punkcie

PC#

_ 8 ,

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

Gdzie:

J ; .

< - R $ f=TD'_*?

Osłabieniem tego zadania może być zadanie PL w postaci standardowej, tj.:

; .

< - 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ą

- =

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

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

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ć

A 3 .

, takie że:

&%g

Gdzie:

A .

< « 7

{ 7

< 7

' (

Punkt siodłowy

Parę

nazywamy punktem siodłowym funkcji 4 w zbiorze AxB, jeżeli dla każdego

- 4 u zachodzi:

Funkcja Lagrange’a dla zadania 7.1

Funkcja Lagrange’a dla zadania 7.1 jest dana jako:

¬ 4 4« 4

!"#

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

jest punktem siodłowym funkcji Lagrange’a w zbiorze AxB, to x jest punktem

optymalnym zadania 7.1 oraz zachodzi

Twierdzenie 7.2

Jeżeli punkt

jest punktem siodłowym funkcji Lagrange’a zadania 7.1 oraz funkcje '7

są

klasy

(pierwsze pochodne istnieją i są ciągłe) w

, to prawdziwe są następujące warunki, znane

jako warunki różniczkowe Kuhna-Tuckera:

Twierdzenie 7.3

Jeżeli funkcje

są wypukłymi funkcjami klasy

(pierwsze pochodne istnieją i są ciągłe) w

, to

każda para

spełniająca warunki Kuhna-Tuckera jest punktem siodłowym funkcji Lagrange’a a

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

&%g

RG=T z { _=T')*<

8 P[C±

²³³³´

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

jest ciągiem zewnętrznych funkcji kar, jeśli:

•

dla każdego A T z {

•

+ dla każdego A T z {

•

PC#

dla każdego A T z {

•

P[C±

²³³³´ ¶ dla każdego A T z {

Przykład funkcji:

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

jest ciągiem wewnętrznych funkcji kar, jeśli:

•

PC#

+ , dla każdego A

T z {

•

P[C±

²³³³´ , dla każdego A

•

K[C±

²³³³´ ¶, dla każdego ciągu

¸ A

, takiego że

K[C±

²³³³´ ¹, gdzie ¹ ºA, ºA -

brzeg zbioru

A dla T z {

Przykład funkcji:

!"#

RG= A

Indeks

Dopełnienie dopuszczalne, 8, 18

Dopełnienie rozwiązania częściowego, 8, 18

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

Hiperpłaszczyzna, 1, 2, 17

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

Podział zbioru, 2, 17

przestrzeń euklidesowa, 2

Punkt siodłowy, 13, 19

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

Simplex, 6, 7, 11, 18

Stożek

Stożek wypukły, 2, 17

Stożek wypukły, 2

warunki Kuhna-Tuckera, 13, 14, 19

Wewnętrzne funkcje kary, 15, 19

Wielościan, 2

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

Document Outline