Pedagogická dokumentácia predmetu
pre školský rok 2002/2003
Číslo predmetu:
2287
|
Názov:
Aplikovaná matematika
|
Gestorujúca katedra:
MDG
|
Študijný odbor:
Realizácia stavieb
|
Ročník: 5.
|
Semester: 10.
|
Rozsah výučby: 3/2 k
|
Forma výučby: P / C 20
|
Typ predmetu:
povinný
|
Spôsob ukončenia:
klasifikovaný zápočet
|
Kreditová hodnota: 4
|
|
Kľúčové slová:
Lineárne programovanie, toky v sieťach, dualita,
celočíselné lineárne programovanie, analýza projektu.
Anotácia:
Lineárne programovanie, simplexový algoritmus,
úloha o maximálnom toku a lineárne programovanie, dualita, tieňové ceny,
minimálny rez v sieti, analýza senzitivity, analýza projektu,
celočíselné lineárne programovanie.
Harmonogram prednášok:
- týždeň:
Lineárne programovanie: Úloha lineárneho programovania,
príklady na lineárne programovanie, riešenie úlohy lineárneho programovania
graficky (prípad dvoch premenných), typy riešení úlohy lineárneho
programovania, prevod všeobecnej úlohy lineárneho programovania na kánonický
tvar.
- týždeň:
Simplexový algoritmus: Simplexový algoritmus pre štandardnú
maximalizačnú úlohu lineárneho programovania, riešenie všeobecnej úlohy
lineárneho programovania dvojfázovým simplexovým algoritmom, rozpoznanie
kedy má úloha nekonečne veľa riešení, diskusia degenerovanosti úlohy.
- týždeň:
Toky v sieťach: Polocesty, zväčšujúci tok, formulácia úlohy o
maximálnom toku ako úlohy lineárneho programovania, algoritmus na hľadanie
maximálneho toku v sieti, variácie úlohy o maximálnom toku (viac zdrojov,
ohraničenia na prietoky vrcholmi, dolné ohraničenia na prietok šípmi).
- týždeň:
Dualita: Duálna úloha k úlohe lineárneho programovania, tieňové
ceny, slabá veta o dualite, úloha duálna k úlohe o maximálnom toku, hľadanie
minimálneho rezu pomocou algoritmu na hľadanie maximálneho toku, diskusia o
mini-maxových úlohách, exponenciálna zložitosť simplexového algoritmu a
degenerácia úlohy, duálny simplexový algoritmus.
- týždeň:
Analýza projektu: Prehľadávanie do šírky, úloha o najdlhšej
ceste a zistenie dĺžky trvania projektu, rezervy činnosti, náklady na
skrátenie projektu, nákladová krivka.
- týždeň:
Celočíselné lineárne programovanie: Úloha celočíselného
lineárneho programovania, duálny simplexový algoritmus, orezávacia metóda
hľadania celočíselného riešenia, metóda vetvenia.
- týždeň:
Analýza senzitivity: Zmena koeficientu pravej strany (s
diskusiou o tieňových cenách), zmena koeficientu účelovej funkcie, zmena
koeficientu v stĺpci nebázickej premennej, pridanie novej činnosti.
Semester má len 7 týždňov.
Harmonogram cvičení:
- týždeň:
Lineárne programovanie: Zostavenie úlohy lineárneho
programovania pre príklady z praxe, riešenie úlohy lineárneho programovania
graficky (prípad dvoch premenných), prevod všeobecnej úlohy lineárneho
programovania na kánonický tvar.
- týždeň:
Simplexový algoritmus: Simplexový algoritmus pre štandardnú
maximalizačnú úlohu lineárneho programovania, riešenie všeobecnej úlohy
lineárneho programovania dvojfázovým simplexovým algoritmom.
- týždeň:
Toky v sieťach: Formulácia úlohy o maximálnom toku ako úlohy
lineárneho programovania, algoritmus na hľadanie maximálneho toku v sieti,
variácie úlohy o maximálnom toku (viac zdrojov, ohraničenia na prietoky
vrcholmi, dolné ohraničenia na prietok šípmi).
- týždeň:
Dualita: Určovanie tieňových cien, duálny simplexový
algoritmus, hľadanie minimálneho rezu pomocou algoritmu na hľadanie
maximálneho toku.
- týždeň:
Analýza projektu: Zistenie dĺžky trvania projektu, náklady na
skrátenie projektu, nákladová krivka.
- týždeň:
Celočíselné lineárne programovanie: Orezávacia metóda
hľadania celočíselného riešenia, metóda vetvenia.
- týždeň:
Analýza senzitivity: Zmena koeficientu pravej strany,
zmena koeficientu účelovej funkcie, zmena koeficientu v stĺpci nebázickej
premennej, pridanie novej činnosti.
Semester má len 7 týždňov.
Nadväznosti: Matematika I.
Podmienky absolvovania:
Klasifikovaný zápočet: Vypracovanie a odovzdanie projektu, ktorý bude
študentom zadávaný individuálne. V prípade závažných nedostatkov v projekte
je treba projekt prepracovať podľa pripomienok tak, aby bol vyriešený
správne.
Literatúra:
prednášky
Plesník J.: Grafové algoritmy, Alfa, Bratislava, 1987.
Toma V.: Teória a algoritmy lineárneho programovania, matematicko-fyzikálna
fakulta, Bratislava 1983.
Winston W.L.: Operation research, 2nd ed, PWS-Kent Publishing
company, Belmont, California, 1991.