خوارزميات مقترحة من نوع تحليل LU لحل مسائل البرمجة الخطية كثيرة الأصفار

الملخص

يعتبر حل مسائل البرمجة الخطية باستخدام طرائق تحليل LU كثيرة الأصفار هي مسألة مفتوحة، مما يجعلها مجالا مهما للبحث و التطوير. لذلك نكرس اهتمامنا في هذه المقالة على تطوير خوارزميات من نوع تحليل LU كثيرة الأصفار عند تنفيذ خوارزمية سيمبليكس المعدلة. نصف في هذه المقالة خوارزميتين فعالتين تعتمدان على تحليل LU لحل مسألة البرمجة الخطية كثيرة الأصفار. نجري العديد من تجارب المحاكاة الحاسوبية لتوضيح فعالية هاتين الخوارزميتين. نقارن النتائج الحاصلة مع تلك الناتجة من تطبيق طريقة Golub – Bartels وطريقة Golub – Bartels كثيرة الأصفار و طريقة Forrest – Tomlin و طريقة Reid لتبيان فعالية الخوارزميات المطورة. نبين من التجارب العددية أن الخوارزميتين المقترحتين هما الأفضل بين الخوارزميات المدروسة ولذلك نوصي باستخدامهما في المكتبات البرمجية الجاهزة كبديل عن الطرائق الحالية لحل مسائل البرمجة الخطية كثيرة الأصفار.

The solution of linear programming problems by sparse LU decomposition is an open problem providing room for further research. This paper tries to develop sparse LU decomposition – based algorithms when implementing Simplex algorithm.

In this paper, we describe efficient algorithms which are based on LU decomposition for solving sparse linear programming problems. Many numerical simulations are carried out to illustrate the efficiency of the proposed algorithms. We compare the obtained results with Golub – Bartels method, Sparse Golub – Bartels method, Forrest – Tomlin method and Reid method to show the efficiency of the proposed algorithms. From the numerical experiments carried out, it is shown that the proposed algorithms are much better than that of available methods. So we recommend using this method in software packages as new alternative for solving the sparse linear programming problems.