A new geometric approach to multiobjective linear programming problems

• Autorzy: Kaci Mustapha , Radjef Sonia

Identyfikatory

DOI

10.14708/ma.v51i1.7166

Warianty tytułu

PL

Nowe geometryczne podejście do wielokryterialnego programowania liniowego

• Języki publikacji: EN

Abstrakty

EN

This paper is a follow-up to a previous work where we developed a new geometric approach to sensitivity analysis. In this paper, we present a simple method to determine whether a given multiobjective linear programming problem (MOLPP) has an ideal solution (i.e. all of the objective functions are optimized simultaneously) without having to calculate the optimal value of each objective function. First, we divide the space of linear forms into a finite number of sets based on a fixed convex polygonal subset of R2 using an equivalency relationship. All the elements from a given equivalency class have the same optimal solution. Next, we characterize the equivalence classes of the quotient set using a geometric approach to sensitivity analysis. Finally, a numerical example is given to illustrate the method.

PL

W tym artykule przedstawiamy nową metodę rozwiązywania problemów programowania liniowego z wieloma celami (MOLPP), która eliminuje potrzebę obliczania optymalnej wartości każdej funkcji celu. Metoda ta jest kontynuacją naszych wcześniejszych prac dotyczących analizy wrażliwości, gdzie opracowaliśmy nowe podejście geometryczne. Pierwszym krokiem naszego podejścia jest podział przestrzeni form liniowych na skończoną liczbę zbiorów opartych na stałym wypukłym podzbiorze wielokąta R2. Dokonujemy tego za pomocą relacji równoważności, która zapewnia, że wszystkie elementy z danej klasy równoważności mają takie same rozwiązanie optymalne. Następnie charakteryzujemy klasy równoważności zbioru ilorazowego za pomocą podejścia geometrycznego do analizy wrażliwości. Ten krok jest kluczowy w identyfikacji rozwiązania idealnego dla MOLPP. Korzystając z tego podejścia, możemy określić, czy dana MOLPP ma rozwiązanie idealne, bez konieczności obliczania optymalnej wartości każdej funkcji celu. Jest to znacząca poprawa w stosunku do istniejących metod, ponieważ znacznie zmniejsza złożoność obliczeniową i czas wymagany do rozwiązania MOLPP. Aby zilustrować naszą metodę, przedstawiamy numeryczny przykład, który dowodzi jej skuteczności. Nasza metoda jest prosta, ale potężna i może być łatwo zastosowana do szerokiego zakresu MOLPP. Niniejsza praca przyczynia się do dziedziny optymalizacji poprzez przedstawienie nowego podejścia do rozwiązywania MOLPP, które jest wydajne, skuteczne i łatwe do zaimplementowania.

Słowa kluczowe

EN

linear programming; sensitivity analysis; affine geometry; multiobjective programming

PL

programowanie liniowe; analiza wrażliwości; geometria afiniczna; programowanie wielokryterialne

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2023
• Tom: Vol. 51, no. 1
• Strony: 3--12
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Kaci Mustapha

• Department of Mathematics, Signal Image Parole (SIMPA) Laboratory. University of Sciences and Technology of Oran Mohamed Boudiaf USTO-MB, Algeria.

• https://orcid.org/0000-0002-1965-5889

autor

Radjef Sonia

• Department of Mathematics, Signal Image Parole (SIMPA) Laboratory. University of Sciences and Technology of Oran Mohamed Boudiaf USTO-MB, Algeria

• https://orcid.org/0000-0002-1131-297X

Bibliografia

• [1] D. Darvishi, F. Pourofoghi, J. Y. Forrest. Sensitivity analysis of grey linear programming for optimization problems. Operations Research and Decisions 2021: 31(4), 35-52.
• [2] G.B. Dantzig, Linear Programming and Extensions, Princeton University Press. 1963.
• [3] Daellenbach, G. Hans, Introduction to Operational Research Techniques, University of canterbury Christchurch, New Zealand. 1978.
• [4] M. Kaci, S. Radjef. A new geometric approach for sensitivity analysis in linear programming. Mathematica Applicanda, 49(2):145-157. 2022.
• [5] M. Kaci, S. Radjef. The set of all the possible compromises of a multi-level multi-objective linear programming problem. Croatian Operational Research Review, 13:(1), 13-30. 2022.
• [6] T. Koltai, V. Tatay. A practical approach to sensitivity analysis in linear programming under degeneracy for management decision making. International Journal of Production Economics, Volume 131(1), 392-398. 2011.
• [7] D. Kuchta. Fuzzy solution of the linear programming problem with interval coefficients in the constraints. Operations Research and Decisions 2005: 15(3-4), 35-42.
• [8] W.A. Mandal, S. Islam. Multiobjective geometric programming problem under uncertainty. Operations Research and Decisions 2017: 27(4), 85-109.
• [9] M. Sivri, H. G. Kocken, I. Albayrak, S. Akin. Generating a set of compromise solutions of a multiobjective linear programming problem through game theory. Operations Research and Decisions 2019: 29(2), 77-88.
• [10] A. Shahin, P. Hanafizadeh, M. Hlad Sensitivity analysis of linear programming in the presence of correlation among right-hand side parameters or objective function coefficients. Central European Journal of Operations Research, 24(3), 5633. 2014.
• [11] J. Stoer, C. Witzgall - Convexity and optimization in finite dimensions I-Springer-Verlag. 1970.

Uwagi

PL

Opracowane ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).