Solution of Selected Graph Theory Problems in MPL for Windows

Úloha čínského listonoše a úloha obchodního cestujícího jsou předmětem této práce. Tyto úlohy patří do matematického odvětví zvaného teorie grafů. Představené a definované jsou eulerovské grafy a eulerovské cykly, které slouží k řešení úlohy čínského listonoše. Další část této práce se zabývá hamiltonovými cykly, které tvoří základ úlohy obchodního cestujícího. Obě úlohy jsou v této práci formulované a jejich teoretické řešení je představené za pomoci původních algoritmů. Cílem této práce je dané algoritmy řešit s použitím matematických modelů zapsaných v optimalizačním systéme Mathematical Programming Language (MPL). Grafy představující konkrétní úlohy jsou ve formě matic zadané do tabulkového kalkulátoru Microsoft Excel, kde sú dále transformované za pomocí maker, kterých zdrojový kód je zapsaný ve Visual Basic for Applications (VBA). Za pomoci knižnice OptiMax je možné přímé propojení zdrojového kódu z VBA s modely v MPL, kterých řešení se opět zapíše do MS Excel.Vzpomenuté algoritmy jsou úspěšně implementované a přichází s optimálním řešením úlohy čínského listonoše i úlohy obchodného cestujícího.

The Chinese postman problem and the travelling salesman problem are both objects of this thesis. These problems belong to a branch of mathematics called graph theory. Presented and defined are Eulerian graphs and Eulerian cycles that are used to solve the Chinese postman problem. The other part of this thesis is focused on Hamiltonian cycles. They form the basis of the travelling salesman problem. Both problems formulated in this work and their theoretical solutions are presented with the aid of original algorithms. The aim of this thesis is to solve the given algorithms using mathematical models written in the optimization system Mathematical Programming Language (MPL). Graphs representing specific problems are introduced in form of matrices in a Microsoft Excel spreadsheet where they are further transformed using macros whose source code is written in Visual Basic for Applications (VBA). With the help of the OptiMax library, it is possible to directly link the source code from VBA to models in MPL, the solution of which is written back to MS Excel.These algorithms are successfully implemented and result in the optimal solution of the Chinese postman problem and the travelling salesman problem.