פרויקטים בחקר ביצועים

    1. "איקס - עיגול "
    2. קובייה הונגריית
    3. דו קרב משלוש

    בתחילת מלחמת העולם ה-II מדענים בריטיים התבקשו לבחון את הבעיות שכרוכות בהגנת המדינה. עליהם היה להחליט על הדרך היעילה ביותר לנצל את המשאבים המוגבלים להגנה. למשל, השימוש במכ"ם ובמפציצים. מקובל לייחס לאירוע זה את תחילתו של תחום ה-OR. האמריקאים בהמשך, יישמו את התחום החדש לניתוח בעיות לוגיסטיות וטקטיות כמו: פיזור מיטבי של מוקשיים ימיים ובחירת פרופיל טיסה. בסיום המלחמה, גם ארגונים עסקיים החלו לעשות שימוש בתחום. ב- 1947 פרסם גורג' דנציג מארה"ב את שיטת הסימפלקס בתכנות לינארי ומאז פותחו מודלים וישטות נוספות. התאוצה הגדולה ביישמוים החלה במקביל להתפתחות המחשבים.
    לעיתים קרובות, OR משתמש לנתח מערכות אמיתיות ומורכבות. בעיקר במטרה לשפר או להביא את הביצועים לאופטימום האפשרי. חקר ביצועים הוא גם תחום העוסק בקבלת החלטות אופטימאלית או יוריסטיות במערכות דטרמיניסטיות וסטוכסטיות לבעיות שמקורן ב" עולם האמיתי", ע"י ייצוגן במודלים מתמטיים. רוב יישומי חקר-ביצועים מתאפיינים ע"י הצורך בהקצאה או ניצול אופטימאלי של משאבים, שכמתום מוגבלת, בין פעיליות שונות.

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

    המודלים בחקר ביצועים מתחלקים לשתי קטגוריות:

    1. מודלים דטרמיניסטיים
      • תכנון לינארי
      • תכנון דינאמי
    2. מודלים סטוכסטיים
      • תורת המשחקים
      • שרשראות מרקוב
      • תורת התורים
      • תורת ההחלטות
      • תכנון דינאמי

    השלבים העיקריים בפתרון בעיה בגישת חקר הביצועים הם:

    1. ניסוח הבעיה
    2. בניית מודל מתמטי לייצוג המערכת הנחקרת
    3. מציאת פתרון למודל
    4. בחינת המודל והפתרון שהתקבל ממנו
    5. בניית בקרה על הפתרון
    6. מימוש הפתרון הלכה למעשה

     

    שלבים במודל והרכב הבעיה

    1. ניסוח הבעיה
      • מטרות (Objective functions): (א) עלות (Cost) / רווח (Revenue), (ב) איכות (Quality), (ג) מהירות (Speed), (ד) מחוייבות (Responsibility) ו- (ה) גמישות (Flexibility).
        את המטרה יש להביא לאופטימום: (א) מינימום (Minimun) או (ב) מקסימום (Maximum). לא תמיד ניתן להגיע לפתרון אופטימלי ולכן לעיתים נסתפק בפתרון יוריסטי.
      • האילוצים (Constraints): בעיקר לגבי השימוש במשאבים. למשאבים יש קיבולת מוגבלת.
      • הפרמטרים (Parameters): נתונים כמותיים הרלוונטיים לבעיה הנחקרת.
      • משתני החלטה (Decision variables): קבלת החלטה לגבי אותם משתנים משפיעה על טיב ההגעה למטרה.
    2. בניית מודל מתמטי לייצוג המערכת הנחקרת
      • המידול המתמטי של הבעיה כולל ניסוח כך שתהייה נוחה לניתוח.
      • החוקר יבנה בדרך כלל מודל מתמטי המייצג את עיקרי הבעיה
      • בדרך כלל יש להניח הנחות הגיוניות ומקלות לפני המידול המתמטי
      • הניסוח המתמטי כולל את: פונקצית המטרה והאילוצים
    3. בניית פתרון למודל
      • על מנת למצוא פתרון לבעיה יש להחליט מהו האלגוריתם (Algorithm - שיטת הפתרון) הסטנדרטי של OR הניתן ליישום (בדר"כ עם חבילת תוכנה מתאימה).
      • במקרים מסוימים יש לפתח אלגוריתם חדש כדי לפתור את הבעיה.
    4. בחינת המודל והפתרון שהתקבל ממנו
      • כאשר עברנו מהבעיה למודל הנחנו הנחות.
      • כדי לוודא שהמודל המתמטי אכן מייצג את הבעיה באופן מדויק עלינו לבצע ניתוח רגישות (Sensitivity Analysis).
      • ע"י ניתוחי רגישות נוכל לבחון עד כמה רגיש המודל לשינויים בפרמטרים.
    5. בניית בקרה על הפתרון
      • לאחר שיש בידינו מודל משביע רצון נרצה לבצע בו שימוש חוזר.
      • בקרה על המודל אחת לכמה זמן תעזור לבחון את ההשפעה של שינויים על מהימנותו של המודל.
      • שינויים יכולים להיות ב: (א) ערכי הפרמטרים, (ב) הוספה או ביטול של אילוצים ו- (ג) במטרות.
    6. מימוש הפתרון הלכה למעשה
      • הצגה של הפתרון שיש לאמץ.
      • הפיכת הפתרון לדרך פעולה
      • תיעוד

     

    שימושים בחקר ביצועים

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

    מקורות:

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