Operations research models — מודלים של חקר פעולות

מודלים של חקר פעולות

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

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

ניסוח כללי של הבעיה ומבנה המודל בחפ

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

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

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

מבחינה רעיונית, ניתן לייצג מודל חפ כ"קופסה שחורה", שבה עיקר תשומת הלב מוקדשת להגדרת כניסות ויציאות:

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

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

הגדרה מתמטית של המודל

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

מודל מתמטי טיפוסי בחפ

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

למקסם (או למזער) את פונקציית המטרה בכפוף לקיום האילוצים.

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

פתרונות במודלים של חפ

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

סיווג מודלים של חקר פעולות

ניתן לסווג מודלי חפ לפי מאפיינים שונים, בפרט לפי המנגנון המתמטי המשמש ולפי סוג הבעיה:

לפי המבנה המתמטי

• מודלים של תכנות לינארי (תל): פונקציית המטרה וכל האילוצים הם פונקציות לינאריות של המשתנים.
• מודלים של תכנות לינארי שלם: חלק מהמשתנים או כולם חייבים לקבל ערכים שלמים.

• מודלים של תכנות לא-לינארי (תלל): פונקציית המטרה ו/או האילוצים הם פונקציות לא-לינאריות.
• מודלים של תכנות קמור: מקרה פרטי של תלל, שבו פונקציית המטרה ממוזערת (או שמוקסמת פונקציה קעורה), ותפ"ס הוא קבוצה קמורה.

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

לפי בעיות טיפוסיות בחפ

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

ספרות

• ונצל א. ס. חקר פעולות: בעיות, עקרונות, מתודולוגיה. — מוסקבה: נאוקה, 1988.
• אקוף ר., סאסיאני מ. יסודות חקר הפעולות. — מוסקבה: מיר, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)

ראו גם

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