يساعدك التحسين في العثور على أفضل نتيجة تحقق ربحًا أو تقلل التكاليف أو تحدد معلمة تؤدي إلى فشل عمليات الأعمال.
تسمى هذه العملية أيضًا البرمجة الرياضية. إنه يحل مشكلة تحديد توزيع الموارد المحدودة اللازمة لتحقيق الهدف الذي حدده رئيس مشكلة التحسين. من بين جميع الخيارات الممكنة ، من المستحسن العثور على الخيار الذي يزيد (أو يقلل) معامل التحكم ، على سبيل المثال ، الربح أو التكلفة. تسمى نماذج التحسين أيضًا وصفية أو معيارية لأنها تسعى إلى إيجاد استراتيجية مجدية للأعمال.
تاريخ التنمية
البرمجة الخطية (LP) تعمل مع فئة من مشاكل التحسين حيث تكون جميع القيود خطية.
تقديم نبذة تاريخية عن تطور LP:
- في عام 1762 ، حل لاغرانج مشاكل التحسين البسيطة مع قيود المساواة.
- في عام 1820 ، قرر جاوسنظام المعادلات الخطية باستخدام الحذف.
- في عام 1866 ، أتقن ويلهلم جوردان طريقة إيجاد أخطاء المربعات الصغرى كمعيار مناسب. هذا يسمى الآن طريقة Gauss-Jordan.
- ظهر الكمبيوتر الرقمي عام 1945.
- اخترع Danzig طرقًا بسيطة في عام 1947.
- في عام 1968 ، قدم Fiacco و McCormick طريقة Inside Point.
- في عام 1984 ، طبق Karmarkar الطريقة الداخلية لحل البرامج الخطية ، مضيفًا تحليله المبتكر.
أثبتتLP أنها أداة قوية للغاية لنمذجة مشاكل العالم الحقيقي وكنظرية رياضية مطبقة على نطاق واسع. ومع ذلك ، فإن العديد من مشكلات التحسين المثيرة للاهتمام غير خطية.
ماذا تفعل في هذه الحالة؟ تتضمن دراسة مثل هذه المشكلات مزيجًا متنوعًا من الجبر الخطي وحساب التفاضل والتكامل متعدد المتغيرات والتحليل العددي والطرق الحسابية. يقوم العلماء بتطوير خوارزميات حسابية ، بما في ذلك طرق النقطة الداخلية للبرمجة الخطية والهندسة وتحليل مجموعات ووظائف محدبة ودراسة المشكلات المنظمة بشكل خاص مثل البرمجة التربيعية.
يوفر التحسين غير الخطي فهمًا أساسيًا للتحليل الرياضي ويستخدم على نطاق واسع في مختلف المجالات مثل الهندسة وتحليل الانحدار وإدارة الموارد والاستكشاف الجيوفيزيائي والاقتصاد.
تصنيف مشاكل التحسين
خطوة مهمة فيعملية التحسين هي تصنيف النماذج ، حيث يتم تكييف خوارزميات الحل الخاصة بهم لنوع معين.
1. مشاكل التحسين المنفصل والمستمر. بعض النماذج تكون منطقية فقط إذا كانت المتغيرات تأخذ قيمًا من مجموعة فرعية منفصلة من الأعداد الصحيحة. يحتوي البعض الآخر على بيانات يمكن أن تأخذ أي قيمة حقيقية. عادة ما يكون حلها أسهل. أدت التحسينات في الخوارزميات ، جنبًا إلى جنب مع التطورات في تكنولوجيا الكمبيوتر ، إلى زيادة حجم وتعقيد مشكلة تحسين البرمجة الخطية بشكل كبير.
2. تحسين غير محدود ومحدود. الاختلاف المهم الآخر هو المهام التي لا يوجد فيها قيود على المتغيرات. يمكن أن تتراوح على نطاق واسع من المقدرين البسيطين إلى أنظمة المساواة وعدم المساواة التي تشكل العلاقات المعقدة بين البيانات. يمكن تصنيف مشاكل التحسين هذه وفقًا لطبيعة الوظائف (الخطية وغير الخطية ، المحدبة والسلسة ، القابلة للتفاضل وغير القابلة للتفاضل).
3. مهام الجدوى. هدفهم هو العثور على القيم المتغيرة التي تلبي قيود النموذج دون أي هدف تحسين محدد.
4. مهام التكامل. تستخدم على نطاق واسع في التكنولوجيا والاقتصاد. الهدف هو إيجاد حل يلبي شروط التكامل. في الممارسة العملية ، غالبًا ما يتم إعادة صياغة المهام ذات الأهداف المتعددة إلى أهداف فردية.
5. الحتمية مقابل التحسين العشوائي. يفترض التحسين الحتمي أن البيانات لـالتخصيصات دقيقة تمامًا. ومع ذلك ، في العديد من قضايا الساعة لا يمكن أن تكون معروفة لعدد من الأسباب.
الأول يتعلق بخطأ قياس بسيط. السبب الثاني أكثر جوهرية. يكمن في حقيقة أن بعض البيانات تمثل معلومات حول المستقبل ، على سبيل المثال ، الطلب على منتج أو السعر لفترة زمنية مقبلة. عند التحسين في ظل ظروف التحسين العشوائية ، يتم تضمين عدم اليقين في النموذج.
المكونات الرئيسية
الوظيفة الهدف هي التي يجب تصغيرها أو تكبيرها. معظم أنواع مشاكل التحسين لها وظيفة موضوعية واحدة. إذا لم يكن الأمر كذلك ، فيمكن في كثير من الأحيان إعادة صياغتها للعمل.
استثناءان لهذه القاعدة:
1. مهمة البحث الهدف. في معظم تطبيقات الأعمال ، يريد المدير تحقيق هدف محدد مع تلبية قيود النموذج. لا يرغب المستخدم بشكل خاص في تحسين شيء ما ، لذلك ليس من المنطقي تحديد وظيفة موضوعية. يشار إلى هذا النوع عادة بمشكلة الرضا.
2. الكثير من الميزات الموضوعية. في كثير من الأحيان ، يرغب المستخدم في تحسين عدة أهداف مختلفة في وقت واحد. عادة ما تكون غير متوافقة. قد لا تكون المتغيرات التي يتم تحسينها لهدف واحد هي الأفضل للآخرين.
أنواع المكونات:
- المدخلات الخاضعة للرقابة هي مجموعة من متغيرات القرار التي تؤثر على قيمة دالة الهدف. في مهمة الإنتاج ، قد تشمل المتغيرات توزيع الموارد المتاحة المختلفة أو العمالة المطلوبةكل عمل.
- القيود هي العلاقات بين متغيرات القرار والمعلمات. بالنسبة لمشكلة الإنتاج ، ليس من المنطقي قضاء الكثير من الوقت في أي نشاط ، لذلك حدد جميع المتغيرات "المؤقتة".
- الحلول الممكنة والمثلى. تسمى قيمة القرار للمتغيرات ، والتي بموجبها يتم استيفاء جميع القيود ، بأنها مرضية. تجدها معظم الخوارزميات أولاً ، ثم تحاول تحسينها. أخيرًا ، يغيرون المتغيرات للانتقال من حل ممكن إلى آخر. تتكرر هذه العملية حتى تصل الوظيفة الهدف إلى الحد الأقصى أو الحد الأدنى. هذه النتيجة تسمى الحل الأمثل.
يتم استخدام خوارزميات مشاكل التحسين المطورة للبرامج الرياضية التالية على نطاق واسع:
- محدب.
- منفصل.
- تربيعي.
- هندسي.
أدوات Google Linear Solvers
التحسين الخطي أو البرمجة هو الاسم الذي يطلق على العملية الحسابية لحل المشكلة على النحو الأمثل. تم تصميمها على شكل مجموعة من العلاقات الخطية التي تنشأ في العديد من التخصصات العلمية والهندسية.
تقدم Google ثلاث طرق لحل مشاكل التحسين الخطية:
- مكتبة Glop مفتوحة المصدر.
- إضافة Linear Optimization لأوراق Google.
- خدمة التحسين الخطي في برمجة تطبيقات Google.
Glop مدمج في Googleحلالا خطي. وهي متوفرة في المصدر المفتوح. يمكنك الوصول إلى Glop من خلال غلاف أدوات OR-Tools الخطي ، وهو عبارة عن غلاف لـ Glop.
تتيح لك وحدة التحسين الخطي لـ Google Sheets تنفيذ بيان خطي لمشكلة التحسين عن طريق إدخال البيانات في جدول بيانات.
البرمجة التربيعية
تستخدم منصة Premium Solver إصدار LP / Quadratic ممتدًا من أسلوب Simplex مع حدود معالجة مشكلة LP و QP تصل إلى 2000 متغير قرار.
يستخدم SQP Solver للمشكلات واسعة النطاق تطبيقًا حديثًا لطريقة المجموعة النشطة مع التفرقة لحل مشكلات البرمجة التربيعية (QP). يستخدم محرك XPRESS Solver امتدادًا طبيعيًا لـ "Interior Point" أو طريقة Newton Barrier لحل مشكلات QP.
يطبق MOSEK Solver طرق "نقطة داخلية" وطرق ثنائية تلقائية. هذا فعال بشكل خاص لمشاكل QP المقترنة بشكل فضفاض. يمكنه أيضًا حل مشاكل Scale Quadratic Constraint (QCP) و Second Order Cone Programming (SOCP).
حسابات متعددة العمليات
يتم استخدامها بنجاح كبير مع استخدام ميزات Microsoft Office ، على سبيل المثال ، حل مشاكل التحسين في Excel.
في الجدول أعلاه الرموز هي:
- K1 - K6 - العملاء الذين يحتاجون إلى توفير السلع
- S1 - S6 هي مواقع إنتاج محتملة يمكن بناؤها لهذا الغرض. يمكن إنشاؤها1 ، 2 ، 3 ، 4 ، 5 أو كل المواقع الستة.
هناك تكاليف ثابتة لكل منشأة مدرجة في العمود الأول (إصلاح).
إذا لم يغير الموقع أي شيء ، فلن يتم احتسابه. ثم لن تكون هناك تكاليف ثابتة.
تحديد المواقع المحتملة للحصول على أقل تكلفة
في هذه الظروف ، إما أن يكون الموقع محددًا أم لا. هاتان الحالتان هما: "صحيح - خطأ" أو "1 - 0". هناك ست حالات لستة مواقع ، على سبيل المثال ، تم تعيين 000001 على السادس فقط ، وتم تعيين 111111 على الكل.
في نظام الأرقام الثنائية ، يوجد بالضبط 63 خيارًا مختلفًا من 000001 (1) إلى 111111 (63).
L2-L64 يجب أن تقرأ الآن {=MULTIPLE OPERATION (K1)} ، هذه هي نتائج جميع الحلول البديلة. ثم القيمة الدنيا هي=Min (L) والبديل المقابل هو INDEX (K).
CPLEX Integer Programming
في بعض الأحيان لا تكفي العلاقة الخطية للوصول إلى قلب مشكلة العمل. هذا صحيح بشكل خاص عندما تتضمن القرارات اختيارات منفصلة ، مثل فتح أو عدم فتح مستودع في موقع معين. في هذه الحالات ، يجب استخدام البرمجة الصحيحة.
إذا كانت المشكلة تتضمن اختيارات منفصلة ومستمرة ، فهي عبارة عن برنامج عدد صحيح مختلط. يمكن أن يكون لها مشاكل تربيعية خطية ومحدبة ونفس قيود الترتيب الثاني.
تعد البرامج الصحيحة أكثر تعقيدًا من البرامج الخطية ، لكن لها تطبيقات تجارية مهمة. برمجةيستخدم برنامج CPLEX طرقًا رياضية معقدة لحل مشاكل الأعداد الصحيحة. تتضمن أساليبه البحث بشكل منهجي عن مجموعات محتملة من المتغيرات المنفصلة باستخدام ارتخاء البرامج الخطية أو التربيعية لحساب الحدود على قيمة الحل الأمثل.
يستخدمون أيضًا LP وطرق حل مشكلات التحسين الأخرى لحساب القيود.
قياسي Microsoft Excel Solver
تستخدم هذه التقنية التنفيذ الأساسي لطريقة Simplex الرئيسية لحل مشاكل LP. يقتصر على 200 متغير. يستخدم "Premium Solver" أسلوب بسيط أساسي محسن مع حدود على الوجهين للمتغيرات. يستخدم النظام الأساسي Premium Solver إصدارًا موسعًا من LP / Quadratic Simplex Solver لحل مشكلة التحسين مع ما يصل إلى 2000 متغير قرار.
يطبق LP على نطاق واسع لمنصة Premium Solver تنفيذًا متطورًا لأسلوب بسيط ومزدوج البسيط ، والذي يستخدم التباين في نموذج LP لتوفير الوقت والذاكرة ، والاستراتيجيات المتقدمة للتحديث و مصفوفات إعادة البناء والتسعير والتناوب المتعدد والجزئي وللتغلب على الانحطاط. يتوفر هذا المحرك في ثلاثة إصدارات (قادر على التعامل مع ما يصل إلى 8000 أو 32000 أو متغيرات وحدود غير محدودة).
يتضمن MOSEK Solver البسيط الأساسي والثنائي ، وهي طريقة تستغل أيضًا التباين وتستخدم استراتيجيات متقدمة لتحديث المصفوفة و "إعادة البناء". كان يحل مشاكل غير محدودة الحجمتم اختباره على مشاكل البرمجة الخطية بملايين متغيرات القرار
مثال خطوة بخطوة في EXCEL
لتحديد نموذج مشكلة التحسين في Excel ، قم بتنفيذ الخطوات التالية:
- تنظيم البيانات الخاصة بالمشكلة في جدول بيانات في شكل منطقي.
- حدد خلية لتخزين كل متغير.
- إنشاء صيغة في الخلية لحساب النموذج الرياضي المستهدف لمشكلة التحسين.
- إنشاء صيغ لحساب الجانب الأيسر من كل قيد.
- استخدم مربعات الحوار في Excel لإخبار Solver بمتغيرات القرار والأهداف والقيود والحدود المرغوبة على تلك المعلمات.
- قم بتشغيل "Solver" للعثور على الحل الأمثل.
- إنشاء ورقة Excel.
- تنظيم البيانات الخاصة بالمشكلة في Excel حيث يتم حساب صيغة الدالة الهدف والقيد.
في الجدول أعلاه ، تم حجز الخلايا B4 و C4 و D4 و E4 لتمثيل متغيرات القرار X 1 و X 2 و X 3 و X 4. أمثلة القرار:
- تم إدخال نموذج مزيج المنتجات (ربح 450 دولارًا و 1150 دولارًا و 800 دولارًا و 400 دولارًا لكل منتج) في الخلايا B5 و C5 و D5 و E5 على التوالي. يسمح ذلك بحساب الهدف في F5=B5B4 + C5C4 + D5D4 + E5E4 أو F5:=SUMPRODUCT (B5: E5، B4: E4).
- في B8 أدخل مقدار الموارد المطلوبة لتصنيع كل نوع من المنتجات.
- معادلة لـ F8:=SUMPRODUCT (B8: E8، $ B $ 4: $ E $ 4).
- انسخ هذاالصيغة في F9. علامات الدولار في $ B $ 4: $ E $ 4 تشير إلى أن نطاق الخلايا هذا يظل ثابتًا.
- في G8 أدخل كمية الموارد المتاحة من كل نوع ، المقابلة لقيم القيود على اليمين. هذا يسمح لك بالتعبير عنها على النحو التالي: F11<=G8: G11.
- هذا يعادل أربعة حدود F8<=G8 ، F9 <=G9 ، F10 <=G10 و F11=0
مجالات التطبيق العملي للطريقة
التحسين الخطي له العديد من التطبيقات العملية كمثال على مشكلة التحسين:
يمكن للشركة أن تصنع العديد من المنتجات بهامش مساهمة معروف. يتطلب إنتاج وحدة من كل عنصر قدرًا معروفًا من الموارد المحدودة. تتمثل المهمة في إنشاء برنامج إنتاج لتحديد المقدار الذي يجب إنتاجه من كل منتج بحيث يتم تعظيم ربح الشركة دون انتهاك قيود الموارد.
مشاكل الخلط هي الحل لمشاكل التحسين المتعلقة بدمج المكونات في المنتج النهائي. مثال على ذلك هو مشكلة النظام الغذائي التي درسها جورج دانزيج عام 1947. يتم إعطاء عدد من المواد الخام ، مثل الشوفان ولحم الخنزير وزيت عباد الشمس ، إلى جانب محتواها الغذائي ، مثل البروتين والدهون وفيتامين أ وسعرها للكيلوغرام. يتمثل التحدي في مزج منتج نهائي واحد أو أكثر من المواد الخام بأقل تكلفة ممكنة مع احترام الحد الأدنى والحد الأقصى لقيمتها الغذائية.
التطبيق الكلاسيكي لمشكلة التحسين الخطي هو تحديد التوجيه للاحتياجاتحركة الاتصالات السلكية واللاسلكية أو شبكات النقل. في نفس الوقت ، يجب أن يتم توجيه التدفقات عبر الشبكة بحيث يتم تلبية جميع متطلبات حركة المرور دون انتهاك شروط النطاق الترددي.
في النظرية الرياضية ، يمكن استخدام التحسين الخطي لحساب الاستراتيجيات المثلى في الألعاب ذات المجموع الصفري لشخصين. في هذه الحالة ، يتم حساب التوزيع الاحتمالي لكل مشارك ، وهو معامل الخلط العشوائي لاستراتيجياته.
لا توجد عملية تجارية ناجحة في العالم ممكنة بدون التحسين. هناك العديد من خوارزميات التحسين المتاحة. بعض الطرق مناسبة فقط لأنواع معينة من المشاكل. من المهم أن تكون قادرًا على التعرف على خصائصها وتحديد طريقة الحل المناسب.
