Optymalizacja liniowa

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)

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.