Egzamin sklada sie z 3 czesci:
part I:
1cz. materialy - 2x4p - zadania teoretyczne
2cz. materialy - 2x2p - zadania rachunkowe
part II:
3cz. bez materialow - 4x1/2p - zadania na rozkminke

7pkt zalicza

1cz. - 1h20m (tzn z tego wynika ze teoria i praktyka razem)
2cz. - 10m (czyli te zadania rozkminke)

Material przerobiony na wykladach:
-Algorytmy simpleks (prymalny, dualny)
-Metody odciec (dla zadan PCL, PCLM)
-Ogolna metoda podzialu i oszacowan
-Metoda podzialu i oszacowan dla zadan PLB
-Metoda rozw. zadania PLB z wykorzystaniem ograniczenia zastepczego
-Metoda najwiekszego spadku
-Wyznaczanie punktu siodlowego przy pomocy warunkow rozniczkowych Kuhna-Tuckera
-Metody funkcji kary
-Metody kierunkow dopuszczalnych
-Metoda Zoutendijk'a (strefy Zadania te co pamiętam.

Zadania z zeszlego roku wersja A:

part I

1. Zadanko dotyczyło przejścia z zadania prymalnego do dualnego (prymalne rozwiązane simplexem).
2. Było narysowane drzewko (z węzłami S, S1, S3, S4, S2) i trzeba było policzyć sume i iloczyn zbiorów
3. Zadanko na simplexa prymalnego, wystandaryzować i napisać dwie iteracje
4. zadanko PCL, (funckja + ograniczenia), zapisać w postaci 7.1, następnie zrobić funkcje Lagrage`a i zapisać warunki KunaTraktora

part II (bez materiałów)

1. Kiedy w algorytmie simpleks zmienne bazowe są rozwiązaniem optymalnym
2. Coś o wypłukłości, czy jest wypukłe, odpowiedź uzasadnij
3. coś o spadku, ale nie pamiętam Uśmiech
4. nie pamiętam

Odpowiedzi:

ad. I 1.
-str 21, 22
ad. I 2.
-teoria podzialu zbiorów suma chyba zawsze równała sie S
a iloczyn równał sie zbiorowi pustemu.
Wszystko ładnie i pięknie wedlog wzorowi nr. 5.57
-Jest def na stronie 65 na ten temat, ja bym sie na nie powołał (pamietajcie ze S to zbiory l calkowitych, wiec wywalenie ulamkow przy podziale nic nie zmienia o ile sie nie oslabi zbioru rozw dop) plus ew powolywac się na definicje dzialania sumy i iloczynu.

Zadania z zeszlego roku wersja B:

part I

1. Dane jest zadanie wypukłe PL o wielu rozwiązaniach x1, x2.
Jakie sa powiazania miedzy tymi rozwiązaniami i jak znalezc kolejne rozwiazanie .
(było to na pierwszych laborkach Duży uśmiech)
2. Dane dwa zadania prymalne i zanlezc do nich dualne i udowodnic ze sa to te same zadania.
Jedno było standaryzacja drugiego
3.Rozwiązac simpleks prymalny dwie iteracje
4.Napisać zadanie restrykcyjne i osłąbione do danego PCL

part II (bez materiałów):

1. Jakie punkty zbioru rozw. dopuszczalnych przeglada simpleks
2 Czy kierunek dopuszczcalny musi byc kierunkiem poprawy
3 Do czego słuzą wzory Kuhna-Tuckera
4 Napisać kiedy następuje zamknięcie punktu w metodzie odcięć i oszaco


Odpowiedzi:

ad. I 4.
osbłabione - zabrać jakieś ograniczenie (np. zabrac całkowitoliczbowosc)
restrykcyjne - dodać, np ze naturalne, albo x1>50

Zadania z zeszlego roku wersja C:

part I

1. dane są dwa różne rozwiązania optymalne funkcji wypukłej na zbiorze wypukłym [tex]min x \in R f(x)[/tex] oznaczone jako x* i y*. jaka jest zależność między f(x*) i f(y*) oraz jak wyznaczyć inne rozwiązanie optymalne z*.

2. dane są dwa zadania prymalne:
[tex]\min\ 5x_1 + 3x_2 + 4x_3\\
przy ogr. \begin{cases} 2x_1 - x_2 + 4x_3 \geq 5
\\ 8x_1 + 2x_2 - x_3 \geq 8
\\ x_i \geq 0, i = 1,2,3
\end{cases}[/tex]

[tex]\min\ 5x_1 + 3x_2 + 4x_3\\
przy ogr. \begin{cases} 2x_1 - x_2 + 4x_3 -x_4 = 5
\\ 8x_1 + 2x_2 - x_3 - x_5 = 8
\\ x_i \geq 0, i = 1, ..., 5
\end{cases}[/tex]
przedstawić je w postaci zadań dualnych oraz stwierdzić, czy są rownowazne zadania.

3. standaryzacja i dwie iteracje simpleksem prymalnym:
[tex]\min\ 5x_1 + 8x_2 - x_3\\
przy ogr. \begin{cases} 3x_1 - x_2 + 5x_3 \geq 5
\\ -x_1 + 4x_2 + 5x_3 \leq 6
\\ x_i \geq 0, i = 1,2,3
\end{cases}[/tex]

4. napisać zadanie osłabione i wzmocnione do poniższego zadania PCL:
[tex]\max\ 5x_1 + 8x_2 - 4x_3\\
przy ogr. \begin{cases} 2x_1 + 5x_2 - x_3 \leq 5
\\ 4x_1 - 1x_2 + 8x_3 \leq 8
\\ x_i \geq 0, x_i \in Z, i = 1,2,3
\end{cases}[/tex]

part II (Bez materiałow)

1. przez jakie punkty przechodzimy szukając rozwiązania w Simpleksie
2. czy kierunek dopuszczalny musi być kierunkiem poprawy
3. do czego służą równania różniczkowe Kuhna-Tuckera
4. kiedy występuje zamknięcie wierzchołka w metodzie podziału i oszacowań

Odpowiedzi:

part I

Ad 1.
f(x*) = f(y*) na mocy 1.10
z = O*x* + (1-O)*y*, O w przedziale 0-1

Ad 2.
tak, bo wychodzą identyczne zadania dualne... nie chce mi się tego transponować, więc nie pokażę; kwestia jedynie pomnożenia przez -1.

Ad 3.
wierzę, że nie muszę nic pisać...

Ad 4.
restrykcja - PLB, albo np xi>=50... cokolwiek, co jakoś ogranicza Mrugnięcie
osłabienie - zwykłe PL

part II

Ad 1.
napisałem wyżej

Ad 2.
nie jestem tego pewny, więc pozostawiam to wam...
chyba jednak raczej tak, ponieważ x = t*s, a t>0, więc zawsze powinien nieco poprawić...

Ad 3.
do wyznaczenia punktu siodłowego, w którym znajduje się ekstremum funkcji

Ad 4.
str. 68-69- wiem, tylko trzy ale nie chce mi sie pisać...

Zadania z zeszlego roku wersja D:

Part II(bez materialow)

1.Przez jakie wierzcholki przechodzimy algorytmem simplex
2.Do czego wyznaczamy warunki Kuhna-Tuckera
3.Kiedy zamykamy wierzcholki w zadaniu PCL
4.Jaki kierunek nazywamy dopuszczalnym

1. Kiedy w algorytmie simpleks zmienne bazowe są rozwiązaniem optymalnym
2. Coś o wypłukłości, czy jest wypukłe, odpowiedź uzasadnij
3. Jakie punkty zbioru rozw. dopuszczalnych przeglada simpleks
4 Czy kierunek dopuszczcalny musi byc kierunkiem poprawy
5 Do czego słuzą wzory Kuhna-Tuckera
6 Napisać kiedy następuje zamknięcie punktu w metodzie odcięć.
7. kiedy występuje zamknięcie wierzchołka w metodzie podziału i oszacowań
8.Kiedy zamykamy wierzcholki w zadaniu PCL
9.Jaki kierunek nazywamy dopuszczalnym


Rozwiązania:

1.   Gdy Deltai <=0  dla i należącego do przedzialu od i=1 do n
2.   Jesli chodzi o funkcje wypukłą to jest wtedy gdy
       F(teta*x+(1-teta)*y)<=teta*f(x)+(1-teta)*f(y)
teta nalezy do przedzialu [0,1], x,y naleza do omegi (zbioru rozw. dopuszczalnych) omega nalezy do E^(n)
3.   Simpleks przegląda wierzchołkowe punkty wielościanu, a następnie porównując wartości funkcji w punktach wierzchołkowych.
4.   Nie, ponieważ gdy s jest kierunkiem dopuszczalnym, to by był on kierunkiem poprawiającym musi byc spelniona nierówność: f(x+t*s)<f(x)  (str.121)
5.   Wzory Kuhna-Tuckera wykorzystujemy do wyznaczania punktów siodłowych.
6.   
7.    Metoda podziału i oszacowań gdy zachodzi co najmniej jeden z dwóch warunków
(str. 68)
8.   Odp. Jak wyżej
9.   Kierunek dopuszczalny s należący do E^(n) w pkt. x należącym do R z kreska jest wtedy gdy dla dowolnego t należącego do [0,jakas liczba >0]  punkt postaci
x’=x+s*t nalezy do zbioru R z kreska (str. 118)

Moze ktos spr. odp, odpowiedziec na tych ktorych nie znam