مشكلة تحسين المسار - الذكاء الاصطناعي - ثالث ثانوي

283 رابط الدرس الرقمي الدرس الثالث مشكلة تحسين المسار البرمجة الرياضية في مشكلات التحسين Mathematical Programming in Optimization Problems في الدرسين السابقين تم توضيح كيفية استخدام الخوارزميات الاستدلالية لحلّ أنواع مختلفة من مشكلات التحسين، وبالرغم من أن البرمجة الرياضية الاستدلالات بإمكانها أن تكون سريعة جدًا وتُنتج في العادة حلولا جيدة، www.ien.edu.sa (Mathematical Programming) هي رياضية. إلا أنها لا تضمن دائما إيجاد الحل الأمثل، وقد لا تكون مناسبة لكل تقنية تُستخدم لحلّ مشكلات التحسين أنواع المشكلات، وفي هذا الدرس ستُركّز على أسلوب تحسين مختلف عن طريق صياغتها على هيئة نماذج وهو البرمجة الرياضية ( Mathematical Programming). يُمكن للبرمجة الرياضية أن تحلّ العديد من مشكلات التحسين مثل: تخصيص الموارد، وتخطيط الإنتاج، والخدمات اللوجستية والجدولة، وتتميز هذه التقنية بأنها تُوفّر حلًّا مثاليًا مضمونًا ويُمكنها التعامل مع المشكلات المعقدة ذات القيود المتعددة. يبدأ حلّ البرمجة الرياضية بصياغة مشكلة التحسين المعطاة على شكل نموذج رياضي باستخدام المتغيرات، حيث تُمثَّل هذه المتغيرات القيم التي يجب تحسينها ، ثم يتم استخدامها لتحديد الدالة الموضوعية والقيود ، وهما يصفان المشكلة معا ويُمكِّنان من استخدام خوارزميات البرمجة الرياضية. تستخدم البرمجة الرياضية متغيرات القرار (Decision Variables) التي تساعد مُتَّخِذ القرار في إيجاد الحل المناسب عن طريق ضبطها والتحكم فيها ، كما يمكنها أن تستخدم متغيرات الحالة (State Variables) التي لا يتحكم فيها مُتَّخِذ القرار وتفرضها البيئة الخارجية ، وبالتالي لا يمكن ضبط متغيّرات الحالة. تُوفّر القوائم التالية أمثلة على متغيرات القرار ومتغيرات الحالة لبعض مشكلات التحسين الشائعة: جدول :52 أمثلة على متغيرات القرار ومتغيرات الحالة متغيرات القرار متغيرات الحالة الكمية التي يجب إنتاجها من كل تَوفّر المواد الخام، وسعة آلات الإنتاج، وتوفّر العمالة المطلوبة للإنتاج. تخطيط الإنتاج منتج. نقل الموارد عدد السلع التي يجب نقلها من المسافة بين الأماكن التي يجب زيارتها وسعة مكان لآخر. المركبات. ترتيب كل مُهمَّة والمدة الزمنية تَوفّر العمال والآلات والمواعيد النهائية، ووزن جدولة المهام اللازمة لإجرائها. أهمية كل مُهمَّة. و توزيع الموظفين تكليف العمّال وجدولتهم للقيام مهارات كل عامل وتفضيلاته، وجاهزيته حسب المهام بمهام مختلفة في أوقات مختلفة. والمهارات المطلوبة منه لإنجاز كل مهمة. وزارة التعليم Ministry of Education 2024-1446

و تتم صياغة الدالة الموضوعية كتعبير رياضي (Mathematical Expression) لتحسينها ( بزيادتها أو تقليلها ) بناءً على المتغيّرات المناسبة، وتُمثَّل هذه الدالة الهدف من مشكلة التحسين مثل: زيادة الربح أو تقليل التكاليف، وتُحدد في العادة بناءً على متغيرات القرار، كما تُحدد أحيانًا بناءً على متغيرات الحالة، وبالمثل يُمكن صياغة القيود باستخدام المتغيرات والمتباينات الرياضية. توجد عدة أنواع من البرمجة الرياضية مثل البرمجة الخطية - Linear Programming ) ، والبرمجة الرباعية (Quadratic Programming - QP) وبرمجة الأعداد الصحيحة المختلطة (Mixed Integer Programming - MIP). يركّز هذا الدرس على برمجة الأعداد الصحيحة المختلطة المستخدمة في المشكلات التي تتقيّد فيها متغيرات القرار بالأعداد الصحيحة مثل: مشكلات الجدولة أو اختيار الطريق. مشكلة حقيبة الظهر The Knapsack Problem مشكلة حقيبة الظهر 1/0 هي مثال بسيط على استخدام برمجة الأعداد الصحيحة المختلطة لصياغة الدالة الموضوعية والقيود ، وتُعرَّف المشكلة على النحو التالي: لديك حقيبة ظهر بسعة قصوى تبلغ وحدة ، ومجموعة من العناصر I، بحيث يكون لكل عنصرة متغيّران من متغيّرات الحالة هما وزن العنصر : وقيمته : ٧ ، والمطلوب هو تعبئة الحقيبة بمجموعة العناصر ذات أقصى قيمة ممكنة في حدود سعة الحقيبة. يُستخدم متغيّر القرار التتبع تجميعات العناصر التي ستُعبأ في حقيبة الظهر، حيث تكون 1 = x إذا تم اختيار العنصرة للإضافة للحقيبة، بينما تكون 0 = x خلاف ذلك، ويتمثل الهدف في انتقاء مجموعة فرعية من العناصر من 1 بحيث تشمل: • القيد (Constraint مجموع أوزان العناصر المنتقاة بها لا يزيد عن السعة القصوى C. الدالة الموضوعية (Objective: Function) : مجموع قيم العناصر المنتقاة بها هي أقصى قيمة ممكنة. وزارة التعليم Ministry of Education 2024-1446 V-20 W-5 ,10 W, 10 -> | V2=23 W2=19 شكل 5.6 مشكلة حقيبة الظهر W3=8 V=15 W4=11 V₁₂ =7 W5=2 V5=7 يوضّح الشكل 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 weights = = [20, 10, 23, 15, 7, 7] # values of available items [5, 10, 19, 8, 11, 2] %23 weights of available items 284

285 وزارة التعليم Ministry of Education 2024-1446 C = 40 #knapsack capacity I range(len(values)) # creates an index for each item: 0,1,2,3,... = solver Model("knapsack") # creates a knapsack solver = solver.verbose = 0 # setting this to 1 will print more information on the progress of the solver x = [] #represents the binary decision variables for each item. # for each items creates and appends a binary decision variable for i in I: x.append(solver.add_var(var_type = BINARY)) # creates the objective function solver.objective = maximize(xsum(values[i] * x[i] for i in I)) # adds the capacity constraint to the solver solver += xsum(weights[i] * x[i] for i in I) <= C #solves the problem solver.optimize() <OptimizationStatus.OPTIMAL: 0> يُنشئ المقطع البرمجي القائمة x لتخزين متغيرات القرار الثنائية للعناصر، وتُوفّر المكتبة mip في البايثون ما يلي: أداة (add_varvar_type= BINARY لإنشاء المتغيّرات الثنائية وإضافتها إلى خوارزمية الحلّ. أداة ()maximize لمشكلات التحسين التي تحتاج لزيادة دالة موضوعية، أما مشكلات التحسين التي تتطلب تصغير الدالة الموضوعية، فتستخدم الأداة ()minimize. • أداة ( )xsum لإنشاء التعبيرات الرياضية التي تتضمن المجاميع (sums) ، وفي المثال السابق تم استخدام هذه الأداة لحساب مجموع الوزن الإجمالي للعناصر في إنشاء قيد السعة وحلّه. أداة ( ) optimize لإيجاد حلّ يحسن الدالة الموضوعية في ظل الالتزام بالقيود، وتستخدم الأداة برمجة الأعداد الصحيحة المختلطة للنظر بكفاءة في توليفات القيم المختلفة لمتغيّرات القرار ولإيجاد التوليفة التي تُحسّن الهدف. • المعامل = + لإضافة قيود إضافية إلى خوارزمية الحلّ الموجودة. في المقطع البرمجي أدناه تحتوي القائمة X على متغيّر ثنائي واحد لكل عنصر ، وبعد حساب الحلّ سيكون كل متغيّر مساويًا للواحد إذا أدرج العنصر في الحلّ، وسيُساوي صفرًا بخلاف ذلك. تستخدم المكتبة mip بناء الجملة x[i].x لإظهار القيمة الثنائية للعنصر ذي الفهرس ،أ، وتحسب خوارزمية الحلّ متغيّر القرار ، ثم تجد القيمة الإجمالية والوزن الإجمالي للعناصر المنتقاة عن طريق التكرار على متغيّر القرار x ، وتجمع الأوزان والقيم لكل عنصر منتقى ، استنادًا إلى [i]، وتعرضها كما هو موضح في المقطع البرمجي التالي: total_weight total_value = 0 # stores the total weight of the items in the solution = 0 # stores the total value of the items in the solution

for i in I: # for each item if x[i].x == 1: # if the item was selected print('item', i, 'was selected') #updates the total weight and value of the solution total_weight += weights[i] total_value += values[i] print('total weight', total_weight) print('total value', total_value) item was selected item 2 was selected item 3 was selected item 5 was selected total weight 34 total value 65 مشكلة البائع المتجول Traveling Salesman Problem مشكلة البائع المتجوّل (Traveling Salesman Problem (TSP) من المشكلات الأخرى التي يُمكن حلّها ببرمجة الأعداد الصحيحة المختلطة وهي مشكلة مألوفة الأمثلة الواردة في مُخطَّط مشكلة البائع المتجوّل متصلة اتصالا تاما؛ فهناك تُعنى بتحديد أقصر مسار يمكن أن يسلكه بائع متجول لزيارة مدن معينة مرة واحدة، حافة تصل كل زوج من العقد بالآخر. دون أن يكرّر زيارة أي منها، ثمّ يعود للمدينة الأصلية، ويصوّر الشكل 5.7 نسخةً من هذه المشكلة. تُمثَّل كل دائرة ( عقدة ) مدينة أو موقعًا يجب زيارته ، وهناك حافة تربط بين موقعين إذا كان من الممكن السفر بينهما ، ويُمثَّل الرقم الموجود على الحافة التكلفة ( المسافة) بين الموقعين. في هذا المثال، تم ترقيم المواقع وفقًا لترتيبها في الحل الأمثل للمشكلة، وتكون التكلفة الإجمالية للطريق 1341 تساوي 80 = 15+30+25+10، وهو أقصر طريق ممكن لزيارة كل مدينة مرة واحدة فقط والعودة إلى نقطة البداية. توجد تطبيقات عملية لمشكلة البائع المتجوّل في الخدمات اللوجستية، والنقل، وإدارة الإمدادات والاتصالات، فهي تنتمي إلى عائلة أوسع من مشكلات تحديد الطريق التي تشمل أيضًا مشكلات شهيرة أخرى موضحة فيما يلي: 3 15 1 20 4 35 30 10 25 2 شكل 5.7 نسخة على مشكلة البائع المتجوّل • تتضمن مشكلة تحديد مسار المركبات (Vehicle Routing Problem إيجاد الطرق المثلى لأسطول من المركبات لتوصيل السلع أو الخدمات لمجموعة من العملاء في ظل تقليل المسافة الإجمالية المقطوعة إلى الحد الأدنى، وتشمل تطبيقاتها الخدمات اللوجستية وخدمات التوصيل وجمع النفايات. • تتضمن مشكلة الاستلام والتسليم (Pickup and Delivery Problem إيجاد الطرق المثلى للمركبات لكي تستلم ( تُحمل أو تُرْكِب) وتسلّم (تُوصل البضائع أو الأشخاص إلى مواقع مختلفة، وتشمل تطبيقاتها خدمات سيارات الأجرة، والخدمات الطبية الطارئة، وخدمات النقل الجماعي. تتضمن مشكلة جدولة مواعيد القطارات (Train Timetabling Problem إيجاد جداول زمنية مثالية للقطارات في شبكة سكك الحديد في ظل تقليل نسبة التأخير إلى الحد الأدنى وضمان الاستخدام الفعّال للموارد، وتشمل تطبيقاتها النقل بالسكك الحديدية والجدولة وزارة التعليم Ministry of Education 2024-1446 286

287 وزارة التعليم Ministry of Education 2024-1446 يمكن استخدام المقطع البرمجي التالي لإنشاء نسخة من مشكلة البائع المتجوّل، وتقبل الدالة عدد المواقع المراد زيارتها ، ونطاق المسافة يُمثَّل الفرق بين المسافة الأقصر والمسافة الأطول بين موقعين، ثم تُظهر: مصفوفة المسافة التي تشمل المسافة المسندة بين كل زوج ممكن من المواقع. مجموعة عناوين المواقع العددية ( عنوان لكل موقع). الموقع الذي يكون بمثابة بداية الطريق ونهايته، ويُشار إليه باسم موقع startstop الانطلاق والتوقف ) . import random import numpy from itertools import combinations def create_problem_instance(num_locations, distance_range): # initializes the distance matrix to be full of zeros dist_matrix = numpy.zeros((num_locations, num_locations)) # creates location ids: 0,1,2,3,4,... location_ids = set(range(num_locations)) # creates all possible location pairs location_pairs = combinations(location_ids, 2) for i,j in location_pairs: #for each pair distance = random.randint(*distance_range) #samples a distance within range # the distance from i to j is the same as the distance from j to i dist_matrix[j,i] = distance dist_matrix[i,j] = distance # returns the distance matrix, location ids and the startstop vertix return dist_matrix, location_ids, random.randint (0, num_locations - 1) يستخدم المقطع البرمجي التالي الدالة الواردة سابقًا لإنشاء نسخة من مشكلة البائع المتجوّل، بحيث يتضمن 8 مواقع ، ومسافات ثنائية تتراوح بين 5 و 20 dist_matrix, location_ids, startstop = create_problem_instance(8, (5, 20)) print(dist_matrix) print(startstop) [[ 19. 17. 15. 18. 17. 7. 15.] [19. 0. 15. 18. 11. 6. 20. 5.] [17. 15. 0 17. 15. 7. 5. 11.] [15. 18. 17. 0. 19. 7. 7. 16.] [18. 11. 15. 19. 0. 17. 20. 17.] [17. 6. 7. 7. 17. 0 15. 14.] [ 7. 20. 7. 20. 15. 0 14.] [15. 5. 11. 16. 17. 14. 14. 0.11 3 5. و لاحظ أن الخط القطري يُمثل المسافات من العقد إلى نفسها ([dist_matrix[ii) ، وبالتالي فإن المسافات تساوي أصفارا.

إنشاء خوارزمية حلّ القوة المفرطة لمشكلة البائع المتجوّل Creating a Brute-Force Solver for the Traveling Salesman Problem تستخدم الدالة التالية خوارزمية حلّ القوة المفرطة لتعداد جميع الطرق الممكنة ( التباديل) وإظهار أقصر مسار، وتقبل هذه الدالة مصفوفة المسافة وموقع الانطلاق والتوقف الذي تُظهره الدالة ()create_problem_instance. لاحظ أن الحل الممكن لنسخة مشكلة البائع المتجوّل (TSP) هي تبديل مدن يبدأ من مدينة start stop ) الانطلاق والتوقف ) ثم ينتهي إليها . وزارة التعليم Ministry of Education 2024-1446 from itertools import permutations def brute_force_solver(dist_matrix, location_ids, startstop): # excludes the starstop location location_ids = location_ids - {startstop} # generate all possible routes (location permutations) all_routes = permutations(location_ids) best_distance = float('inf') # initializes to the highest possible number best_route None # best route so far, initialized to one = for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc = startstop # current location for next_loc in route: distance += dist_matrix[curr_loc,next_loc] # adds the distance of this step curr_loc = next_loc #goes to the next location distance += dist_matrix[curr_loc,startstop] #goes to the starstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route # adds the startstop location at the beginning and end of the best route and returns return [startstop] + list(best_route) + [startstop], best_distance تستخدم خوارزمية حلّ القوة المفرطة أداة ( )permutations لإنشاء كل الطرق الممكنة. لاحظ أن موقع startstop ( الانطلاق والتوقف) يُستبعد من التباديل؛ لأنه يجب أن يظهر دائمًا في بداية كلّ طريق ونهايته، فعلى سبيل المثال، إذا كانت لديك أربعة مواقع ،0 ، و1 ، و2 ، و3 ، وكان الموقع 0 هو موقع start stop الانطلاق والتوقف) ، ستكون قائمة التباديل الممكنة كما يلي: for route in permutations({1,2,3}): print(route) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) 288

289 وزارة التعليم Ministry of Education 2024-1446 تحسب خوارزمية حلّ القوة المفرطة المسافة الإجمالية لكل طريق، وتُظهر في النهاية الطريق ذا المسافة الأقصر. يُطبق المقطع البرمجي التالي خوارزمية الحلّ على نسخة مشكلة البائع المتجوّل التي تم إنشاؤها سابقا: brute_force_solver(dist_matrix, location_ids, startstop) ([3, 5, 2, 7, 1, 4, 0, 6, 3], 73.0) على غرار خوارزميات حلّ القوة المفرطة التي تم توضيحها في الدروس السابقة، لا تُطبق هذه الخوارزمية إلا علـى نُسخ مشكلة البائع المتجوّل الصغيرة؛ لأن عدد الطرق الممكنة يتزايد أضعافا مضاعفة كلما زاد العدد N، ويساوي !(1-N)، وعلى سبيل المثال، عندما يكون 15 = N، فإن عدد الطرق الممكنة يساوي 87,178,291,200 = !14. استخدام برمجة الأعداد الصحيحة المختلطة لحل مشكلة البائع المتجول Using MIP to Solve the Traveling Salesman Problem ij لاستخدام برمجة الأعداد الصحيحة المختلطة (MIP) لحلّ مشكلة البائع المتجوّل (TSP)، يجب إنشاء صيغة رياضية تُغطي كلًا من الدالة الموضوعية وقيود مشكلة البائع المتجوّل. تتطلب الصيغة متغيّر قرار ثنائي x لكل انتقال محتمل : ( من موقعة إلى موقع آخر ، واذا كانت المشكلة بها عدد N من المواقع، فإن عدد الانتقالات الممكنة يساوي (1-Nx (N. إذا كانت x تساوي 1، فإن الحل يتضمن الانتقال من الموقع : إلى الموقع ، وخلاف ذلك إذا كانت x تساوي ، فلن يُدرج هذا الانتقال في الحلّ. يُمكن الوصول بسهولة إلى العناصر في مصفوفة numpy ثنائية الأبعاد عبر الصيغة البرمجية [i,j]، فعلى سبيل المثال: ij ij arr = numpy.full((4,4), 0) #creates a 4x4 array full of zeros print(arr) arr[0, 0] = 1 arr[3, 3] = 1 print() print(arr) [[ 0 0 0 0 ] [0 0 0 [ 0 0 0 0] [ 0 0 0 0 ]] [[1 0 0 0] [ 0 0 0 0] [0 0 0 0] [ 0 0 0 1]] يستخدم المقطع البرمجي الأداة ()product من المكتبة itertools لحساب جميع انتقالات المواقع المحتملة، فعلى = ids {0, 1, 2} for i, j in list(product(ids, ids)): print(i, j) 00 0 1 0 2 10 1 1 1 2 20 2 1 2 2 سبيل المثال:

وزارة التعليم Ministry of Education 2024-1446 يستخدم المقطع البرمجي التالي مكتبة البايثون mip لإنشاء خوارزمية حلّ برمجة الأعداد الصحيحة المختلطة، ثم يضيف متغيّر قرار ثُنائي لكل انتقال ممكن في نسخة مشكلة البائع المتجوّل التي تم إنشاؤها سابقًا: from itertools import product # used to generate all possible transition from mip import BINARY from mip import Model, INTEGER solver = Model() # creates a solver solver.verbose = 0 # setting this to 1 will print info on the progress of the solver # 'product' creates every transition from every location to every other location transitions = list(product(location_ids, location_ids)) N = len(location_ids) # number of locations # creates a square numpy array full of 'None' values x numpy.full((N, N), None) = # adds binary variables indicating if transition (i->j) is included in the route for i, j in transitions: x[i, j] = solver.add_var(var_type = BINARY) Nxn لتخزين المتغيرات يستخدم المقطع البرمجي السابق أداة numpy.full لإنشاء مصفوفة numpy بحجم الثنائية . بعد إضافة متغيرات القرار x ، يُمكن استخدام المقطع البرمجي التالي لصياغة وحساب الدالة الموضوعية لمشكلة البائع المتجوّل، حيث تقوم الدالة بالتكرار على كل انتقال ممكن : < i وتُضرب مسافتها [dist_matrix[i,j متغير قرارها [x[i ، وإذا تم إدراج الانتقال في الحل سيؤخذ 1 = [i] و [dist_matrix[i,j بعين الاعتبار، وبخلاف ذلك ستضرب [dist_matrix[i,j في صفر ليتم تجاهلها: وو # the minimize tool is used then the objective function has to be minimized from mip import xsum, minimize # objective function: minimizes the distance solver.objective = minimize(xsum(dist_matrix[i,j]*x[i][j] for i,j in transitions)) لک تهدف الخطوة التالية إلى التأكد بأن الخوارزمية تُظهر الحلول التي تضمن زيارة كل المواقع لمرة واحدة فقط، باستثناء موقع startstop الانطلاق والتوقف ) حسب ما تتطلبه مشكلة البائع المتجوّل، وزيارة كل موقع مرة واحدة تعني أن الطريق الصحيح يُمكن أن: • يصل إلى كل موقع مرة واحدة فقط. يغادر من كل موقع مرة واحدة فقط. ويُمكن إضافة قيود الوصول والمغادرة هذه بسهولة كما يلي: # for each location id for i in location_ids: solver += xsum(x[i,j] for j in location_ids - {i}) solver += xsum(x[j,i] for j in location_ids - {i}) == 1 # exactly 1 arrival == 1 # exactly 1 departure 290

291 وزارة التعليم Ministry of Education 2024-1446 تشمل الصيغة الكاملة لمشكلة البائع المتجوّل نوعًا إضافيًا آخرًا من القيود لضمان حساب الطرق المتصلة، ففي نسخة مشكلة البائع المتجوّل الواردة في الشكل 5.8 يُفترض أن الموقع 0 هو موقع الانطلاق والتوقف. في هذا المثال، أقصر طريق ممكن هو 0 <3>4<1>2، بمسافة سفر إجمالية قدرها ،24 ، ولكن عند عدم وجود قيد اتصال سيكون هناك حلّ صحيح آخر يشمل طريقين غير متصلين هما: 0>3<4 > 0و1 > 12 ، وهذا الحلّ المتمثل في وجود طريقين يمتثل لقيود الوصول والمغادرة التي تم تعريفها في المقطع البرمجي السابق؛ لأن كل موقع يدخل له ويخرج منه مرة واحدة فقط، ولكن هذا الحلّ غير مقبول لمشكلة البائع المُتجوّل. يمكن فرض حلّ يشمل طريقًا واحدًا متصلا بإضافة متغير القرار ا لكل موقع أ ، وستحافظ هذه المتغيرات على ترتيب زيارة كل موقع في الحل. m 3 1 م 6 4 5 3 2 7 5 شكل 5.8 نسخة مشكلة البائع المتجوّل 0 # adds a decision variable for each location y = [solver.add_var(var_type = INTEGER) for i in location_ids] Ya على سبيل المثال، إذا كان الحلّ هو: 0 <3>4<1 > 2 > 0 ، فستكون قيم ا كما يلي: 2 = 1 = = 3 = y ، والموقع 0 هو موقع الانطلاق والتوقف، ولذلك لا تؤخذ قيمة y الخاصة به بعين الاعتبار. 2 Y3 يُمكن استخدام متغيرات القرار الجديدة هذه لضمان الاتصال من خلال إضافة قيد جديد لكل انتقال i > زلا يشمل موقع starstop الانطلاق والتوقف) . # adds a connectivity constraint for every transition that does not include the startstop for (i, j) in product( location_ids # ignores transitions from a location to itself if i != j: {startstop}, location_ids solver += y[j] - y[i] >= (N+1) * x[i, j] - N {startstop}): ij إذا كانت 1 = x لانتقال i > زوتم إدراج هذا الانتقال في الحلّ، فإن المتباينة الواردة في الأعلى تصبح 1 + [i] = y[i]، ومعنى ذلك أن المواقع التي ستُزار لاحقًا لا بد أن تكون قيمة ( الخاصة بها أعلى، بالإضافة إلى قيود الوصول والمغادرة، وسيكون الطريق الذي لا يشمل موقع الانطلاق والتوقف صحيحًا فقط إذا: 28 بدأ وانتهى بالموقع نفسه؛ لضمان أن يكون لكل موقع وصول واحد ومغادرة واحدة فقط. خُصصت قيم لا أعلى لكل المواقع التي ستُزار لاحقًا؛ لأن [y[i يجب أن تكون أكبر من [y[i لكل الانتقالات التي تم إدراجها في الطريق، ويؤدي هذا أيضًا إلى تجنب إضافة الحافة نفسها من اتجاه مختلف، على سبيل المثال: i←jġj←i ولكن إذا كان الموقع يمثل بداية الطريق ونهايته، فلا بد أن تكون قيمة y الخاصة به هي أكبر وأصغر من قيم كل المواقع الباقية في الطريق، ونظرًا لاستحالة هذا الأمر ، فستؤدي إضافة قيد الاتصال إلى استبعاد أية حلول بها طرق لا تشمل موقع الانطلاق والتوقف.

على سبيل المثال، فكّر في الطريق 11 الوارد في الحلّ المكون من طريقين لنسخة مشكلة البائع المتجوّل الموضحة في الشكل السابق، حيث يتطلب قيد الاتصال أن تكون +1+ وأن تكون 11 + 2 ، وهذا مستحيل، سيتم استبعاد الحلّ. فلذلك ≥ 1 V3 4 3 2 1 4 في المقابل، يتطلب الحلّ الصحيح ٥> 3>4<1>2 0 أن تكون 1 + وأن تكون 1 + 2 ، وأن تكون +1+ ، ويُمكن تحقيق ذلك بضبط قيم ل كما يأتي: 0 = y و 1 = 1 و 2 = 1 و 3 = y ، ولا تنطبق قيود الاتصال على الانتقالات التي تشمل موقع startstop ( الانطلاق والتوقف) . تجمع الدالة التالية كل الأشياء معًا لإنشاء خوارزمية حلّ برمجة الأعداد الصحيحة المختلطة لمشكلة البائع المتجوّل: 4 1 from itertools import product. from mip import BINARY, INTEGER from mip import Model from mip import xsum, minimize def MIP_solver(dist_matrix, location_ids, startstop): solver = Model() # creates a solver solver.verbose = 0 # setting this to 1 will print info on the progress of the solver # creates every transition from every location to every other location transitions = list(product (location_ids, location_ids)) N = len(location_ids) #number of locations # create an empty square matrix full of 'None' values x numpy.full((N, N), None) = # adds binary decision variables indicating if transition (i->j) is included in the route for i, j in transitions: x[i, j]=solver.add_var(var_type = BINARY) #objective function: minimizes the distance solver.objective = minimize(xsum (dist_matrix[i, j]*x[i][j] for i,j in transitions)) # Arrive/Depart Constraints for i in location_ids: solver + xsum(x[i, j] for j in location_ids += - - {i}) == 1 # exactly 1 arrival = solver + xsum(x[j,i] for j in location_ids - {i}) == 1 # exactly 1 departure # adds a binary decision variable for each location y = [solver.add_var(var_type=INTEGER) for i in location_ids] # adds connectivity constraints for transitions that do not include the startstop for (i, j) in product (location_ids - {startstop}, location_ids - {startstop}): if i = j #ignores transitions from a location to itself solver y[j] - y[i] >=(N+1)*x[i,j] - N solver.optimize() #solves the problem # prints the solution += if solver.num_solutions: # if a solution was found best_route = [startstop] # stores the best route curr_loc startstop # the currently visited location while True: for next loc in location_ids: # for every possible next location if x[curr_loc, next_loc].x == 1: # if x value for the curr_loc->next_loc transition is 1 best_route.append(next_loc) # appends the next location to the route curr_loc=next_loc # visits the next location break if next_loc break == startstop: # exits if route returns to the startstop return best route, solver.objective_value # returns the route and its total distance وزارة التعليم Ministry of Education 2024-1446 292

293 يولَّد المقطع البرمجي التالي 100 نسخة من مشكلة البائع المتجوّل تشمل 8 مواقع وتتراوح المسافات فيها بين 5 و20، كما أنه يستخدم خوارزمية حلّ القوة المفرطة، وخوارزمية حلّ برمجة الأعداد الصحيحة المختلطة لحل كل حالة، ويُظهر النسبة المئوية للأسلوبين اللذين أظهرا طريقين لهما المسافة نفسها: same_count = for i in range(100): dist_matrix, location_ids, startstop=create_problem_instance(8, [5,20]) route1, dist1 = brute_force_solver(dist_matrix, location_ids, startstop) route2, dist2 = MIP_solver(dist_matrix, location_ids, startstop) # counts how many times the two solvers produce the same total distance if dist1 dist2: == same_count += 1 print(same_count / 100) 1.0 تؤكد النتائج أن خوارزمية حلّ برمجة الأعداد الصحيحة المختلطة تُظهر الحلّ الأمثل بنسبة 100% لكل نُسخ المشكلة، ويوضّح المقطع البرمجي التالي سرعة خوارزمية حلّ برمجة الأعداد الصحيحة المختلطة من خلال استخدامها لحلّ 100 نسخة كبيرة تتضمن كلٌّ منها 20 موقعاً : import time start = time.time() # starts timer for i in range(100): dist_matrix, location_ids, startstop = create_problem_instance(20, [5,20]) route, dist = MIP_solver(dist_matrix, location_ids, startstop) stop=time.time() # stops timer print(stop - start) #prints the elapsed time in seconds 188.90074133872986 على الرغم من أن وقت التنفيذ الدقيق سيعتمد على قوة معالجة الجهاز الذي تستخدمه لتنفيذ مفكرة جوبيتر، إلا أنه من المفترض أن يستغرق التنفيذ بضع دقائق لحساب الحلّ لجميع مجموعات البيانات المئة. عدد وهذا بدوره مذهل إذا تم الأخذ في الاعتبار أن الطرق الممكنة لكل نسخة من النسخ المئة هي: 121,645,100,000,000,000 = 19 طريقًا مختلفًا، ومثل هذا العدد الكبير من الطُّرق يفوق بكثير قدرات أسلوب القوة المفرطة، ومع ذلك فإنه عن طريق البحث الفعّال في هذه المساحة الهائلة الخاصة بجميع الحلول الممكنة يُمكن لخوارزمية حلّ برمجة الأعداد الصحيحة المختلطة أن تجد الطريق الأمثل بسرع عة. وعلى الرغم من مزايا البرمجة الرياضية إلا أنها تملك قيوداً خاصة أيضًا، فهي تتطلب فهما قويًا للنمذجة الرياضية وقد لا تكون مناسبة للمشكلات المعقدة التي يصعب فيها التعبير عن الدالة الموضوعية والقيود بواسطة الصيغ الرياضية، وعلى الرغم من أن البرمجة الرياضية أسرع بكثير من أسلوب القوة المفرطة إلا أنها قد تظل بطيئة جدا بالنسبة لمجموعات البيانات الكبيرة، وفي مثل هذه الحالات يقدِّم الأسلوب الاستدلالي الموضَّح في الدرسين السابقين بديلًا أكثر سرعة. و وزارة التعليم Ministry of Education 2024-1446

وزارة التعليم Ministry of Education 2024-1446 تمرينات اشرح طريقة استخدام البرمجة الرياضية لحلّ مشكلات التحسين المعقدة. ما مزايا وعيوب أسلوب برمجة الأعداد الصحيحة المختلطة في حل مشكلات التحسين ؟ 1 2 294

295 قم بتحليل مشكلتين من مشكلات التحسين يُمكن حلهما باستخدام البرمجة الرياضية، ثم حدد متغيرات الحالة ومتغيرات القرار الخاصة بهما. وزارة التعليم Ministry of Education 2024-1446 اذكر ثلاث مشكلات تحسين مختلفة من عائلة مشكلات تحديد المسار. 3 4

5 أنشئ دالة خوارزمية حلّ القوة المفرطة لمشكلة البائع المتجوّل، من خلال إكمال المقطع البرمجي التالي بحيث تُظهر الدالة المسار الأفضل والمسافة الإجمالية المثلى: وزارة التعليم Ministry of Education 2024-1446 from itertools import permutations def brute force_solver(dist_matrix, location_ids, startstop): # excludes the startstop location location_ids = { } # generates all possible routes (location permutations) all_routes best_distance = float('inf') #initializes to the highest possible number best_route = None # best route so far, initialized to None for route in all_routes: # for each route distance = 0 # total distance in this route curr_loc= for next loc in route: distance += curr_loc= distance += # current location [curr_loc, next_loc] # adds the distance of this step # goes the next location [curr_loc, ] # goes to back to the startstop location if distance < best_distance: # if this route has lower distance than the best route best_distance = distance best_route = route # adds the startstop location at the beginning and end of the best route and returns return [startstop] list(best_route) + [startstop], best_distance 296

297 6 أنشئ خوارزمية حلّ برمجة الأعداد الصحيحة المختلطة لمشكلة البائع المتجوّل، من خلال إكمال المقطع البرمجي التالي، بحيث تنتقي متغيرات القرار وقيود الاتصال انتقاء صحيحًا: وزارة التعليم Ministry of Education 2024-1446 def MIP_solver(dist_matrix, location_ids, startstop): solver = () # creates a solver solver.verbose = 0 # setting this to 1 will print info on the progress of the solver # creates every transition from every location to every other location transitions = list( (location_ids, location_ids)) N = len(location_ids) #number of locations # creates an empty square matrix full of 'None' values x numpy.full((N, N), None) = # adds binary decision variables indicating if transition (i->j) is included in the route for i, j in transitions: x[i, j] = solver. # objective function: minimizes the distance solver.objective = (var_type= ) (xsum(dist_matrix[i, j] * x[i][j] for i, j in transitions)) #Arrive/Depart Constraints for i in location_ids: solver += xsum( solver += xsum( # Adds a binary decision variable for each location for j in location_ids - {i}) == 1 for j in location_ids - {i}) == 1 y = [solver. (var_type= ) for i in location_ids] # Adds connectivity constraints for transitions that do not include the startstop for (i, j) in product(location_ids - {startstop}, location_ids {startstop}): if i != j: # ignores transitions from a location to itself solver += y[j] - y[i] >= (N + 1) * x[i, j] - N solver. ( ) # solves the problem