البرمجة الخطية: ما الغرض منها ، النماذج ، القيود ، التطبيقات - رياضيات - 2026

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

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

الشكل 1. تستخدم البرمجة الخطية على نطاق واسع لتحسين الأرباح. المصدر: Piqsels.

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

Z = ل ₁ س + ك ₂ ص

مع k ₁ و k ₂ ثابت. تُعرف هذه الوظيفة باسم الوظيفة الموضوعية. بالطبع ، هناك مواقف تستحق أكثر من متغيرين للدراسة ، كونها أكثر تعقيدًا:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

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

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

تم تطوير البرمجة الخطية بشكل مستقل من قبل الفيزيائي الأمريكي وعالم الرياضيات جورج دانتزيغ (1914-2005) وعالم الرياضيات والاقتصادي الروسي ليونيد كانتوروفيتش (1912-1986) بعد فترة وجيزة من الحرب العالمية الثانية.

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

الشكل 2. علماء الرياضيات جورج دانتزيغ (يسار) وليونيد كانتوروفيتش (يمين). المصدر: F. Zapata.

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

العناصر اللازمة لإنشاء نموذج برمجة خطي مناسب لحالة عملية هي:

-دالة الهدف

-متغيرات القرار

-قيود

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

من الناحية الرياضية ، يمكن التعبير عن هذه الوظيفة باختصار باستخدام تدوين الجمع:

Z = ∑k _i x _i

في هذه المعادلة ، k _i هي معاملات و x _i هي متغيرات القرار.

متغيرات القرار هي عناصر النظام الذي يتم التحكم فيه وقيمها هي أرقام حقيقية موجبة. في المثال المقترح ، متغيرات القرار هي كمية كل منتج يتم تصنيعه للحصول على أقصى ربح.

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

أنواع القيود

يمكن أن يكون لديك عدد M من القيود ، بدءًا من j = 1 إلى j = M. رياضيا القيود ثلاثة أنواع:

1. A _j = ∑ a _ij. س _ط
2. B _j ≥ ∑ b _ij. س _ط
3. C _j ≤ ∑ c _ij. س _ط

القيد الأول هو من نوع المعادلة الخطية ويعني أن القيمة A _j ، المعروفة ، يجب احترامها.

القيدان المتبقيان هما متباينات خطية وهذا يعني أنه يمكن احترام القيم المعروفة B _j و C _j أو تجاوزها ، عندما يكون الرمز الذي يظهر هو ≥ (أكبر من أو يساوي) أو يتم احترامه أو عدم تجاوزه ، إذا كان الرمز ≤ (اقل او يساوي).

مثال نموذجي

مجالات التطبيق متنوعة للغاية ، تتراوح من إدارة الأعمال إلى التغذية ، ولكن لفهم الطريقة ، يُقترح أدناه نموذج بسيط لموقف عملي مع متغيرين.

يشتهر متجر المعجنات المحلي بتخصصين: كعكة الغابة السوداء وكعكة ساكريبانتين.

في تحضيرها يحتاجون إلى البيض والسكر. تحتاج إلى 9 بيضات و 500 غرام من السكر للغابة السوداء ، بينما تحتاج إلى 8 بيضات و 800 غرام من السكر بالنسبة للسكريبانتين. أسعار البيع المعنية هي 8 دولارات و 10 دولارات.

المشكلة هي: كم كعكة من كل نوع يجب أن يصنعها المخبز لتعظيم ربحه مع العلم أنه يحتوي على 10 كيلو من السكر و 144 بيضة؟

متغيرات القرار

متغيرات القرار هي "x" و "y" ، والتي تأخذ قيمًا حقيقية:

-x: عدد كعكات الغابة السوداء

-y: كعك من النوع المقدس.

قيود

يتم تحديد القيود من خلال حقيقة أن عدد الكعك هو كمية موجبة وهناك كميات محدودة من المواد الخام لتحضيرها.

لذلك ، في الشكل الرياضي ، تأخذ هذه القيود الشكل:

1. س ≥ 0
2. و ≥0
3. 9 س + 8 ص ≤ 144
4. 0.5 س + 0.8 ص ≤ 10

تشكل القيود 1 و 2 حالة عدم السلبية التي تم الكشف عنها سابقًا ، وجميع التفاوتات التي أثيرت خطية. في القيود 3 و 4 القيم التي يجب عدم تجاوزها: 144 بيضة و 10 كجم من السكر.

دالة الهدف

أخيرًا ، الوظيفة الموضوعية هي الربح الذي يتم الحصول عليه عند تصنيع كمية "x" من كعك الغابة السوداء بالإضافة إلى كمية "y" من sacripantines. يتم بناؤه بضرب السعر في كمية الكعك المصنوع وإضافة كل نوع. إنها دالة خطية نسميها G (x، y):

م = 8 س + 10 ص

طرق الحل

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

- طريقة بيانية أو هندسية

عندما يكون لديك مشكلة ذات متغيرين مثل تلك الموجودة في القسم السابق ، تحدد القيود منطقة متعددة الأضلاع في المستوى xy ، تسمى المنطقة المجدية أو منطقة الصلاحية.

الشكل 3. المنطقة المجدية ، حيث يوجد حل لمشكلة التحسين. المصدر: ويكيميديا ​​كومنز.

تم إنشاء هذه المنطقة باستخدام خطوط التقييد ، وهي الخطوط التي تم الحصول عليها من عدم المساواة في القيود ، والتي تعمل فقط مع علامة المساواة.

في حالة المخبز الذي يريد تحسين الأرباح ، فإن خطوط القيد هي:

1. س = 0
2. ص = 0
3. 9 س + 8 ص = 144
4. 0.5 س + 0.8 ص = 10

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

لحسن الحظ ، بالنسبة لمشكلة المعجنات ، المنطقة المجدية ليست فارغة ، لدينا أدناه.

الشكل 4. المنطقة المجدية لمشكلة المعجنات. الخط مع كسب 0 يتخطى الأصل. المصدر: F. Zapata مع Geogebra.

يتم العثور على الحل الأمثل ، إن وجد ، بمساعدة الوظيفة الهدف. على سبيل المثال ، عند محاولة العثور على أقصى ربح G ، لدينا السطر التالي ، والذي يسمى خط الربح - iso:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

باستخدام هذا الخط نحصل على جميع الأزواج (x ، y) التي توفر ربحًا معينًا G ، لذلك توجد مجموعة من الخطوط وفقًا لقيمة G ، ولكن جميعها بنفس المنحدر -k ₁ / k ₂ ، لذلك فهي خطوط متوازية.

الحل الأمثل

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

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

بالنسبة للمعجنات ، الرؤوس المرشحة هي A و B و C.

- طريقة دانتزيغ البسيطة

الطريقة الرسومية أو الهندسية قابلة للتطبيق على متغيرين. ومع ذلك ، يكون الأمر أكثر تعقيدًا عندما يكون هناك ثلاثة متغيرات ، ومن المستحيل استخدامه لعدد أكبر من المتغيرات.

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

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

التطبيقات

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

فيما يلي بعض المجالات:

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

- لإسناد المهام المناسبة لموظفي الشركة أو المصنع أو الجداول الزمنية لهم.

-في اختيار أكثر الأطعمة مغذية وبأقل تكلفة في صناعات المواشي والدواجن.

تمارين محلولة

- التمرين 1

حل نموذج البرمجة الخطية المطروحة في الأقسام السابقة بيانياً.

المحلول

من الضروري رسم مجموعة القيم التي يحددها نظام القيود المحدد في المشكلة:

1. س ≥ 0
2. و ≥0
3. 9 س + 8 ص ≤ 144
4. 0.5 س + 0.8 ص ≤ 10

المنطقة المعطاة من خلال المتباينات 1 و 2 تقابل الربع الأول من المستوى الديكارت. فيما يتعلق بالمتباينات 3 و 4 ، نبدأ بإيجاد خطوط التقييد:

9 س + 8 ص = 144

0.5 س + 0.8 ص = 10 ← 5 س + 8 ص = 100

المنطقة المجدية عبارة عن رباعي الأضلاع رءوسه هي النقاط A و B و C و D.

الحد الأدنى للربح هو 0 ، وبالتالي فإن السطر 8x + 10y = 0 هو الحد الأدنى وخطوط الربح المتساوية لها ميل -8/10 = - 0.8.

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

الشكل 5. حل رسومي للتمرين 1 ، يوضح المنطقة المجدية ونقطة الحل C في أحد رؤوس المنطقة المذكورة. المصدر: F. Zapata.

يتوافق هذا الحل مع خط منحدر -0.8 يمر عبر أي من النقاط A أو B أو C ، وإحداثياتها هي:

أ (11 ؛ 5.625)

ب (0 ؛ 12.5)

ج (16 ، 0)

حل مثالي

نحسب قيمة G لكل نقطة من هذه النقاط:

- (11 ؛ 5.625): G _A = 8 × 11 + 10 × 5.625 = 144.25

- (0 ؛ 12.5): G _B = 8 × 0 + 10 × 12.5 = 125

- (16 ، 0): G _C = 8 × 16 + 10 × 0 = 128

تم العثور على أعلى ربح في تصنيع 11 كعكة الغابة السوداء و 5625 كعكًا مقدسًا. يتوافق هذا الحل مع الحل الموجود من خلال البرنامج.

- تمرين 2

تحقق من نتيجة التمرين السابق باستخدام وظيفة Solver المتوفرة في معظم جداول البيانات مثل Excel أو LibreOffice Calc ، والتي تتضمن خوارزمية Simplex للتحسين في البرمجة الخطية.

المحلول

الشكل 6. تفاصيل الحل من التمرين 1 من خلال جدول بيانات Libre Office Calc. المصدر: F. Zapata.

الشكل 7. تفاصيل الحل من التمرين 1 من خلال جدول بيانات Libre Office Calc. المصدر: F. Zapata.

المراجع

1. متألق. البرمجة الخطية. تم الاسترجاع من: brilliant.org.
2. إبين ، 2000. بحوث العمليات في العلوم الإدارية. الخامس. الإصدار. برنتيس هول.
3. Haeussler، E. 1992. الرياضيات للإدارة والاقتصاد. الثاني. الإصدار. Grupo الافتتاحية Iberoamericana.
4. Hiru.eus. البرمجة الخطية. تم الاسترجاع من: hiru.eus.
5. ويكيبيديا. البرمجة الخطية. تعافى من: es. wikipedia.org.