Úvod do podnikových informačných systémov VO WS 2008 PDF na stiahnutie zadarmo
Úvod do podnikovej informatiky VO ZS 2008/2009 Riadenie dátových modelov Wilfried Grossmann
Na určenie optimálneho správania sa často používajú matematické modely. Na tento účel sa definuje objektívna funkcia, ktorá závisí od rozhodovacích premenných. Pre tieto rozhodovacie premenné sa zvyčajne musia brať do úvahy obmedzenia.
Príklad problému s diétou Príklad: problému s diétou Na výživu potrebujete určité množstvo dvoch vitamínov A a B, ktoré sú obsiahnuté v živinách a v ovocí a mlieku. Ovocie a mlieko majú určitú jednotkovú cenu. Koľko jednotiek ovocia a mlieka by mal človek skonzumovať denne, aby boli náklady čo najnižšie?
Údaje napríklad pre kontrolu Príklad problému so stravou Ovocie Mlieko Minimálna denná potreba Vitamín A 2 4 40 B 4 2 50 Náklady na jednotku Obsah vitamínu na jednotku 3 2,5
Príklad problému s diétou Formulácia problému s diétou ako úlohy Premenná rozhodovania x = jednotky spotrebovaného ovocia y = jednotky spotrebovaného mlieka
Príklad problému s diétou Pretože existujú určité minimálne požiadavky na množstvo vitamínov, tieto množstvá musia spĺňať nasledujúce podmienky 2x + 4x + 4 y 2 y x 0, y 40 50 0
Príklad problému s diétou Množstvá ovocia a mlieka, ktoré spĺňajú tieto podmienky, sa nazývajú Prípustný rozsah Grafické znázornenie 30 25 20 Vitamín B 4x + 2y = 50 Mlieko 15 10 Prípustný rozsah 5 0 0 5 10 15 20 25 Ovocie Vitamín A: 2x + 4y = 40
Príklad problému so stravou Objektívna funkcia vyplýva z nákladov na spotrebované živiny z = 3 x + 2. 5 y Tieto náklady by mali byť minimálne
Príklad problému s diétou Hľadáme riešenie nasledujúceho problému min z = 2x + 4x + 4 y 2 y x 0, y 3x 40 50 0 + 2,5r
Príklad problému so stravou Grafické znázornenie s 30 peňažnými jednotkami Náklady 30 Mlieko 25 20 15 10 5 0 Vitamín B 4x + 2y = 50 Cieľová funkcia: Náklady Prípustný rozsah 0 5 10 15 20 25 Ovocie Vitamín A: 2x + 4y = 40 Tieto náklady zjavne nevedú k prípustnému riešeniu
Príklad problému so stravou grafické znázornenie s 50 peňažnými jednotkami 30 mlieka 25 20 15 10 5 0 vitamínu B 4x + 2y = 50 objektívna funkcia: náklady prípustný rozsah 0 5 10 15 20 25 ovocie vitamín A: 2x + 4y = 40 Tieto náklady majú za následok prípustné riešenie, môžeme ale nájdi lepšie riešenia
Príklad problému s diétou Optimálne riešenie s hodnotou 42,5 peňažných jednotiek s 10 jednotkami ovocia a 5 jednotkami mlieka 30 mlieka 25 20 15 10 5 0 Vitamín B 4x + 2y = 50 Cieľová funkcia: náklady Prípustný rozsah 0 5 10 15 20 25 Ovocie VitamínA: 2x + 4r = 40
Lineárne programovanie, všeobecné problémy ako tento príklad sa nazývajú lineárne programy Otázky: Za akých podmienok možno otázku formulovať ako lineárny program? Proporcionalita, aditívnosť, deliteľnosť, rozhodnosť
Lineárne programovanie, všeobecné Čo je povolený rozsah, ak existujú viac ako dve premenné? Konvexný mnohosten Je to vždy tak, že riešenie sa predpokladá v rohu? Áno, ak existuje riešenie Ako môžete všeobecne vypočítať toto riešenie? Rohy zodpovedajú riešeniam lineárnych rovníc. Potrebujeme efektívne metódy na nájdenie optimálneho rohu
Lineárne programovanie, citlivosť Ako sa zmení riešenie, keď zmeníme cenu produktu? Príklad: Riešenie, ak náklady na mlieko na jednotku klesnú na 1,2 30 Mlieko 25 20 15 10 5 0 Vitamín B 4x + 2y = 50 Cieľová funkcia: Náklady Prípustný rozsah 0 5 10 15 20 25 Ovocie Vitamín A: 2x + 4y = 40
Lineárne programovanie, citlivosť Ako sa zmení riešenie, keď zmeníme potrebu vitamínov? Príklad: Riešenie, ak sa minimálna potreba vitamínu A zvýši na 60 jednotiek. Náklady sú potom 49 peňažných jednotiek 30 25 20 vitamín B 4x + 2y = 50 mlieko 15 prípustný rozsah 10 objektívna funkcia: náklady 5 vitamín A: 0 2x + 4y = 40 0 5 10 15 20 25 30 35 ovocie
Lineárne programovanie, dualita Úvaha o probléme z pohľadu predajcu ovocia a mlieka: Zákazník skutočne chce vitamíny a za vitamíny platí a mlieko?
Lineárne programovanie, dualita Táto otázka vedie k nasledujúcemu problému: max z = 40x + 2x + 4 y 3 4x + 2 y 2,5 x 0, y 0 50y Táto úloha sa nazýva dvojitá úloha
Dualita lineárneho programovania Riešenie poskytuje cenu 1/3 za jednotku pre vitamín A a cenu 7/12 za jednotku pre vitamín B. Hodnota riešenia je opäť 42,5. Existuje teda rovnováha medzi nákladmi kupujúceho a príjmom predávajúceho.
Lineárne programovanie, dualita Grafické znázornenie 2 Cena vitamínu B 1,5 1 0,5 0 Prípustný rozsah Cena mlieka 4x + 2y = 2,5 Cieľová funkcia: Výdatnosť 0 0,5 1 1,5 2 Cena vitamínu A Cena ovocia: 2x + 4y = 3
Celé číslo lineárne programovanie Môže sa metóda použiť aj vtedy, keď všetky hodnoty musia byť celé čísla? Nie! Príklad: nájdite riešenie v celých číslach max z = 11x 10x y 40 x + y 20 x 0, y 0 y
Celé číslo lineárne programovanie Optimálne riešenie: x = 5, y = 10 s hodnotou 45 Riešenie lineárneho programu: x = 5,45, y = 14. 54, hodnota 45,45 Ďalšie riešenie celého čísla: x = 5, y = 15, hodnota 40 30 25 y 20 15 10 5 10x-y = 40 Prípustný rozsah Cieľová funkcia: Výhoda x + y = 20 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 x