Dualita v úlohách vícekriteriálního programování

Abstract

This diploma thesis comprises of theoretical and practical part. In the theoretical part, we present comparison of di erent approaches to duality in multiobjective programming. We focus on dual problem formulated by Bitran and generalize the assumptions of strong duality theorem for this type of problem. We show that this dual problem is a special case of concept of exact duality developed by Dolecki and that it can be viewed as a generalization of Wolfe type dual problem presented by Nehse. In the practical part, we present algorithm for generating set of weak efficient solutions of concave multiobjective maximization problem with compact convex set of feasible solutions. This algorithm is based on construction of scalarized problem to the original multiobjective problem and makes use of the properties of its dual problem. We describe implementation of this algorithm and illustrate its usage on an example.

Tato diplomová práce se skládá z teoretické a praktické části. V teoretické části jsou porovnány různé přístupy k dualitě ve vícekriteriálním programování. Zaměříme se na duální úlohu formulovanou Bitranem a zobecníme předpoklady, za kterých pro tuto duální úlohu platí věta o silné dualitě. Ukážeme, že tuto duální úlohu lze získat jako speciální případ schématu exaktní duality, které navrhl Dolecki, a že na ni lze nahlížet jako na zobecnění duální úlohy Wolfeho typu, kterou popisuje Nehse. V praktické části uvádíme algoritmus pro výpočet množiny slabě effi cientních řešení úlohy konkávní vícekriteriální maximalizace, jejíž množina přípustných řešení je kompaktní a konvexní. Tento algoritmus je založen na konstrukci skalárního ekvivalentu k původní vícekriteriální úloze a využívá vlastností jemu příslušné duální úlohy. Popíšeme implementaci algoritmu a její použití ilustrujeme na příkladu.