طريقتين من مرحلة حل المشكلات في البرمجة الخطية: المرحلتين الأولى والثانية

في هذه الطريقة ، يتم حل المشكلة على مرحلتين كما هو موضح أدناه.

الطور الأول:

(أ) يجب أن تكون جميع المصطلحات الخاصة بـ RHS غير سالبة. إذا كان البعض ، ثم يجب أن يتم إجراء + ve كما هو موضح في وقت سابق.

(ب) قيود صريحة في الشكل القياسي.

(ج) إضافة متغيرات اصطناعية في القيود المتعلقة بالمساواة أو القيود المفروضة على النوع (>).

(د) تشكيل دالة هدف جديدة تتكون من مجموع جميع المتغيرات الصناعية

W = A ₁ + A ₂ + ........................ + A _m

تُعرف الدالة (W) بنموذج عدم الجدوى.

(هـ) يجب تقليل الدالة W إلى الحد الأدنى رهناً بقيود المشكلة الأصلية ويتم الحصول على الحل الأمثل الأساسي الأمثل.

قد تنشأ أي من الحالات الثلاث التالية:

(موافق. W> 0 ومتغير اصطناعي واحد على الأقل يظهر في العمود "المتغيرات الأساسية" عند المستوى الإيجابي. في مثل هذه الحالة ، لا يوجد أي حل ممكن للحلقة LPP الأصلية ويتم إيقاف الإجراء.

(2) دقيقة. W = 0 ويظهر متغير اصطناعي واحد على الأقل في عمود "المتغيرات الأساسية" عند مستوى الصفر. في مثل هذه الحالة ، قد يكون أو لا يكون الحل الأمثل الأساسي المناسب لشكل عدم الجدوى حلًا أساسيًا ملائمًا (LPP) (الأصلي) المعطى للحصول على حل عملي أساسي ، فإننا نواصل المرحلة الأولى ونحاول دفع جميع المتغيرات الصناعية من الأساس ثم المضي قدما في المرحلة الثانية.

(ج) W = 0 ولا يظهر أي متغير اصطناعي في العمود "الحل الحالي للمتغيرات الأساسية". في مثل هذه الحالة ، تم العثور على حل عملي أساسي لحزمة LPP الأصلية. الشروع في المرحلة الثانية.

المرحلة الثانية:

استخدم الحل المثالي الأساسي الأمثل للمرحلة الأولى كحل بداية للحزمة LPP الأصلية باستخدام طريقة simplex التي تجعل التكرارات إلى أن يتم الحصول على الحل الأمثل الأساسي الأمثل لها.

وتجدر الإشارة إلى أن دالة الهدف الجديدة W هي دوماً من نوع التدني بغض النظر عما إذا كانت قيمة LPP (الأصلية) المعطاة ذات تعظيم أو تقليل إلى أدنى حد. دعونا نأخذ المثال التالي.

المثال 1 (طريقة البسيط بمرحلتين):

استخدم طريقتين البسيط طريقة ل

تصغير Z = -3X - 2Y - 2Z

تخضع إلى 5X + 7Y + 4Z <7

-4X + 7Y + 5Z> –2

3X + 4 V - 6Z> 29/7

X، Y، Z> 0

حل:

الطور الأول

وهو يتألف من الخطوات التالية.

(أ) في القيد الثاني ، تكون RHS -ve ، حيث تكون مصنوعة + ve بضربه بعلامة ناقص على كلا الجانبين

4X - 7Y - 5Z <2

(ب) إضافة متغيرات الركود في القيود

5X + 7Y + 4Z + S ₁ = 7

4X - 7Y - 5Z + S ₂ = 2

3X + 4Y - 6Z - S ₃ = 29/7

حيث X ، Y ، Z ، S ₁ ، S ₂ ، S ₃ > 0

(ج) ضع X = Y = Z = 0 ، نحصل على S ₁ = 7 ، S ₂ = 2 ، S ₃ = -29/7. كحل أولي. لكن السلسلة S ₃ هي -ve ، سنقوم بإضافة متغير اصطناعي A ، أي

3X + 4Y- 6Z- S ₃ + A ₁ = 29/7

(د) يتم تحديد الوظيفة الموضوعية التي هي نوع تدني إلى الحد الأقصى

تكبير Z = 3X + 2Y + 2Z

(هـ) نقدم وظيفة موضوعية جديدة W = A ₁ للمرحلة الأولى التي ينبغي تقليلها إلى الحد الأدنى.

(و) استبدال X = Y = Z = S ₃ = 0 في القيود التي نحصل عليها S ₁ = 7 ، S ₂ = 2 ، / A ₁ = 29/7 كمحلول أولي مبدئي أساسي إذا تم تشكيله.

اختبار الأمثل preformed

بما أن Cj-Ej سلبي تحت نفس الأعمدة (مشكلة التقليل إلى أدنى حد ممكن) ، فيمكن تحسين الحل المجدي الأساسي الحالي.

التكرار نحو الحل الأمثل:

أداء التكرارات للحصول على الحل الأمثل.

استبدل S ₁ × X ₂ . هذا موضح في الجدول أدناه

يوجد في الجدول رابط لصف المفتاح X عمود هو عمود المفتاح وعمود y هو العمود الأول للهوية. بعد طريقة كسر التعادل نجد أن العمود y لا يكسر التعادل. العمود التالي من الهوية ، أي أن S _2- column ينتج A ₁ -row بصفته صف المفتاح. وهكذا (1/7) هو العنصر الأساسي هو جعل الوحدة في الجدول

استبدل A ₁ × كما هو موضح في الجدول أدناه

يقدم الجدول 5 الحل الأمثل. أيضا ، بما أن الحد الأدنى من W = 0 وليس هناك متغير اصطناعي في المتغيرات الأساسية أي في الحل الحالي ، فإن Table5 يعطي حلًا عمليًا مناسبًا للمرحلة Phase-Ll

المرحلة الثانية:

الوظيفة الهدف الأصلي

تكبير Z = 3x + 2y + 2Z + OS ، + 0S ₂ + 0S ₃

يجب تعظيمه باستخدام القيود الأصلية. باستخدام حل المرحلة الأولى كحل البدء للمرحلة الثانية وإجراء الحساب باستخدام خوارزمية simplex ، نحصل على الجدول 6