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 2 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.