مرجع
آخر الزيارات

برمجة الأعداد الصحيحة

1٬274 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. تتناول المقالة 15 قسماً، منها «,»، «تحقيق الدوال المنطقية» و«المتغيرات».
المحتويات
  1. ,
  2. تحقيق الدوال المنطقية
  3. المتغيرات
  4. التخطيط الإنتاجي
  5. مثال
  6. بحيث ان where and
  7. الجدولة الزمني
  8. التطبيقات
  9. رد الفعل للبحث الأمثل
  10. استخدام أحادية النمط الكاملة
  11. الخوارزميات
  12. الشكل القياسي والمتعارف عليه للبرمجة الخطية الصحيحة
  13. الخوارزميات الدقيقة
  14. ُطرق الحدس المهنية
  15. شبكة هوبفيلد

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

من جانب آخر، البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.

إضافةً إلى ذلك، حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود.

,

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

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

والبرمجة الخطية الصحيحة بالشكل القياسي يُعبر عنها كالتالي:

وعلى صعيد آخر، بحيث أن المُدخلات ال C , B عبارة عن متجهات وال A عباره عن مصفوفة تحتوي على قيم صحيحة

تحقيق الدوال المنطقية

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

المتغيرات

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

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

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

التخطيط الإنتاجي

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

مثال

ومن جهة أخرى، الحل الوحيد الأمثل التي تصل فيه الدلة إلى حالة الإستقرار وتكون برمجة خطية غير مقيده هو (1.8, 2.8) حيث أن قيمة دالة الهدف في النقطة السابقة هي القيمة 2.8

وفي السياق ذاته، الخطوط الزرقاء مع المحاور تُعبِر عن مجسم للبرمجة الخطية البسيطة المُعطى بشروط عدم التساوي.

ومن جهة أخرى، لاحظ أنه إذا قرَّبنا قيمة دالة الهدف (2.8) إلى أقرب عدد صحيح (3) من الشكل نلاحظ أنه خارج منطقة الحل.

الشكل التالي يوضح المسألة التالية:

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

ومن ناحية أخرى، الهدف من الأمثَلَه هو تحريك الخط الأسود المُنقَّط أعلى مايمكن بشرط أن يضل ملامس للمُجسم. نقاط الحل الأمثل لهذه المسألة هي (1,2) و (2, 2) حيث أن قيمة دالة الهدف في النقطتين السابقتين هي القيمة 2.

بحيث ان where and

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

كذلك، وبما أن ال يكون في نطاق الحل ونحن نعرف أن ال نفرض ان . Let هي عبارة عن العناصر المكافئة للأعمدة الأساسية التي تُعبر عن الحلول الأساسية . بتعريف الأساسيات، هناك بعض المصفوفات الجزئية المربعة B من A مع أعمدة خطية مستقلة مثال ذلك of

كل الحلول الأساسية الممكنة أعداد صحيحة.

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

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

أن ال B أعداد صحيحة. ولذلك:

ومن ناحية أخرى، حيث أن ال A, B, C أعداد صحيحة وال A أُحادية النمط، لاحقًا كل الحلول الأساسية الممكنة تكون أعداد صحيحة. بناء على ذلك، الحل الناتج من طريقة التبسيط (برمجة) نضمن بأن يكون عدد صحيح. لتوضيح أن كل الحلول الأساسية الممكنة تكون أعداد صحيحة نفرض أن ال x هو حل أساسي عشوائي ضمن نطاق الحل

الجدولة الزمني

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

التطبيقات

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

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

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

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

رد الفعل للبحث الأمثل

طريقة حل المسائل الحسابية لإيجاد مسارات جديدة عن طريق الرسم

استخدام أحادية النمط الكاملة

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

الخوارزميات

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

الشكل القياسي والمتعارف عليه للبرمجة الخطية الصحيحة

وفي هذا الصدد، البرمجة الخطية الصحيحة في الشكل المُتعارف عليه يُعبر عنها كالتالي:

الخوارزميات الدقيقة

وفي هذا الصدد، Lenstra in 1983 يوضح أنه عندما يكون عدد المتغيرات ثابت، فإن البرمجة الصحيحة يمكن أن تُحل باستخدام كثيرة الحدود.

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

من جهة ثانية، عندما المصفوفة A لاتكون أحادية النمط، هناك تغيٌر في الخوارزميات التي تُستعمل في حل البرمجة الخطية الصحيحة بشكل دقيق.

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

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

ُطرق الحدس المهنية

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

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

  • هناك طُرق أخرى للحدس المهني من الممكن أن تُطبق على البرمجة الخطية الصحيحة:
  • تسلق الهضاب
  • تخمير محاكى

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

شبكة هوبفيلد

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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