Podstawy Optymalizacji

Egzamin

(01.02.2011 r.)

Zadania praktyczne (80 minut)

Zad. 1

Rozwiązując zadanie liniowe PL
,
otrzymano dwa różne rozwiązania optymalne
oraz

. Czy istnieje inne rozwiązanie optymalne? Jeśli tak to zapisz zbiór wszystkich zadań optymalnych jakie można wyznaczyć z wektorów
i
. Jaka jest zależność między
i
? Uzasadnij odpowiedź.

Rozwiązanie:

Tak, istnieją inne rozwiązania. Jest ich nieskończenie wiele. Twierdzenie 1.10 przepisać. Jest to zbiór wypukły i każdy zbiór zawierający się w nim też jest wypukły.

Jest to zbiór:

Zależność
i
to przepisać twierdzenie 2.4.Zad. 2

Rozwiązaniem zadania PCL jest dendryt

- zdefiniować zbiory:
i

- podać wyniki działań:

Rozwiązanie:

Ad. 1.

Ad. 2.

Zad. 3

Zadanie liniowe. Zrobić standaryzację i rozwiązać algorytmem prymalnym Simplex (2 iteracje czyli 2 tabelki).

Ograniczenia:

Rozwiązanie:

Standaryzacja:

Zastosowanie M-metody:

Tabela 1.

			5	-1	8	0	0	M
		Z0	Z1	Z2	Z3	Z4	Z5	Z6
NB	c^B	5M	2M-5	-M+1	4M-8	-M	0	0
x6	M	5	2	-1	4	-1	0	1
x5	0	6	-1	5	2	0	1	0

Tabela 2.

			5	-1	8	0	0	M
		Z0	Z1	Z2	Z3	Z4	Z5	Z6
NB	c^B	10	-1	-1	0	-2	0	2-M
x3	8	5/4	2/4	-1/4	1	-1/4	0	1/4
x5	0	7/2	-2	11/2	0	1/2	1	-1/2

Zad. 4

Zadanie nieliniowe z ograniczeniami.

Ograniczenia:

Doprowadzić do postaci 7.1.

Zbadać, czy
jest kierunkiem poprawy.

Rozwiązanie:

(strona 111)

Sprowadzenie do postaci (7.1.), przyjmując
.

Korzystam z warunków K-T (7.13.), (7.14.)

nie jest kierunkiem poprawy, ponieważ jest rozwiązaniem optymalnym.

(tylko jak zbadać?)Zadania teoretyczne (10 minut)

1. Jaką złożoność ma algorytm Simplex?

Odp.: Algorytm Simplex ma złożoność
.

2. Do czego służą warunki różniczkowalności w algorytmie K-T?

Odp.: Do wyznaczania punktu siodłowego.

3. Opisać metodę rozwiązania zadania nieliniowego bez ograniczeń.

Odp.:

1)
- obranie punktu początkowego

2)
- wyznaczania kierunku poprawy (wektor rozpoczynający się w x0 i mówi, gdzie się poruszać)

3)
- punkt końcowy

4) sprawdzenie warunku stopu

4. Jak inaczej nazywamy zadanie refleksyjne?

Odp.: Zadania osłabione. (?)

S = S₀

S₁

S₂

S₃

S₄

S₄

S₃

S₂

S₁

S = S₀

---