LINEARNO PROGRAMIRANJE M020 (2+1+1 ) 4 ECTS BODA
| CILJEVI KOLEGIJA | Upoznati studente s modeliranjem, rješavanjem i interpretiranjem realnih problema koji se mogu svesti na problem linearnog programiranja. Obraditi i analizirati poznate numeričke metode za rješavanje problema linearnog programiranja kao i dati odgovarajuće geometrijske interpretacije. Pri tome se koriste različite mogućnosti programskog paketa Mathematica. |
| POTREBNO PREDZNANJE | Preddiplomski studij matematike |
| SADRŽAJ KOLEGIJA | |
| SADRŽAJ KOLEGIJA | 1. Uvodni dio: Definicija problema linearnog programiranja.
Primjeri problema linearnog programiranja. Po dijelovima linearna konveksna funkcija. Grafičko rješavanje dvodimenzionalnog problema linearnog programiranja. 2. Geometrija linearnog programiranja: Poliedar i konveksni skupovi. Ekstremne točke, vrhovi i bazično dopustivo rješenje. Poliedar u standradnom obliku. Degeneracija. Egzistencija i optimalnost ekstremne točke 3. Simpleks metoda: Uvjet optimalosti. Izvod i implementacija simpleks metode. Blandovo pravilo. Određivanje početnog bazičnog rješenje. Analiza složenosti simpleks metode. 4. Dualni problem: Dualni problem. Teoremi slabe i jake dualnosti. Farkaševa lema i linearne nejednakosti. Teoremi i separaciji. Dualna simpleks metoda. 5. Analiza osjetljivosti: Lokalna analiza osjetljivosti. Globalna analiza osjetljivosti. Interpretacija. 6. Elipsoidalna metoda: Geometrijsko značenje i složenost. |
| IZVOĐENJE KOLEGIJA | Predavanja, vježbe i seminari su obavezni. |
| VREDNOVANJE ZNANJA | |
|
Ispit se sastoji od pismenog i usmenog dijela, a polaže se
nakon odslušanih predavanja i obavljenih vježbi i seminara. Tijekom semestra studenti mogu polagati 3 kolokvija i redovito rješavati domaće zadaće, koji zamjenjuju pismeni dio ispita. |
|
1. D. Bertsimas, J. N. Tsitsiklis, Introduction to Linear Optimization, Athena
Scientific, 1997
LITERATURA KOJA SE PREPORUČUJE
1. K. G. Murty, Linear and Combinatorial Programming, John Wiley & Sons,
Inc., 1983.
2. L. Neralić, Uvod u matematičko programiranje 1, Element, Zagreb, 2003.
3. G. Sierksma, Linear and Integer Programming, Marcel Dekker, Inc., Nemhauser,
1999.
4. D. Kincaid, W. Cheney, Numerical Analysis, Brooks/Cole Publishing Company,
New York, 1996.
5. A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons,
Inc., NY, SAD, 1999.