A rank one updating interior algorithm for linear programming

Abstract

In this paper we propose an interior point algorithm for linear programming which requires O(n³L) arithmetic operations Since Karmarkar presented a new polynomial time algorithm for linear programming many interior point algorithms have been developed Karmarkar's algorithm requires at most O(nL) iterations and O(n² ) arithmetic operations on average in each iteration The algorithm proposed in this paper requires O(nL) iterations like Karmarkar’s algorithm but it only requires O(n²) arithmetic operations in each iteration As for the revised simplex algorithm we store an inverse matrix in the algorithm and update it by at most rank one at each iteration

في هذا البحث تم فرض خوارزمية نقاط داخلية للبرمجة الخطية والتي تتطلب عدة عمليات حسابية تتناسب مع (ن³ ل) ومنذ أن طور (كراماكار) خوارزمية للبرمجة الخطية الزمنية ؛ فلقد طورت عدة خوارزميات مماثلة لها وتتطلب خوارزمية (كراماكار) عدة دورات تتناسب مع (ن ل)، وفي المتوسط تتطلب كل دورة عدة عمليات حسابية تتناسب مع (ن ²’ ) والخوارزمية المقترحة في هذا البحث تتطلب عدة دورات تتناسب مع (ن ل) بينما تتطلب في كل دورة عدة عمليات حسابية تتناسب مع (ن²) وبخصوص خوارزميةالسمبلكس المراجعة فإنها تخزن المصفوفة المعاكسة في الخوارزمية وتجددها على الأكثر برتبة واحدة في كل دورة