تعريف البرمجة الخطية وتطبيقاتها

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

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

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

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

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

بعض الافتراضات التي تم اتخاذها أثناء العمل مع البرمجة الخطية هي:

• يجب التعبير عن عدد القيود بالكمية.
• يجب أن تكون العلاقة بين القيود والوظيفة الموضوعية خطية.
• يجِبُ تَحسينُ الوظيفةِ الخطِيَّةِ (أي الوظيفةِ الموضوعِيَّةِ).

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

المكونات الأساسية لـ LP هي كما يلي:

• متغيرات القرار.
• القيود.
• البيانات.
• وظائف موضوعية.

أساليب البرمجة الخطية

• حل البرمجة الخطية بطريقة Simplex.
• حل البرمجة الخطية باستخدام R.
• حل البرمجة الخطية بطريقة رسومية
• حل البرمجة الخطية باستخدام برنامج حل مفتوح، (5983).

شروط البرمجة الخطية

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

مجالات تطبيق البرمجة الخطية

من الأمثلة في الواقع هو النظر في القيود المفروضة على العمالة والمواد وتحقيق أفضل مستويات الإنتاج لتحقيق أقصى قدر من الربح في ظروف معينة، وهذا يعد جزءا من منطقة حيوية في علم الرياضيات المعروفة باسم تقنيات التحسين وتطبيقات LP في بعض المجالات الأخرى هي:

• الهندسة: “تساعد على حل مشاكل التصميم والتصنيع وتحسين الشكل النهائي للمنتجات.
• التصنيع الفعال: لتعظيم الربح تستخدم الشركات التعبيرات الخطية.
• صناعة الطاقة: توفر طرقاً لتحسين نظام الطاقة الكهربائية.
• تحسين النقل: لكفاءة التكلفة والوقت.

أهمية البرمجة الخطية

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

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

• توفر البرمجة الخطية رؤى لمشاكل العمل.
  يساعد على حل المشاكل متعددة الأبعاد.
  تساعد LP في إجراء التعديلات وفقًا لتغير الحالة.
• يساعد تحليل تكلفة الإنتاج والأرباح في اتخاذ أفضل الحلول المثلى باستخدام LP للأشياء المختلفة.

مشاكل البرمجة الخطية

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

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

خطوات استخدام البرمجة الخطية

• الخطوة 1: تحديدُ مشكلةٍ معينةٍ (أيِّ اكتبْ قيودَ عدمِ المساواةِ والوظيفةِ الموضوعيَّةِ).
• الخطوة 2: من خلال إضافة متغير الركود إلى كل متباين، يمكن تحويل المتباينات المعطاة إلى معادلات.
• الخطوة 3: يمكن إنشاء لوحة بسيطة أولية وكتابة دالة الهدف في الصف السفلي حيث يتم عرض كل قيد من قيود عدم المساواة في صفه الخاص، ويمكن تمثيل المشكلة في شكل مصفوفة معززة تسمى اللوحة الأولية البسيطة.
• الخطوة 4: يتم تحديد العمود المحوري من خلال تحديد أكبر إدخال سلبي في الصف السفلي، حيث يُعد أكبر معامل في دالة الهدف، والذي يساعد على زيادة قيمة الدالة الهدف بأسرع ما يمكن.
• الخطوة 5: لحساب حاصل القسمة، نحتاج إلى قسمة المدخلات في العمود الأقصى اليمين للإدخالات في العمود الأول، باستثناء الصف السفلي، ويتم اختيار أصغر حاصل قسمة الذي يحدد الصف المطابق. ستتم اعتبار الصف المحدد والعنصر المحدد في هذه الخطوة عنصرًا محوريًا.
• الخطوة 6: يتم إجراء التدوير المحوري لجعل جميع الإدخالات الأخرى في العمود تساوي صفرًا.
• الخطوة 7: إذا لم تكن هناك إدخالات سلبية في الصف السفلي، يمكن إنهاء العملية، وإلا يجب البدء من الخطوة الرابعة.
• الخطوة 8: أخيرًا، تم تحديد الحل النهائي المتعلق بلوحة الطباعة البسيطة.

الفرق بين المعادلات الخطية وغير الخطية

لمعرفة الاختلاف بين المعادلتين، سواء كانت خطية أم غير خطية، يتعين على الفرد معرفة التعريفات الخاصة بهما.

المعادلات الخطية

• يشكّل خطٌ مستقيمٌ أو يُمثّل معادلةَ الخط المستقيم.
• تتميز بأن لديها درجة واحدة فقط، أو يمكن تعريفها أيضًا على أنها معادلة بدرجة قصوى 1.
• تشكل كل هذه المعادلات خطًا مستقيمًا في المستوى XY، حيث يمكن لهذه الخطوط أن تمتد في أي اتجاه ولكن بشكل مستقيم.
• التمثيل العام للمعادلة الخطية هو y = mx + c، حيث x و y هما المتغيران، و m هو ميل الخط و c هي قيمة ثابتة.

أمثلة:

10x = 1
9y + x + 2 = 0
4y = 3x
99x + 12 = 23 y

المعادلات غير الخطية

• إنه لا يشكل خطًا مستقيمًا، بل يشكل منحنى.
• المعادلة غير الخطية لها درجة 2 أو أكثر من ذلك، ولكنها ليست أقل من 2.
• إذا زادت قيمة الدرجة، سيزداد انحناء المنحنى في الرسم البياني.
• التمثيل العام للمعادلات غير الخطية هي ax2 + by2 = c ، حيث xو y هما المتغيرات، و a و b و c هي الثوابت.

أمثلة:

x2+y2 = 1
x2 + 12xy + y2 = 0
x2+x+2 = 25 .

ملحوظة:

عادةً ما تحتوي المعادلة الخطية على متغير واحد، وإذا كانت المعادلة تحتوي على متغيرين فإنها تعرف عادةً بأنها معادلة خطية في متغيرين، على سبيل المثال، إن 5x + 2 = 1 هي معادلة خطية في متغير واحد، بينما 5x + 2y = 1 هي معادلة خطية في متغيرين.