--- title: "Integer programming — البرمجة الصحيحة" source: "https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9" wiki: "systems-analysis.info/int" article: "Integer_programming_—_البرمجة_الصحيحة" language: "ar" categories: - "Category:Arabic" - "Category:Operations research" - "Category:Pages with reference errors" revision_id: 3261 wiki_created_at: 2026-09-06T23:18:05Z wiki_modified_at: 2026-09-06T23:18:05Z downloaded_at: 2026-09-07T22:55:59Z --- # Integer programming — البرمجة الصحيحة **البرمجة الصحيحة** (**IP**؛ بالإنجليزية: *integer programming*) هي فرع من فروع الأمثَلة الرياضية، يدرس المسائل التي يجب أن تتخذ فيها بعض المتغيرات أو جميعها قيمًا عددية صحيحة فقط^{[\[1\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-ru-wiki-ip-1)}. الحالة الخاصة الأكثر دراسة هي **البرمجة الخطية الصحيحة** (**ILP**؛ بالإنجليزية: *integer linear programming*)، حيث تكون دالة الهدف والقيود خطية. على عكس البرمجة الخطية، حيث يمكن للمتغيرات أن تأخذ أي قيم حقيقية، فإن شرط العدد الصحيح يجعل حل مسائل البرمجة الصحيحة أكثر صعوبة بكثير^{[\[2\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-wolsey-book-2)}. تجد البرمجة الصحيحة تطبيقات واسعة في الاقتصاد، والخدمات اللوجستية (اللوجستيات)، وتخطيط الإنتاج، وغيرها من المجالات التي تكون فيها المتغيرات بطبيعتها متقطعة (على سبيل المثال، عدد الوحدات المنتجة أو عدد العمال)^{[\[3\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-pisaruk-book-3)}. ## التعريف والمصطلحات يمكن كتابة المسألة العامة للبرمجة الخطية الصحيحة على النحو التالي: إيجاد المتجه $x$ الذي: يُعظّم (أو يُصغّر) $c^{T}x$ وفقًا للشروط: $Ax \leq b$ $x \geq 0$ $x \in {\mathbb{Z}}^{n}$ (جميع مكونات المتجه $x$ هي أعداد صحيحة) حيث $x$ هو متجه المتغيرات، و$c$ و$b$ هما متجهان، و$A$ هي مصفوفة المعاملات^{[\[4\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-conforti-book-4)}. بناءً على متطلبات المتغيرات، يتم تمييز الأنواع التالية من المسائل: - **البرمجة الصحيحة بالكامل** (Pure Integer Programming): يجب أن تكون جميع المتغيرات أعدادًا صحيحة. - **البرمجة الصحيحة المختلطة** (*mixed-integer programming, MIP*): يجب أن يكون جزء فقط من المتغيرات أعدادًا صحيحة. - **البرمجة البولانية (0-1)** (Boolean 0-1 Programming): تأخذ المتغيرات القيم 0 أو 1 فقط، مما يسمح بنمذجة القرارات المنطقية من نوع «نعم/لا». ## الخصائص الرئيسية والتعقيد ### التعقيد الحسابي تُعتبر مسألة البرمجة الخطية الصحيحة في الحالة العامة NP-صعبة (NP-hard)^{[\[5\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-karp-1972-5)}. هذا يعني أنه لا توجد خوارزمية معروفة قادرة على إيجاد الحل الأمثل الدقيق لمسألة برمجة صحيحة عامة في وقت متعدد الحدود. يرجع التعقيد إلى الطبيعة التوافقية للمسألة، حيث يمكن أن ينمو عدد الحلول الصحيحة الممكنة بشكل أسي مع زيادة عدد المتغيرات. ### العلاقة مع البرمجة الخطية (الاسترخاء الخطي) لأي مسألة برمجة صحيحة، يمكن صياغة **الاسترخاء الخطي** (linear relaxation) الخاص بها — وهي مسألة برمجة خطية (LP) يتم فيها إزالة شرط كون المتغيرات أعدادًا صحيحة. حل الاسترخاء الخطي له خاصيتان مهمتان: 1. يمكن إيجاده بسرعة أكبر بكثير (في وقت متعدد الحدود). 2. القيمة المثلى لدالة الهدف في الاسترخاء الخطي تعطي تقديرًا (حدًا أعلى لمسألة التعظيم وحدًا أدنى لمسألة التصغير) للقيمة المثلى للمسألة الصحيحة الأصلية^{[\[2\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-wolsey-book-2)}. ومع ذلك، فإن مجرد تقريب الحل الكسري للاسترخاء الخطي إلى أقرب أعداد صحيحة لا يؤدي عادةً إلى حل أمثل أو حتى مقبول للمسألة الصحيحة^{[\[1\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-ru-wiki-ip-1)}. ### خاصية الأحادية الكاملة للوحدة توجد فئة مهمة من مسائل البرمجة الخطية الصحيحة التي يمكن حلها بنفس سهولة حل استرخاءاتها الخطية. هذه هي المسائل التي تكون فيها مصفوفة القيود $A$ **أحادية الوحدة بالكامل** (totally unimodular)، أي أن محدد أي مصفوفة جزئية مربعة منها يساوي 0، +1، أو -1. إذا كانت المصفوفة $A$ أحادية الوحدة بالكامل وكان المتجه $b$ ذا قيم صحيحة، فإن جميع رؤوس متعدد السطوح للحلول الممكنة للاسترخاء الخطي ستكون تلقائيًا ذات قيم صحيحة. وبالتالي، فإن الحل الذي يتم إيجاده باستخدام طريقة سيمبلكس سيكون حلاً صحيحًا^{[\[4\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-conforti-book-4)}. من أمثلة هذه المسائل مسألة النقل ومسألة التعيين. ## طرق الحل لحل مسائل البرمجة الصحيحة العامة التي لا تتمتع بخاصية الأحادية الكاملة للوحدة، تم تطوير طرق دقيقة تعتمد على أفكار التعداد الضمني. - **طريقة التفريع والتحديد** (*Branch and Bound*) — هي الطريقة الدقيقة الرئيسية، وتعتمد على التقسيم المنهجي لمجموعة الحلول الممكنة إلى مجموعات فرعية (التفريع) واستبعاد المجموعات الفرعية التي من المؤكد أنها لا تحتوي على الحل الأمثل. يُستخدم الاسترخاء الخطي لتقييم إمكانات المجموعات الفرعية^{[\[6\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-en-wiki-ip-6)}. - **طريقة المستويات القاطعة** (طريقة غوموري؛ *Cutting Plane Method*) — هي نهج تكراري يضيف بشكل متتابع قيودًا خطية جديدة («قواطع») إلى المسألة. هذه القواطع «تقطع» الحلول الكسرية للاسترخاء الخطي دون المساس بأي حلول صحيحة ممكنة، مما يقرب تدريجيًا منطقة الحلول الممكنة للاسترخاء الخطي من الغلاف المحدب للحلول الصحيحة^{[\[6\]](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_note-en-wiki-ip-6)}. تستخدم أدوات الحل الحديثة (solvers) عادةً خوارزميات هجينة مثل **طريقة التفريع والقطع** (*Branch and Cut*)، التي تجمع بين مزايا كلا النهجين. ## أمثلة ومجالات التطبيق تسمح البرمجة الصحيحة بنمذجة العديد من المسائل الكلاسيكية في الأمثَلة التوافقية (combinatorial optimization). - *مسألة الحقيبة*: مسألة كلاسيكية في البرمجة (0-1) تتطلب اختيار مجموعة من العناصر بأقصى قيمة إجمالية، مع عدم تجاوز حد معين للوزن الإجمالي. - *مسألة البائع المتجول*: مسألة البحث عن أقصر مسار يمر عبر مجموعة محددة من المدن. يمكن صياغتها كمسألة برمجة صحيحة، حيث تمثل المتغيرات إدراج أضلاع الرسم البياني في المسار النهائي. بفضل مرونتها، تعد البرمجة الصحيحة واحدة من أكثر الأدوات المطلوبة في بحوث العمليات وتجد تطبيقات في مجالات مثل: - **اللوجستيات وإدارة سلاسل الإمداد**: أمثَلة مسارات النقل، وتحديد مواقع المستودعات، وإدارة المخزون. - **تخطيط الإنتاج**: وضع جداول الإنتاج، وتخصيص الموارد، وتحميل المعدات. - **التمويل والاقتصاد**: تكوين المحافظ الاستثمارية، ووضع ميزانيات الاستثمار الرأسمالي. - **الاتصالات والطاقة**: تصميم شبكات الاتصالات، وتخطيط تشغيل وحدات الطاقة. ## انظر أيضًا - البرمجة الخطية - طريقة التفريع والتحديد ## المراجع 1. ↑ ^{[1.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-ru-wiki-ip_1-0)} ^{[1.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-ru-wiki-ip_1-1)} "Целочисленное программирование". *Википедия*. [١] Cite error: Invalid `` tag; name "ru-wiki-ip" defined multiple times with different content 2. ↑ ^{[2.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-wolsey-book_2-0)} ^{[2.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-wolsey-book_2-1)} Wolsey, Laurence A. (2020). *Integer Programming* (2nd ed.). John Wiley & Sons. 3. [↑](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-pisaruk-book_3-0) Писарук Н.Н. (2010). *Модели и методы смешанного целочисленного программирования*. Минск: БГУ. 4. ↑ ^{[4.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-conforti-book_4-0)} ^{[4.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-conforti-book_4-1)} Conforti, M., Cornuéjols, G., & Zambelli, G. (2014). *Integer Programming*. Springer. 5. [↑](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-karp-1972_5-0) Karp, Richard M. (1972). "Reducibility among Combinatorial Problems". In: *Complexity of Computer Computations*. Springer. 6. ↑ ^{[6.0](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-en-wiki-ip_6-0)} ^{[6.1](https://systems-analysis.info/int/Integer_programming_%E2%80%94_%D8%A7%D9%84%D8%A8%D8%B1%D9%85%D8%AC%D8%A9_%D8%A7%D9%84%D8%B5%D8%AD%D9%8A%D8%AD%D8%A9#cite_ref-en-wiki-ip_6-1)} "Integer programming". *Wikipedia*. [٢]