O równoważności metod: kar i dwóch faz

• Autorzy: Ireneusz Nykowski

Warianty tytułu

On the Equivalence of the Big M and Two Phase Methods

• Języki publikacji: PL

Abstrakty

Artykuł przedstawia, że dwie wersje algorytmu simplex powszechnie stosowanego w rozwiązywaniu zadań "problemu LP"; metoda kar lub metoda dwóch faz są równoważne. Równoważność jest tu rozumiana jako rozpoczęcie od tego samego pierwszego rozwiązania bazowego, wykonania takiej samej liczby iteracji potrzebnych do otrzymania optymalnego rozwiązania bazowego oraz przebieganie przez te same wierzchołki. Osiągamy równoważność obu metod jeśli: I. w konstrukcji tabeli simplex zastosujemy MKb w metodzie kar oraz tablicę DFb w metodzie dwóch faz; II. w przypadku kilku kandydatur w selekcji nowej zmiennej bazowej wyróżniamy kandydaturę zmiennej o najniższym możliwym numerze.

EN

The article demonstrates that the two versions of the simplex algorithm universally applied for the solution of the tasks of the LP problem; the Big M method or the two phase method, are equivalents. Equivalence is understood here as a start from the same first basic solution, the execution of the same number of iterations needed for obtaining a basic optimal solution, and a trip along the same peaks. We attain the equivalence of both methods if: I. in the construction of simplex tables we apply MKb in the Big M method and DFb tables in the two phase method; II. in the case of several candidatures in the selection of a new basic variable we distinguish the candidature of a variable with the smallest possible number. (original abstract)

Słowa kluczowe

PL

Programowanie liniowe; Badania operacyjne

EN

Linear programming; Operations research

• Czasopismo: Przegląd Statystyczny
• Rocznik: 1995
• Tom: 42
• Numer: z. 2
• Strony: 181--188

Twórcy

autor

Ireneusz Nykowski

• Szkoła Główna Handlowa w Warszawie

Bibliografia

• [1] Charnes, A., Cooper W.W., Henderson A.: An Introduction to Linear Programming, (1953).
• [2] Dantzig G.B., Orden A., Wolfe Ph.: The Generalized Simplex Method for Minimizing a Linear Form Under Linear Inequality Restraints, Pacific Journal of Mathematics (1955), vol. 5, no. 2.
• [3] Simonnard M.: Programowanie liniowe, PWN 1967.