The Asymptotic Integer Algorithm
Thesis title: | Asymptotický celočíselný algortimus |
---|---|
Author: | Murinová, Michaela |
Thesis type: | Bakalářská práce |
Supervisor: | Kalčevová, Jana |
Opponents: | Jablonský, Josef |
Thesis language: | Česky |
Abstract: | Tato práce se zabývá úlohami celočíselného programování a metodami pro jejich řešení. Nejznámějšími metodami jsou metoda větví a mezí a Gomoryho metoda řezných nadrovin. Cílem mé práce je přiblížit čtenářům alternativní metodu asymptotického celočíselného algoritmu. Tato metoda je založena na podobné myšlence jako metoda zaokrouhlování. Základní myšlenkou je dovolit nebazickým proměnným nabývat nenulové hodnoty. Při grafickém znázornění dochází k oříznutí množiny přípustných (neceločíselných) řešení, přičemž ovšem nesmí být ztraceno žádné celočíselné řešení. Tato metoda je představena na příkladu, který je součástí hlavní kapitoly, a dále na vlastním příkladu ve třetí kapitole. |
Keywords: | algoritmus nejkratší cesty; relaxed problem; group problem; celočíselné programování |
Thesis title: | The Asymptotic Integer Algorithm |
---|---|
Author: | Murinová, Michaela |
Thesis type: | Bachelor thesis |
Supervisor: | Kalčevová, Jana |
Opponents: | Jablonský, Josef |
Thesis language: | Česky |
Abstract: | This work is dealing with the tasks of integer programming and with the methods for their solving. The most famous methods are "branch and bounds method" and the Gomory's method of cut algorithms. The purpose of this work is to get readers acquainted with the alternative method of asymptotic integer algorithm. This method is based on the similar idea as the rounding procedure. The main idea is to enable the nonbasic variables gain a non-zero value. It leads to cutting the continuous (noninteger) solution space on the graphics illustration, while no integer solution should be lost. This method is presented on the example, which is a part of the main chapter and furthermore on its own example in the third chapter. |
Keywords: | group problem; relaxed problem; integer programming; shortest-route algorithm |
Information about study
Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
---|---|
Type of study programme: | Bakalářský studijní program |
Assigned degree: | Bc. |
Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
Faculty: | Faculty of Informatics and Statistics |
Department: | Department of Econometrics |
Information on submission and defense
Date of assignment: | 15. 4. 2010 |
---|---|
Date of submission: | 17. 5. 2010 |
Date of defense: | 8. 6. 2010 |
Identifier in the InSIS system: | https://insis.vse.cz/zp/26207/podrobnosti |