يحوث العمليات طريقة السمبلكس 3

طريقة السمبلكس هي واحدة من أكثر الطرق استخدامًا في بحوث العمليات لحل مشاكل البرمجة الخطية، حيث تهدف إلى إيجاد الحل الأمثل لمشكلة تزيد أو تقلل من دالة هدف تحت مجموعة من القيود الخطية. إليك شرحًا مبسطًا لخطوات هذه الطريقة:
1. *صياغة المشكلة:*
أبدأ بتحديد دالة الهدف (Objective Function) التي ترغب في تعظيمها أو تقليلها، وعادة ما تكون على الشكل:
\[ Z = c_1x_1 + c_2x_2 + \ldots + c_nx_n \]
تحديد القيود (Constraints) التي تكون على شكل معادلات أو متباينات خطية:
\[ a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1 \]
\[ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n \leq b_2 \]
\[ \vdots \]
\[ a_{m1}x_1 + a_{m2}x_2 + \ldots + a_{mn}x_n \leq b_m \]
2. *تجهيز المصفوفة الابتدائية:*
تحويل القيود إلى شكل متساوي عن طريق إضافة متغيرات جديدة تسمى المتغيرات الاصطناعية (Slack Variables)، بحيث تكون على الشكل:
\[ a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n + s_1 = b_1 \]
إعداد المصفوفة الابتدائية (Initial Simplex Tableau) والتي تشمل معاملات المتغيرات الأساسية (Basic Variables) وغير الأساسية (Non-Basic Variables).
3. *اختيار المتغير الداخل والمتغير الخارج:*
*المتغير الداخل:* يتم اختياره بناءً على أكبر معامل في الصف السفلي (الصف الخاص بدالة الهدف) والذي يكون سالبًا في حالة التعظيم أو موجبًا في حالة التصغير.
*المتغير الخارج:* يتم اختياره باستخدام قاعدة النسبة الأقل (Ratio Test) التي تتضمن قسمة قيم الطرف الأيمن (Right-Hand Side) على القيم الموجبة في عمود المتغير الداخل.
4. *تحديث المصفوفة:*
تحديث المصفوفة باستخدام تقنية العمليات الصفية للحصول على مصفوفة جديدة تحقق شرط الحل الأمثل.
5. *التحقق من الحل الأمثل:*
يتم التحقق مما إذا كانت جميع القيم في الصف السفلي (الصف الخاص بدالة الهدف) غير سالبة في حالة التعظيم أو غير موجبة في حالة التصغير. إذا كانت الحالة صحيحة، يكون الحل الحالي هو الحل الأمثل.
6. *الاستمرار أو التوقف:*
إذا لم يتحقق الحل الأمثل، يتم تكرار العملية بدءًا من اختيار المتغير الداخل والخارج وتحديث المصفوفة حتى الوصول إلى الحل الأمثل.
هذه الخطوات تتكرر حتى يتم العثور على الحل الأمثل الذي يحقق الهدف المطلوب.