תכנון לא-לינארי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

ניסוח מתמטי של הבעיה[עריכת קוד מקור | עריכה]

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

\max_{x \in X}f(x)

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

\min_{x \in X}f(x)

כדי להביא את המטרה למינימום, כאשר:

f: R^n \to R
X \subseteq R^n

שיטות לפתרון[עריכת קוד מקור | עריכה]

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]