(485) A New Two-Phase Method for Linear Programs with Inequality Constraints طريقة جديدة ثنائية المراحل للبرامج الخطية ذات القيود غير المتساوية
abstract This paper presents a two-phase method for solving linear programming problems with inequality constraints. The method is applicable to standard minimization problems subject to a system of linear inequalities and non-negativity restrictions on the decision variables. The proposed approach...
Сохранить в:
| Главный автор: | |
|---|---|
| Формат: | |
| Опубликовано: |
معهد التخطيط القومي
2026
|
| Online-ссылка: | https://repository.inp.edu.eg/handle/123456789/6424 |
| Метки: |
Добавить метку
Нет меток, Требуется 1-ая метка записи!
|
| Итог: | abstract This paper presents a two-phase method for solving linear programming problems with inequality constraints. The method is applicable to standard minimization problems subject to a system of linear inequalities and non-negativity restrictions on the decision variables. The proposed approach begins by transforming the inequalities into equivalent equations through the introduction of non-negative slack variables. To obtain an initial feasible solution, artificial variables are introduced for those constraints that require them, and a Phase I objective function is defined as the sum of all artificial variables. The first phase determines a feasible basis by minimizing this auxiliary objective function, while the second phase optimizes the original objective function using the feasible solution obtained. The procedure provides a systematic and efficient framework for solving linear programming problems that do not possess an obvious initial basic feasible solution. Illustrative examples are presented to demonstrate the implementation and effectiveness of the method.
تقدم هذه الورقة طريقةً ذات مرحلتين لحل مسائل البرمجة الخطية التي تتضمن قيودًا على شكل متباينات. وتُطبق هذه الطريقة على مسائل التصغير القياسية الخاضعة لنظام من المتباينات الخطية وقيود عدم السالبية المفروضة على متغيرات القرار.
تبدأ الطريقة المقترحة بتحويل المتباينات إلى معادلات مكافئة من خلال إدخال متغيرات فائض (Slack Variables) غير سالبة. وللحصول على حل أساسي أولي قابل للتحقيق، يتم إدخال متغيرات اصطناعية (Artificial Variables) للقيود التي تتطلب ذلك، كما تُعرَّف دالة هدف للمرحلة الأولى على أنها مجموع جميع المتغيرات الاصطناعية.
تهدف المرحلة الأولى إلى إيجاد أساس قابل للتحقيق من خلال تصغير هذه الدالة المساعدة، في حين تُستخدم المرحلة الثانية لتحسين دالة الهدف الأصلية بالاعتماد على الحل القابل للتحقيق الذي تم الحصول عليه في المرحلة الأولى.توفر هذه الإجراءات إطارًا منهجيًا وفعالًا لحل مسائل البرمجة الخطية التي لا تمتلك حلاً أساسيًا أوليًا قابلًا للتحقيق بشكل واضح. كما تُعرض أمثلة توضيحية لبيان كيفية تطبيق الطريقة وإثبات كفاءتها وفعاليتها.
|
|---|