ملخص بحوت عمليات في الحاسوب

موضوع: ملخص بحوت عمليات في الحاسوب 21/9/2011, 03:31

ملخص بحوت عمليات في الحاسوب

بسم الله الرحمن الرحيم

بحوث العمليات OR
الهدف : التعرف على المبادئ الأساسية لهذا العلم العام ومنهجية استخدامه في حل المشكلات واتخاذ القرارات .
- تقسم المشكلات التي يعالجها هذا المنهج بالتعقيد الشديد في ظروفها ومكوناتها وعواملها .
- يؤدي استخدام أساليب بحوث العمليات إلى الحلول المثالية ونتائج فعالة .
* تعالج بحوث العمليات بشكل عام مسائل الاستخدام الأمثل للموارد المتاحة .
تعريف بحوث العمليات ( أهميتها ، وتطورها ، واستخداماتها ).
- أعلنت جمعية بحوث العمليات الإنجليزية عن مسابقة لتعريف بحوث العمليات، وقد قدر عدد التعاريف بما يزيد عن مائة تعريف في وقتها، ماذا يعني ذلك ؟
انه ليس من السهل وضع تعريف جامع لبحوث العمليات والسبب في ذلك هو أنها دخلت في كثير من القضايا، وامتهنها أفراد ذوي خلفيات علمية مختلفة، فعرّفها كل واحد منهم حسب خلفيته العلمية وحسب التجربة التي مرّ بها مع بحوث العمليات .
 جمعية بحوث العمليات الأمريكية : عرفتها كما يلي :
تتعلق بحوث العمليات بقرار مبني على أسس علمية، بكيفية تصميم نظم " نماذج " وتشغيل النظم البشرية الآلية والتي تعمل في ظل تخصيص موارد نادرة .
 البريطانيون قالوا :
بحوث العمليات هي التطبيق للأساليب العلمية على حل المشاكل المعقدة التي تنشأ من إدارة وتوجيه الأنظمة الكبيرة من الأفراد والآلات والمواد والأموال في مجال الصناعة ومنشآت الأعمال والحكومة والدفاع بغرض تطوير نموذج للنظم مبني على أسس علمية يتضمن مقاييس العوامل مثل الصدفة والمخاطرة، والغرض من هذا العمل هو مساعدة الإدارة في بناء سياستها وتصرفاتها بطريقة علمية .
* مآخذ على التعريف :
- ليس ضروري أن تكون المشكلة محل البحث معقدة حتى يتم تطبيق استخدام أساليب بحوث العمليات لحلها، بل يمكن تطبيقها على المشاكل الروتينية والتشغيلية كمشكلة تخطيط الإنتاج المتكرر بصفة دورية .
- ليس ضروري أن يكون النظام كبيراً، بل يمكن ن تطبق على مشاكل تواجه الأفراد أو الأسرة مثل مشكلة عمل موازنة للأسرة وتخطيط النقدية و لحل مشاكل المشاريع الصغيرة وتحسين أدائها .

* يمكن أن تعرف بحوث العمليات بشكل عام :
هي استخدام الطريقة العلمية في البحث عن حلول للمشكلات التي تواجه العمليات المختلفة (الإنتاجية أو الاقتصادية أو الإدارية أو العسكرية أو الصناعية أو غيرها) بهدف إيجاد الحلول المثلى للمشكلات التي تواجه هذه العمليات .
* وعلى الرغم من التباين في تعريف بحوث العمليات إلا أنها تقسم بخمس خصائص تعتبر ركائز أساسية لها وهي :
1. استخدام الطريقة العلمية في البحث .
2. استخدام المدخل الشمولي و التنظيمي .
3. استخدام خبرات وتخصصات متنوعة .
4. استخدام النماذج الرياضية .
5. استخدام تقنية المعلومات .

- تساعد الإدارة الحديثة خاصة في مجال ترشيد القرارات والتحليل والتقويم الإدارية المتعلقة بالتنبؤ والتخطيط والتحليل والتقويم والرقابة .
أهم ميزات بحوث العمليات :
1. توفر إمكانية القياس الكمي للظواهر المختلفة .
2. تساعد في توليد عدد كبير من البدائل والمفاضلة بينهما للوصول إلى الحل الأمثل بسرعة وكفاءة عالية .
3. تساعد في حل المشكلات واتخاذ القرارات .
4. تتيح إمكانية ربط الأهداف الفرعية للأنشطة المختلفة بالأهداف العامة للنظام الكلي .
5. توفر الوسائل اللازمة لتنسيق الأنشطة المختلفة ولتحكم فيها .
تطور بحوث العمليات :
- رافقت مسائل بحوث العمليات الإنسان منذ خلقه .
- أخذت طابع المنهج العلمي إبان الحرب العالمية الثانية التي راح ضحيتها ما يقرب من 45 مليون إنسان، وكلفت ما يزيد عن 850 مليار دولار، وقد واجهت بريطانيا ضربات جوية من الألمان مما دعاها للتفكير في :
- دراسة حجم الهجمات الجوية الألمانية وقوة تأثيرها لتحديد عدد الإصابات، ومدى الطاقة الإنتاجية ومدى عمق القنابل المتساقطة من الطيران والمساحة التي تغطيها ومن ثم الإجابة على سؤال وهو :
- كيفية تصميم وبناء ملاجئ ::::TERS مناسبة تقي من هذه القنابل وتتلافى آثارها ؟.
- كيفية صد تلك الغارات الجوية قبل وصولها للجزر البريطانية ؟
لذلك كونت الحكومة البريطانية فرقاً من العلماء لدراسة هذه المشاكل بقيادة عالم الفيزياء البريطاني " بلاكيت " حيث ضم الفريق علماء من تخصصات مختلفة وكان شعاره أن ( عقلين أفضل من عقل واحد ) وكانت النتيجة التصدي لمشكلة الطيران .
* تم تشكيل فريق آخر لمعالجة مشكلة السفن في المحيط الأطلسي حيث كانت تسيطر على عليه الغواصات البحرية الألمانية، وتغرق السفن التجارية الأمريكية المحملة بالمواد والعتاد المرسلة لمساعدة بريطانيا وأوروبا " الحلفاء " وقد وصل عدد السفن المغرقة خلال شهر واحد سنة 1942م ما يقرب عن 142 سفينة مما مكن الألمان من السيطرة شبه الكاملة على المحيط الأطلسي .
* بعد النجاح المبدئي لهذه الفرق تم تشكيل فرق أخرى لدراسة المشاكل المستجدة في الحرب ولحل المشاكل التي تواجه الجيش براً وبحراً وجواً .
* انتقل هذا الأسلوب خلال الحرب إلى الجيش الأمريكي لإيجاد الحلول للمشاكل وإيجاد أفضل الطرق لتموين الجيش بالمواد والعتاد ومن ثم إلى باقي دول الحلفاء .
* أصبح موضوع بحوث العمليات علماً مستقلاً بذاته بعد الحرب 1951م وخاصة في أمريكيا .

استخدام بحوث العمليات :
1. الأغراض العسكرية . 2. المجالات الصناعية .
3. المؤسسات المالية . 4. الدوائر الحكومية والمستشفيات .
5. الزراعة .
مراحل وخطوات تطبيق بحوث العمليات
1. الملاحظة وجمع البيانات .
2. تحديد المشكلة: ( هدف، بدائل، متغيرات تؤثر في تحقيق الهدف "داخلية أو خارجية"، المعايير أو المقاييس .
3. بناء النموذج الرياضي .
4. تحليل النموذج وإيجاد الحل الأمثل .
5. التنفيذ والتقويم والمراجعة .

أساليب بحوث العمليات ومجالات تطبيقها :
يمكن تصنيف أساليب بحوث العمليات بشكل عام إلى مجموعات متشابهة على النحو التالي :
1- أساليب البرمجة الخطية :
تهتم بحل المشكلات المتعلقة بتوزيع الموارد الإنتاجية على عدد من الاحتياجات التي يتم التنافس عليها، ضمن مجموعة من القيود بحيث يحقق هذا التوزيع أفضل نتيجة ممكنة ( سمبلكس، النقل والتعيين، فوجل التقريبية ).
2- أساليب دراسة الاحتمالات :
تكون النتائج ذات طبقة احتمالية، وهذا يعني أننا نكون غير متأكدين تماماً من حدوث هذه النتائج، ومن أساليبها ( التنبؤ، ونظرية القرارات، وصفوف الانتظار، والنماذج الاحتمالية لرقابة المخزون، والمحاكاة، ونظرية المباريات، وتحليلات ماكروف وغيرها ) وهي تتصل باتخاذ قرارات .
3. أساليب تحليل الشبكات :
من أهم الأساليب المستخدمة في تخطيط المشروعات ومتابعتها بهدف تنفيذها بأقل ما يمكن من الزمن والكلفة مع مراعاة الاستخدام الأمثل للموارد المتاحة، واهم أساليبها :
ا- طريقة المسار الحرج " CPM " .
ب- أسلوب بيرت " PERT " لمراجعة وتقييم المشاريع .
4. أساليب رياضية أخرى :
ا- أساليب رقابة المخزون .
ب- البرمجة الديناميكية : " استثمار طويل الأجل، تجديد المعدات واستبدالها، تطوير المشروعات، اقصر طرق نقل البضائع، الجدولة الزمنية " وتستخدم الحل بطريقة المراحل المتتالية ويعتبر الزمن احد المتغيرات في النماذج الديناميكية، كما تمثل كل مرحلة قراراً معيناً يمتد تأثيره إلى المرحلة التي تليها .
ج- البرمجة اللاخطية : تشبه البرمجة الخطية في توزيع الموارد المحدودة واستخداماتها ولكنها تمتاز بكون العلاقات التي تربط بين متغيراتها غير خطية وهي تمثل بمعادلات من الدرجة الثانية أو الثالثة وتعتبر طرق حلها أكثر صعوبة من مسائل البرمجة الخطية .
* استخدام الحاسوب في بحوث العمليات :
لولا الحاسوب لبقيت بحوث العمليات OR دراسات نظرية دون تطبيق عملي .
* بحوث العمليات وأنظمة المعلومات الإدارية :
يقوم نظام المعلومات الإداري بتجميع البيانات ومعالجتها بغية مساعدة الإدارة في اتخاذ القرارات في الوقت وبالشكل المناسبين، وهذا أيضا ما تقوم به أساليب بحوث العمليات .

البرمجة الخطية
تعريفها :
- كلمة برمجة : تعني تخطيط وليس لها علاقة ببرامج الحاسوب .
- خطية : تعني أن الاقتران الرياضي الممثل للمسألة هو اقتران خطي " من الدرجة الأولى ".
إذن البرمجة الخطية تعني : تخطيط الأنشطة للحصول على أفضل النتائج لتحقيق الهدف الأفضل من بين جميع البدائل .
* تتركب مسألة البرمجة الخطية من :
أ- دالة الهدف ( تعبر عن أفضل الأرباح أو اقل التكاليف ) .
A- ::::::IVE FUNCTION :
MAX : Z = X 1 + 2 X2 .
ب- مجموعة من القيود يجب استيفاؤها .
وتسمى قيود المسألة أو القيود المهيكلة كما يسمى X1, X2 بمتغيرات القرار بحيث نبحث عن أفضل مزيج من هذين المركبين يجب أن تكون العلاقة بين هذه المتغيرات خطية.
B- STRUCTURAL CONSTRAINTS :
2 X1 + 6 X2  42
4 X1 + 2 X2  36
X2  4
ج- القيود عدم السلبية :
C- NON-NEGATIVITY RESTRICTIONS
X1 , X2  0 .
النموذج العام للمسائل البرمجية الخطية
الصيغة الرياضية
* يمكن التوصل إلى النموذج الرياضي العام عن طريق :
1- تحديد المتغيرات 2- تحديد دالة الهدف.
3- تحديد القيود المهيكلة 4- تحديد قيود عدم السلبية .
مثال : لإثبات النموذج العام لمسائل البرمجة الخطية
قيود الكميات اللازمة للإنتاج دالة الهدف
المنتوج ساعات العمل خشب م3 دهان / لتر الربح بالدينار
X1 طاولة 1 6.5 0.1 1.3 40
X2 كرسي 2 2.0 0.02 0.2 10
الكمية المتاحة 500 36 120 -

MAX : Z = 40 X1 + 10 X2
S.T :
6.5 X1 + 2 X2  500
0.1 X1 + 0.02 X2  36
1.3 X1 + 0.2 X2  120
N.N :
X1 , X2  0

(MAX , MIN) :
S.T. حسب القيود
a11X1 + a12X2 + ……. + a1n Xn  b1
a21X1 + a22X2 + ……. + a2n Xn  b2
a31X3 + a32X3 + ……. + a3n Xn  b3
a41X4 + a42X4 + ……. + a4n Xn  b4
N.N
X1 , X2 , …….. XN  0
بحيث أن :
I = 1 TO N
J = 1 TO N
لوضع النموذج على شكل مصفوفة
Z = CX
aX ( , = , ) b
X  0

مثال : إذا علمت أن مصنع للأجهزة يصنع نوعان من أجهزة الحاسوب حسب الجدول التالي :
MAX : Z = 3 X1 + 2 X2
S.T
3 X1 + X2  1500
X1 + X2  1000
X1 , X2  0
الأجهزة مواد خام ساعات العمل أرباح
الجهاز الأول 3 1 3
الجهاز الثاني 1 1 2
المتوفر 1500 1000

مثال : تتخصص إحدى الشركات الصناعية في إنتاج أربعة نوعيات من المنتجات، والجدول التالي يوضح رموز المنتجات وهامش ربح الوحدة، والعمليات الصناعية اللازمة لإنتاج تلك النوعيات ومعدل احتياج كل سلعة من هذه العمليات الصناعية وكذلك الطاقة القصوى للأقسام الصناعية:
MAX : Z = 2000 X1 + 5000 X2 + 4000 X3 + 2000 X4
S.T:
20 X1 + 20 X2 + 12 X3 + 10 X4  900
20 X1 + 25 X2 + 30 X3 + 15 X4  900
N.N:
X1 , X2 , X3 , X4  0

الأقسام الإنتاجية
المنتجات تجميع تصنيع ربح الوحدة
X1 20 20 2000
X2 20 25 5000
X3 12 30 4000
X4 10 15 2000
الطاقة 900 900 -

مثال : مصنع للحقائب ينتج نوعين من الحقائب وللمصنع وحدتان إنتاجيتان يتوفر لدى الوحدة الأولى 1500 ساعة / شهرياً ولدى الوحدة الثانية 1000 ساعة، ربح الحقيبة الواحدة للمنتج الأول 3 دنانير، وربح الحقيبة من النوع الثاني 2 دنانير .
- تحتاج الحقيبة الواحدة من النوع الأول إلى 3 ساعات في الوحدة الإنتاجية الأولى وساعة واحدة في الوحدة الإنتاجية الثانية .
- تحتاج الحقيبة الواحدة من النوع الثاني إلى 1 ساعة في الوحدة الإنتاجية الأولى و 1 ساعة في الوحدة الإنتاجية الثانية .
المطلوب : اكتب النموذج الرياضي لتغطية الأرباح .
MAX: Z = 3 X1 + 2 X2
S.T:
3 X1 + X2  1500
X1 + X2  1000
N.N:
X1 , X2  0

النوع مرحلة 1 مرحلة 2 الربح
حقيبة 1 3 1 3
حقيبة 2 1 1 2
موارد 1500 1000 -

الطريقة البيانية GRAPHICAL METHOD
لحل مشاكل البرمجة الخطية
- تعتبر طريقة سهلة وبسيطة وواضحة في معالجة مشاكل البرمجة الخطية، خاصة تلك المشاكل التي لا يزيد فيها المتغيرات عن اثنين والتي تحتوي على عدد بسيط من القيود.
- تعتبر مقدمة لدراسة طرق وأساليب أخرى أكثر تعقيداً مثل السمبلكس.
* يجب إتباع الخطوات التالية في أسلوب الرسم البياني :
- رسم المحور السيني والصادي ( الجزء الموجب من كل منهما ).
- تحديد نقطتين لكل مستقيم ( معادلة ).
- رسم المستقيمات المعبرة من المعادلات.
- تحديد نقطة الإمكانيات المتاحة.
- تعيين نقطة ضمن الإمكانيات المتاحة التي تعطي أفضل النتائج ( أعلى عائد أو أقل تكلفة )، وعادة ما تكون نقطة تقاطع مستقيمات، وتكون في حالة تعظيم الأرباح بعد ما يكون عن نقطة الأصل، وتكون في حالة تقليل التكاليف اقرب ما يكون من نقطة الأصل.

مثال: إليك النموذج الرياضي لإحدى المسائل :
MAX: Z = 10 X1 + 40 X2
SUBJECT TO:
1 X1 + 2 X2  100
1 X1 + 5 X2  150
X1  0 , X2  0
الحل :
أ) تحويل القيود إلى متساويات
المستقيم الأول المستقيم الثاني
1 X1 + 2 X2 = 100 1 X1 + 5 X2 = 150
ب) تحديد نقطتين لكل مستقيم حتى يمكن رسمه وذلك بمعرفة قيم الإحداثيتين كما يلي :
المنتج ركز على إنتاج X1 وأهمل X2 .
المستقيم الأول
X1 = 0 , 2 X2 = 100 , X2 = 100/2 = 50
المنتج ركز على إنتاج X2 وأهمل X1 .
المستقيم الأول
X2 = 0 , X1 = 100 .
النقطتان هما (100, 0 ) و ( 0, 50 ).
- يمكن الآن رسم الإحداثي السيني والصادي وتحديد المستقيم الأول عليه .
* تحديد اتجاه المستقيم باختباره مع نقطة الأصل
أي نعوض عن X1 = 0 , X2 = 0 .
0 + 0  100
إذاً اتجاه المستقيم هو نحو نقطة الأصل.

المستقيم الثاني

1 X1 + 5 X2 = 150
X1 = 0 , 5 X2 = 150, X2 = 150/5 = 30 .
X2 = 0 , X1 = 150 .
- يمكن الآن رسم المستقيم الثاني :

- تحديد منطقة الإمكانيات المتاحة والتي تحقق كلا من المستقيمين ( المنطقة المظللة ).
* تحديد النقطة التي يكون الربح عندها أعلى ما يكون وذلك بإحدى طريقتين :
- الطريقة الأولى : تقييم نقاط تقاطع المستقيمات على أطراف منطقة الإمكانيات المتاحة.
- الطريقة الثانية : رسم مستقيم دالة الهدف ISO – PROFIT LINE
الطريقة الأولى
تقييم نقاط تقاطع المستقيمات :
النقاط X1 X2 Z = 10 X1 + 40 X2 النتيجة
أ 0 0 0 * 0 + 0 0
ب 100 0 10 * 100 + 0 1000
ج 66.7 16.7 66.7 * 10 + 16.7 * 40 1335
د 0 30 10 * 0 + 30 * 40 1200

الطريقة الثانية
رسم مستقيم دالة الهدف ( يرسم عند النقطة ج ).
وأخيرا تحديد مستوى استغلال الموارد عند النقطة ج ( 66.6 ، 16.6 ).
القيود الطاقة دالة الهدف المستغل فائض
X1 + 2 X2 100 16.6 * 2 + 66.6 99.99 لا شيء
X1 + 5 X2 150 66.6 + 5 * 16.6 149.99 لا شيء تقريباً

الطريقة المبسطة SIMPLEX METHOD

خطوات الطريقة المبسطة
1- تحويل دالة الهدف إلى دالة صفرية
Z – 10 X1 – 40 X2 = 0
2- تحويل القيود من هيئة متراجحات إلى هيئة معادلات من خلال إضافة متغير يسمى SLACK .
1 X1 + 2 X2 + S1 = 100
1 X1 + 5 X2 + S2 = 150
3- تثبيت شرط عدم السلبية .
X1 , X2 , S1 , S2 ≥ 0
4- تكوين جدول الحل الأولي والذي يتضمن دالة الهدف والقيود المفروضة :
متغيرات أساسية X1 X2 S1 S2 RHS
Z -10 -40 0 0 0
S1 1 2 1 0 100
S2 1 5 0 1 150
5- اختبار المتغير الداخل :
المتغير الداخل : هو المتغير الذي يشتمل على أكبر قيمة في دالة الهدف ولكن بإشارة سالبة مثل (-40) X2 .
6- تحديد المتغير الخارج :
ويتم عن طريق قسمة الموارد ( الجانب الأيمن ) على عناصر العمود المحوري المناظرة ويكون المتغير الخارج صاحب القيمة الأقل بإشارة موجبة .
داخل ناتج
متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ -10 -40 0 0 0
S1 1 2 1 0 100 50
خارجS2 1 5 0 1 150 30
العنصر المظلل 5 يسمى العنصر الممهد .
7- نقطة التقاطع للعمود المحوري والمتغير الخارج تسمى العنصر الممهد ( PIVOT ).
8- تحويل PIVOT إلى 1 ( نقسم المعادلة على 5 ) .

X2 0.2 1 0 0.2 30

- تحويل جميع عناصر العمود المحوري إلى أصفار .
متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ -10 -40 0 0 0
S1 1 2 1 0 100 50
X2 S2 0.2 1 0 0.2 150 30

X2 40 * 0.2 1 * 40 40 * 0 40 * 0.2 40 * 30
8 40 0 8 1200

متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ -2 0 0 8 1200
S1 1 2 1 0 100 50
X2 0.2 1 0 0.2 150 30
نضرب المعادلة الممهدة ( * -2) ونجمعها للمعادلة S1 .
X2 -2 * 0.2 1 * -2 -2 * 0 -2 * 0.2 -2 * 30
-0.4 -2 0 -0.4 -60
جدول الحل الثاني :
متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ -2 0 0 8 1200
S1 0.6 0 1 -0.4 40
X2 0.2 1 0 0.2 30
اختيار المتغير الداخل أكبر قيمة بإشارة سالبة (-2) X2 .
- تحديد المتغير الخارج : قسمة الجانب الأيمن على العناصر في العمود المحوري ويكون المتغير صاحب القيمة الأقل بإشارة موجبة .
خارج S1  40 / 0.6 = 66.6
X2  30 / 0.2 = 150
متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ -2 0 0 8 1200
X1 1 0 1.67 -0.67 66.67 66.67
X2 0.2 1 0 0.2 30
المعادلة X1 تضرب في 2 وتجمع لدالة الهدف .
X1 1 * 2 0 * 2 1.67 * 2 -0.67 * 2 66.67 * 2 66.67 * 2
2 0 3.34 -1.34 133.34 133.34
X1 تضرب في (* 0.2) وتجمع إلى X2 .
X1 1 * -0.2 0 * -0.2 1.67 * -0.2 -0.67 * -0.2 66.67 * -0.2
-0.2 0 -0.334 0.134 -13.334
متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
دالة الهدفZ 0 0 3.34 66.6 1333.34
X1 1 0 1.67 -0.67 66.67
X2 0 1 -0.334 1.334 -13.334

سؤال : حل السؤال التالي بأسلوب سمبلكس :
MAX: Z = 1000 X1 + 2000X2
S.T:
2 X1 + 4 X2 ≤ 100
8 X1 + 6 X2 ≤ 240
X1 , X2 ≥ 0
الحل :
Z - 1000 X1 - 2000 X2 = 0
S.T:
2 X1 + 4 X2 + 1 S1 = 100
8 X1 + 6 X2 + 1 S2 = 240
X1 , X2 , S1 , S2 ≥ 0

متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
Z -1000 -2000 0 0 5000
S1 2 4 1 0 100 25
S2 8 6 0 1 240 40
الداخل X2
الخارج S1
X2 تضرب في 2000 وتجمع إلى Z .
1000 2000 500 0 6000

متغيرات أساسية X1 X2 S1 S2 RHS RATIO ( θ )
Z 0 0 500 0 5000
X2 0.5 1 0.25 0 25
S2 5 0 -1.25 0 90
نضرب X2 في -6 ونجمع إلى S2 .
-3 -6 -1.5 0 -150
الحل أمثل :
Z = 1000 * 0 + 2000 * 25
Z = 50000
X1 = 0
X2 = 25
سؤال : أوجد الحل الأمثل للمسألة التالية بطريقة السمبلكس :
MAX: Z = 3 X1 + 4 X2 + X3
S.T:
3 X1 + 2 X2 + 4 X3 ≤ 80
1 X1 + 5 X2 + 1 X3 ≤ 70
5 X1 + 4 X2 + 6 X3 ≤ 96
X1 , X2 , X3 ≥ 0
الحل :
Z - 3 X1 - 4 X2 - X3 = 0
S.T:
3 X1 + 2 X2 + 4 X3 + 1 S1 = 80
1 X1 + 5 X2 + 1 X3 + 1 S2 = 70
5 X1 + 4 X2 + 6 X3 + 1 S3 = 96
X1 , X2 , X3 , S1 , S2 , S3 ≥ 0

المتغيرات الأساسية X1 X2 X3 S1 S2 S3 SOL. RATIO (θ)
Z -3 -4 -1 0 0 0 0
S1 3 2 4 1 0 0 80 40
S2 1 5 1 0 1 0 70 14
S3 5 4 6 0 0 1 96 24
1/5 5/5 1/5 0/5 1/5 0/5 70/5 بقسمة S2 على 5
0.2 1 0.2 0 0.2 0 14 الناتج بالشكل التالي
للتوضيح :
المتغير الداخل هو -4 X2
المتغير الخارج هو 14 S2

المتغيرات الأساسية X1 X2 X3 S1 S2 S3 SOL. RATIO (θ)
Z -2.2 0 -0.2 0 0.8 0 56
S1 2.6 0 3.6 1 -0.4 0 52 20
X2 0.2 1 0.2 0 0.2 0 14 70
S3 4.2 0 5.2 0 -0.8 1 40 9.52
0.8 4 0.8 0 0.8 0 56 (X2 * 4) + Z
-0.4 -2 -0.4 0 -0.4 0 -28 (X2 * -2) + Z
-0.8 -4 -0.8 0 -0.8 0 -56 (X2 * -4) + Z

المتغيرات الأساسية X1 X2 X3 S1 S2 S3 SOL.
Z 0 0 2.5 0 0.4 0.5 60.99
S1 0 0 0.4 1 0.1 -0.6 46.1
X2 0 1 0 0 0.58 -0.5 13.54
X1 1 0 1.24 0 -0.19 0.24 2.27
-0.2 0 -0.2 0 0.38 -0.05 -0.46 (X1 * -0.2) + X2
-2.6 0 -3.20 0 0.5 -0.6 -5.9 (X1 * -2.6) + S1
2.2 0 2.7 0 -0.4 0.5 4.99 (X1 * 2.2) + Z

X1 = 2.27 , X2 = 13.54 , X3 = 0 , Z = 60.99

تعدد الحلول المثلى :
1- تكون لمشكلة البرمجة الخطية حلول مثلى متعددة عندما توازي دالة الهدف الخطية أحد القيود الهيكلية المحددة لمنطقة الإمكانيات المتاحة .
مثال :
MAX: Z = 2 X1 + 4 X2
S.T:
5 X1 + X2 ≤ 400
4 X1 + 8 X2 ≤ 480
X1 , X2 ≥ 0

المستقيم الأول المستقيم الثاني
نفرض أي قيمة لZ ولتكن 100 ..
100 = 2 X1 + 4 X2
X1 = 0 , X2 = 0
X2 = 25 , X1 = 50
(0, 25) , (50, 0) 5 X1 + X2 = 400
X1 = 0,
X2 = 400 4X1 + 8X2 = 480
X1 = 0,
X2 = 60
X2 = 0,
X1 = 80 X2 = 0,
X1 = 120

عدم وجود حالات مقبولة :
2- إذا كانت قيود مشكلة البرمجة الخطية بصيغة معنية بحيث تكون منطقة تقاطع القيود عبارة عن مجموعة خالية فلن نحصل على حلول مقبولة .
MINIMIZE : Z = 20 X1 + 15 X2
S.T:
5 X1 + 10 X2 ≤ 25
5 X1 + 10 X2 ≥ 50
X1 , X2 ≥ 0

المستقيم الأول المستقيم الثاني
5 X1 + 10 X2 = 25
X1 = 0,
X2 = 2.5 5 X1 + 10 X2 = 50
X1 = 0,
X2 = 5
X2 = 0,
X1 = 5 X2 = 0,
X1 = 10

الانحلال : DEGENERACY
3- إذا كان عدد القيود الهيكلية هما قيدان وعدد المتغيرات الأساسية التي تكون قيمها أكبر من صفر أقل من عدد القيود فإن الحل عبارة عن حل منحل DEGENERATE .
MAX: Z = 12 X1 + 8 X2
S.T:
4 X1 + 9 X2 ≤ 1800
3 X1 + 2 X2 ≤ 400
X1 , X2 ≥ 0
الحل :
X1 = 0, X2 = 200, (0, 200)
X2 = 0, X1 = 450, (450, 0)

X1 = 0, X2 = 200, (0, 200)
X2 = 0, X1 = 133.3, (133.3, 0)

مشكورة يا احلى ياسمين

هلا و غلا بالغالية

ملخص بحوت عمليات في الحاسوب