Network model (operations research) — מודל רשת

From Systems analysis Wiki
Jump to navigation Jump to search

מודלים רשתיים (במחקר ביצועים; באנגלית Network models) — הם מחלקה של מודלים מתמטיים המייצגים בעיה בצורת גרף (רשת), שבו קודקודים (צמתים) מסמנים עצמים או מצבים, וצלעות (קשתות) — קשרים או תהליכים ביניהם[1]. בהקשר של אופטימיזציה, במונח "רשת" מובן לעתים קרובות גרף מכוון, אשר בניתוח תפעולי נקרא ישירות "רשת"; קודקודי רשת כזו נקראים צמתים, והצלעות — קשתות[2].

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

הגדרה וטרמינולוגיה

הבסיס למודלים רשתיים הוא תורת הגרפים. המושגים המרכזיים הם:

  • רשת זרימה (באנגלית flow network): גרף מכוון שבו לכל צלע יש קיבולת (capacity) וזרימה (flow). בגרף מוגדרים שני קודקודים מיוחדים: מקור (source), ממנו יוצאת הזרימה, ושקע (sink), אליו היא נכנסת[1].
  • חוק שימור הזרימה: עבור כל קודקוד שאינו מקור או שקע, סך הזרימה הנכנסת חייב להיות שווה לסך הזרימה היוצאת. תנאי זה הוא אנלוג דיסקרטי לחוקי שימור פיזיים[3].
  • תכנון רשתי: מודל המייצג פרויקט כמכלול של פעולות קשורות זו בזו (קשתות) ואירועים (צמתים). רשתות כאלה הן גרפים מכוונים אציקליים, המשקפים את סדר ביצוע העבודות[4].

מאפיינים ומשפטים מרכזיים

למודלים רשתיים יש מספר מאפיינים מיוחדים המאפשרים שימוש באלגוריתמים יעילים ביותר לפתרונם.

  • שלמות הפתרון: בעיות רבות של אופטימיזציה ברשת (כגון זרימה מקסימלית או מסלול קצר ביותר) מחזיקות בתכונה של אוניטודולריות מלאה של מטריצת האילוצים. בזכות כך, אם פרמטרי הבעיה (קיבולות, אורכים) הם שלמים, הפתרון האופטימלי שנמצא בשיטות תכנות לינארי יהיה גם שלם, ללא צורך בהכנסת אילוצים נוספים[5][6].
  • משפט הזרימה המקסימלית והחתך המינימלי: תוצאה מרכזית בתורת הזרימות. קובע כי ערך הזרימה המקסימלית מהמקור לשקע שווה לקיבולת המינימלית מבין כל החתכים המפרידים בין המקור לשקע. משפט זה מבסס קריטריון אופטימליות לזרימה ועומד בבסיס אלגוריתמים רבים[6][7].
  • עיקרון האופטימליות למסלולים קצרים ביותר: אם המסלול מנקודה A לנקודה C הוא הקצר ביותר, אזי כל קטע ממנו (למשל, מנקודת ביניים B עד C) הוא גם המסלול הקצר ביותר בין הקודקודים המתאימים. תכונה זו, העומדת בבסיס התכנות הדינמי, מבטיחה את נכונותם של אלגוריתמים כגון אלגוריתם דייקסטרה[8].
  • תכונות עץ הפרישה המינימלי (MST):
  • תכונת החתך: עבור כל חתך בגרף, הצלע בעלת המשקל המינימלי החוצה את החתך שייכת לפחות ל-MST אחד.
  • תכונת המעגל: בכל מעגל בגרף, הצלע בעלת המשקל המקסימלי אינה שייכת לאף MST.

על תכונות אלה מבוססת נכונות האלגוריתמים "החמדניים" של פרים וקרוסקל[9].

בעיות מרכזיות באופטימיזציה ברשתות

  • בעיית המסלול הקצר ביותר: מציאת מסלול בעל אורך (משקל) כולל מינימלי בין שני צמתים נתונים. נפתרת באמצעות אלגוריתם דייקסטרה (למשקלים אי-שליליים) או אלגוריתם בלמן-פורד (למשקלים כלליים)[8].
  • בעיית הזרימה המקסימלית: קביעת הזרימה המקסימלית האפשרית מהמקור לשקע בהינתן קיבולות הקשתות. השיטה הקלאסית לפתרון — אלגוריתם פורד-פולקרסון[6].
  • בעיית עץ הפרישה המינימלי: מציאת תת-גרף המחבר את כל קודקודי הרשת ובעל עלות כוללת מינימלית של צלעות.
  • שיטת המסלול הקריטי (CPM): במודלים רשתיים לתכנון — קביעת רצף העבודות הארוך ביותר, הקובע את הזמן המינימלי האפשרי לביצוע הפרויקט כולו. עבודות הנמצאות על מסלול זה אינן כוללות רזרבה זמנית[10].

דוגמאות

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

ראו גם

  • מחקר ביצועים
  • תורת הגרפים
  • בעיית התחבורה
  • שיטת המסלול הקריטי
  • PERT

הערות

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.info/int/index.php?title=Network_model_(operations_research)_—_מודל_רשת&oldid=4864"