طريقة (2)

تعتمد هذه الطريقة في حل جملة المعادلات الخطية على جبر المصفوفات، وتتألف من الخطوات التالية :

1- تشکیل جدول السيمبلكس وذلك بنقل الطرف الأيمن من دالة الهدف إلى الطرف الأيسر، وفي مثالنا السابق يتم على الشكل التالي : 

هـ - 6س₁ - 2س₂= 0

وجدول السيمبلكس يأخذ الشكل التالي :   

ونلاحظ أن قيم متغيرات القاعدة في سطرها معدومة لأننا نبدأ بالحل من القيمة p . نشير إلى أن الحل الأمثل يكون عندما تكون جميع قيم السطر (هـ) والمقابلة للمتغير اكبر او يساوي Φ (p) .

2 ـ ومن خلال ملاحظة قيم السطر (هـ) نلاحظ أن هناك قيمتين سالبتين (6) تقابل المتغير س ₁ و (2) تقابل المتغير (س₂)، وعليه نختار إحداهما ولتكن (6). والعامود الذي يحوي هذه القيمة يكون عامود الدوران والمتغير فيه هو المتغير الداخل. أي أن س₁ متغير داخل.

3- نحدد عنصر الدوران في عامود الدوران، وذلك بقسمة عناصر العامود (ث) على عناصر عامود الدوران الموجبة فقط، ونأخذ ناتج القسمة الأقل. والسطر الذي يحويها هو سطر الدوران .والعنصر الذي يكون عبارة عن تقاطع سطر الدوران مع عامود الدوران هو عنصر - الدوران. وفي مثالنا الحالي وبإتباع الخطوات السابقة نحصل على ما يلي : 

4 - تشكيل جدول جديد وذلك على الشكل التالي: 

يتم تبديل متغير القاعدة في سطر الدوران بمتغير القاعدة مع عامود الدوران، ويجب أن تكون جميع عناصر عامود الدوران في الجدول الجديد أصفاراً ما عدا مكان عنصر - الدوران يجب أن يساوي الواحد.

ولاستبدال سطر الدوران بعامود الدوران نقوم بقسمة عناصر سطر الدوران من الجدول (1) على عنصر الدوران، وفي مثالنا يكون التالي:

ج ) حسب قيمة (هـ) على الشكل التالي :

قيمة المتغير التابع لـ (هـ) في العمود المستبدل م₂ × عناصر سطر الدوران

د) نحسب قيمة باقي متغيرات القاعدة وهي هنا فقط (م₁) ويتم ذلك على الشكل التالي:

 قيمة العنصر (م₁) المتقاطعة مع (م₂) بعد التبديل × عناصر سطر الدوران +  عناصر السطر القديم لـ م₁ :

توضع هذه القيم الجديدة في جدول سيمبلكس ثاني ثم تفحص قيم عناصر السطر (هـ ₁) فإذا كانت جميعها موجبة فالحل أمثل ، وإذا كانت هناك قيماً سالبة تكرر الخطوات السابقة. 

نلاحظ أن جميع قيم عناصر السطر (هـ) موجبة، وبالتالي فإن الحل هو الحل الأمثل، وقيم (المجاهيل هي: س = 14، م₁ = س2 = p) وهي نفس النتيجة في الطريقة السابقة.

2-2 مسائل تقليل التكاليف

مثال (4-4)

لدينا البرنامج الخطي التالي :

الحل :

نضرب دالة الهدف بـ (-1) والشرط الخطي الاول بـ(-1) وتتحول دالة الهدف الى اقصى :

   يوضع (– هـ = هـ ) ونقل الطرف الايسر الى الطرف الايمن في دالة الهدف واضافة متغيرات الفرق نحصل على ما يلي :

مواضيع ذات صلة

البرمـجـة الخـطيـة لمسألة البائع المتجول (حالة خاصة في التخصيص)

البرمـجـة الخـطيـة (مـسائل التخـصيـص) فـي حالـة تـعظيـم الأربـاح

الطـريـقـة الهنـغاريـة فـي حـل مـسائـل التـخصـيـص

البرمجة الخطية (مسائل التخصيص) ـ الشكل العام والحالة الخاصة

طـريقـة التـوزيـع المعدلة (Multiplies Method) لحـل مسألـة الـنقـل

طرائق البحث عن الحل الأمثل لمسألـة الـنقـل (طـريـقـة المـسـار المـغـلـق)

طـريـقـة الجـزاء (طـريـقـة فـوجـل NAM) لحـل مسألـة الـنقـل

نـمـاذج مـصفوفـة الـنقـل و طرائـق حـل مسألـة الـنقـل

البـرمـجة الخـطيـة (مـسائـل النـقـل) ــ نـمـوذج مـصفـوفـة النقل ودالـة الهـدف

خـوارزمـيـة السيـمـبـلـكـس الـمطـورة وأمثلة تـطبيقـية عـليـها (حـالـة 2)

خـوارزمـيـة السيـمـبـلـكـس الـمطـورة وأمثلة تـطبيقـية عـليـها (حـالـة 1)

طرائـق البـرمـجـة الخـطيـة (طريـقة السيـمبلـكس The Simplex Method) 1