برمجة الأعداد الصحيحة المختلطة ومشكلة حقيبة الظهر - كتاب الذكاء الإصطناعي - الصف 12 - الفصل 1 - المملكة العربية السعودية

تتم صياغة الدالة الموضوعية كتعبير رياضي (Mathematical Expression) لتحسينها (بزيادتها أو تقليلها) بناءً على المتغيرات المناسبة. وتمثل هذه الدالة الهدف من مشكلة التحسين مثل: زيادة الربح أو تقليل التكاليف، وتُحدّد في العادة بناءً على متغيرات القرار. كما تُحدّد أحيانًا بناءً على متغيرات الحالة. وبالمثل يمكن صياغة القيود باستخدام المتغيرات والمتباينات الرياضية. توجد عدة أنواع من البرمجة الرياضية، مثل: البرمجة الخطية (Linear Programming - LP)، والبرمجة التربيعية (Quadratic Programming - QP)، وبرمجة الأعداد الصحيحة المختلطة (Mixed Integer Programming - MIP). يركز هذا الدرس على برمجة الأعداد الصحيحة المختلطة المستخدمة في المشكلات التي تتقيد فيها متغيرات القرار بالأعداد الصحيحة مثل: مشكلات الجدولة أو اختيار الطريق.

مشكلة حقيبة الظهر The Knapsack Problem

مشكلة حقيبة الظهر 1/0 هي مثال بسيط على استخدام برمجة الأعداد الصحيحة المختلطة لصياغة الدالة الموضوعية والقيود. وتُعرف المشكلة على النحو التالي: لديك حقيبة ظهر بسعة قصوى تبلغ C وحدة، ومجموعة من العناصر I ، بحيث يكون لكل عنصر i متغيران من متغيرات الحالة هما وزن العنصر w وقيمته v ، والمطلوب هو تعبئة الحقيبة بمجموعة العناصر ذات أقصى قيمة ممكنة في حدود سعة الحقيبة. يُستخدم متغير القرار x لتتبع تجميعات العناصر التي ستُعبأ في حقيبة الظهر، حيث تكون 1 = x إذا تم اختيار العنصر i للإضافة للحقيبة، بينما تكون 0 = x بخلاف ذلك. ويتمثل الهدف في انتقاء مجموعة فرعية من العناصر من I بحيث تشمل:

• القيود (Constraint): مجموع أوزان العناصر المنتقاة بها لا يزيد عن السعة القصوى C. • الدالة الموضوعية (Objective Function): مجموع قيم العناصر المنتقاة بها هي أقصى قيمة ممكنة.

يوضح الشكل 5.6 مثالاً على مسألة حقيبة ظهر مكونة من ستة عناصر بأوزان وقيم محددة، وحقيبة ظهر بسعة قصوى تساوي أربعين وحدة. يقوم المقطع البرمجي التالي بتثبيت مكتبة البايثون المفتوحة المصدر mip الخاصة ببرمجة الأعداد الصحيحة المختلطة لحل نسخة مشكلة حقيبة الظهر 1/0. ويستورد الوحدات الضرورية:

!pip install mip # install the mip library # imports useful tools from the mip library from mip import Model, xsum, maximize, BINARY values = [20, 10, 23, 15, 7, 7] # values of available items weights = [5, 10, 19, 8, 11, 2] # weights of available items

وزارة التعليم Ministry of Education 2023 - 1447

284

تتم صياغة الدالة الموضوعية كتعبير رياضي (Mathematical Expression) لتحسينها (بزيادتها أو تقليلها) بناءً على المتغيرات المناسبة. وتمثل هذه الدالة الهدف من مشكلة التحسين مثل: زيادة الربح أو تقليل التكاليف، وتُحدّد في العادة بناءً على متغيرات القرار. كما تُحدّد أحيانًا بناءً على متغيرات الحالة. وبالمثل يمكن صياغة القيود باستخدام المتغيرات والمتباينات الرياضية. توجد عدة أنواع من البرمجة الرياضية، مثل: البرمجة الخطية (Linear Programming - LP)، والبرمجة التربيعية (Quadratic Programming - QP)، وبرمجة الأعداد الصحيحة المختلطة (Mixed Integer Programming - MIP). يركز هذا الدرس على برمجة الأعداد الصحيحة المختلطة المستخدمة في المشكلات التي تتقيد فيها متغيرات القرار بالأعداد الصحيحة مثل: مشكلات الجدولة أو اختيار الطريق.مشكلة حقيبة الظهر The Knapsack Problemمشكلة حقيبة الظهر 1/0 هي مثال بسيط على استخدام برمجة الأعداد الصحيحة المختلطة لصياغة الدالة الموضوعية والقيود. وتُعرف المشكلة على النحو التالي: لديك حقيبة ظهر بسعة قصوى تبلغ C وحدة، ومجموعة من العناصر I ، بحيث يكون لكل عنصر i متغيران من متغيرات الحالة هما وزن العنصر w وقيمته v ، والمطلوب هو تعبئة الحقيبة بمجموعة العناصر ذات أقصى قيمة ممكنة في حدود سعة الحقيبة. يُستخدم متغير القرار x لتتبع تجميعات العناصر التي ستُعبأ في حقيبة الظهر، حيث تكون 1 = x إذا تم اختيار العنصر i للإضافة للحقيبة، بينما تكون 0 = x بخلاف ذلك. ويتمثل الهدف في انتقاء مجموعة فرعية من العناصر من I بحيث تشمل:• القيود (Constraint): مجموع أوزان العناصر المنتقاة بها لا يزيد عن السعة القصوى C. • الدالة الموضوعية (Objective Function): مجموع قيم العناصر المنتقاة بها هي أقصى قيمة ممكنة.يوضح الشكل 5.6 مثالاً على مسألة حقيبة ظهر مكونة من ستة عناصر بأوزان وقيم محددة، وحقيبة ظهر بسعة قصوى تساوي أربعين وحدة. يقوم المقطع البرمجي التالي بتثبيت مكتبة البايثون المفتوحة المصدر mip الخاصة ببرمجة الأعداد الصحيحة المختلطة لحل نسخة مشكلة حقيبة الظهر 1/0. ويستورد الوحدات الضرورية:!pip install mip # install the mip library# imports useful tools from the mip library from mip import Model, xsum, maximize, BINARY values = [20, 10, 23, 15, 7, 7] # values of available items weights = [5, 10, 19, 8, 11, 2] # weights of available items2023 - 1447--- VISUAL CONTEXT --- **DIAGRAM**: شكل 5.6: مشكلة حقيبة الظهر Description: A diagram illustrating the Knapsack Problem. A blue backpack (knapsack) is centered, with six rectangular items surrounding it. Three items are on the left, and three are on the right, with dashed arrows pointing towards the backpack, indicating they can be placed inside. Each item is labeled with its value (v) and weight (w). Data: The diagram shows six distinct items, each with a specific value and weight. These items are potential candidates to be placed into the knapsack, which has a defined capacity (mentioned as 40 units in the accompanying text). The goal is to select items to maximize total value without exceeding the knapsack's weight capacity. Key Values: Item 0: v₀=20, w₀=5, Item 1: v₁=10, w₁=10, Item 2: v₂=23, w₂=19, Item 3: v₃=15, w₃=8, Item 4: v₄=7, w₄=11, Item 5: v₅=7, w₅=2 Context: This visual element serves as a concrete example for 'The Knapsack Problem' discussed in the text. It helps to visualize the items, their properties (value and weight), and the concept of selecting items to optimize a total value within a capacity constraint. The values and weights shown here are directly used in the Python code example provided below the figure.