05796nam a22002297a 4500 INP 20260622100515.0 260429b1964 ua ja||f |||| 001 0 eng d EG-INP EG-INP 21 338.9 T.R Amer, Roshdi The Simplex Algorithm in a Compact Form Roshdi Amer Cairo Institute of National Planning 1964 52P Paper 26cm مذكرة خارجية 484 This study presents a compact version of the Simplex Algorithm for solving linear programming problems with inequality constraints. The proposed approach aims to improve computational efficiency and significantly reduce memory requirements compared with the conventional canonical simplex method. The motivation behind the research lies in addressing large-scale optimization problems where traditional simplex tables require substantial storage capacity and computational effort. The paper develops a compact tabular representation that stores only the essential numerical information needed during each iteration of the algorithm. It explains the pivoting operations and the criteria for selecting pivot elements, demonstrating how the method systematically moves from one feasible basic solution to another until the optimal solution is reached. To illustrate the methodology, the author provides a complete numerical example and presents a geometric interpretation of the algorithm, clarifying the relationship between simplex iterations and movements along the vertices of the feasible region. The study also examines special situations that may arise during computation, including degeneracy, multiple optimal solutions, and unbounded problems. Furthermore, a proof of the finiteness of the algorithm is established, ensuring convergence after a finite number of iterations. An additional contribution of the paper is its treatment of the dual linear programming problem. A constructive proof of the duality theorem is presented, followed by the development of a compact dual solution method based on the same underlying principles. The work concludes with practical exercises and a computer program designed to implement the proposed algorithm. The study concludes that the compact simplex formulation provides an efficient alternative to the traditional simplex method by reducing memory consumption and computational time while maintaining mathematical accuracy and optimality. Consequently, it offers valuable applications in operations research, economic planning, decision-making, and large-scale optimization problems. تتناول هذه الدراسة تطوير صيغة مدمجة لخوارزمية السمبلكس المستخدمة في حل مشكلات البرمجة الخطية ذات القيود غير المتساوية، وذلك بهدف تحسين الكفاءة الحسابية وتقليل متطلبات الذاكرة مقارنة بالطريقة التقليدية (Canonical Simplex Method). وتنبع أهمية الدراسة من الحاجة إلى معالجة المشكلات الخطية الكبيرة التي تتطلب قدرات تخزينية وزمنية مرتفعة عند استخدام الجداول التقليدية للسمبلكس. يعرض الباحث الإطار النظري للخوارزمية المدمجة من خلال بناء جداول حسابية أكثر اختصاراً تسمح بالاحتفاظ فقط بالعناصر الضرورية في كل خطوة من خطوات الحل. كما يشرح عمليات الارتكاز (Pivoting Operations) وآليات اختيار عنصر الارتكاز الأمثل، موضحاً أثر ذلك في الانتقال المنظم بين الحلول الأساسية الممكنة حتى الوصول إلى الحل الأمثل وتتضمن الدراسة مثالاً عددياً متكاملاً يوضح كيفية تطبيق الخوارزمية خطوة بخطوة، مع تقديم تفسير هندسي للحركة بين رؤوس منطقة الحل الممكن، بما يساعد على فهم الأساس الرياضي للخوارزمية. كذلك تناقش الدراسة بعض الحالات الخاصة التي قد تظهر أثناء التنفيذ، مثل الانحلال (Degeneracy) والحلول المتعددة والمشكلات غير المحدودة، إضافة إلى تقديم برهان على محدودية الخوارزمية وضمان انتهائها بعد عدد محدود من الخطوات كما تتناول الدراسة مفهوم البرنامج الخطي الثنائي (Dual Linear Program)، وتقدم برهاناً بنائياً لنظرية الازدواجية، ثم تعرض طريقة مدمجة لحل المشكلات الثنائية اعتماداً على المبادئ نفسها المستخدمة في النموذج الأصلي. واختتمت الدراسة بمجموعة من التمارين التطبيقية وبرنامج حاسوبي لتنفيذ الخوارزمية عملياً وتخلص الدراسة إلى أن الصيغة المدمجة لخوارزمية السمبلكس تمثل بديلاً فعالاً للطريقة التقليدية، حيث تسهم في تقليل متطلبات التخزين وزمن التنفيذ مع المحافظة على الدقة الرياضية وكفاءة الوصول إلى الحل الأمثل، مما يجعلها مناسبة للتطبيقات الحاسوبية واسعة النطاق في مجالات التخطيط والبحوث التشغيلية واتخاذ القرار.... Qmark The Simplex Algorithm 3348 Emad copycat 22156 22156 0 INP INP EN 0 INP INP EN