Monge property for interval matrices

• Název práce v češtině: Mongeova vlastnost pro intervalové matice
• Název v anglickém jazyce: Monge property for interval matrices
• Klíčová slova: Intervalová analýza, Silná Mongeovost, Slabá Mongeovost, Problém obchodního cestujícího
• Klíčová slova anglicky: Interval analysis, Strong Monge, Weak Monge, Travelling salesman problem
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: prof. Mgr. Milan Hladík, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 30.10.2018
• Datum zadání: 30.10.2018
• Datum potvrzení stud. oddělením: 06.11.2018
• Datum a čas obhajoby: 27.06.2019 09:00
• Datum odevzdání elektronické podoby: 16.05.2019
• Datum odevzdání tištěné podoby: 17.05.2019
• Datum proběhlé obhajoby: 27.06.2019
• Oponenti: prof. RNDr. Karel Zimmermann, DrSc.

Zásady pro vypracování

- Vyjádření různých podmínek pro silnou Mongeovu vlastnost intervalové matice
- Volitelně podmínky pro slabou Mongeovu vlastnost intervalové matice
- Analýza algoritmických aspektů výše zmíněných podmínek
- Analýza operací zachovávajících Mongeovu vlastnost intervalové matice
- Prozkoumání použití pro optimalizační úlohy s nepřesnými daty

Seznam odborné literatury

[1] R.E. Burkard, B. Klinz, R. Rudolf, Perspectives of Monge properties in optimization, Discrete Appl. Math., 70, 95-161, 1996.
[2] M. Fiedler. Remarks on Monge matrices. Mathematica Bohemica, 127(1), 27-32, 2002.
[3] M. Fiedler et al., eds., Linear Optimization Problems with Inexact Data, Springer, New York, 2006.
[4] M. Hladík. Weak and strong solvability of interval linear systems of equations and inequalities. Linear Algebra Appl., 438(11):4156-4165, 2013.

Předběžná náplň práce

Mongeova matice je definovaná jednoduchou podmínkou a hraje důležitou roli v několika problémech. Například v dopravních úlohách charakterizuje velice efektivně řešitelné případy. Cílem práce je zobecnit tyto matice na intervalové v silném smyslu (všechny jsou Mongeovy) a slabém smyslu (aspoň jedna je Mongeova). Bude nás zajímat charakterizace těchto vlastností, jejich složitost a postačující/nutné podmínky.