Silná neomezenost úloh intervalového lineárního programování
Popis výsledku
V článku je charakterizována nutná a postačující podmínka pro silnou neomezenost úlohy intervalového lineárního programování. Jsou také ukázány podmínky pro silnou přípustnost a silnou řešitelnost této ulohy. Nutné a postačující podmínky pro silnou přípustnost, silnou řešitelnost a silnou neomezenost je možné verifikovat ověřením příslušných vlastností pomocí konečných algoritmů. Ověření silné přípustnosti a ověření silné řešitelnosti je NP-těžké. V článku je dokázáno, že také ověření silné neomezenostije NP-těžké. V článku je také dokázáno několik výsledků týkajících se slabé řešitelnosti soustav intervalových lineárních nerovnic.
Klíčová slova
Interval linear inequalitiesInterval linear programmingStrong feasibilityStrong solvabilityStrong unboundednessWeak solvability
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Strong Unboundedness of Interval Linear Programming Problems
Popis výsledku v původním jazyce
A necessary and sufficient condition for strong unboundedness of an interval linear programming problem is described. We also show conditions for strong feasibility and strong solvability of this problem. The necessary and sufficient conditions for strong feasibility, strong solvability and strong unboundedness can be verified by checking the appropriate properties by the finite algorithms. Checking strong feasibility and checking strong solvability are NP-hard. We show that checking strong unboundedness is NP-hard as well. Also several results on weak solvability of interval linear inequalities are presented.
Název v anglickém jazyce
Strong Unboundedness of Interval Linear Programming Problems
Popis výsledku anglicky
A necessary and sufficient condition for strong unboundedness of an interval linear programming problem is described. We also show conditions for strong feasibility and strong solvability of this problem. The necessary and sufficient conditions for strong feasibility, strong solvability and strong unboundedness can be verified by checking the appropriate properties by the finite algorithms. Checking strong feasibility and checking strong solvability are NP-hard. We show that checking strong unboundedness is NP-hard as well. Also several results on weak solvability of interval linear inequalities are presented.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2007
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, SCAN 2006 Conference Post-Proceedings
ISBN
978-0-7695-2821-2
ISSN
—
e-ISSN
—
Počet stran výsledku
4
Strana od-do
—
Název nakladatele
IEEE Computer Society Press
Místo vydání
Los Alamitos
Místo konání akce
Duisburg
Datum konání akce
26. 9. 2006
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—
Základní informace
Druh výsledku
D - Stať ve sborníku
CEP
BA - Obecná matematika
Rok uplatnění
2007