Publikace na Matematicko-fyzikální fakulta |
2008
Abstrakt
Pro danou úlohu lineárního programování představujeme efektivní algorithmus na počítání tolerancí pro vstupní data. Tolerancemi rozumíme takové intervaly, že vstupní hodnoty úlohy se mohou nezávisle a simultánně pohybovat v rámci svých intervalů tak, že optimální hodnota lineárního programu nepřekročí danou horní a dolní mez.
Novým přínosem tohoto postupu je možnost uvažovat některé vybrané, ale třeba i všechny vstupní hodnoty najednou. Časová složitost algoritmu je polynomiální. Ačkoli vypočtené tolerance nejsou optimální (mj. díky závislostem mezi parametry), výsledky jsou uspokojivé.
Tuto metodu ilustrujeme na problému výběru portfolia, modelovaného pro naše účely jako lineární program.