وظیفه

یکی از شناخته شده ترین مسائل بهینه سازی ترکیبی مسئله انتساب است. یک مثال در اینجا آمده است: فرض کنید گروهی از کارگران باید مجموعه ای از وظایف را انجام دهند و برای هر کارگر و وظیفه، هزینه ای برای انتساب کارگر به کار وجود دارد. مشکل این است که هر کارگر را حداکثر به یک کار اختصاص دهید، بدون اینکه دو کارگر یک کار را انجام دهند، در حالی که هزینه کل را به حداقل می رساند.

شما می توانید این مشکل را با نمودار زیر تجسم کنید که در آن چهار کارگر و چهار وظیفه وجود دارد. لبه ها نشان دهنده تمام راه های ممکن برای انتساب کارگران به وظایف هستند. برچسب های روی لبه ها هزینه های اختصاص کارگران به وظایف است.

یک انتساب مربوط به زیرمجموعه ای از لبه ها است که در آن هر کارگر حداکثر یک یال منتهی به بیرون دارد و هیچ دو کارگری دارای لبه هایی هستند که به یک کار منتهی می شوند. یکی از تکالیف ممکن در زیر نشان داده شده است.

کل هزینه تکلیف 70 + 55 + 95 + 45 = 265 است.

بخش بعدی نحوه حل یک مسئله انتساب را با استفاده از حل کننده MIP و حل کننده CP-SAT نشان می دهد.

ابزارهای دیگر برای حل مشکلات تکلیف

OR-Tools همچنین چند ابزار دیگر را برای حل مشکلات تخصیص ارائه می دهد که می توانند سریعتر از حل کننده های MIP یا CP باشند:

• حل کننده انتساب جمع خطی
• حل کننده جریان حداقل هزینه

با این حال، این ابزارها فقط می توانند انواع ساده مشکلات انتساب را حل کنند. بنابراین برای حل‌کننده‌های عمومی که می‌توانند طیف گسترده‌ای از مشکلات را حل کنند (و برای اکثر برنامه‌ها به اندازه کافی سریع هستند)، حل‌کننده‌های MIP و CP-SAT را توصیه می‌کنیم.