ملتقى طلاب وطالبات جامعة الملك فيصل,جامعة الدمام - ( الشرح الجديد) البرمجة الخطية من هنا بالطريقتين البياني و السمبلكس

هنا شرح للبرمجة الخطية بالطريقتين البيانية و السمبلكس
بس الاول ايه فايدة البرمجة الخطية؟؟
لو عندنا مثلا مصنع بينتج غسالات عادي و فول اوتوماتيك .... وعندنا خامات و عدد ساعات عمل معين منقدرش نزود عليها ....في حاجة.. احنا نعرف ازاي ننتج كام غسالة عادي و فول اوتوماتيك بحيث نحقق اقصي استفادة من الخامات الموجودة عندنا و في نفس الوقت نلتزم بعدد ساعات العمل ؟؟؟ من البرمجة الخطية هي اللي بتقولنا نعمل ايه
البرمجة الخطية بتستخدم في دراسات الجدول و الحاجات دي قبل ما نعمل مشروع لاننا بنعرف من خلالها الربح حيبقي كام.... تمام كده؟؟

طيب ندخل علي خطوات الحل ....
احنا قلنا ان الحل بطريقتين البيانية و السمبلكس
في خطوات ثابتة في الطريقتين يعني بنعملها سواء بياني او سمبلكس
اولا صياغة النموذج الرياضي
يعني عايزين ارقام نحل بيها المسألة
بنعمل 3 حاجات
اول حاجة دالة الهدف
يعني ايه؟؟
بصوا ... هدف اي شركة او منشأة حاجة من 2 اما يكتروا الارباح او يقللوا التكلفة ..
لو جاب في المسألة سيرة ربح يبقي الدالة تعظيم... لو جاب سيرة تكلفة يبقي الدالة تدنية او تخفيض
و عموما حكاية الدالة تعظيم و لا تخفيض دي بنستخدمها في اخر المسألة عشان نعرف حناخد اكبر رقم و لا اقل رقم

تاني حاجة هي القيود ..
و دي بتبقي في صورة متباينات بتعبر عن الارقام اللي في المسألة < او >

تالت حاجة شرط عدم السلبية ..
يعني س و ص اللي في المسألة يبقوا يااما صفر يا اما رقم ... لاننا اما حننتج او لا .. مافيش حاجة اسمها سالب غسالة مثلا .. تمام؟؟

http://img268.imageshack.us/img268/1516/018yv.jpg

دي كده خطوات ثابتة
بعد كده اما بنحل بالاسلوب البياني او السمبلكس
اولا ... الحل بالاسلوب البياني

http://img638.imageshack.us/img638/3920/019qwz.jpg

1____ نحول المتباينات لمعادلات بنشيل علامة < او > و نحط بدالها =
2____نجيب نقطتين من كل معادلة و ده باننا نعوض عن السين مرة بصفر و نشوف الصاد بكام .. و مرة نعوض عن الصاد بصفر و نشوف السين بكام ..عشان نرسم المعادلة
3____نرسم المعادلات
4____ ناخد نقطة اختبار تحت الخط او فوق الخط و اسهل نقطة تاخدها هي (0 , 0) عوض بيها في المتباينة لو حققت المتباينة يبقي د ه هو اتجاه الحل .. يعني لو نقطة (0 , 0) دي كانت فوق الخط يبقي منطقة الحلول المشتركة فوق الخط و العكس بردو
5___ نحدد منطقة الحلول المشتركة من علي الرسم و طبعا تطبيقا لشرط عدم السلبية فالمنطقة دي حتبقي في الربع الاول في الرسم لان كله موجب ...
6___بعد كده تشوف النقط اللي بتقع فيها منطقة الحلول المشتركة و تعوض بيهم كلهم في دالة الهدف
لو الدالة تعظيم ... اختار النقطة اللي تدي اكبر رقم
لو الدالة تدنية..... اختار النقطة اللي تدي اقل رقم

مثال

http://img197.imageshack.us/img197/9721/020iqy.jpg

احنا اول خطوة عندنا صياغة النموذج الرياضي صح؟؟
طب ما هو عاملهولنا في المسألة يبقي ندخل علي الخطوة التانية علي طول

شايفين المعادلتين اللي في النص ...
دي دوال ثابتة يعني ايا كانت قيمة الصاد بردو السين حتبقي 5 .....حتي لو الصاد بمليون السين حتبقي 5 بردو لان اصلا الصاد مش حتأثر علي المعادلة يعني مش متغير بيغير في نتيجة المعادلة تمام؟
في المثال ده حنرسم الاربع ارباع ليه؟؟
عشان عندنا قيم سالبة للسين و الصاد ....بس بردو منطقة الحلول في الربع الاول فقط
شوفوا الرسمة
علي فكرة كل خط معادلة مكتوب جنبه معادلته و كل خط له لون بس الصورة مش موضحة كفاية

http://img580.imageshack.us/img580/638/021we.jpg

Uploaded with ImageShack.us

و بعد ما رسمنا ناخد بقي نقطة الاختبار لكل خط ..
مثال ... شايفين الخط الازرق بتاع المعادلة 3س _ 4ص = 12
عايزين نعرف هل منطقة الحلول المفروض تبقي فوق الخط و لا تحته ؟؟
ناخد نقطة اختبار و لتكن (0 , 0) فوق الخط و نعوض بيها في المتباينة مش المعادلة... لا المتباينة الاصلية
حنلاقي ان
3×0 _ 4× 0 < 12
0 < 12
هو الصفر اقل من ال 12 ؟؟ ايوة ..
خلاص يبقي منطقة الحلول فوق الخط
و لو لأ يبقي تحت الخط

ملحوظة... احنا بناخد اي نقطة اختبار اي واحدة بس اهم حاجة متكونش تقع علي الخط نفسه يعني فوقه او تحته
احنا بنستسهل و بناخد (0 , 0) لانها اسهل نقطة

بس في الخط بتاع 7س+35ص = 0
مينفعش ناخد (0 , 0) نقطة اختبار لانها تقع علي الخط نفسه .... تمام؟

ازاي نحدد منطقة الحلول المشتركة ؟؟؟
هي منطقة في الربع الاول لان كله موجب
و لازم تبقي فوق الخط الازرق
و فوق الخط الاسود
و تحت الخط الفوشيا
و شمال الخط الاحمر
بصوا كدة حتلاقوها هي...

نطلع بقي النقط بتاعة منطقة الحلول المشتركة و نسميها ا ب ج د و كدة يعني

http://img717.imageshack.us/img717/5133/022uyz.jpg

و بعد كده نعوض بيها في دالة الهدف و نسأل نفسنا هي الدالة دي كانت تعظيم و لا تدنية؟؟
لو تعظيم يبقي ناخد اكبر رقم
لو تدنية يبقي ناخد اقل رقم

شايفين النقطة ج ... فيها مشكلة صغيرة احنا مش عارفين الصاد بكام بالظبط هل 6, و لا 7, و لا كام بالظبط
فبنشوف النقطة ج دي تقاطع انهي خطين و بالتالي انهي معادلتين ... و نحلهم مع بعض بالتعويض و نجيب قيمة ص

بس كده ...
طيب مثال لدالة التدنية بقي

http://img847.imageshack.us/img847/4901/023rx.jpg

http://img17.imageshack.us/img17/4826/024cn.jpg

http://img856.imageshack.us/img856/7233/025gq.jpg

بس و انتهت المسألة ...
دي كانت الطريقة البيانية او الهندسية ....
علي فكرة في حاجة ... لو جالنا في المسألة متغيرين س ص يبقي ينفع نحل بالبياني و السمبلكس كمان
بس لو جالنا اكتر من متغيرين س ص ع مثلا يبقي مينفعش نحل الا بالسمبلكس عشان كدة طريقة السمبلكس اسمها الطريقة العامة لانها بتحل كله ...بس لو في مسألة و جه متغيرين و مقالش حل بطريقة كذا ... طبعا استسهل و حل بالبياني لانها اقصر من السمبلكس

اسلوب السمبلكس

زي ما قلنا بنسميها الطريقة العامة لانها بتحل كل الحالات ...
و معلش لازم تكونوا فاهمين النخفيض المحوري عشان تحلوا دي كويس و ده اللي حشرحه النهاردة باذن الله
و نبدأ بمثال

http://img535.imageshack.us/img535/483/026eil.jpg

طبعا اول خطوة الثابتة في الطريقتين هي صياغة النموذج الرياضي
بصوا ...
اعتبروا المنتج الاول س و المنتج التاني ص
بيقول اننا لما ننتج وحدة من المنتج الاول بنكسب 6 جنيه طيب لما ننتج وحدتين يبقي نكسب كام؟
12 ... طب لو 3 وحدات يبقي نكسب كام ؟
18 .... صح . طيب احنا عملنا ايه ضربنا 6 في العدد اللي حنتجه ...
طيب ما العدد ده احنا عايزين نعرفه يبقي عايزين نعرف لما ننتج س نكسب كام
و كذلك الصاد بردو

يبقي دالة الهدف و ارمزلها باي رمز ...حتساوي 6س + 4ص
طب القيود
بيقولك المنتج الاول بيستغرق ساعتين في الالة الاولي و المنتج التاني بياخد 6 ساعات و عندنا 360 ساعة بس ننتج فيهم طيب ننتج كام وحدة من المنتج الاول و كام وحدة من المنتج التاني بحيث ميزيدوش عن 360 ساعة ..
يعني لازم عدد ساعات انتاجهم في الالة الاولي ميزدش عن 360 صح ؟؟
و كذلك الالة التانية و التالتة ...

http://img851.imageshack.us/img851/5579/027cv.jpg

ده كان الخطوات الثابتة طيب ايه اللي حيتغير
هناك في البياني كنا بنحول المتباينات معادلات علي طول
بس هنا في السمبلكس لما بنحول المتباينات معادلات بنضيف متغير راكد يعني ايه ؟؟
ده لو اتبقي في الاخر يبقي في طاقة غير مستغلة او راكدة ... مثلا اشتغلنا في الالة الاولي 300 ساعة بدل 360 يبقي الطاقة الغير مستغلة دي او المتغير الراكد يبقي بكام؟....60 ساعة
بنسميه ك1 ك2 ك3 و هكذا بترتيب المعادلات

و بعدين نعمل جدول ...نكتب فيه كل المتغيرات ...

http://img838.imageshack.us/img838/6696/028agi.jpg

وبعد ما عملنا الجدول ده وكتبنا فيه كل المتغيرات
عايزين حاجتين
عمود الحل وصف الحل
ايه دول ونجيبهم منين؟
اول حاجه نبص علي عمود الثوابت هل فيه سالب؟؟؟؟
لا
طب لو فيه؟؟
هنقول في المثال الي بعد المثال ده...
بعد كده نبص علي اخر صف في الجدول هل فيه سوالب؟
ايوه فيه نعمل ايه ؟
نختار اكبر رقم باشاره سالبه في الصف الاخير ويبقي العمود الي فيه الرقم ده هو عمود الحل
بعد كده نقسم عمود الثوابت علي عمود الحل كل ثابت قدامه الرقم بتاعه في الصف
ونختار اقل ناتج قسمه موجب ويبقي الصف بتاعه هو صف الحل لكن ملحوظه هامه احنا عمرنا ما بنقسم اخر ثابت ابدا لان ده هو الربح

بعد كده هيطلع لينا تقاطع صف الحل مع عمود الحل في رقم

الرقم ده بنحوله واحد وبالعقل كده اي رقم عاوزين نحوله 1 بنقسمه علي نفسه صح؟
هنقسم الصف كله علي الرقم ده زي ما مكتوب في الصوره الي فاتت

http://img856.imageshack.us/img856/7517/029es.jpg

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

الجدول هيبقي فيه حاجه واحده متغيره ان الرقم الي قولنا عليه مفتاح الحل جنبيه متغير راكد علي اليمين بنشيله ونحط بداله المتغير العادي الي فوقيه س ص ع
دلوقتي احنا حولنا الرقم ده لواحد والمطلوب مننا اننا نحول باقي العمود الي اصفار

ازاي ؟
بنضرب صف الحل الي فيه الرقم الي حولناه لواحد × الرقم الي عاوزين نحوله صفر بعكس اشارته وبعدين نجمع كل ده علي الصف القديم بتاع الرقم الي عاوزين نحوله لصفر
ودي الطريقه الي هنمشي بيها طول المسأله

http://img19.imageshack.us/img19/7761/030jp.jpg

ونمشي بنفس الخطوات بتاعه قبل كده ونشوف هل في الصف الاخير رقم سالب ؟ الخ الخ الخ

http://img4.imageshack.us/img4/5908/031qh.jpg

http://img580.imageshack.us/img580/1397/032kui.jpg

كده حل المسأله خلص وطلعنا قيمه س و ص ومقدار الطاقه الغير مستغله في المتغير الراكد ك1

الي فات ده مثال ثاني طويل بس ركزو في الكلام الي تحتيه خط والحل في الصفحه الجايه

http://img818.imageshack.us/img818/1821/033uy.jpg

ملاحظه مهمه

لو تلاحظوا ان س جنبها النسبه علي طول اما ال ص جنبها النسبه مضروبه ×3
ليه ؟؟؟
لان الفوائد بتاعه س هتتحسب مره واحده بس لانها كل سنتين والمده كلها ثلاث سنين اما ص فالفوايد بتاعتها هتتحسب ثلاث مرات لانها سنويه و المده كلها ثلاث سنين وال ع هتتحسب مرتين لانها كل سنه ونص

http://img717.imageshack.us/img717/5174/034vui.jpg

لو تلاحظوا ان القيود فيها 1 معادله واحنا عارفين ان القيود لازم تبقي متابينات طيب نعمل ايه ؟؟؟؟؟
بنحول المعادله الي متباينتين واحده < والثانيه >
زي مانتم شايفين في شروط الحل ان القيود لازم تبقي علي شكل متباينات بس كمان لازم تكون جميع المتباينات علي شكل اقل من <
وعشان نحول المتباينه من اكبر من الي اقل من بنضرب المتباينه في سالب واحد
وبعدين نحول المتباينات الي معادلات ونضيف المتغيرات الراكده

http://img9.imageshack.us/img9/8285/035sl.jpg

وبعدين نعمل الجدول الاول الي بنكتب فيه كل المتغيرات ونبدا الحل
كنا قولنا فوق اننا بنبص علي عمود الثوابت الاول هل فيه ارقام سالبه ؟ هنا بقي فيه
نعمل ايه ؟.
اولا هنختار صف الحل الاول قبل عمود الحل باننا بنختار اكبر رقم باشاره سالبه من عمود الثوابت ويبقي هو ده صف الحل وبعدين نقسم الرقم ده علي جميع ارقام الصف ونختار اقل ناتج قسمه موجب ويكون ده هو عمود الحل وهكذا ...
بس ملحوظه
اصلا في الجدول الثاني مش هتلاقي سوالب في عمود الثوابت يعني بص علي الصف الاخير علي طول...
ونكمل بقيه حل المسأله زي ما قولنا قبل كده
ويبقي تقاطع صف الحل مع عمود الحل هو الرقم الي هنحوله الي واحد.........الخ
جربوا تحلوا المثال ده لوحدكم عشان الطريقه تثبت

وكده انتهي اسلوب السمبلكس