Optymalizacja I

fakultatywne

Na wykładzie zostaną omówione metody sympleks ( w tym również dwufazowa i dualna), zadanie transportowe, zadania całkowitoliczbowe oraz aspekty geometryczne.

Zadanie programowania liniowego. Przykłady praktycznych modeli optymalizacji liniowej. Zadanie standardowe, zbiór dopuszczalny, rozwiązania optymalne. (1 wykład)

Podstawowe wiadomości o zbiorach wypukłych. Geometria zbioru dopuszczalnego, wielościany wypukłe. Punkty, kierunki i promienie ekstremalne, procedury ich generowania. Uwypuklenie zbioru wierzchołków

i promieni ekstremalnych. Twierdzenie Caratheodory'ego. Lemat Farkasa. (3 wykłady)

Zadanie kanoniczne, tablica sympleks, bazowe rozwiązanie dopuszczalne, dopuszczalność i optymalność tablicy. Pierwotna metoda sympleks. Różne wersje dwufazowej metody sympleks. Metoda dużego M. (3 wykłady)

Zadanie dualne. Twierdzenia o dualności. Warunki równowagi. Interpretacja ekonomiczna dualności, ceny dualne. Wrażliwość zadania. (2 wykłady)

Dualna metoda sympleks, jej ograniczenia i zastosowania. (1 wykład)

Grafy i przepływy w sieciach. (2 wykłady)

Zagadnienie transportu. (1 wykład)

Metoda podziału i ograniczeń. Zagadnienia całkowitoliczbowe. (2 wykłady)

M.S. Bazaraa, J.J. Jarvis, H.D. Sherali, Linear Programming and Network Flows. John Wiley and Sons, 1990.

S. Gass, Programowanie liniowe. PWN, Warszawa 1980.

Student

1. zna podstawowe pojęcia przestrzeni metrycznej Euklidesowej, przestrzeni liniowej i afinicznej;

2. zna pojęcia półprzestrzeni, wielościanu i wielościanu uogólnionego. Potrafi udowodnić, że są to podzbiory wypukłe i domknięte;

3. umie budować modele matematyczne typowych problemów optymalizacji liniowych i zapisywać je jako badanie ekstremów funkcji liniowych na wielościanach uogólnionych;

3. umie posługiwać się algorytmami metody sympleks: prostym, dwufazowym i dualnym. Wie jakie mogą być wyniki i kiedy jaki stosować;

4. zna teorię dualności: Potrafi opisywać wielościany uogólnione zarówno jako przecięcia półprzestrzeni jak i uwypuklenie punktów i prostych. Potrafi zadaniu programowania liniowego przyporządkować zadanie dualne i opisywać punkty optymalne jednego z zadań, znając rozwiązanie drugiego;

5. potrafi rozwiązywać zadania programowania liniowego w liczbach całkowitych. Zna metodę odcięć, w szczególności odcięcie Gomorego;

6. zna metodę rozgałęzień i odcięć ( B&B ). Umie stosować podziały Dakina;

7. zna kilka specyficznych algorytmów jak algorytm obliczania optymalnego przepływu w sieciach, zagadnienie transportowe czy problem przyporządkowania.