Feasible region — תחום הפתרונות הקבילים

תחום הפתרונות הקבילים (תפ"ק) (המכונה גם קבוצת הפתרונות הקבילים, באנגלית Feasible region, feasible set) — במחקר פעולות, באופטימיזציה ובמידול מתמטי, זהו קבוצת כל הפתרונות האפשריים (ערכות ערכי משתנים) המקיימים את כל האילוצים המוטלים על הבעיה.

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

הגדרה וגיבוש

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

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

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

פרשנות גיאומטרית

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

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

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

תפקיד באופטימיזציה

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

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

תכונות תפ"ק (בבעיות תכנות לינארי)

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

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

תפ"ק יכול להיות:

• חסום: בעל ממדים סופיים.
• בלתי-חסום: משתרע לאינסוף בכיוון אחד או יותר.
• ריק: אינו מכיל אף נקודה.

ספרות

• Ventzel E. S. מחקר פעולות: בעיות, עקרונות, מתודולוגיה. — מוסקבה: Nauka, 1988.
• Ackoff R., Sasieni M. יסודות מחקר הפעולות. — מוסקבה: Mir, 1971.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

ראו גם

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