1. **بيان المشكلة:** نريد حل البرنامج الخطي (P1): $$\max z_1 = x_1 + x_2 + x_3 + x_4 + x_5$$ مع القيود: $$\begin{cases} x_1 + x_2 + x_5 \leq 1 \\ x_3 + x_4 + x_5 \leq 1 \\ x_2 + x_3 + x_5 \leq 1 \\ x_i \geq 0, \quad i=1,...,5 \end{cases}$$ 2. **تحويل القيود إلى معادلات باستخدام متغيرات الفائض:** نضيف متغيرات فائض $s_1, s_2, s_3 \geq 0$ لكل قيد: $$\begin{cases} x_1 + x_2 + x_5 + s_1 = 1 \\ x_3 + x_4 + x_5 + s_2 = 1 \\ x_2 + x_3 + x_5 + s_3 = 1 \end{cases}$$ 3. **كتابة دالة الهدف بصيغة السمبلكس:** نريد تعظيم: $$z = x_1 + x_2 + x_3 + x_4 + x_5$$ نكتبها كالتالي: $$z - x_1 - x_2 - x_3 - x_4 - x_5 = 0$$ 4. **إعداد جدول السمبلكس الابتدائي:** المتغيرات الأساسية: $s_1, s_2, s_3$ | المتغيرات | $x_1$ | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $s_1$ | $s_2$ | $s_3$ | RHS | |---|---|---|---|---|---|---|---|---|---| | $s_1$ | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | | $s_2$ | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | | $s_3$ | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | | $z$ | -1 | -1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 5. **اختيار المتغير الداخل:** نختار المتغير الذي له أكبر قيمة سالبة في صف $z$، جميعهم -1 متساوية، نختار $x_1$. 6. **حساب نسب القيد لاختيار المتغير الخارج:** نحسب $\frac{RHS}{x_1}$ حيث $x_1 > 0$: - $s_1$: $\frac{1}{1} = 1$ - $s_2$: $x_1=0$ لا يمكن - $s_3$: $x_1=0$ لا يمكن إذاً المتغير الخارج هو $s_1$. 7. **تحديث الجدول بعد الدوران حول $x_1$ و $s_1$:** - نجعل $x_1$ متغيرًا أساسيًا بحل المعادلة الأولى: $$x_1 = 1 - x_2 - x_5 - s_1$$ - نعوض في الصفوف الأخرى وصف $z$: الصف $s_2$: $$s_2 = 1 - x_3 - x_4 - x_5$$ (لا يحتوي $x_1$) الصف $s_3$: $$s_3 = 1 - x_2 - x_3 - x_5$$ (لا يحتوي $x_1$) صف $z$: $$z = 0 + x_1 + x_2 + x_3 + x_4 + x_5$$ نعوض $x_1$: $$z = 0 + (1 - x_2 - x_5 - s_1) + x_2 + x_3 + x_4 + x_5 = 1 - s_1 + x_3 + x_4$$ 8. **الجدول الجديد:** | المتغيرات | $x_2$ | $x_3$ | $x_4$ | $x_5$ | $s_1$ | $s_2$ | $s_3$ | $x_1$ | RHS | |---|---|---|---|---|---|---|---|---|---| | $x_1$ | -1 | 0 | 0 | -1 | -1 | 0 | 0 | 1 | 1 | | $s_2$ | 0 | -1 | -1 | -1 | 0 | 1 | 0 | 0 | 1 | | $s_3$ | -1 | -1 | 0 | -1 | 0 | 0 | 1 | 0 | 1 | | $z$ | 0 | 1 | 1 | 0 | -1 | 0 | 0 | 0 | 1 | 9. **اختيار المتغير الداخل الجديد:** في صف $z$، المتغيرات ذات المعاملات الموجبة هي $x_3$ و $x_4$ (1 و 1)، نختار $x_3$. 10. **حساب نسب القيد لاختيار المتغير الخارج:** - $x_1$: $x_3=0$ لا يمكن - $s_2$: $\frac{1}{-1}$ سالب لا يمكن - $s_3$: $\frac{1}{-1}$ سالب لا يمكن لا يوجد متغير يمكنه الخروج، إذن الحل الأمثل قد تحقق. 11. **الحل النهائي:** المتغيرات الأساسية هي $x_1 = 1$, $s_2 = 1$, $s_3 = 1$, والباقي صفر. 12. **قيمة دالة الهدف:** $$z = 1$$ **النتيجة:** الحل الأمثل هو: $$x_1 = 1, x_2 = 0, x_3 = 0, x_4 = 0, x_5 = 0$$ وقيمة الهدف: $$z = 1$$