حالة الدوران في طريقة السمبلكس: The Cycling Case in The Simplex Method

عبد الله محمد الشيخ

المؤلفون

د. عبد الله محمد الشيخ كلية الاقتصاد والعلوم السياسية جامعة مصراتة

الكلمات المفتاحية:

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

الملخص

إن حل مشاكل البرمجة الخطية بطريقة السمبلكس (Method Simplex) تبدأ بوضع حل مبدئي (Initial Solution) للمشكلة، ثم تبدأ عملية تحسين الحل باتباع خطوات محددة، يتم تكرارها عدة مرات إلى أن يتم الوصول إلى حلً لا يمكن تحسينه، وهو الحل الأمثل (Optimal Solution)، تسمى عملية تكرار تلك الخطوات بالدورات (Iterations)، وعدد هذه الدورات يختلف من مسألة إلى أخرى، حيث يتم إدخال متغير معين واخراج أخر في كل دورة، ويمكن أن يكون هناك دورات إضافية في المسألة الواحدة (يمكن الاستغناء عليها)، وتحدث هذه الدورات الإضافية بسبب إدخال متغير غير ملائم للحل في دورة معينة، وبالتالي إخراجه في دورة أخرى قد تكون مباشرة للدورة التي دخل فيها، أو إخراجه في دورة أخرى لاحقة، وتسمى هذه العملية بظاهرة بالدوران Cycling)). ونقدم هنا دراسة نظرية لهذه لظاهرة، بهدف معرفة مسبيباتها، والتدابير اللازمة لمنع حدوثها، مع تقديم تحليل منطقي ودقيق لكل ذلك.

وللوصول لأهداف الورقة، قمنا بدراسة وتحليل خطوات الحل لطريقة السمبلكس، وتتبع هذه الخطوات باستخدام الطريقة البيانية (Graphical Method)، وقد تبين إن هذه الظاهرة يمكن أن تحدث عند تحديد المتغير الداخل للحل (العمود المحوري pivot column)، والذي على أساسها يتم تحديد المتغير الخارج (الصف المحوري Pivot Row)، فعدم تحديد المتغير الداخل المناسب يعني وجود دورات إضافية (جداول إضافية). وقد تم تحديد مكمن هذا الخلل ومعالجته، وقد تم اقتراح طريقة لتحديد المتغير الملائم للدخول والملائم للخروج، وتم تطبيق هذه الطريقة على مجموعة مشاكل، ومقارنة نتائج الطريقة المقترحة بنتائج الطريقة التقليدية، وقد تميزت الطريقة المقترحة عن الأخرى، فلم تحدث هذه الظاهرة عند استخدام الطريقة المقترحة، ولوحظ في الطريقة المقترحة انخفاض واضح في عدد الجداول اللازمة للوصول للحل الأمثل، حيث انخفض عدد الجداول في المتوسط بنسبة %36.

المراجع

كعبور، محمد 1992، أساسيات بحوث العمليات، كلية المحاسبة، غريان.

Alkubaisi, M. M., 2016, "Shortcut methods for simplex-based sensitivity analysis of linear programming and related software issues", International Journal for Quality Research, 11, 1. 209 – 220

Azlan, N. A., Saptari, A. and Mohamad, E., 2017, "Augmentation of Simplex Alghrithm for Linear Programming Problem to Enhance Computational Performance", Journal of Advanced Manufacturing Technology, eISSN: 2289-8107 Special Issue. 31– 46.

Dadush, D., and Huiberts, S., 2019, " A Friendly Smoothed Analysis of the Simplex Method", Computer Science > Data Structures and Algorithms, V 4. 01–52.

Elshaikh, A., 2014, " Adaptive Heuristic Methods for the Continuous p-Centre Location Problems ", PhD Thesis, Kent Business School, University of Kent, UK.

Ezema, I.B., and Amakom, U., 2012, "Optimizing profit with the linear Programming model-A focus on Golden plastic Industry Limited", Interdisciplinary Journal of Research in Business, 2, 2. 37–49.

Hoffman, A., Mannos, M., Sokolosky, D and Wiegmann, D., 1953, "Computational experience in solving linear programs", SIAM Journal, 1. 1 – 33.

Hussain, M. R., Qayyum, M. and Hussain, M. E., 2019, "Effect of Seven Steps Approach on Simplex Method to Optimize the Mathematical Manipulation", International Journal of Recent Technology and Engineering (IJRTE), 7, 5. 34 – 43.

Kumar, A., and Nandi, S., 2017, " Literature Review of Optimization Technique Business: Based on Case", International Journal of Management (IJM), 8, 2. 231–236.

Koberstein, A., November 2005, "The Dual Simplex Method, Techniques for a fast and stable implementation", Dissertation, Faculty of Economics, University of Paderborn, Germany.

Kurtz, D et al,. 1992, Principles of Managements, McGraw-Hill Inc, USA.

Maros, István,. 2012, Computational techniques of the simplex method, Vol. 61. Springer Science & Business Media

Nadar, K.D., 2016, "Some Applications of Simplex Method", International Journal of Engineering Research and Reviews, 4, 1. 60–63.

Obot, U. A., Anthony, M. and Ozuomba, S., 2016, "A Novel Tabular Form of the Simplex Method for Solving Linear Programming Problems ", International journal of Computer Science & Network Solutions, 4, 2. 2345 – 2397.

Orden, M., 1952, " Solution of systems of linear inequalities on a digital computer", Proceedings of the meeting of the ACM, May 2, 1952, Pittsburgh, PA, 1952. Directorate of Management Analysis, Headquarters, U.S. Air Force, Washington, D.C.

Render, B., Jr, R., and Balakrishnan, N., 2003, Managerial Decision Modeling with Spreadsheets, Prentice HallNew Jersey.

Salhi, S., 2006, "Heuristic Search In Action: The Science of Tomorrow", Paper presented at OR 48 Conference, University of Bath, Bath, UK.

Suleiman, N. A., and Nawkhass, M. A., 2013, " A New Modified Simplex Method to Solve Quadratic Fractional Programming Problem and Compared it to a Conventional Simplex Method by Using Pseudoaffinity of Quadratic Fractional Functions ", Applied Mathematical Sciences, 7, 76. 3749–3764.

Taha A.H., 2007, Operations Research AN Introduction 8th ed.Pearson prentice hell, New Jersey.

Todd, M. J., 2001, The Many Facets of Linear Programming, Math. Program., Ser. B.