Geometrie intervalových lineárních soustav
Geometry of interval linear systems
bachelor thesis (DEFENDED)
![Document thumbnail](/bitstream/handle/20.500.11956/184380/thumbnail.png?sequence=7&isAllowed=y)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/184380Identifiers
Study Information System: 257147
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Rada, Miroslav
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Computer Science with specialisation in General Computer Science
Department
Department of Applied Mathematics
Date of defense
7. 9. 2023
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
Czech
Grade
Excellent
Keywords (Czech)
intervalové lineární systémy|polyedry|geometrie|konvexita|konvexní obalKeywords (English)
interval linear systems|polyhedra|geometry|convexity|convex hullIntervalové lineární systémy rovnic a nerovnic jsou lineární systémy, kde reálné prvky vektorů a matic nahradíme uzavřenými intervaly reálných čísel. Množiny řešení těchto sys- témů mají zajímavé vlastnosti, a to zejména, že jsou sjednoceními exponenciálně mnoha polyedrů. Toto činí řešení mnoha problémů těžkým, zatímco na druhou stranu mají mno- žiny formu, která je intuitivně přístupná pro analýzu. Tato práce se zabývá studováním geometrie těchto množin. Začneme rekapitulací jejich známých vlastností, jako jsou ome- zenost a souvislost. V prvé řadě se ale budeme soustředit na podmínky konvexity a na charakterizaci konvexního obalu, kde je obojí známé pro speciální případ systémů s re- gulárními intervalovými maticemi. S využitím teorie polyedrů tyto výsledky zobecníme, zejména pro obecné systémy intervalových lineárních nerovnic. Ukážeme ilustrativní pří- klady, některé sloužící jako protipříklady v případech, kde zobecnění nejsou možná. 1
Interval linear systems of equalities and inequalities are linear systems, where the real numbered entries of the vectors and matrices are replaced with closed intervals of real numbers. The sets of solutions to these systems have interesting properties, mainly that they are unions of exponentially many convex polyhedra. This makes solving many problems hard, while on the other hand, the solution sets have a form that is convenient to analyze. This thesis deals with studying the geometry of such sets. We will begin by reviewing known properties of these sets, such as boundedness and connectedness. But mostly, we will focus on the conditions for convexity and the characterization of the convex hull, which are both known for the special case of systems with invertible interval matrices. Using polyhedral theory, we will broaden these results, mostly to general systems of interval linear inequalities. We will present illustrative examples, some serving as counter-examples in cases where generalizations are not possible. 1