Tato diplomová práce se věnuje statickým lokačním a lokačně-cenovým optimalizačním úlohám. Cílem těchto úloh je dle stanoveného kritéria optimalizovat umístění jednotlivých zařízení, případně i jejich prodejní ceny. První část práce se zabývá podrobným popisem vybraných známých nekompetitivních i kompetitivních lokačních a lokačně-cenových úloh. Věnuje se také úvodu do problematiky Voroného diagramů. Zbývající část práce je vlastním přínosem autora a věnuje se novým formulacím a modifikacím kompetitivních lokačních a lokačně-cenových optimalizačních úloh. Pro úlohy na grafu je zavedena volba prodejní ceny a možnost rovnoměrného dělení poptávky uzlu mezi více konkurenčních zařízení. Jsou předloženy nové formulace úloh smíšeně-celočíselného lineárního programování a rovněž také exaktní algoritmy pro řešení týchž úloh – včetně porovnání dob jejich běhu. Dále je odvozena úloha matematického programování pro kompetitivní spojitou úlohu v rovině. Nakonec jsou pro kompetitivní spojitou úlohu v rovině s diskrétní poptávkou formulovány úlohy smíšeně-celočíselného nelineárního programování a exaktní algoritmus i heuristika spočívající v řešení úloh konvexního programování – opět včetně porovnání dob jejich běhu.
This thesis focuses on static location and location–price optimization problems. The goal of these problems is to optimize the placement of individual facilities, and possibly also their selling prices, according to a given criterion. The first part of the thesis is focused on a detailed description of selected non-competitive and competitive location and location–price problems, as well as an introduction to the topic of Voronoi Diagrams. The remaining part of the thesis represents the author’s original contribution and deals with new formulations and modifications of competitive location and location–price optimization problems. For problems defined on a graph, the option to set a selling price is introduced, along with the possibility of uniformly distributing a node's demand among multiple competing facilities. New formulations using mixed-integer linear programming and new exact algorithms are presented – including comparisons of their computation times. Furthermore, a mathematical programming model is derived for the competitive continuous problem in the plane. Finally, for the continuous competitive problem in the plane with discrete demand, mixed-integer nonlinear programming models are formulated, as well as both an exact algorithm and a heuristic method based on solving convex programming problems – again, including comparisons of their computation times.
Klíčová slova:
optimization; mathematical programming; algorithm; location problem; location-price problem