תחילת העבודה עם OR-כלים עבור Java

הקטעים הבאים יעזרו לך להתחיל לעבוד עם OR-Tools עבור Java:

• מהי בעיית אופטימיזציה
• פתרון בעיית אופטימיזציה ב-Java
• דוגמאות נוספות ל-Java
• זיהוי סוג הבעיה שרוצים לפתור

מהי בעיית אופטימיזציה?

מטרת האופטימיזציה היא למצוא את הפתרון הטוב ביותר לבעיה מתוך קבוצה גדולה של פתרונות אפשריים. (לפעמים תהיו מרוצים מכל פתרון בר-ביצוע; גם OR-כלים יכולים לעשות את זה).

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

בדומה לכל בעיות האופטימיזציה, בעיה זו כוללת את הרכיבים הבאים:

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

  פתרון אופטימלי הוא פתרון שבו הערך של פונקציית היעד הוא הטוב ביותר. ('הטוב ביותר' יכול להיות מקסימום או מינימום).

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

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

השלב הראשון בפתרון בעיית אופטימיזציה הוא זיהוי היעדים והאילוצים.

פתרון בעיית אופטימיזציה ב-Java

בשלב הבא נותנים דוגמה לבעיית אופטימיזציה, ומראים איך להגדיר ולפתור אותה ב-Java.

דוגמה לאופטימיזציה לינארית

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

הגדלה מקסימלית של 3x + y בכפוף להגבלות הבאות:

1. 1 ≤ x 0
2. 2 ≤ y
3. x + y ≤ 2

פונקציית היעד בדוגמה הזו היא 3x + y. גם פונקציית המטרה וגם המגבלות ניתנים על ידי ביטויים ליניאריים, ולכן זוהי בעיה ליניארית.

השלבים העיקריים בפתרון הבעיה

השלבים הבסיסיים להגדרה ולפתרון של בעיות בכל שפה זהים:

1. מייבאים את הספריות הנדרשות.
2. מצהירים על הפותר,
3. יוצרים את המשתנים,
4. מגדירים את האילוצים,
5. נגדיר את פונקציית היעד,
6. קוראים את הפותר
7. הצגת התוצאות.

תוכנית Java<

הקטע הזה עובר דרך תוכנית Java שמגדירה את הבעיה ופותרת אותה.

הערה: תוכנית Java המלאה והשלבים להפעלה שלה מוצגים בסוף הקטע.

אלה השלבים:

• מייבאים את הספריות הנדרשות.

  import com.google.ortools.Loader;
  import com.google.ortools.linearsolver.MPConstraint;
  import com.google.ortools.linearsolver.MPObjective;
  import com.google.ortools.linearsolver.MPSolver;
  import com.google.ortools.linearsolver.MPVariable;

• מצהירים על הפותר.

  // Create the linear solver with the GLOP backend.
  MPSolver solver = MPSolver.createSolver("GLOP");

  MPSolver הוא פתרון wrapper של בעיות של תיכנות לינארי או של תיכנות עם מספרים שלמים.
• יוצרים את המשתנים.

  // Create the variables x and y.
  MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
  MPVariable y = solver.makeNumVar(0.0, 2.0, "y");
  
  System.out.println("Number of variables = " + solver.numVariables());

• מגדירים את המגבלות. שני האילוצים הראשונים, 0 &leq; x ≤ 1 ו-0 &leq; y ≤ 2, כבר מוגדרים על ידי ההגדרות של המשתנים. הקוד הבא מגדיר את האילוץ x + y &leq; 2:

  // Create a linear constraint, 0 <= x + y <= 2.
  MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
  ct.setCoefficient(x, 1);
  ct.setCoefficient(y, 1);
  
  System.out.println("Number of constraints = " + solver.numConstraints());

  השיטה setCoefficient מגדירה את המקדמים של x ו-y בביטוי של האילוץ.
• מגדירים את פונקציית היעד.

  // Create the objective function, 3 * x + y.
  MPObjective objective = solver.objective();
  objective.setCoefficient(x, 3);
  objective.setCoefficient(y, 1);
  objective.setMaximization();

  השיטה setMaximization מצהירה שזו בעיית מקסימיזציה.
• מפעילים את הפותר ומציגים את התוצאות.

  solver.solve();
  System.out.println("Solution:");
  System.out.println("Objective value = " + objective.value());
  System.out.println("x = " + x.solutionValue());
  System.out.println("y = " + y.solutionValue());

השלמת התוכנית

התוכנית המלאה מוצגת בהמשך.

package com.google.ortools.linearsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.linearsolver.MPConstraint;
import com.google.ortools.linearsolver.MPObjective;
import com.google.ortools.linearsolver.MPSolver;
import com.google.ortools.linearsolver.MPVariable;

/** Minimal Linear Programming example to showcase calling the solver. */
public final class BasicExample {
  public static void main(String[] args) {
    Loader.loadNativeLibraries();
    // Create the linear solver with the GLOP backend.
    MPSolver solver = MPSolver.createSolver("GLOP");

    // Create the variables x and y.
    MPVariable x = solver.makeNumVar(0.0, 1.0, "x");
    MPVariable y = solver.makeNumVar(0.0, 2.0, "y");

    System.out.println("Number of variables = " + solver.numVariables());

    // Create a linear constraint, 0 <= x + y <= 2.
    MPConstraint ct = solver.makeConstraint(0.0, 2.0, "ct");
    ct.setCoefficient(x, 1);
    ct.setCoefficient(y, 1);

    System.out.println("Number of constraints = " + solver.numConstraints());

    // Create the objective function, 3 * x + y.
    MPObjective objective = solver.objective();
    objective.setCoefficient(x, 3);
    objective.setCoefficient(y, 1);
    objective.setMaximization();

    solver.solve();

    System.out.println("Solution:");
    System.out.println("Objective value = " + objective.value());
    System.out.println("x = " + x.solutionValue());
    System.out.println("y = " + y.solutionValue());
  }

  private BasicExample() {}
}

הפעלת תוכנית Java

אפשר להפעיל את התוכנית שלמעלה באופן הבא:

1. מעתיקים את הקוד שלמעלה, מדביקים אותו בקובץ חדש ושומרים אותו בשם my_program.java.
2. פותחים חלון פקודה ברמה העליונה של הספרייה שבה התקנתם את OR-Tools, ומזינים:

   make run SOURCE=relative/path/to/my_program.java

   כאשר relative/path/to/ הוא הנתיב לספרייה שבה שמרתם את התוכנה.

הערה: עליכם להריץ את הפקודה שלמעלה מהרמה העליונה של הספרייה שבה התקנתם את OR-Tools (שבה נמצא ה-Makefile).

התוכנית מחזירה את הערכים של x ו-y שמגדילים את פונקציית היעד:

Solution:
x =  1.0
y =  1.0

כדי להדר את התוכנית מבלי להפעיל אותה, מזינים:

make build SOURCE=relative/path/to/my_program.java

דוגמאות נוספות ל-Java

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

זיהוי סוג הבעיה שברצונך לפתור

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

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

בהמשך תמצאו סקירה כללית קצרה על סוגי הבעיות ש-OR-Tools פותרות, וקישורים לקטעים במדריך הזה שמסבירים איך לפתור כל סוג של בעיה.

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

אופטימיזציה לינארית

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

הפתרון העיקרי בכלי OR-Tools לסוג הבעיה הזה הוא פותר האופטימיזציה הלינארי, שהוא למעשה wrapper של כמה ספריות שונות, לצורך אופטימיזציה לינארית ומעורבת של מספרים שלמים, כולל ספריות של צד שלישי.

מידע נוסף על אופטימיזציה לינארית

אופטימיזציה של מספרים שלמים מעורבים

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

מידע נוסף על אופטימיזציה של מספרים מעורבים

אופטימיזציה של אילוצים

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

מידע נוסף על אופטימיזציה של אילוצים

מטלה

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

למידע נוסף על הקצאה

אריזה

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

מידע נוסף על אריזה של סלים

תזמון

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

מידע נוסף על תזמון

יצירת מסלול מתבצעת

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

מידע נוסף על מסלולים

זרימות רשת

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

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

מידע נוסף על תהליכי עבודה ברשת