المستوى البياني

May 03

المستوى البياني

بحوث عمليات | البرمجة الخطية | المحاضرة الأولى المستوى البياني.

فيديو المستوى البياني



وبعد تحديد النقطة التي تمثل الحل الأمثل نوجد قيمة x1  و x2 بالحل المشترك للمستقيمين المتقاطعين عند النقطة المحددة وم�

عمل الطالبة شيماء محمد

النسب المثلثية للزوايا الحادة



مزيد من المعلومات حول المستوى البياني

طرق حل البرمجة الخطية بالأسلوب البياني (الخورزميات) 

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

أما خطوات الاسلوب البياني لحل البرامج االخطية ذات المتغيرين سنتناولها من خلال المثال التالي.

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

1- نرسم في مستوى محورين متعامدين المحور الأفقي يمثل المتغير X1 والمحور العمودي يمثل المتغير X2 .

2- نرسم المستقيمات التي تحددها المتباينات ونحدد المنطقة المقبولة والمنطقة المرفوضة.

لرسم المستقيم للمتباينة (1) نكتب المتباينة على شكل مساواة كما يلي:

نصل بين النقطتين فنحصل على المستقيم المطلوب الذي يقسم المستوى إلى منطقتين احدهما تحقق المتباينة (1) والأخرى لا تحققها ولتحديد أي المنطقتين مقبولة نأخذ احداثيات اية نقطة من أحد المنطقتين, وللسهولة نأخذ أحداثيات مبدأ الاحداثيات (0, 0) ونعوضها في المتباينة فإذاا حققت هذه النقطة المتباينة عندئذ تكون المنطقة التي تحوي هذه النقطة مقبولة ونرفض المنطقة الأخرى .

بما ان النقطة (0،0) تحقق المتباينة الأولى عندئذ المنطقة المقبولة هي المستقيم والنقطة الواقعة ما دون المستقيم ونظلل المنطقة المرفوضة كما في الصورة السابقة باتباع نفس الاسلوب السابق نرسم بقية المستقيمات . أقرأ ايضاً : مراحل دراسة بحوث العمليات (الخورزميات)

لرسم المستقيم (2) :

المنطقة المقبولة نقاط المستقيم والنقاط اسفل المستقيم باتجاه مبدأ الاحداثيات (المستقيم (2), والشكل (2)(. لرسم مستقيم المتبايته (3) :

المنطقة المقبولة نقاط المستقيم والنقاط اسفل المستقيم باتجاه مبدأ الاحداثيات (المستقيم(2), والشكل(2)(. لرسم مستقيم المتباينة (3):

المنطقة المقبلولة نقاط المستقيم والنقاط اسفل المستقيم باتجاه مبدأ الاحداثيات (المستقيم (3) والشكل (2))

شرط عدم السلبية (4) يتحقق فقط في النقاط الموجبة أي في الربع الأول من منطقة المحاور والاحداثية أي أم النقاط ما دون المحور الأفقي مرفوضة والنقاط على يسار المحور العامودي مرفوضة, أنظر الرسم (2).

من الشكل السابق نلاحظ أن النقاط المحققة للبرنامج الخطي هي تلك النقاط الواقعة ضمن المضلع الذي رؤوسه (ABCDE) تدعى هذه المنطقة بمنطقة الحل وحسب نظريات البرمجة الخطية فإن الحل يكون متوضع في أحد رؤوس مضلع منطقة الأمكانيات (اي احدى ذوراتت منطقة الحل اذ أن كل ذورة تمثل حل أولي يحقق البرنامج الخطي المعطى) .

4- تحديد الحل الأمثل للبرنامج الخطي :

لتحديد الذورة التي تمثل الحل الأمثل يمكن استخدام احدى الطريقتين

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

الذورة (C) لحساب احداثياتها نحل المعادلتين(1) مع (3) الممثلتين لتقاطع المستقيمين في تلك النقطة حلاً مشتركاً أي.

الذروة (D) لحساب أحداثياتها نحل المعادلتين (2) و (3) المتمثلتين لتقاطع المستقيمين في تلك النقطة حلاً مشتركاً أي :

بالمقارنة بين قيم Z لجميع النقاط (الذروات) نجد أن :

الذروة (D) تمثل الحل الأمثل أي :

وهذا هو الحل الأمثل للبرناج الخطي المعطى والذي يحقق الشروط الخطية ويعطي الدالة الهدف أفضل قيمة .

ثانياً: الطريقة المختصرة وتتلخص في تحديد اتجاه دالة الهدف, إذ أنه أجل قيمة ثابته لـ Z فإن معادلة دالة الهدف تمثل خطاً مستقيماً واقعاً في مستوى الاحداثيات الديكارتية, وأي نقطة منه تعطي دالة الهدف القمية ذاتها.

كما أنه من أجل كل قيمة جديدة لـ Z  نحصل على خط مستقيم جديد, وأن جميع هذه الخطوات ستكون متوازية( وذلك لأن ميل أي خط مستقيم Z= C1C1 + C2C2  هو وهذه القيمة مستقلة عن قيمة Z وحسب مثالنا ميل دالة الهدف )

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

وحسب مثالنا لنأخذ قيمتين لـ Z  ونرسم المستقيمين الممثلان لدالة الهدف انظر الشكل السابق في الأعلى رسم 2 , أي :

من هاتين القيمتين لـ Z نأخذ فكرة عن اتجاه دالة الهدف, ونلاحظ أنه كلما أعطينا قيمة أكبر لدالة الهدف كلما حصلنا على المستفيم آخر مواز للسابق, ونلاحظ أن آخر نقطة يشترك فيها مستقيم دالة الهدف مع منطقة الحل هي النقطة D وذلك لأن أي تزايد على قيمة Z سيخرج المستقيم خارج منطقة الحل(للسهولة يمكن رسم مستقيم واحد لدالة الهدف ثم وضع حافز المسطرة واجراء عملية السحب بشكل متواز بالاتجاه المناسب دالة الهدف, وعندئذ آخر نقطة تلامس حافة المسطرة منطقة الحل تكون هي الممثلة للحل الأمثل.

وبعد تحديد النقطة التي تمثل الحل الأمثل نوجد قيمة x1  و x2 بالحل المشترك للمستقيمين المتقاطعين عند النقطة المحددة وم�

Source: http://anshrnow.com/article/165/هندسة%20لغات%20البرمجة/الأسلوب-البياني-لحل-البرمجة-الخطية-(الخورزميات)


المستوى البيانيالمستوى البياني