Afiniczne algorytmy skalujące prymalno-dualne

• Autorzy: Henryk J. Runka

Warianty tytułu

Afine Scalling Primo-dual Algorythms

• Języki publikacji: PL

Abstrakty

W afinicznym algorytmie prymalno-dualnym układ warunków zawiera układ warunków zadania pierwotnego (prymarnego), układ KKT (warunki zadania dualnego) i układ warunków komplememntarności. Zatem dopuszczalne rozwiązanie takiego układu jest rozwiązaniem optymalnym dla obydwu zadań. Jednak układ warunków komplementarności jest układem warunków nieliniowych. Dotyczy to zarówno zadań programowania liniowego, jak i zadań programowania kwadratowego. O ile jednak zadań programowania liniowego warunki komplementarności mogą być przedstawione również jako jeden warunek liniowy, to dla zadań programowania kwadratowego zawsze jest to układ warunków nieliniowych lub jeden warunek nieliniowy. Postać warunków komplementarności w zadaniach programowania liniowego i programowania kwadratowego w pierwszym punkcie pracy. Następnie przedstawiono koncepcje tych algorytmów dla rozwiązywania zadań programowania liniowego i kwadratowego (kolejno punkt 2 i 3). Ostatni punkt pracy przedstawia koncepcjęi mplementacji tych algorytmów w języku programowania obiektowego C++

EN

The article presents the general concept of scalling primo-dual algorythm for solving linear and quadratic programming problems, their similariries and spetial variants. In both cases one can derive initial solution in the same way, however the matrices of these systems differ because in the objective function there apears quadratic form matrix. For that reason there are differences in the method for deriving the evolution directions of solutions of the primary and dual problems. For the system of the equations constitutes, in both cases, the admissible solution for these systems is at the same time the optimal one. In the case of linear programming problemsone can present the complementary conditions as a single linear condition and solve the generalised systemof conditions with this single condition. The solution of such a system, however, we can obtain by taking advantage of the Gramm-Schmidt ortogonalization. In the case of quadratic programming problems, the complementary conditions are non-linear. We also present in the article the general concept of implementing these algorythms in the object oriented programming C++

Słowa kluczowe

PL

Algorytmy; Badania operacyjne; Programowanie matematyczne; Programowanie komputerów

EN

Algorithms; Operations research; Mathematical programming; Computer programming

• Czasopismo: Przegląd Statystyczny
• Rocznik: 2003
• Tom: 50
• Numer: z. 4
• Strony: 81--107

Twórcy

autor

Henryk J. Runka

Bibliografia

• [1] Aspvall B., Stone R.E., Khachiyan's linear programming algorithm, Journal of algorithms 1(1980), strony 1-13.
• [2] Bazaraa M.S., Sherall H.D., Shetty C.M., Nonlinear Programming Theory and Algorithms, J. Wiley & Sons, 2nd ed., 1993.
• [3] Chang Yih-Long, Sullivan R.S., QS Version 2.1. Prentice Hall, 1996.
• [4] Fang Shu-Cherng, Puthenpura S., Linear Optimization and Extensions. Theory and Algorithms, Prentice Hall, 1993.
• [5] Ignizio J.P, Cavalier T.M., Linear Programming. Prentice Hall, Industrial and System Engineering, 1994.
• [6] Jansen B., Interior Point Techniques in Optimization. Complementarity, Sensitivity and Algorithms, Kluwer Academic Publishers, 1997.
• [7] Karmarkar N., A new polynomial-time algorithm for linear programming, Combinatorica 4 (1984), strony 373-395.
• [8] Nash S.G., Sofer A., Linear and Nonlinear Programming, McGraw-Hill, 1996.
• [9] Runka H.J., Programowanie matematyczne, część II, programowanie nieliniowe, Akademia Ekonomiczna w Poznaniu, MD 18, 1997.
• [10] Runka H.J., Programowanie matematyczne, część I, programowanie liniowe, Akademia Ekonomiczna w Poznaniu, MD 20, 1997.
• [11] Runka H.J., Początkowe rozwiązanie dla afinicznego algorytmu skalującego, Przegląd Statystyczny, Zeszyt 2, 1999.
• [12] Runka H.J., Algorytmy skalujące prymalne rozwiązywania zadań programowania liniowego i kwadratowego, Przegląd Statystyczny, w druku.
• [13] Vanderbei R.J., Linear Programming. Foudations and Extensions, Kluwer, 2000.