Przedmiot: PROGRAMOWANIE MATEMATYCZNE

Prowadzący: dr Tadeusz Miłosz, prof. dr hab. Jerzy Śleszyński,

Rodzaj i wymiar zajęć: wykład dla studiów dziennych (30 godzin)

Cel i program zajęć:

Zasadniczym celem wykładu jest przedstawienie możliwości sformalizowanego podejścia do prostych i nieco bardziej złożonych problemów decyzyjnych i ekonomicznych. Przedstawiane są matematyczne podstawy takiego podejścia zaczerpnięte z analizy matematycznej, algebry i optymalizacji. Celem zajęć jest zapoznanie studentów z konkretnymi metodami programowania matematycznego przydatnymi do rozwiązywania problemów decyzyjnych o charakterze ekonomicznym. Pierwsza część zajęć poświęcona jest programowaniu nieliniowemu i ma charakter wybitnie teoretyczny.

Druga część zajęć poświęcona jest programowaniu liniowemu. Wykład dostarcza opisu metod i algorytmów, które są wykorzystywane do formalizowania i rozwiązywania problemów decyzyjnych. Celem tej części wykładu jest również przekazanie umiejętności zastosowania do danego problemu właściwego modelu decyzyjnego, posłużenia się odpowiednim algorytmem rozwiązującym, a także zinterpretowania otrzymanego rozwiązania. Wykład uzupełniają ćwiczenia, których zaliczenie jest warunkiem przystąpienia do egzaminu. Ponadto, ćwiczenia dotyczące części liniowej uzupełnione są zajęciami w pracowni informatycznej (pakiet wspomagania podejmowania decyzji: „Decision”).

Tematy wykładów:

1. Zadanie ekstremalne bez ograniczeń:

- warunki konieczne i dostateczne pierwszego i drugiego rzędu,

- kryterium Sylvestera,

- twierdzenie Weierstrassa,

- schemat rozwiązywania zadań.

2. Zadanie ekstremalne z ograniczeniami równościowymi:

- sformułowanie zadania,

- warunki konieczne pierwszego rzędu (zasada Lagrange’a),

- warunek konieczny drugiego rzędu,

- warunek dostateczny drugiego rzędu,

- schemat rozwiązywania zadania.

3. Zadanie ekstremalne z ograniczeniami równościowymi i nierównościowymi:

- sformułowanie zadania,

- warunki konieczne pierwszego rzędu (zasada Lagrange’a),

- warunek konieczny drugiego rzędu,

- warunek dostateczny drugiego rzędu,

- schemat rozwiązywania zadania.

4. Elementy analizy wypukłej:

- zbiory wypukłe,

- stożki wypukłe,

- wielościenne zbiory wypukłe,

- funkcje wypukłe,

- twierdzenia o oddzielaniu.

5. Funkcje sprzężone:

- definicja funkcji sprzężonej,

- twierdzenie Fenchela-Moreau,

- zadanie dualne.

6. Subróżniczki:

- definicja subróżniczki,

- twierdzenie Moreau-Rockafellara,

- twierdzenie Dubowickiego-Miliutina,

- zadanie wypukłe.

7. Zadanie programowania wypukłego:

- twierdzenie Kuhna-Tuckera,

- warunki różniczkowe Kuhna-Tuckera,

- schemat rozwiązywania zadania.

8. Podstawy programowania liniowego (PL):

- rozwiązywanie układu równań liniowych,

- liniowa niezależność wektorów,

- rozwiązanie bazowe,

- warunki poszukiwania optimum zadania PL,

- jedno- i wielokryterialne modele programowania liniowego.

9. Ogólne sformułowanie zadania PL:

- funkcja kryterium i warunki ograniczające,

- standardowa i klasyczne postaci zadania PL,

- zmienne decyzyjne, pomocnicze i sztuczne zadania PL,

- rozwiązanie dopuszczalne i optymalne.

10. Zagadnienie transportowe:

- interpretacja problemu,

- formalna postać modelu,

- algorytm transportowy,

- niezbilansowane zadanie transportowe,

- zdegenerowane rozwiązanie bazowe.

11. Rozwinięcia zadania transportowego i zagadnienia sieciowe:

- problem tras niedopuszczalnych,

- zagadnienie wieloetapowe,

- problem przydziału,

- maksymalny przepływ w sieci,

- problem komiwojażera,

- metoda ścieżki krytycznej.

12. Podstawy metody sympleks:

- pierwsze dopuszczalne rozwiązanie bazowe,

- badanie optymalności rozwiązań,

- tablica i algorytm metody sympleks,

- graficzna interpretacja metody sympleks.

13. Zagadnienie dualności w PL:

- para symetrycznych zadań PL,

- rozwiązania pary zadań dualnych,

- zmienne i ograniczenia pary zadań dualnych,

- warunki Dantziga‑Ordena,

- ekonomiczna interpretacja zmiennych dualnych.

14. Analiza postoptymalna:

- graficzna interpretacja analizy postoptymalnej,

- ekonomiczna interpretacja problemu,

- parametryczne zadanie PL,

- metoda rozwiązywania zadania PL z parametrem.

Literatura (podkreślona pozycja podstawowa):

Chiang A.C., 1994. Podstawy ekonomii matematycznej. PWE, Warszawa.

Dubnicki W., Zorychta K., 1972. Metody programowania wypukłego. Wydawnictwa Uniwersytetu Warszawskiego, Warszawa.

Gass S.I., 1976. Programowanie liniowe. PWN, Warszawa.

Grabowski W., 1980. Programowanie matematyczne. PWE, Warszawa.

Ignasiak E. (red.), 2001. Badania operacyjne. PWE, Warszawa.

Miłosz T., 2004. Skrypt do zajęć z programowania matematycznego. Uniwersytet Warszawski, Wydział Nauk Ekonomicznych, Warszawa (w druku).

Moore J.H., Weatherford L.R., 2001. Decision Modeling with Microsoft® Excel. Prentice Hall, Upper Saddle River.

Nykowski I., 1980. Programowanie liniowe. PWE, Warszawa.

Taylor III B.W., 2001. Introduction to Management Science. Prentice Hall, Upper Saddle River.

Wagner H.M., 1980. Badania operacyjne. PWE, Warszawa.

Egzamin: przedmiot kończy się pisemnym egzaminem, na który składają się cztery zadania obejmujące materiał wybrany z wykładu i przerobiony na ćwiczeniach.