Tolerance vah ve vícekriteriálním lineárním programování

Abstract

This thesis deals with the computation of the maximal tolerance of weight in scalariza- tion problems of multiobjective linear programming. The maximal tolerance is defined as the largest feasible perturbation of scalarization weights for which a given solution remains efficient. Attention is paid to methods based on a conic characterization of optimality using the tangent cone and its extreme directions. For the case of a fixed scalarization, a formula for computing the maximal tolerance is presented. Furthermore, a method for selecting a scalarization that maximizes the maximal tolerance is proposed. The proposed methods are compared with known approaches based on basis stability in terms of solution quality, computational complexity, and classes of problems to which the methods can be applied. It is proved that the general problem of finding the maximal tolerance is co-NP-complete.

Práce se zabývá výpočtem maximální tolerance vah ve skalarizační úloze vícekriteriál- ního lineárního programování. Maximální tolerance je definována jako největší přípustná změna vah skalarizace, při níž zůstává dané řešení eficientní. Pozornost je věnována me- todám založeným na kuželovém popisu optima pomocí tečného kužele a jeho extrémních směrů. Pro případ pevně dané skalarizace je odvozen vzorec pro výpočet maximální tole- rance. Dále je navržena metoda, která zvolí skalarizaci takovou, aby nalezená maximální tolerance byla co největší. Navržené metody jsou porovnány se známými přístupy zalo- ženými na bázické stabilitě z hlediska kvality řešení, časové složitosti a typů úloh, na něž lze tyto metody aplikovat. Je dokázáno, že obecný problém hledání maximální tolerance je co-NP-úplný.