מטלה

אחת הבעיות הידועות ביותר של אופטימיזציה קומבינטורית היא בעיית ההקצאה. לדוגמה, נניח שקבוצה של עובדים צריכה לבצע סדרת משימות, ולכל עובד ולכל משימה יש עלות להקצאת העובד למשימה. הבעיה היא להקצות לכל עובד משימה אחת לכל היותר, בלי שני עובדים שמבצעים את אותה המשימה, ולצמצם את העלות הכוללת.

תוכלו לראות את הבעיה בתרשים שלמטה, שבו יש ארבעה עובדים וארבע משימות. הקצוות מייצגים את כל הדרכים האפשריות להקצאת עובדים למשימות. התוויות בקצוות הן העלויות של הקצאת עובדים למשימות.

הקצאה היא חלק משני קצוות, כאשר לכל עובד יש קצה אחד ביותר החוצה ממנו, ואין שני עובדים עם קצוות שמובילים לאותה המשימה. מטלה אפשרית אחת מוצגת בהמשך.

העלות הכוללת של המטלה היא 70 + 55 + 95 + 45 = 265.

בקטע הבא מוסבר איך פותרים בעיה בהקצאה, באמצעות פותר הבעיות ב-MIP ודרך פתרון CP-SAT.

כלים אחרים לפתרון בעיות במטלות

OR-Tools מספק גם כמה כלים אחרים לפתרון בעיות במטלות, שיכולים להיות מהירים יותר מהפתרונות MIP או CP:

• פתרון הקצאות של סכום לינארי
• פתרון בעיות מינימליות של זרימת עלויות

עם זאת, הכלים האלו יכולים לפתור רק סוגים פשוטים של בעיות שקשורות למטלות. לכן, לפתרון בעיות כלליות שמסוגלות להתמודד עם מגוון רחב של בעיות (והן מהירים מספיק לרוב האפליקציות), אנחנו ממליצים להשתמש בפתרונות MIP ו-CP-SAT.