مشاكل البرمجة الخطية وحلولها وتطبيقاتها [بمثال]

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

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

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

الآن تكلفك كيس واحد من البرتقال 500 روبية هندية بينما يكلفك كيس التفاح 750 روبية هندية. يمكنك جني 100 روبية هندية من بيع كيس واحد من البرتقال و 200 روبية هندية من بيع كيس واحد من التفاح.

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

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

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

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

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

فيما يلي بعض المصطلحات الأساسية للبرمجة الخطية:

قيد

تسمى قيود (أو قيود) متغيرات قرارك بالقيود. معظم قيود الوقت هي القيود التي لديك على مواردك لحل مشكلة ما.

متغير القرار

تحدد هذه المتغيرات مخرجاتك. تعتمد نتيجتك على هذه المتغيرات ، ولهذا نسميها "متغيرات القرار".

تقييد عدم السلبية

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

دالة الهدف

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

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

يجب أن تعرف كيفية صياغة البرمجة الخطية لتطبيقها في الحياة الواقعية. لنفترض أنك شركة مصنعة للألعاب وأنت تنتج لعبتين فقط: A و B. بشكل تقريبي ، تتطلب ألعابك مصدرين X و Y لتصنيعها. فيما يلي متطلبات لعبك:

• تتطلب منك وحدة واحدة من اللعبة "أ" وحدة واحدة من المورد X وثلاث وحدات من المورد "ص"

• تتطلب وحدة واحدة من اللعبة B وحدة واحدة من المورد X ووحدتين من المورد Y

لديك خمس وحدات من المورد X و 12 وحدة من المورد Y. هوامش ربحك من بيع هذه الألعاب هي:

• 6 روبية هندية على كل وحدة مباعة من اللعبة أ
• 5 روبية هندية على كل وحدة مباعة من اللعبة "ب"

كم عدد وحدات كل لعبة ستنتجها لتحقيق أقصى ربح؟

الحل

دعنا نمثل مشكلة البرمجة الخطية في معادلة:

ع = 6 أ + 5 ب

هنا ، يشير z إلى إجمالي الربح ، حيث يشير a إلى العدد الإجمالي لوحدات اللعبة A و b يشير إلى العدد الإجمالي للوحدات B. هدفنا هو تعظيم قيمة Z (الربح).

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

أ + ب 5

الآن كل وحدة من اللعبة A و B تتطلب 3 و 2 من المورد Y على التوالي. ولدينا إجمالي 12 وحدة فقط من المورد Y ، لذا من الناحية الحسابية ، سيبدو كما يلي:

3 أ + 2 ب 12

تذكر أن قيم وحدات اللعبة A يمكن أن تكون بالأعداد الصحيحة فقط. هذا يعني أن لدينا أيضًا قيود a-> 0 و b <-0.

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

قراءة: أفكار وموضوعات مشروع البرمجة الخطية

خطوات صياغة مسائل البرمجة الخطية

لصياغة مشكلة البرمجة الخطية ، اتبع الخطوات التالية:

• أوجد متغيرات القرار
• ابحث عن الوظيفة الموضوعية
• التعرف على القيود
• تذكر القيود غير السلبية

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

حل مشاكل البرمجة الخطية مع R.

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

مثال

لنبدأ بمشكلة أساسية. لدى المؤسسة منتجان بسعر بيع يبلغ 25 روبية هندية و 20 روبية هندية ويطلق عليهما المنتج أ و ب على التوالي. كل يوم ، لديهم 1800 وحدة من الموارد لإنتاج هذه المنتجات. يتطلب المنتج "أ" 20 وحدة موارد ، بينما يتطلب "ب" 12 وحدة موارد. يبلغ وقت الإنتاج لكل من هذين المنتجين أربع دقائق ، وتحصل المنظمة على إجمالي ثماني ساعات عمل كل يوم. المشكلة ما هي كمية الإنتاج لكل من هذه المنتجات لتعظيم أرباح الشركة؟

المحلول:

سنبدأ في حل هذه المشكلة بتحديد وظيفتها الموضوعية:

الحد الأقصى (المبيعات) = الحد الأقصى (25 ص 1 + 20 ص 2 )

هنا ، 25 و 20 هما أسعار المنتجين A و B على التوالي ، y1 هو إجمالي وحدات المنتج A المنتج و y2 هو إجمالي وحدات المنتج B المنتج. متغيرات القرار لدينا هي y1 و y2.

سنقوم الآن بتعيين القيود لمشكلتنا:

قيد الموارد:

20 ذ 1 + 12 ص 2 1800

ضيق الوقت:

4 ص 1 + 4 ص 2 8 * 60

نهدف إلى العثور على العدد الصحيح من المنتجات التي يتعين علينا تصنيعها لتحقيق أقصى ربح.

استخدام R لحل المشكلة:

سنستخدم lpsolve لحل مشكلة LP هذه ونبدأ بتعيين وظيفة الهدف:

> تتطلب (lpSolve)

تحميل الحزمة المطلوبة: lpSolve

> الهدف. في <- ج (25 ، 20)

> الهدف

[1] 25 20

ثم سنبني مصفوفة للقيود:

> const <- المصفوفة (c (20، 12، 4، 4)، nrow = 2، byrow = TRUE)

> const

[، 1] [، 2]

[1 ،] 20 12

[2،] 4 4

> time_constraints <- (8 * 60)

> Resource_constraints <- 1800

> قيود الوقت

[1] 480

> Resource_constraints

[1] 1800

لنقم الآن بإنشاء المعادلات المحددة بالفعل:

> rhs <- c (resources_constraints ، time_constraints)

> rhs

[1] 1800480

> الاتجاه <- ج ("<=" ، "<=")

> الاتجاه

[1] "<=" "<="

بمجرد إضافة جميع المعلومات الضرورية ، يمكننا البدء في العثور على الإجابة المثلى. صيغة الحزمة الخاصة بنا هي:

lp (الاتجاه ، الهدف ، الثابت ، الثابت ، الثابت ، الثابت)

> الأمثل <- lp (direction = "max" ، object.in ، const ، direction ، rhs)

> الأمثل

النجاح: الوظيفة الهدف هي 2625

> ملخص (مثالي)

طول وضع الطبقة

الاتجاه 1 -لا- رقمي

x.count 1 -لا- رقمي

الهدف 2 -لا- رقمي

كونست.كونت 1 -لا- رقمي

القيود 8 -لا- رقمية

int.count 1 -لا- رقمي

int.vec 1 -none- رقمي

bin.count 1 -none- رقمي

binary.vec 1-بدون- رقمي

num.bin.solns 1-بدون- رقمي

الهدف 1 -لا- رقمي

الحل 2 -لا- رقمي

تحضير 1-بلا- رقمي

compute.sens 1 - بدون - رقمي

Sens.coef. من 1 - بدون - رقمي

Sens.coef.to 1 - بدون - رقمي

ثنائيات 1-بلا- رقمية

ثنائيات من 1 بدون عددي

ثنائي.إلى 1-بلا- رقمي

المقياس 1 -لا- رقمي

use.dense 1-بدون- رقمي

dense.col 1 -لا- رقمي

dense.val 1 -لا- رقمي

dense.const.nrow 1-بدون- رقمي

dense.ctr 1 -لا- رقمي

use.rw 1 -none- رقمية

tmp 1 - بدون حرف

الحالة 1 -لا- رقمية

بعد تشغيل الكود أعلاه ، يمكنك الحصول على الحلول المطلوبة لمشكلتنا.

القيم المثلى لـ y1 و y2:

تذكر أن y1 و y2 هما وحدتا المنتج A والمنتج B اللذان كان علينا إنتاجهما:

> الحل الأمثل

[1] 4575

رقم المبيعات الأمثل:

الحد الأقصى للربح الذي يمكننا تحقيقه بالقيم التي تم الحصول عليها لـ y1 و y2 هو:

> الأمثل $ objval

[1] 2625

اقرأ أيضًا: الجبر الخطي لتعلم الآلة

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

كما ذكرنا سابقًا ، تجد البرمجة الخطية تطبيقات في العديد من الصناعات. فيما يلي بعض المجالات التي نستخدمها فيها:

• مع تزايد شعبية خدمات التوصيل ، أصبحت البرمجة الخطية واحدة من أكثر الطرق المفضلة لإيجاد المسارات المثلى. عندما تأخذ Ola أو Uber ، سيستخدم البرنامج البرمجة الخطية للعثور على أفضل طريق. تستخدمه أيضًا شركات التوصيل مثل Amazon و FedEx لتحديد أفضل الطرق لرجال التوصيل. يركزون على تقليل وقت التسليم والتكلفة.
• يعمل التعلم الخاضع للإشراف في التعلم الآلي على المفاهيم الأساسية للبرمجة الخطية. في التعلم الخاضع للإشراف ، يجب عليك العثور على النموذج الرياضي الأمثل للتنبؤ بالمخرجات وفقًا لبيانات الإدخال المقدمة.
• يستخدم قطاع البيع بالتجزئة البرمجة الخطية لتحسين مساحة الرف. مع توفر العديد من العلامات التجارية والمنتجات ، يعد تحديد مكان وضعها في المتجر مهمة صعبة للغاية. يمكن أن يؤثر وضع المنتج في المتجر على مبيعاته بشكل كبير. تستخدم سلاسل البيع بالتجزئة الرئيسية مثل Big Bazaar و Reliance و Walmart وما إلى ذلك البرمجة الخطية لتحديد موضع المنتج. يجب عليهم مراعاة مصلحة المستهلكين مع ضمان أفضل وضع للمنتج لتحقيق أقصى ربح.
• تستخدم الشركات البرمجة الخطية لتحسين سلاسل التوريد الخاصة بها. تعتمد كفاءة سلسلة التوريد على العديد من العوامل مثل الطرق المختارة ، والتوقيتات ، وما إلى ذلك. باستخدام البرمجة الخطية ، يمكنهم العثور على أفضل الطرق ، والتوقيتات ، والتخصيصات الأخرى للموارد لتحسين كفاءتها.

تعرف على المزيد حول البرمجة الخطية وعلوم البيانات

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

يمكنك معرفة المزيد حول علم البيانات والمفاهيم المتعلقة به ، من خلال الانتقال إلى مدونتنا. لدينا العديد من الموارد القيمة لمساعدتك على تعلم المزيد. فيما يلي بعض القراءة الإضافية:

• أهم الأسباب لتصبح عالم بيانات
• الخوارزميات التي يجب أن يعرفها كل عالم بيانات
• كيف تصبح عالم بيانات

من ناحية أخرى ، يمكنك الحصول على دورة في علوم البيانات للتعلم من خبراء الصناعة. ستتعلم بشكل تفاعلي من خلال مقاطع الفيديو والاختبارات والمشاريع. سيساعدك الحصول على دورة تدريبية على تعلم المهارات اللازمة لتصبح عالم بيانات محترفًا. تحقق من دبلوم PG الخاص بـ IIIT-B & upGrad في علوم البيانات والذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، وجهاً لوجه مع مرشدين في الصناعة ، وأكثر من 400 ساعة التعلم والمساعدة في العمل مع الشركات الكبرى.