يتم استخدام مشكلة البرمجة الخطية لإيجاد إما الحد الأقصى أو الحد الأدنى لوظيفة موضوعية تخضع لبعض القيود. هذه القيود عادة ما تكون من عدم المساواة. عندما يتم استيفاء هذه القيود ، يحصل المرء على حل ممكن. عندما يكون أحد هذه الحلول إما الحد الأقصى أو الحد الأدنى حسب الوظيفة الموضوعية ، يحصل المرء على الحل الأمثل /
في العديد من مواقف الحياة الواقعية ، قد يتطلب المرء أن تكون متغيرات القرار عددًا صحيحًا حيث يتعين على المرء معرفة عدد الحافلات المطلوبة أو عدم وجود عدد من الموظفين المطلوب نشرهم وما إلى ذلك ، وتسمى هذه الفئات من المشكلات باسم مشاكل البرمجة الصحيحة.
لا يمكن حل مشاكل البرمجة الصحيحة باستخدام طريقة Simplex ، يجب حلها باستخدام طريقة الفرع والربط. يمكن للمرء أن يتخيل المنطقة المجدية المحاطة بالقيود في مشكلة تحسين محدبة بخطوط أفقية وعمودية مرسومة عند كل نقطة عدد صحيح. سيقع حل مشكلة البرمجة الخطية الصحيحة على أي من الخطوط الأفقية أو الرأسية داخل المنطقة المجدية. لم تعد المجموعة المجدية محدبة ويصبح حلها شاقًا للغاية بسبب الطبيعة غير المحدبة.
هناك عدة أنواع مختلفة من الطرق المستخدمة لحل مشاكل البرمجة الخطية الصحيحة. الطريقة الأكثر شيوعًا هي طريقة الفرع والربط.
يتضمن الفرع والربط تخفيف قيود عدد صحيح وحل البرنامج الخطي باستخدام إما الأسلوب الرسومي أو البسيط. إذا تحولت جميع متغيرات القرار إلى أعداد صحيحة بعد تخفيف قيود الأعداد الصحيحة ، فإن مجموعة الحلول صحيحة.
ومع ذلك ، إذا لم ينتج عن حل البرنامج الخطي المريح قيمًا صحيحة كحلول لمتغيرات القرار ، يتعين على المرء أن يستخدم أسلوبًا فرعيًا ومحدودًا عن طريق حل المشكلة الأصلية بقيمة صحيحة محدودة لمتغير القرار مضافًا إلى مجموعة القيود. عندما يتم حل مجموعة المشكلات الجديدة هذه ، إذا كانت تنتج قيمة مثلى بقيم صحيحة ، فقد تكون هناك قيم أفضل وبالتالي يجب التحقق من الفروع الأخرى. في النهاية يجب اختيار الحل من إحدى العقد الموجودة في الفروع التي تمت زيارتها والتي تكون إما الحد الأقصى أو الحد الأدنى. علينا أن نحافظ بشكل متكرر على حل استرخاء خطي للمشكلة باستخدام حدود صحيحة أحدث والتحقق من أفضل حل ممكن في السياق. بالنسبة لمشكلة البرمجة الصحيحة ذات الأبعاد الأقل ، قد يكون من الأفضل استخدام طريقة رسومية لحل المشكلة.
امتداد مشكلة البرمجة الصحيحة هو مشكلة البرمجة 0-1 حيث يمكن أن تأخذ متغيرات القرار 0 أو 1. هذا النوع من المشاكل مفيد بشكل خاص في حل المشكلات المشابهة لمسألة knap sack.
