طريقة هوموري. حل مشاكل البرمجة الصحيحة

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

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

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

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

ولإثبات الخوارزميات العددية في حل المشاكل، يصبح من الضروري فرض شروط إضافية مختلفة.

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

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

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

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

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

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

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

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