Cykl 2/6 w metodzie sympleks

• Autorzy: Sebastian Sitarz

Warianty tytułu

The 2/6 Cycle in Simplex Method

• Języki publikacji: PL

Abstrakty

Celem niniejszej pracy jest przedstawienie i analiza zjawiska cykliczności występującego w zdegenerowanych zadaniach programowania liniowego na przykładzie cyklu typu 2/6. Podano postać ogólną zadania programowania liniowego, w którym występuje cykl 2/6 na podstawie pracy Halla i McKinnona [5]. Ponadto zaprezentowano przykład numeryczny ilustrujący występowanie cyklu 2/6.(abstrakt oryginalny)

EN

The paper presents the analysis of the 2/6 cycles in the simplex method. We demonstrate the general form of linear programming problem in which the cycle 2/6 appear. This fact is based on work by Hall and McKinnon [5]. Moreover we present a simple numerical example to illustrate the 2/6 cycle. (original abstract)

Słowa kluczowe

PL

Programowanie liniowe; Programowanie matematyczne

EN

Linear programming; Mathematical programming

• Czasopismo: Studia i Materiały Polskiego Stowarzyszenia Zarządzania Wiedzą
• Rocznik: 2010
• Tom: 31
• Strony: 293--299

Twórcy

autor

Sebastian Sitarz

• Uniwersytet Śląski w Katowicach

Bibliografia

• [1]Fletcher, R.: Resolving degeneracy in quadratic programming. Annals of Operations Research, 47, pp. 307-334, 1993.
• [2]Gass S. I., Virjamuri S.: Cycling in linear programming problems, Computers and Operations Research, 31, pp. 303-311, 2004.
• [3]Goldfarb D., Sit W. Y.: Worst case behavior of the steepest edge simplex method, Discrete Applied Mathematics, 1, pp. 277-285, 1979.
• [4]Grabowski W.: Programowanie matematyczne, PWE, Warszawa 1980.
• [5]Hall J.A.J., McKinnon K.I.M.: The simplest examples where the simplex method cycles and conditions where EXPAND fails to prevent cycling, Mathematical Programming, Ser. B 100, pp. 133-150, 2004.
• [6]Hoffman A. J.: Cycling in the Simplex Algorithm, Report No. 2974, National Bureau of Standards, Gaithersburg, MD, 1953.
• [7]Jurasz D.: Cykle w algorytmie sympleks. Praca magisterska napisana pod kierunkiem S. Sitarza, Uniwersytet Śląski, Instytut Matematyki, 2009.
• [8]Sitarz S.: Postoptimal analysis in multicriteria linear programming, European Journal of Operational Research, 191, 2008, pp. 7-18.
• [9]Wolfe P.: A technique for resolving degeneracy in linear programming. SIAM Journal of Applied Mathematics, 11, pp. 205-211, 1963.
• [10]http: //www.maths. ed.ac. uk/hal l/PublicLP/.