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

كتابة: Asmaa آخر تحديث: 20 سبتمبر 2021 , 13:03

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

للعثور على الفرق بين المعادلتين أي الخطية وغير الخطية يجب على المرء معرفة التعريفات الخاصة بهما.

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

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

أمثلة:

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

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

  • إنه لا يشكل خطاً مستقيماً ولكنه يشكل منحنى.
  • المعادلة غير الخطية لها الدرجة 2 أو أكثر من 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 هي معادلة خطية في متغيرين.[1]

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى
إغلاق