وهناك الكثير من المهام ذات الطابع الاقتصادي ، والمشاكليرتبط التخطيط وحتى حل المشكلات من المجالات الأخرى للنشاط البشري بالمتغيرات المتعلقة بالأعداد الصحيحة. نتيجة لتحليلهم والبحث عن الحلول المثلى ، ظهر مفهوم المشكلة المتطرفة. ميزاته هي الميزة أعلاه لاتخاذ قيم عدد صحيح ، والمشكلة نفسها تعتبر في الرياضيات كبرمجة عدد صحيح.
كما الاستخدام الرئيسيالمهام مع المتغيرات التي تأخذ القيم الصحيحة هي التحسين. وتسمى الطريقة التي تستخدم البرمجة الخطية عدد صحيح أيضا طريقة لقطة.
طريقة Gomori حصلت على اسمها بالاسمالرياضيات ، أول من وضع خوارزمية في 1957-1958 ، والتي لا تزال تستخدم على نطاق واسع لحل مشاكل البرمجة الخطية عدد صحيح. الشكل المتعارف عليه لمشكلة البرمجة الصحيحة يجعل من الممكن الكشف بشكل كامل وواضح عن مزايا هذه الطريقة.
طريقة جوموري للخطيةالبرمجة تعقد مهمة العثور على القيم المثلى. بعد كل شيء ، فإن النزاهة هي الشرط الرئيسي ، بالإضافة إلى جميع معالم المشكلة. غالبًا ما تكون هناك حالات لا تصل فيها المهمة ، التي لديها خطط مقبولة (عدد صحيح) ، إلى الحد الأقصى عندما يكون للوظائف المستهدفة قيود على مجموعة مقبولة. هذا بسبب عدم وجود حلول عدد صحيح تمامًا. بدون هذا الشرط ، كقاعدة عامة ، يتم العثور على ناقل مناسب في شكل حل.
لإثبات الخوارزميات العددية في حل المشكلات ، يصبح من الضروري فرض شروط إضافية متعددة.
Используя метод Гомори, обычно считают множество تخطط لمشكلة يحدها ما يسمى متعدد الوجوه من الحلول. على هذا الأساس ، يترتب على ذلك أن مجموعة جميع خطط الأعداد الصحيحة للمهمة المعنية لها قيمة محدودة.
أيضًا ، لضمان سلامة الوظيفة ، يُفترض أن معاملات القيم هي أعداد صحيحة أيضًا. على الرغم من شدة هذه الظروف ، يمكن تخفيفها قليلاً.
تشتمل طريقة Gomory ، في جوهرها ، على بناء قيود تقطع الحلول التي ليست غير متكاملة. في هذه الحالة ، لا يتم قطع حل واحد لخطة الأعداد الصحيحة.
تتضمن خوارزمية حل المشكلةالعثور على خيارات مناسبة من خلال طريقة simplex ، مع عدم مراعاة شروط النزاهة. إذا كانت جميع مكونات الخطة المثالية تحتوي على حلول متعلقة بالأعداد الصحيحة ، فيمكننا افتراض أن هدف البرمجة الصحيحة قد تحقق. من الممكن الكشف عن عدم إمكانية حل المشكلة ، لذلك نحصل على دليل على أن مشكلة البرمجة الصحيحة لا يوجد لها حل.
فمن الممكن أن في المكوناتالحلول المثالية هي أرقام غير عدد صحيح. في هذه الحالة ، يتم إضافة قيود جديدة إلى جميع قيود المهمة. للقيد الجديد يتميز بوجود عدد من الخصائص. بادئ ذي بدء ، يجب أن يكون خطيًا ، ويجب أن يقطع خطة غير صحيحة عن المجموعة المثلى التي تم العثور عليها. لا ينبغي أن تضيع حل عدد صحيح واحد ، اقتطاعها.
عند إنشاء قيد ، ينبغي للمرء اختيار مكون الخطة الأمثل مع الجزء الكسري الأكبر. ستتم إضافة هذا التقييد إلى جدول simplex الموجود بالفعل.
نجد حل المشكلة التي تم الحصول عليها باستخدامالبسيط العادي يحول. نحن نتحقق من حل المشكلة لوجود خطة عدد صحيح مثلى ، إذا تم استيفاء الشرط ، يتم حل المشكلة. إذا تم الحصول على النتيجة مرة أخرى مع وجود حلول غير متكاملة ، فإننا نقدم قيدًا إضافيًا ، ونكرر عملية الحساب.
بعد أن نفذنا عددًا محدودًا من التكرارات ، نحقق الخطة المثلى للمشكلة ، التي تم وضعها قبل برمجة عدد صحيح ، أو نثبت عدم إمكانية حل المشكلة.
