الوظيفة الإضافية Solver

[محمد حجازي]

السلام عليكم ...

هذه سلسلة تعليمية عن استخدام الوظيفة الإضافية Solver كنت قد نشرتها سابقاً في أحد المواقع ولكن و للأسف فقد فقدت نتيجة خلل فني في ذلك الموقع ، ولذلك فقد أحببت أن أعيد طرحها في هذا المنتدى بعد أن قمت بعمل بعض التعديلات عليها ، أرجو أن تنال إعجابكم.

[محمد حجازي]

السلام عليكم ...

تستخدم الوظيفة الإضافية Solver لحل مسائل البرمجة الخطية و اللاخطية ، ولكننا سنقتصر في أمثلتنا هنا على مسائل البرمجة الخطية (حيث يمكن للوظيفة Solver حل جميع مسائل البرمجة الخطية بما فيها مسائل الإنتاج و مسائل النقل و التخصيص ..... الخ) ، مع العلم أن مسائل البرمجة اللاخطية تُحل بنفس الطريقة .

البرمجة الخطية :

إن أسلوب البرمجة الخطية هو أحد الأساليب الهامة في اتخاذ القرارات ، وتعتبر مسائل البرمجة الخطية إحدى مسائل التفضيل Optimization Problems ، وتعتبر أيضاً من مسائل بحوث العمليات Operations Research .

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

في بداية الثلاثينات تم تشكيل نوع جديد من مسائل التفضيل عرفت بمسائل البرمجة ، فعند وجود عدد من الموارد Resources (قوة عمل ، مواد أولية ، ....الخ) تشترك معاً في إنتاج سلعة أو تقديم خدمة فإنه يمكن تشكيل مسألة برمجة لحساب وإيجاد أفضل تخصيص Optimal Allocation لهذه الموارد وذلك لتحقيق هدف معين .

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

مكونات مسألة البرمجة الخطية :

1. تابع هدف Objective Function نسعى لإيجاد أفضل وضع له (سواءً كان الهدف تعظيم أم تقليل) .

2. متغيرات قرار يجب تحديدها للوصول إلى الهدف المرغوب .

3. متراجحات تشير إلى الموارد وتحدد كميتها فتسمى بالمقيدات Constraints .

مراحل تشكيل مسألة البرمجة الخطية :

1. تشكيل تابع الهدف.

2. وضع المتراجحات و المعادلات التي تمثل مقيدات (شروط) المسألة .

3. وضع متراجحات عدم السلبية : وتعني أن متغيرات القرار لا يمكن إلا أن تكون قيماً موجبة ، حيث يتماشى ذلك مع الواقع (لا يمكن أن تكون مثلاً عدد الوحدات المنتجة سالبة) .

ملاحظة :

عندما تكون العلاقة بين المتغيرات في دالة الهدف و المتراجحات الشرطية خطية ، تسمى عندئذ المسألة مسألة برمجة خطية Linear Programming .

أما إذا كانت العلاقة بين المتغيرات في دالة الهدف أو أحد المتراجحات الشرطية (شروط المسألة) غير خطية ، تسمى عندئذ المسألة مسألة برمجة لا خطية Non Linear Programming .

مثال مبسط :

تنتج شركة المجد نوعين من المواد الغذائية X1,X2 ، حيث يحقق النوع الأول ربحاً قدره (70) وحدة نقدية ، أما النوع الثاني فيحقق ربحاً مقداره (50) وحدة نقدية .

إن إنتاج وحدة من النوع الأول يتطلب وحدتين من المادة الأولية الأولى وأربع وحدات من المادة الأولية الثانية .

أما إنتاج وحدة من النوع الثاني فيتطلب أربع وحدات من المادة الأولية الأولى وأربع وحدات من المادة الأولية الثانية .

أما الكمية المتاحة من المادة الأولية الأولى فهي (40) وحدة ، ومن المادة الأولية الثانية (70) وحدة . و المطلوب بناء نموذج رياضي لهذه المسألة .

الحل :

بفرض أن X1 هي عدد الوحدات المنتجة من النوع الأول .

بفرض أن X2 هي عدد الوحدات المنتجة من النوع الثاني .

فيكون النموذج الرياضي على الشكل التالي :

نلاحظ أن تابع الهدف يسعى لتعظيم الأرباح

هذا شرح سريع جداً ، وعذراً إن لم أستطع إيصال المعلومة بالشكل المطلوب ، وذلك لأنني افترضت أن مستخدم الوظيفة الإضافية Solver سيكون على دراية كاملة بعلم البرمجة الخطية و اللاخطية.

في الدرس القادم سوف نتعرف على كيفية حل هذه النماذج الرياضية باستخدام تطبيق Solver.

[محمد حجازي]

السلام عليكم ...

بعد أن تعرفنا في الدرس السابق على كيفية تشكيل نموذج برمجة خطية ، سنتعرف اليوم على كيفية حل هذا النموذج بواسطة تطبيق Solver :

من القائمة Tools نختار Add-Ins لتظهر لنا النافذة التالية :

إذا لم يكن مربع الاختيار Solver Add-in مفعلاً فقم بتفعيله ثم اضغط OK .

قم باختيار القائمة Tools مرة أخرى وستجد الخيار Solver قد أدرج ضمنها :

قم باختيار Solver حتى تظهر لك النافذة التالية :

نضع في المربع Set Target Cell مرجع الخلية التي تحتوي على تابع الهدف ، ونحدد في الخيار Equal To: نوع تابع الهدف :

• Max : تعني أن البرنامج يقوم بالبحث عن أعلى قيمة ممكنة لتابع الهدف عند حل النموذج ، وذلك ضمن القيود المفروضة .

• Min : تعني أن البرنامج يقوم بالبحث عن أصغر قيمة ممكنة لتابع الهدف عند حل النموذج ، وذلك ضمن القيود المفروضة .

• Value of : تعني أن البرنامج يعمل على حل النموذج عند قيمة محددة لتابع الهدف ، وذلك ضمن القيود المفروضة .

نضع في المربع By Changing Cells مرجع الخلايا التي تحتوي على متغيرات النموذج الخطي ، الخيار Guess يقوم بتوقع الخلايا التي تحتوي على متغيرات النموذج في ضوء الخلية التي تحتوي على تابع الهدف (أنا شخصياً لا أنصح باستخدام هذا الخيار لأنه لا يعطي نتائج صحيحة في أغلب الأحيان ، و أنصح بالاعتماد على الإدخال اليدوي لنطاق الخلايا التي تحتوي على متغيرات النموذج) .

في المجموعة Subject to the Constraints: نقوم بإدخال القيود :

الخيار Add لإضافة القيود ، الخيار Change لتعديل القيود المظللة ، الخيار Delete لحذف القيود المظللة .

نضغط على الخيار Add لتظهر لنا النافذة التالية :

في المربع Cell Reference: أدخل مرجع الخلية التي تريد تقييد القيمة (Constraint) له ، بمعنى آخر أدخل مرجع الخلية التي تحتوي على الطرف الأيسر للقيد (قيد مورد ، قيد متغير) .

انقر فوق العلاقة ( <= أو = أو >= أو Int أو Bin ) التي تريد تطبيقها بين طرفي القيد ، عند النقر فوق Int تظهر كلمة integer (عدد صحيح) في المربع Constraint . عند النقر فوق Bin تظهر كلمة binary (ثنائي 0 أو 1) في المربع Constraint .

في المربع Constraint نضع رقماً أو مرجع الخلية التي تحتوي على ثوابت القيود (الطرف الأيمن للقيود) .

لقبول القيد وإضافة آخر، انقر فوق Add .

لقبول القيد والعودة إلى مربع الحوار Solver Parameters، انقر فوق OK .

ملاحظات :

1. يمكنك تطبيق العلاقتين Int و Bin في القيود الموجودة على الخلايا التي يمكن تعديلها فقط .

2. يمكن لبرنامج Solver أن يقبل عدداً من المتغيرات قد يصل إلى 200 متغير ، كما أنه يمكن أن يتضمن كل متغير على قيود قد تصل إلى 100 قيد ، وذلك بالإضافة إلى الحدود وقيود الأعداد الصحيحة على المتغيرات .

الخيار Reset All لإعادة الإعدادات إلى قيمها الأصلية.

الخيار Options يسمح لنا بتصميم الطريقة التي يقوم بها Solver بحل المشكلة ، وذلك حسب الخيارات التالية :

- المربع Max Time يحدد أقصى وقت للحل (عدد الثواني التي تريد السماح بها لوقت الحل) ، حيث يمكن إطالة هذا الزمن حتى 32767 ثانية .

- المربع Iterations يحدد العدد الأقصى للتكرارات أو عدد المرات التي يمكن أن يعمل من خلالها البرنامج على حل المشكلة .

- المربع Precision يحدد درجة الدقة التي يجب أن يحسب بها البرنامج الحل الأمثل للمعادلة وفق القيود المفروضة ، فقد تصل هذه الدقة إلى 0.000001 وهي القيمة الافتراضية والتي تعني أنه إذا كانت قيمة معادلة القيد ضمن 0.000001 من ثابت القيد فهذا الجواب مقبول .

- المربع Tolerance يحدد الدقة التي يجب أن يعتمدها البرنامج في تأكده من تحقق شروط القيود ، حيث أن نسبة التفاوت المسموح به الافتراضية 5% تعني أنه إذا كانت قيمة العدد تتراوح بين 5% زيادة أو نقصاناً فإن البرنامج يعتبره عدداً صحيحاً ، وهذا الخيار يمكن استخدامه في مسائل البرمجة فقط عندما تكون القيود تستخدم أعداداً صحيحة .

- المربع Convergence يحدد النقطة التي يجب أن يتوقف عندها البرنامج عن البحث عن حل أفضل ، حيث يمكننا تحديد هذا الخيار بالقيمة بين 0 و 1 ، فعندما تكون قيمة التغير في المعادلة الهدف أصغر من القيمة المحددة في مربع Convergence فإن البرنامج يتوقف عن البحث ، وتجدر الملاحظة إلى أنه كلما كانت قيمة التقارب أصغر كلما استغرق البرنامج وقتاً أطول في البحث عن الحل الأفضل .

- الزر Save Model يستخدم لحفظ النموذج الحالي ، و الزر Load Model يستخدم لتحميل نموذج تم حفظه مسبقاً .

- الخيار Assume Linear Model يستخدم لجعل البرنامج يفترض أن النموذج الذي يتعامل معه هو نموج خطي ، مما يبسط العمليات التي يقوم بها البرنامج الشيء الذي يختصر من زمن الحل .

- الخيار Assume Non-Negative يستخدم لجعل البرنامج يقبل النتائج (قيم المتغيرات) الموجبة فقط ، وبواسطة هذا الخيار يمكن الاستغناء عن إدخال القيود التي تمثل شرط عدم السلبية .

- الخيار Use Automatic Scaling يستخدم عندما نتعامل مع متغيرات ونتائج معادلات مختلفة من حيث الحجم ، كأن نقوم بحساب معدل معين باستخدام متغيرات كبيرة نسبياً من حيث المبالغ .

- الخيار Show Trial Solution يستخدم لعرض قيم كل محاولة حل (لعرض نتائج كل دورة حل) .

نكمل شرح البرنامج في الدرس القادم مع وعد مني بإدراج مثال عملي عن طريقة الحل .

[محمد حجازي]

السلام عليكم ...

هذا تطبيق عملي كما وعدكم سابقاً :

تنتج شركة الأمل للألبان ثلاثة أنواع من المنتجات . تتطلب كل وحدة من المنتج الأول أربع دقائق من وقت الآلات، وأربعون دقيقة من وقت العمال وبكلفة إنتاج مقدارها عشرُ ليرات للوحدة الواحدة . أما المنتج الثاني فتحتاج الوحدة منه إلى ثلاث دقائق من وقت الآلات ، وخمسون دقيقة من وقت العمال وبكلفة إنتاج مقدارها اثنتي عشرة ليرة . في حين تحتاج كل وحدة من المنتج الثالث إلى خمس دقائق من وقت الآلات ، ومائة وعشرون دقيقة من وقت العمال وبتكلفة خمس عشرة ليرة . علماً بأن أسعار بيع هذه المنتجات على التوالي هي : 17 ، 20 ، 25 ليرة . فإذا كانت هذه الشركة تعمل بمعدل ستة أيام في الأسبوع وبمعدل عمل صافي مقداره 16 ساعة يومياً . وكان يوجد بها ست آلات وستون عاملاً وميزانية أسبوعية مقدارها 15000 ليرة . هذا بافتراض أن كل ما ينتج يسوق . فكيف يمكن توزيع الطاقة المتوفرة بهذه الشركة بشكل يزيد من أرباحها .

(المصدر : امتحانات جامعة القدس المفتوحة ، أما الحل فهو نتاج مجهودي الشخصي الذي يحتمل الخطأ :h )

الحل:

بفرض أن :

X1 : عدد الوحدات المنتجة أسبوعياً من المنتج الأول

X2 : عدد الوحدات المنتجة أسبوعياً من المنتج الثاني

X3 : عدد الوحدات المنتجة أسبوعياً من المنتج الثالث

النموذج الخطي يكون على الشكل التالي :

والآن لنبدأ بحل النموذج الخطي السابق :

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

نلا حظ من الشكل السابق (في شريط الصيغة) أن الصيغة التالية :

=7*A3+8*B3+10*C3

و الموجودة في الخلية D3 تعبر عن تابع الهدف بدلالة متغيرات القرار الممثلة بالخلايا A3 , B3 , C3 . وبنفس الطريقة نضع الصيغ في الخلايا الباقية كما يلي : الخلية B6 :

=4*A3+3*B3+5*C3

الخلية B7 :

=40*A3+50*B3+120*C3

الخلية B8 :

=10*A3+12*B3+15*C3

أما في الخلايا C6 , C7 ، C8 فيتم وضع ثوابت المتراجحات (الطرف الأيمن للمتراجحات) .

والآن نقوم بفتح برنامج Solver وإدخال المعلومات فيه كما في الشكل التالي :

نلاحظ أن خلية الهدف هي الخلية $D$3 ، وأن تابع الهدف من نوع Max

كما نلاحظ أن الخلايا التي تحتوي على المتغيرات موجودة ضمن المجال $A$3:$C$3

ونلاحظ من الشكل السابق المتراجحات المقيدة لنموذج البرمجة السابق ، هذا ونلاحظ أننا أدخلنا قيود عدم السلبية في البرنامج (وكما ذكرنا سابقاً بأننا يمكننا الاستغناء عن قيود عدم السلبية بمجرد تحديد الخيار Assume Non-Negative من نافذة Solver Options)

بعد الانتهاء من كل ما سبق نضغط على الزر Solve فتظهر لنا النافذة التالية :

نلاحظ تغير قيم الخلايا A3 , B3 , C3 ، وبالتالي تغير قيم الخلايا B6 , B7 , B8 ، D3 .

الحل الناتج يقترح بأن ننتج 1500 وحدة أسبوعياً من المنتج الأول ولا ننتج أي وحدة من المنتجين الثاني و الثالث ، حيث يتحقق ربح أسبوعي مقداره 10500 ليرة ، وهو أعظم ربح ممكن .

وفي هذه الحالة فإنه يجب أن تعمل الآلات بمقدار 6000 دقيقة عمل فعلية ، ويجب أن يعمل العمال بمقدار 60000 دقيقة عمل فعلية ، وحيث أن ميزانية الإنفاق الأسبوعية سوف تستهلك بالكامل .

نلاحظ من الحل السابق (مقارنة الخلايا B6 وB7 بالخلايا C6 و C7) وجود فائض غير مستغل في كل من وقت الآلات و وقت العمال (طاقة معطلة) ، وفي هذه الحالة نحن أمام خيارين :

1. التخلص من الطاقة الفائضة قبل البدء بالإنتاج ، أي بيع الآلات وتسريح العمال الفائضين عن الحاجة وذلك لعدم تحمل تكاليف إضافية لا فائدة منها (رواتب ، تكاليف صيانة الآلات ، تكاليف تعطيل رأس المال ، ... الخ) .

2. دراسة إمكانية استغلال الطاقة الفائضة ، حيث يوجد عدة طرق لمعالجة هذه المشكلة من بينها زيادة ميزانية الإنفاق الأسبوعية ، وهذا يتطلب إجراء مقارنة بين سعر الظل للوحدة النقدية الإضافية (الربح الإضافي الناتج عن زيادة ميزانية الإنفاق الأسبوعية بمقدار وحدة نقدية واحدة) وتكلفة اقتراضها .

عذراً ، لا أستطيع التوسع في الشرح أكثر من ذلك لأن مهمتي الآن هي شرح برنامج Solver وليس إعطاء دروس في بحوث العمليات .... ومن كان يريد الاستزادة فعليه بالمراجع .

في هذه المرحلة يخيرنا البرنامج بين الاحتفاظ بقيم الحل على ورقة العمل بالنقر فوق Keep Solver Solution ، أو استعادة البيانات الأصلية بالنقر فوق Restore Original Values .

يمكنك الحصول على أحد أنواع التقارير الموجودة في المربع Reports ، وذلك بتحديد التقرير المرغوب و النقر فوق OK ليتم إنشاء التقرير في ورقة عمل جديدة .

يستخدم الزر Save Scenario لحفظ قيم الخلايا القابلة للتعديل كسيناريو .

ملاحظات:

1. في المثال السابق ، إذا كانت المنتجات غير قابلة للتجزئة فإنه يجب تعريف القيم الموجودة في الخلايا A3 , B3 , C3 كأعداد صحيحة Int وذلك في المجموعة Subject to the Constraints: .

2. إذا كانت إحدى القيم الموجودة في الخلايا B6 , B7 , B8 غير محققة للمتراجحة المقابلة لها ، فهذا يعني أن المسألة مستحيلة الحل . حيث أن Solver يقوم بالبحث عن الحل الأمثل في حدود القيود المفروضة ، وعندما لايجد حلاً أمثلاً فإنه يقوم بالبحث عن الحل الأمثل الذي يحقق أكبر عدد ممكن من القيود المفروضة .

إليكم الآن مسألة أخرى أترك حلها لكم :

ملاحظة : لقد توخيت البساطة في المسائل التي طرحتها ، ومن يريد مسائل أكثر تعقيداً فعليه بالمراجع المتخصصة .

مرفق مثال عن المسألة السابقة:

بقي لدينا التحدث عن التقارير التي يوفرها لنا الـ Solver ، و عن رسائل الخطأ المحتمل ظهورها عند استخدامه ، وسوف أتابع الشرح إن شاء الله في هذين الموضوعين عندما استطيع الحصول على بعض الوقت لإتمام ذلك.

تحياتي

Solver.zip

[محمد حجازي]

السلام عليكم ...

مرفق ملف يتضمن ورقة بحث للأخ :

أحمد حسين بتال

عن كيفية حل نماذج البرمجة الخطية بواسطة الوظيفة الإضافية Solver . (y)

أرجو أن تنال إعجابكم.

solver_ad.rar

[الجزيرة]

بارك الله فيك يا معلم