انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

طريقة ذات المرحلتين Two - Phase Method

Share |
الكلية كلية الادارة والاقتصاد     القسم قسم الادارة الصناعية     المرحلة 3
أستاذ المادة هند عبد الامير احمد محمد       10/03/2020 17:42:52
طريقة ذات المرحلتين Two - Phase Method
تعد طريقة المرحلتين أبسط من طريقة (M) الكبيرة في إيجاد الحل الامثل للبرمجة الخطية (L . P) في حالة التقليل (Minimization)، إذ يمكن الحصول على الحل الأمثل للنموذج بعد أن تتأكد بأن هناك حل لنموذج، وذلك من خلال الحصول على قيمة دالة الهدف الجديدة (r) مساوية للصفر. أي إن (r=0) وبعدمه فلا يوجد حل للنموذج، ويتم الحل بموجب هذه الطريقة على مرحل أساسيتين، وعلى النحو الآتي: أ. المرحلة الأولى:
1.تحويل نموذج البرمجة الخطية (LP) من الصيغة القانونية إلى الصيغة القياسية ومن ثم إضافة المتغيرات الاصطناعية (R1) لقيود النموذج فقط
2. صياغة دالة هدف جديدة (r) بالاعتماد على المتغيرات الاصطناعية (R1)، أي إن:
Min ?(r=R1-R2-…..Rn)
3. تصميم جدول يتضمن الحل الأولي، اعتمادا على معاملات لمتغيرات ( Si ;Xj,Ri ) في قيود لنموذج، ودالة الهدف الجديدة r.
4.نتبع الخطوات السابقة، حتى نحصل على قيمة (0 = r). مما يعني وجود حل للنموذج، والمقترنة في كون (0 > Cj) لجميع معاملات دالة الهدف (r).
ب. المرحلة الثانية:
1. اعتماد الحل الأساسي النهائي في الخطوة (4) من المرحلة الأولى، بعد استبعاد
المتغيرات الاصطناعية (Ri)، ودالة الهدف (r).
2. اعتماد دالة الهدف الأصلية (Z)، وتحسين قيمتها، للحصول على الحل الأمثل للمشكلة.
3.في حالة وجود أحد المعاملات (Cj) أكبر من الصفر (0 < Cj) في صف دالة الهدف (Z)، يعاد إجراء نفس الخطوات حتى يتم الحصول على جميع المعاملات (Cj) أقل أو تساوي الصفر، أي إن (0 > Cj)، مما يعني تم الحصول على الحل الأمثل للنموذج.
مفهوم المشكلة الثنائية: The Concept of Duality Problem
ان لكل نموذج من نماذج البرمجة الخطية نموذجا مقابلا (ثنائية) يسمي أحدا النموذجين بالنموذج الأولي Primal model، بينما يطلق على الآخر تسمية النموذج المقابل (الثنائي) Dual model إن من أهم الصفات المشتركة للنموذج الأولي والثنائي. هو إن الحل الأمثل لأحدهما (في حالة وجود حل) يعطي معلومات كاملة عن الحل الأمثل للنموذج الآخر.
تتمثل أهمية الثنائية في مسائل البرمجة الخطية فيما يلي:
1. تقليص الجهد الحسابي المطلوب في تحليل مسألة البرمجة الخطية التي تحتوي
على عدد كبير من القيود وهذا له فوائد كبيرة في استخدامات وتطبيقات متعددة. 2. تشير الثنائية في البرمجة الخطية إلى إن كل برنامج خطي مكافئ إلى مباراة بين
شخصين ذات مجموع صغري Person Zero Sum game وهذا يؤكد
وجود علاقة بين طريقة البرمجة الخطية ونظرية المباراة. سوف نتطرق إليها عندما نستخدم البرمجة الخطية ونظرية المباراة.
3. بالإمكان الحصول على الحل الأمثل للمسألة الثنائية من جدول الحل الأمثل الأولية مباشرة والعكس صحيح، ولعل من المفيد اختيار المسألة التي تحتوي عدد قليل من القيود. والتي تعتبر ملائمة أكثر للحسابات التكرارية أو بالنسبة للبرامج الجاهزة في الكومبيوتر
4. إذا كان أحد متغيرات النموذج الأول قيمة سالبة فإن حل النموذج هذا غير
ممكن بينما في حالة النموذج المقابل يمكن إيجاد حل للمشكلة عند وجود متغير
ذي قيمة سالبة.


المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
الرجوع الى لوحة التحكم