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:

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. 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.
  6. 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.
  7. 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.

  8. Semester má len 7 týždňov.

 

Harmonogram cvičení:

  1. 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.
  2. 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.
  3. 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).
  4. 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.
  5. týždeň: Analýza projektu: Zistenie dĺžky trvania projektu, náklady na skrátenie projektu, nákladová krivka.
  6. týždeň: Celočíselné lineárne programovanie: Orezávacia metóda hľadania celočíselného riešenia, metóda vetvenia.
  7. týždeň: Analýza senzitivity: Zmena koeficientu pravej strany, zmena koeficientu účelovej funkcie, zmena koeficientu v stĺpci nebázickej premennej, pridanie novej činnosti.

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