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

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

البرمجة الصحيحةهي مسألة غير حتمية متعددة الحدود مسائل NP صعبة. حالة خاصة: البرمجة الخطيه الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتعتبر من المسائل الحتميه متعددة الحدود [[1]]

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

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

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}$,

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

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ,\end{aligned}}$

بحيث أن المُدخلات ال C , B عبارة عن متجهات وال A عباره عن مصفوفه تحتوي على قيم صحيحه لاحظ أنه مشابه للبرمجة الخطيه . البرمجة الخطيه الصحيحه التي ليست في الشكل القياسي يمكن تحويلها الى الشكل القياسي[[2]] عن طريق حذف شرط عدم التساوي بإضافة متغير إضافي للمعادله وإستبدال المتغيرات الغير مُقيده بالإشاره بالفرق بين متغيرين مقيدين بالإشاره .

مثال

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

IP polytope with LP relaxation

The graph on the right shows the following problem.

${\begin{aligned}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\geq 0\\x,y&\in \mathbb {Z} \end{aligned}}$

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

المتغيرات

البرمجة الخطية الصحيحه المختلطة : عباره عن مسألة تحتوي على متغيرات بعضها مُقيده بأن تكون صحيحه والبعض الآخر مسموح لها بأن تكون غير صحيح . البرمجة الخطية صفر- واحد هي المسألة التي تتضمن متغيرات مُقيدة بأن تكون صفر أو واحد . لاحظ أن المتغيرات الصحيحه المحدوده يمكن أن يُعبر عنها كخليط من المتغيرات الرقميه ، على سبيل المثال ، مُعطى متغير صحيح $0\leq x\leq U$ ، المتغير يمكن أن يُعبر عنه بإستخدام $\lfloor \log _{2}U\rfloor +1$ المتغيرات الرقيمه

$x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\rfloor +1}.$

مثال للمسائل التي يمكن صياغتها كبرمجه خطيه صحيحه

العديد من المسائل يمكن صياغتها بشكل برمجه خطيه صحيحه

• سفريات مندوب المبيعات[[3]]
• تحديد نقاط التقاطع[[4]]و[[5]]
• مجموعة ومشاكل التغليف[[6]]و[[7]]
• تحقيق الدوال المنطقيه[[8]]

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

التطبيقات

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

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

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

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

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

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

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

شبكات الإتصالات عن بعد

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

شبكات الهواتف الخلويه

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

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

الخوارزميات

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

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

بينما في الصيغه العامه الحل لمسألة البرمجة الخطية الغير مُقيدة لاتضمن بأن تكون مُثلى، لو البرمجة الخطية الصحيحه بالشكل التالي : $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ بحيث ان $A\mathbf {x} =\mathbf {b}$ where $A,\mathbf {b} ,$ and $\mathbf {c}$ حيث أن ال A, B, C أعداد صحيحه وال A أُحادية النمط، بعد ذالك كل الحلول الأساسيه الممكنه تكون أعداد صحيحة. بناء على ذالك ، الحل الناتج من طريقة التبسيط (برمجة) نضمن بأن يكون عدد صحيح. لتوضيح أن كل الحلول الأساسيه الممكنه تكون أعداد صحيحة نفرض أن ال x هو حل أساسي عشوائي ضمن نطاق الحل وبما أن ال $\mathbf {x}$ يكون في نطاق الحل ونحن نعرف أن ال $\mathbf {x}$ نفرض ان $A\mathbf {x} =\mathbf {b}$. Let $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$هي عبارة عن العناصر المكافئه للأعمده الأساسيه التي تُعبر عن الحلول الأساسيه $\mathbf {x}$ . بتعريف الأساسيات ، هناك بعض المصفوفات الجزئيه المربعه B من A مع أعمده خطية مستقله مثال ذالك$B$ of $A$ من هنا أعمدة ال B تكون مستقله خطية وال B مربعه ، ال B لديها معكوس ، وبالتالي حسب الفرض ال B أحادية النمط ،وبالتالي المحدده $\det(B)=\pm 1$ وأيضا بما أن B لديها معكوس ولذالك $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ بتعرف ال $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$ لاحظ أن $B^{adj}$ يرمز لمقلوب[[10]] ال B وتكون أعداد صحيحه بسبب أن ال B أعداد صحيحه . ولذالك

${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$

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

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

عندما المصفوفه A لاتكون أحادية النمط ، هناك تغيٌر في الخوارزميات التي تُستخدم في حل البرمجة الخطية الصحيحه بشكل دقيق . أحد أصناف الخوارزميات طرق تقاطع المستويات[[11]] التي تعمل على حل البرمجة الخطية الغير مقيده ومن ثم إضافة القيود الخطية التي تقود الحل بإتجاه الأعداد الصحيحه بدون إستثناء أي من نقاط الحل الصحيحه الممكنه. صنف اخر من الخوارزميات يكون متغير من الفرع والحد[[12]] .علي سبيل المثال الفرع والقطع[[13]] يضم الصنفين السابقين . خوارزميات الفرع والحد تمتلك عددا من المميزات اكثر من الخوارزميات التي تستخدم فقط المستويا المتقاطعة. واحدة من ميزات هذه الخوارزميات أنها تعطينا على الأقل حل واحد صحيح بطريقة سريعه في نطاق الحل وليس من الضروري أن يكون حل أمثَل. علاوة على ذالك حلول البرمجة الخطية الغير مقيده يمكن أن تُستخدم لتقييم أسواء حاله تٌحدد بعد الحل الناتج عن الحل الأمثل. أخيرا، طُرق الفرع والحد يمكن أن تُستخدم لكي تعطينا العديد من الحلول المُثلى Lenstra in 1983 يوضح أنه عندما يكون عدد المتغيرات ثابت ، فإن البرمجة الصحيحه يمكن أن تُحل بإستخدام كثيرة الحدود.

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

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

• تسلق الهضاب [[14]]
• تخمير محاكى
• رد الفعل للبحث الأمثل [[15]]
• طريقة حل المسائل الحسابية لإيجاد مسارات جديدة عن طريق الرسم [[16]]
• شبكة هوبفيلد

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