PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | nr 3-4 | 35--42
Tytuł artykułu

The Bottleneck Linear Ordering Problem

Warianty tytułu
Zagadnienie wąskiego gardła w problemie liniowego uporządkowania
Języki publikacji
EN
Abstrakty
Sformułowano zagadnienie wąskiego gardła w problemie liniowego uporządkowania i podano efektywny algorytm jego rozwiązania. W algorytmie wykorzystano dualizm problemów minimalnego cyklu i maksymalnego acyklicznego turnieju. Dualizm ten jest konsekwencją własności symetrii w problemie liniowego uporządkowania. Zaproponowana zmiana funkcji celu z sumy ocen parami porównywalnych alternatyw na minimum z tych ocen powoduje uproszczenie złożoności obliczeniowej problemu z NP-trudnej na wielomianową. Zaprezentowano zastosowanie zagadnienia wąskiego gardła w liniowym uporządkowaniu do ustalania rankingu alternatyw decyzyjnych w przypadku, gdy zadana jest na nich rozmyta relacja preferencji. (abstrakt oryginalny)
EN
The bottleneck linear ordering problem is formulated and an effective algorithm solving it given. The algorithm makes use of the duality of the minimal cycle problem and the maximal acyclic tournament problem. This duality is a consequence of the symmetry property of the linear ordering problem. (original abstract)
Słowa kluczowe
Rocznik
Numer
Strony
35--42
Opis fizyczny
Twórcy
  • Politechnika Wrocławska
  • Politechnika Wrocławska
Bibliografia
  • [1] CHANAS S., KOBYLAŃSKI P., A new Heuristic Algorithm Solving the Linear Ordering Problem, Computational Optimization and Applications, 1996, 6, 191-205.
  • [2] GRÖTSCHEL M., JÜNGER M., REINELT G., On the acyclic subgraph polytope, Mathematical Programming, 1985, Vol. 33, 28-42.
  • [3] KAAS R., A branch and bound algorithm for the acyclic subgraph problem, European Journal of Operational Research, 1981, Vol. 8, 355-362.
  • [4] KRUSKAL J.B., On the shortest spanning subtree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc., 1956, 7, 48-50.
  • [5] LENSTRA H.W. Jr., The acyclic subgraph problem, Report BW26, 1973, Matematisch Centrum, Amsterdam.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171602561

Zgłoszenie zostało wysłane

Zgłoszenie zostało wysłane

Musisz być zalogowany aby pisać komentarze.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.