( هي طريقه لايجاد القيمه العظمى او الصغرى لداله تحت قيود معينه كل منها عباره عن متباينه خطيه )
برمجة خطية
هي طريقة لإيجاد القيمة العظمى أو الصغرى لدالة تحت قيود معينة كل منها عبارة عن متباينة خطية.
تُستخدم هذه الطريقة في مجموعة واسعة من التطبيقات, بما في ذلك:
- التحسين المالي
- التخطيط الإنتاجي
- الجدولة اللوجستية
توجد طريقتان رئيسيتان لحل مشاكل البرمجة الخطية:
- طريقة السيمبلكس
- طريقة الحاجز الداخلي
وبشكل عام، تكون طريقة السيمبلكس أكثر كفاءة للمشاكل ذات عدد كبير من المتغيرات، بينما تكون طريقة الحاجز الداخلي أكثر كفاءة للمشاكل ذات عدد كبير من القيود.
التعريف الرياضي
مشكلة البرمجة الخطية هي كما يلي:
$\min \text or \max \space c^Tx $
بحيث يكون
$Ax \le b$
و $x \ge 0$
حيث:
- $c$ هو متجه من معاملات الدالة الهدف.
- $x$ هو متجه المتغيرات.
- $A$ هي مصفوفة القيود.
- $b$ هو متجه حدود القيود.
الحل باستخدام طريقة السيمبلكس
طريقة السيمبلكس هي خوارزمية لحل مشاكل البرمجة الخطية. وهي تعمل عن طريق تكرار تحسين حل قابل للتطبيق حتى يتم الوصول إلى الحل الأمثل.
في كل تكرار، تحدد طريقة السيمبلكس متغيرًا غير أساسي للدخول إلى مجموعة المتغيرات الأساسية ومتغيرًا أساسيًا للخروج من مجموعة المتغيرات الأساسية. يتم اختيار المتغيرات التي تدخل وتخرج بحيث يتم تقليل قيمة الدالة الهدف.
تستمر طريقة السيمبلكس حتى لا يمكن إجراء أي تحسينات أخرى. وعند هذه النقطة، يكون الحل الأمثل قد تم الوصول إليه.
الحل باستخدام طريقة الحاجز الداخلي
طريقة الحاجز الداخلي هي خوارزمية أخرى لحل مشاكل البرمجة الخطية. وهي تعمل عن طريق إيجاد حل داخلي قابل للتطبيق وتحريك هذا الحل تدريجياً نحو الحل الأمثل.
في كل تكرار، تحسب طريقة الحاجز الداخلي اتجاه البحث الذي من شأنه تقليل قيمة الدالة الهدف. ثم تتحرك بطريقة خطية على طول هذا الاتجاه حتى يتم الوصول إلى حل داخلي قابل للتطبيق جديد.
تستمر طريقة الحاجز الداخلي حتى لا يمكن إجراء أي تحسينات أخرى. وعند هذه النقطة، يكون الحل الأمثل قد تم الوصول إليه.
تطبيقات البرمجة الخطية
تُستخدم البرمجة الخطية في مجموعة واسعة من التطبيقات، بما في ذلك:
التحسين المالي: يمكن استخدام البرمجة الخطية لتحسين محافظ الأسهم والسندات والقرارات الاستثمارية الأخرى.
التخطيط الإنتاجي: يمكن استخدام البرمجة الخطية لتخطيط مستويات الإنتاج وتخصيص الموارد لتحقيق أقصى ربح أو تقليل التكاليف.
الجدولة اللوجستية: يمكن استخدام البرمجة الخطية لجدولة عمليات النقل والتوزيع لتحقيق أقصى قدر من الكفاءة وتقليل التكاليف.
مزايا البرمجة الخطية
تتمتع البرمجة الخطية بعدد من المزايا، منها:
يمكن استخدامها لحل مجموعة واسعة من المشاكل.
توجد خوارزميات فعالة لحل مشاكل البرمجة الخطية.
يمكن استخدام البرمجة الخطية لتحسين مجموعة متنوعة من القرارات.
عيوب البرمجة الخطية
هناك بعض عيوب البرمجة الخطية، منها:
قد يكون من الصعب صياغة بعض المشاكل بالصيغة الخطية.
يمكن أن تكون مشاكل البرمجة الخطية كبيرة الحجم وحسابية المكثفة.
قد لا تكون حلول مشاكل البرمجة الخطية مثالية في جميع الحالات.
الخلاصة
البرمجة الخطية هي أداة قوية لحل مجموعة واسعة من المشاكل. يمكن استخدامها لتحسين مجموعة متنوعة من القرارات، بما في ذلك القرارات المالية وقرارات التخطيط الإنتاجي وقرارات الجدولة اللوجستية. على الرغم من أن البرمجة الخطية لها بعض القيود، إلا أنها لا تزال أداة قيمة لحل العديد من المشاكل في العالم الحقيقي.