3.حالة القيود من الشكل أقل أو يساوي (≥):

مثال تطبيقي 1 :

       ليكن لدينا نموذج البرمجة الخطية التالي :    

المطلوب : أوجد الحل الأمثل باستخدام طريقة ( ).

الحل :

    لحل هذا ابرنامج يجب كتابته أولا في صيغته المعيارية  كشرط أساسي لتسهيل المرور إلى جداول السمبلاكس من خلال تحويل المتراجحات إلى معادلات مع إضافة متغيرات الفجوة كما يلي :

     قبل الانتقال إلى جداول السمبلاكس و لتسهيل تفريغ معاملات الشكل المعياري في الجدول الأول يجب كتابة الشكل النهائي لدالة الهدف و تحويلها إلى معادلة صفرية كما يلي :

Z-2X₁-X₂-0S₁-0S₂=0 

     بعد تفريغ معاملات الشكل المعياري في الجدول الأول و الذي يمثل بدوره حلا أساسيا أوليا تكون فيه قيمة دالة الهدف معدومة وجميع قيم متغيرات الأساس (VB) معدومة ، أما المتغيرات خارج الأساس (VHB) فتختلف عن الصفر. 

     تتشكل جداول السمبلاكس (les Tableaux du  Simplexe) من أربع أقسام رئيسية بحيث يخصص الأول لمتغيرات الأساس (VB) ، أما القسم الثاني فيخصص للمتغيرات خارج الأساس (VHB)، في حين يخصص  القسم الثالث لشعاع الحل (b_i) ، بينما يمثل السطر الأخير قيم دالة الهدف (Z_j-C_j) .

قاعدة 1 :

تتشكل متغيرات الأساس (VB) في الجدول الأول للسمبلاكس  من مجموع المتغيرات

المضافة ( عدا متغيرات القرار) و التي تشكل فيما بينها مصفوفة الوحدة و تختلف قيمتها في شعاع الحل عن الصفر.

الجدول 1:

للانتقال إلى الجدول الموالي بهدف تحسين الحل بالاعتماد على مصفوفة الجدول الأول يجب تحديد وتعيين عنصر الارتكاز أو العنصر المحور (le Pivot) الذي بموجبه يتم إجراء مختلف التحويلات على عناصرها للحصول على حل آخر ممكن و مجاور ، إذ يتم ذلك وفق خطوتين اثنتين.

الخطوة الأولى : يتم فيها تعيين عمود العنصر المحور(le Pivot) ونختار في ذلك العمود الذي يحتوي على أقل قيمة سالبة من قيم دالة الهدف (Z_j-C_j) في حالة التعظيم (Cas de Maximisation) ، و أكبر قيمة موجبة من قيم دالة الهدف (Z_j-C_j) في حالة التدنئة (Cas de Minimisation).

الخطوة الثانية : يتم فيها تعيين سطر العنصر المحور (le Pivot) و نختار في ذلك السطر الذي يحتوي على أقل قيمة موجبة غير معدومة من قيم ( b_i/a_ij ) في حالتي التعظيم و التدنئة.

اختبار الأمثلية :

نتوقف عن تحسين الحل عند تحقق شرط الأمثلية  وهو عندما تصبح كل معاملات دالة الهدف (Z_j-C_j) موجبة أم معدومة  في حالة التعظيم (Cas de Maximisation) ، و كل معاملات دالة الهدف (Z_j-C_j) سالبة أم معدومة  في حالة التدنئة (Cas de Minimisation).

    عملا بخوارزميات السمبلاكس (Algorithme du Simplexe) المذكورة في الخطوتين الأولى و الثانية و بالتطبيق على الجدول الأول نتحصل على عنصر الارتكاز(le Pivot) الناتج عن تقاطع السطر و العمود كما هو موضح في الجدول التالي : 

مباشرة بعد تعيين العنصر المحور(le Pivot) الموجود في العمود الأول و السطر الثاني تتحدد المتغيرة الخارجة من الأساس وهي (S₂) لتعوضها المتغيرة الداخلة في الأساس وهي (X₁) و عليه تصبح متغيرات الأساس في الجدول الثاني مكونة من (X₁ . S₁) ، أما العناصر الجديدة للمصفوفة فيتم حسابها بالاعتماد على قيمة العنصر المحور (le Pivot) وانطلاقا من الجدول الأول كما يلي : 

• بالنسبة للقيم الجديدة لمعاملات عمود العنصر المحور : كل عناصر العمود تكون معدومة فيما عدا  قيمة العنصر المحور(le Pivot) الجديدة فتساوي الواحد صحيح بما أن المتغيرة الموجودة في العمود دخلت في الأساس.
• بالنسبة للقيم الجديدة لمعاملات سطر العنصر المحور: نقوم بقسمة قيم معاملات السطر على قيمة عنصر المحور .
• بالنسبة للقيم الجديدة للمعاملات التي لا تقع في سطر و عمود العنصر المحور: بالنسبة لهذه العناصر فتحسب قيمها الجديدة وفق قاعدة قوس جوردن (Gouss-Jordan ) المعتمدة في حساب معكوس المصفوفة .

فإذا افترضنا أنه لدينا المصفوفة التالية الممثلة لجدول السمبلاكس كما يلي :

بافتراض أن (P) هو عنصر الارتكاز فإن العناصر الجديدة لهذه المصفوفة تحسب كما يلي :

بالنسبة للقيم الجديدة لمعاملات عمود العنصر المحور وهي العناصر b’  ،  P’، g’ ، فقيمها تكون على التوالي :  0 ، 1 ، 0 .

بالنسبة للقيم الجديدة لمعاملات سطر العنصر المحور وهي العناصر d’ ، P’، e’ ، فقيمها تكون على التوالي : d/P ، P/P ، e/P .

بالنسبة للقيم الجديدة للمعاملات التي لا تقع في سطر و عمود العنصر المحور وهي العناصر a’ ، c’،f’  ،  h’ فقيمها تحسب وفق قاعدة قوس جوردن (Gouss-gausse Jordan   ) كما يلي : 

بتطبيق هذه القواعد والخوارزميات المذكورة آنفا نتحصل على الجدول الثاني في شكله التالي :

الجدول الثاني:

   إن الجدول الثاني يعطي لنا حلا أساسيا ممكنا مجاورا مقبولا و قيمة دالة الهدف فيه أفضل من تلك المتحصل عليها في الجدول الأول وهي كما يلي :

S₁  = 1  ,  S₂ = 0  ,  X₁  = 2   ,  X₂    = 0

    بالتعويض في دالة الهدف نتحصل على : Z=2x₁+x₂   = 2 ( 2 )  +  ( 0 ) =  4

لكن السؤال المطروح هو هل هذا الحل الأساسي يعتبر حلا أمثليا أم لا ؟

         للإجابة على هذا السؤال يجب اختبار أمثلية الحل المتوصل إليه ، لكن مما يلاحظ أن شرط الأمثلية     (  0  ≤ Z_j – C_j) (Cas de Maximisation تعظيم حالة ) لم يتحقق بعد وهذا يعني أن هناك إمكانية لتحسين الحل من جديد وعلى هذا الأساس نقوم بتعين العنصر المحور من جديد بتطبيق نفس القواعد والخوارزميات السابقة فيصبح الجدول الثاني كما يلي :

الجدول الثاني:

    بعد تعيين العنصر المحور(le Pivot) الموجود في العمود الثاني و السطر الأول مما يعني أن المتغيرة الخارجة من الأساس هي (S1) لتعوضها المتغيرة الداخلة في الأساس وهي (X2) و عليه تصبح متغيرات الأساس في الجدول الثالث مكونة من (X1 . X2) ، و بعد إجراء مختلف التحويلات بنفس القواعد السابقة نحصل على الجدول التالي : 

الجدول الثالث:

نلاحظ أن شرط الأمثلية محقق ( 0 ≤  Zj – C_j) (Cas de Maximisation تعظيم حالة) و هذا يعني أن الحل الأمثل هو :